48 results on '"Shortest path problem"'
Search Results
2. Dual Dynamic Programming for the Mean Standard Deviation Canadian Traveller Problem.
- Author
-
Guo, Hongliang, Shi, Rui, Rus, Daniela, and Yau, Wei-Yun
- Subjects
- *
DYNAMIC programming , *TRAVEL time (Traffic engineering) , *TRAVELERS , *HEURISTIC algorithms , *APPROXIMATION algorithms , *STANDARD deviations - Abstract
This article studies the mean standard deviation (mean-std) Canadian traveller problem (CTP). Different from the canonical CTP, which aims at minimizing the traveller's expected travel time, while considering edge breakdown probabilities, we introduce the reliability version of CTP, which tries to find a routing policy with the minimal linear combination of the travel time's mean and standard deviation. With the recent development of internet-of-things (IoT) technology, the transportation network's edges' travel-time statistics, i.e., mean and standard deviation, as well as the traversal probabilities, are available to the end users. With those information, we propose a dual dynamic programming (DDP) method, which simultaneously estimates the first-order and the second-order moments of a given decision-list (DL) policy, and thereby makes improvements towards to the optimal one through the generalized policy iteration (GPI) scheme. We construct an open source benchmark environment to evaluate the performance of different mean-std CTP solutions, and show that the DDP method outperforms state of the arts in a range of transportation networks. [ABSTRACT FROM AUTHOR]
- Published
- 2022
- Full Text
- View/download PDF
3. Unifying Offline and Online Multi-Graph Matching via Finding Shortest Paths on Supergraph.
- Author
-
Jiang, Zetian, Wang, Tianzhe, and Yan, Junchi
- Subjects
- *
MULTIGRAPH , *ALGORITHMS , *SOURCE code , *DYNAMIC programming , *HEURISTIC algorithms , *ONLINE algorithms - Abstract
This paper addresses the problem of multiple graph matching (MGM) by considering both offline batch mode and online setting. We explore the concept of cycle-consistency over pairwise matchings and formulate the problem as finding optimal composition path on the supergraph, whose vertices refer to graphs and edge weights denote score function regarding consistency and affinity. By our theoretical study we show that the offline and online MGM on supergraph can be converted to finding all pairwise shortest paths and single-source shortest paths respectively. We adopt the Floyd algorithm and shortest path faster algorithm (SPFA) , to effectively find the optimal path. Extensive experimental results show our methods surpass state-of-the-art MGM methods, including CAO , MISM , IMGM , and many other recent methods in offline and online settings. Source code will be made publicly available. [ABSTRACT FROM AUTHOR]
- Published
- 2021
- Full Text
- View/download PDF
4. Fuzzy Constrained Shortest Path Problem for Location-Based Online Services.
- Author
-
Sori, Ali Abbaszadeh, Ebrahimnejad, Ali, Motameni, Homayun, and Verdegay, Jose Luis
- Subjects
- *
LOCATION-based services , *ENVIRONMENTAL economics , *WEATHER , *FUZZY numbers , *DYNAMIC programming - Abstract
One of the important issues under discussion connected with traffic on the roads is improving transportation. In this regard, spatial information, including the shortest path, is of particular importance due to the reduction of economic and environmental costs. Here, the constrained shortest path (CSP) problem which has an important application in location-based online services is considered. The aim of this problem is to find a path with the lowest cost where the traversal time of the path does not exceed from a predetermined time bound. Since precise prediction of cost and time of the paths is not possible due to traffic and weather conditions, this paper discusses the CSP problems with fuzzy cost and fuzzy time. After formulating the CSP problem an efficient algorithm for finding the constrained optimal path is designed. The application of the proposed model is presented on a location-based online service called Snap. [ABSTRACT FROM AUTHOR]
- Published
- 2021
- Full Text
- View/download PDF
5. A Multiobjective Path-Planning Algorithm With Time Windows for Asset Routing in a Dynamic Weather-Impacted Environment.
- Author
-
Sidoti, David, Avvari, Gopi Vinod, Mishra, Manisha, Zhang, Lingyi, Nadella, Bala Kishore, Peak, James E., Hansen, James A., and Pattipati, Krishna R.
- Subjects
- *
OPTIMUM ship routing , *ROUTING (Computer network management) , *OCEANOGRAPHY - Abstract
This paper presents a mixed-initiative tool for multiobjective planning and asset routing (TMPLAR) in dynamic and uncertain environments. TMPLAR is built upon multiobjective dynamic programming algorithms to route assets in a timely fashion, while considering fuel efficiency, voyage time, distance, and adherence to real world constraints (asset vehicle limits, navigator-specified deadlines, etc.). TMPLAR has the potential to be applied in a variety of contexts, including ship, helicopter, or unmanned aerial vehicle routing. The tool provides recommended schedules, consisting of waypoints, associated arrival and departure times, asset speed and bearing, that are optimized with respect to several objectives. The ship navigation is exacerbated by the need to address multiple conflicting objectives, spatial and temporal uncertainty associated with the weather, multiple constraints on asset operation, and the added capability of waiting at a waypoint with the intent to avoid bad weather, conduct opportunistic training drills, or both. The key algorithmic contribution is a multiobjective shortest path algorithm for networks with stochastic nonconvex edge costs and the following problem features: 1) time windows on nodes; 2) ability to choose vessel speed to next node subject to (minimum and/or maximum) speed constraints; 3) ability to select the power plant configuration at each node; and 4) ability to wait at a node. The algorithm is demonstrated on six real world routing scenarios by comparing its performance against an existing operational routing algorithm. [ABSTRACT FROM AUTHOR]
- Published
- 2017
- Full Text
- View/download PDF
6. Proper Policies in Infinite-State Stochastic Shortest Path Problems.
- Author
-
Bertsekas, Dimitri P.
- Subjects
- *
DYNAMIC programming , *MARKOV processes , *STOCHASTIC control theory , *PERTURBATION theory , *MATHEMATICAL optimization - Abstract
We consider stochastic shortest path problems with infinite state and control spaces, a nonnegative cost per stage, and a termination state. We extend the notion of a proper policy, a policy that terminates within a finite expected number of steps, from the context of finite state space to the context of infinite state space. We consider the optimal cost function $J^*$ , and the optimal cost function $\hat{J}$ over just the proper policies. We show that $J^*$ and $\hat{J}$ are the smallest and largest solutions of Bellman's equation, respectively, within a suitable class of Lyapounov-like functions. If the cost per stage is bounded, these functions are those that are bounded over the effective domain of $\hat{J}$. The standard value iteration algorithm may be attracted to either $J^*$ or $\hat{J}$ , depending on the initial condition. [ABSTRACT FROM AUTHOR]
- Published
- 2018
- Full Text
- View/download PDF
7. A column generation approach for the driver scheduling problem with staff cars
- Author
-
Shyam Sundar Govinda Raja Perumal, Jesper Larsen, Morten Riis, Tue R.L. Christensen, and Richard Martin Lusby
- Subjects
Schedule ,Operations research ,Job shop scheduling ,Computer science ,Heuristic ,Mechanical Engineering ,Column generation ,Transportation ,Management Science and Operations Research ,Dynamic programming ,Shortest path problem ,Driver scheduling problem ,Heuristics ,Integer programming ,Labor union ,Information Systems - Abstract
Given a set of timetabled bus trips, transport companies are faced with the challenge of finding a feasible driver schedule that covers all trips and abides by various labor union regulations. The regulations are primarily concerned with providing sufficient breaks for the drivers during the day. Practical limitations in the city network enforce drivers to travel by cars between bus stops to have breaks. Transport companies have a limited number of cars, known as staff cars,which have to be returned to their respective depots at the end of the day. The simultaneous scheduling of drivers and staff cars for the drivers is known as the driver scheduling problem with staff cars (DSPSC). It is estimated that the DSPSC accounts for 60% of a bus company’s operational expense, and this paper proposes a column generation approach that attempts to minimize operational expense. The column generation framework iterates between a master problem, a subproblem for generating driver variables and a subproblem for generating staff car variables. The subproblem related to the drivers is formulated as a resource constrained shortest path problem, which is solved by a dynamic programming approach. Several heuristic branching strategies are explored to find integer solutions. The proposed methodology is tested on eight real-life instances from seven Northern European bus companies. A comparison with a state-of-the-art mixed integer programming (MIP) solver and an adaptive large neighborhood search (ALNS) heuristic indicate that the column generation approach provides improved solutions for six instances and the average improvement is 1.45%.
- Published
- 2022
8. On the Shortest Path Game.
- Author
-
Darmann, Andreas, Pferschy, Ulrich, and Schauer, Joachim
- Subjects
- *
GRAPH theory , *DECISION making , *POLYNOMIAL time algorithms , *ACYCLIC model , *DYNAMIC programming - Abstract
In this work we address a game theoretic variant of the shortest path problem, in which two decision makers (players) move together along the edges of a graph from a given starting vertex to a given destination. The two players take turns in deciding in each vertex which edge to traverse next. The decider in each vertex also has to pay the cost of the chosen edge. We want to determine the path where each player minimizes its costs taking into account that also the other player acts in a selfish and rational way. Such a solution is a subgame perfect equilibrium and can be determined by backward induction in the game tree of the associated finite game in extensive form. We show that the decision problem associated with such a path is PSPACE-complete even for bipartite graphs both for the directed and the undirected version. The latter result is a surprising deviation from the complexity status of the closely related game Geography . On the other hand, we can give polynomial time algorithms for directed acyclic graphs and for cactus graphs even in the undirected case. The latter is based on a decomposition of the graph into components and their resolution by a number of fairly involved dynamic programming arrays. Finally, we give some arguments about closing the gap of the complexity status for graphs of bounded treewidth. [ABSTRACT FROM AUTHOR]
- Published
- 2017
- Full Text
- View/download PDF
9. Asymptotically optimal feedback planning using a numerical Hamilton-Jacobi-Bellman solver and an adaptive mesh refinement.
- Author
-
Yershov, Dmitry S. and Frazzoli, Emilio
- Subjects
- *
HAMILTON-Jacobi-Bellman equation , *NONHOLONOMIC dynamical systems , *MESH analysis (Electric circuits) , *ADAPTIVE computing systems , *DISCRETIZATION methods , *DYNAMIC programming - Abstract
We present the first asymptotically optimal feedback planning algorithm for nonholonomic systems and additive cost functionals. Our algorithm is based on three well-established numerical practices: 1) positive coefficient numerical approximations of the Hamilton-Jacobi-Bellman equations; 2) the Fast Marching Method, which is a fast nonlinear solver that utilizes Bellman’s dynamic programming principle for efficient computations; and 3) an adaptive mesh-refinement algorithm designed to improve the resolution of an initial simplicial mesh and reduce the solution numerical error. By refining the discretization mesh globally, we compute a sequence of numerical solutions that converges to the true viscosity solution of the Hamilton-Jacobi-Bellman equations. In order to reduce the total computational cost of the proposed planning algorithm, we find that it is sufficient to refine the discretization within a small region in the vicinity of the optimal trajectory. Numerical experiments confirm our theoretical findings and establish that our algorithm outperforms previous asymptotically optimal planning algorithms, such as PRM* and RRT*. [ABSTRACT FROM AUTHOR]
- Published
- 2016
- Full Text
- View/download PDF
10. Value and Policy Iterations in Optimal Control and Adaptive Dynamic Programming.
- Author
-
Bertsekas, Dimitri P.
- Subjects
- *
OPTIMAL control theory , *DYNAMIC programming , *NONLINEAR equations - Abstract
In this paper, we consider discrete-time infinite horizon problems of optimal control to a terminal set of states. These are the problems that are often taken as the starting point for adaptive dynamic programming. Under very general assumptions, we establish the uniqueness of the solution of Bellman’s equation, and we provide convergence results for value and policy iterations. [ABSTRACT FROM PUBLISHER]
- Published
- 2017
- Full Text
- View/download PDF
11. An Efficient CGM-Based Parallel Algorithm for Solving the Optimal Binary Search Tree Problem Through One-to-All Shortest Paths in a Dynamic Graph
- Author
-
Jerry Lacmou Zeutouo and Vianney Kengne Tchendji
- Subjects
Discrete mathematics ,lcsh:T58.5-58.64 ,Computer science ,Optimal binary search tree ,lcsh:Information technology ,Coarse-grained multicomputer ,Computational Mechanics ,Parallel algorithm ,Irregular partitioning ,02 engineering and technology ,Load balancing (computing) ,Graph model ,lcsh:QA75.5-76.95 ,Computer Science Applications ,Dynamic programming ,Dynamic graph model ,020204 information systems ,Shortest path problem ,0202 electrical engineering, electronic engineering, information engineering ,Graph (abstract data type) ,020201 artificial intelligence & image processing ,Minification ,lcsh:Electronic computers. Computer science ,MathematicsofComputing_DISCRETEMATHEMATICS - Abstract
The coarse-grained multicomputer parallel model (CGM for short) has been used for solving several classes of dynamic programming problems. In this paper, we propose a parallel algorithm on the CGM model, with p processors, for solving the optimal binary search tree problem (OBST problem), which is a polyadic non-serial dynamic programming problem. Firstly, we propose a dynamic graph model for solving the OBST problem and show that each instance of this problem corresponds to a one-to-all shortest path problem in this graph. Secondly, we propose a CGM parallel algorithm based on our dynamic graph to solve the OBST problem through one-to-all shortest paths in this graph. It uses our new technique of irregular partitioning of the dynamic graph to try to bring a solution to the well-known contradictory objectives of the minimization of the communication time and the load balancing of the processors in this type of graph. Our solution is based on Knuth’s sequential solution and required $${\mathcal {O}}\left( \dfrac{n^2}{p} \right)$$ time steps per processor and $$\lceil \sqrt{2p} \rceil + k \times \left( {\left\lceil \dfrac{\lceil \sqrt{2p} \rceil }{2} \right\rceil } + 1 \right)$$ communication rounds. Integer k is a parameter used in the partitioning technique of our algorithm. This new CGM algorithm performs better than the previously most efficient solution, which uses regular partitioning of the tasks graph.
- Published
- 2019
12. Improved AND/OR Tree Search Algorithm in Analysis of Stochastic and Time-Dependent Shortest Path Problem
- Author
-
Zhi-ying Xie, Yuan-tong Jiang, Yuan-Rong He, and Chih-Cheng Chen
- Subjects
050210 logistics & transportation ,Mathematical optimization ,Computer science ,Stochastic process ,05 social sciences ,02 engineering and technology ,And–or tree ,Tree diagram ,Computer Science Applications ,Dynamic programming ,QA76.75-76.765 ,Search algorithm ,0502 economics and business ,Shortest path problem ,Path (graph theory) ,0202 electrical engineering, electronic engineering, information engineering ,020201 artificial intelligence & image processing ,Node (circuits) ,Computer software ,Software - Abstract
Real-time vehicle guidance effectively reduces traffic jams and improves the operational efficiency of urban transportation. The trip time on a route is considered as a random process that changes with time, and the shortest path selection requires a random dynamic model and the solution of a decision-making problem. Thus, the shortest trip time is the criterion to determine the dynamic path selection by a random dynamic programming (DP) model which discretizes the trip times in the continuous segments on the route. In this study, a numerical model of random dynamic programming is established by using a probability tree model and an AND/OR (AO∗) algorithm to select the path of the shortest trip time. The results show that the branches of the probability tree are only accumulated on the “quantity” and do not cause a “qualitative” change. The inefficient accumulation of “quantity” affects the efficiency of the algorithm, so it is important to separate the accumulation of “quantity” from node expansion. The accumulation of “quantity” changes the trip time according to the entering time into a segment, which demands an improved AO∗ algorithm. The new AO∗ algorithm balances between efficiency and the trip time and provides the optimal real-time vehicle guidance on the road.
- Published
- 2021
13. A dynamic programming algorithm for solving the k-Color Shortest Path Problem
- Author
-
Serena Fugaro, Paola Festa, Tommaso Pastore, Daniele Ferone, Ferone, D., Festa, P., Fugaro, S., and Pastore, T.
- Subjects
Edge-colored network ,050210 logistics & transportation ,021103 operations research ,Control and Optimization ,Branch and bound ,Computer science ,Reliability (computer networking) ,05 social sciences ,0211 other engineering and technologies ,02 engineering and technology ,Solver ,Dynamic programming ,Field (computer science) ,Constrained Shortest Path ,0502 economics and business ,Path (graph theory) ,Shortest path problem ,Graph (abstract data type) ,Algorithm ,Network optimization - Abstract
Several variants of the classical Constrained Shortest Path Problem have been presented in the literature so far. One of the most recent is the k-Color Shortest Path Problem ($$k$$ k -CSPP), that arises in the field of transmission networks design. The problem is formulated on a weighted edge-colored graph and the use of the colors as edge labels allows to take into account the matter of path reliability while optimizing its cost. In this work, we propose a dynamic programming algorithm and compare its performances with two solution approaches: a Branch and Bound technique proposed by the authors in their previous paper and the solution of the mathematical model obtained with CPLEX solver. The results gathered in the numerical validation evidenced how the dynamic programming algorithm vastly outperformed previous approaches.
- Published
- 2021
14. Learning to plan with uncertain topological maps
- Author
-
Christian Wolf, Jilles Steeve Dibangoye, Olivier Simonin, Edward Beeching, Institut National des Sciences Appliquées de Lyon (INSA Lyon), Université de Lyon-Institut National des Sciences Appliquées (INSA), Robots coopératifs et adaptés à la présence humaine en environnements dynamiques (CHROMA), Inria Grenoble - Rhône-Alpes, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-CITI Centre of Innovation in Telecommunications and Integration of services (CITI), Université de Lyon-Institut National des Sciences Appliquées (INSA)-Université de Lyon-Institut National des Sciences Appliquées (INSA)-Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National des Sciences Appliquées de Lyon (INSA Lyon), Université de Lyon-Institut National des Sciences Appliquées (INSA)-Université de Lyon-Institut National des Sciences Appliquées (INSA), Extraction de Caractéristiques et Identification (imagine), Laboratoire d'InfoRmatique en Image et Systèmes d'information (LIRIS), Université de Lyon-Institut National des Sciences Appliquées (INSA)-Université de Lyon-Institut National des Sciences Appliquées (INSA)-Centre National de la Recherche Scientifique (CNRS)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-École Centrale de Lyon (ECL), Université de Lyon-Université Lumière - Lyon 2 (UL2)-Institut National des Sciences Appliquées de Lyon (INSA Lyon), Université de Lyon-Université Lumière - Lyon 2 (UL2), ANR-15-CE23-0029,DEEPVISION,Apprentissage de problèmes visuels complexes par modélisations profondes et structurées(2015), Université Lumière - Lyon 2 (UL2)-École Centrale de Lyon (ECL), Université de Lyon-Université de Lyon-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-Institut National des Sciences Appliquées de Lyon (INSA Lyon), Université de Lyon-Institut National des Sciences Appliquées (INSA)-Institut National des Sciences Appliquées (INSA)-Centre National de la Recherche Scientifique (CNRS)-Université Lumière - Lyon 2 (UL2)-École Centrale de Lyon (ECL), and Université de Lyon-Institut National des Sciences Appliquées (INSA)-Institut National des Sciences Appliquées (INSA)-Centre National de la Recherche Scientifique (CNRS)
- Subjects
FOS: Computer and information sciences ,Computer Science - Machine Learning ,Computer science ,Computer Science - Artificial Intelligence ,Machine Learning (stat.ML) ,02 engineering and technology ,010501 environmental sciences ,Topology ,Network topology ,01 natural sciences ,Machine Learning (cs.LG) ,Statistics - Machine Learning ,0202 electrical engineering, electronic engineering, information engineering ,[INFO]Computer Science [cs] ,Visual navigation ,0105 earth and related environmental sciences ,Inductive bias ,topological maps ,Probabilistic logic ,graph neural networks ,Graph ,Dynamic programming ,Artificial Intelligence (cs.AI) ,Shortest path problem ,020201 artificial intelligence & image processing ,Data-driven learning - Abstract
We train an agent to navigate in 3D environments using a hierarchical strategy including a high-level graph based planner and a local policy. Our main contribution is a data driven learning based approach for planning under uncertainty in topological maps, requiring an estimate of shortest paths in valued graphs with a probabilistic structure. Whereas classical symbolic algorithms achieve optimal results on noise-less topologies, or optimal results in a probabilistic sense on graphs with probabilistic structure, we aim to show that machine learning can overcome missing information in the graph by taking into account rich high-dimensional node features, for instance visual information available at each location of the map. Compared to purely learned neural white box algorithms, we structure our neural model with an inductive bias for dynamic programming based shortest path algorithms, and we show that a particular parameterization of our neural model corresponds to the Bellman-Ford algorithm. By performing an empirical analysis of our method in simulated photo-realistic 3D environments, we demonstrate that the inclusion of visual features in the learned neural planner outperforms classical symbolic solutions for graph based planning., ECCV 2020
- Published
- 2020
15. Lasso formulation of the shortest path problem
- Author
-
Tryphon T. Georgiou, Anqi Dong, and Amirhossein Taghvaei
- Subjects
FOS: Computer and information sciences ,Statistics::Theory ,Linear programming ,Mathematics - Statistics Theory ,Statistics Theory (math.ST) ,01 natural sciences ,Regularization (mathematics) ,Statistics - Applications ,Statistics - Computation ,Statistics::Machine Learning ,010104 statistics & probability ,Lasso (statistics) ,05C38 (Primary) 62J07, 68R10, 90C25, 90C06(Secondary) ,0502 economics and business ,Computer Science - Data Structures and Algorithms ,FOS: Mathematics ,Statistics::Methodology ,Applied mathematics ,Data Structures and Algorithms (cs.DS) ,Applications (stat.AP) ,0101 mathematics ,Mathematics - Optimization and Control ,Computation (stat.CO) ,050205 econometrics ,Mathematics ,Least-angle regression ,05 social sciences ,Statistics::Computation ,Dynamic programming ,Optimization and Control (math.OC) ,Shortest path problem ,Path (graph theory) ,Dijkstra's algorithm - Abstract
The shortest path problem is formulated as an $l_1$-regularized regression problem, known as lasso. Based on this formulation, a connection is established between Dijkstra's shortest path algorithm and the least angle regression (LARS) for the lasso problem. Specifically, the solution path of the lasso problem, obtained by varying the regularization parameter from infinity to zero (the regularization path), corresponds to shortest path trees that appear in the bi-directional Dijkstra algorithm. Although Dijkstra's algorithm and the LARS formulation provide exact solutions, they become impractical when the size of the graph is exceedingly large. To overcome this issue, the alternating direction method of multipliers (ADMM) is proposed to solve the lasso formulation. The resulting algorithm produces good and fast approximations of the shortest path by sacrificing exactness that may not be absolutely essential in many applications. Numerical experiments are provided to illustrate the performance of the proposed approach., 17 pages
- Published
- 2020
16. A branch and price algorithm to solve the quickest multicommodity k-splittable flow problem
- Author
-
Antonino Sgalambro and Anna Melchiori
- Subjects
Mathematical optimization ,Information Systems and Management ,Dynamic network analysis ,General Computer Science ,Computer science ,0211 other engineering and technologies ,k-splittable flow ,02 engineering and technology ,Management Science and Operations Research ,Upper and lower bounds ,Industrial and Manufacturing Engineering ,Scheduling (computing) ,Linearization ,0502 economics and business ,Branch and Price ,050210 logistics & transportation ,021103 operations research ,Branch and price ,05 social sciences ,Flows over time ,Flow network ,Dynamic programming ,Exact algorithm ,Modeling and Simulation ,Shortest path problem ,Quickest flow ,Networks - Abstract
In the literature on Network Optimization, k-splittable flows were introduced to enhance modeling accuracy in cases where an upper bound on the number of supporting paths for each commodity needs to be imposed, thus extending the suitability of network flow tools for an increased number of practical applications. Such modeling feature has recently been extended to dynamic flows with the introduction of the novel strongly NP-hard Quickest Multicommodity k-splittable Flow Problem (QMCkFP). Such a flows over time problem asks for routing and scheduling of each commodity demand through at most k different paths in a dynamic network with arc capacities per time step, while minimizing the time required by the overall process. In this work, we propose the first exact algorithm for solving the QMCkSFP. The developed technique falls within the Branch and Price class and is based on original relaxation, pricing and branching procedures. Linearization and variable substitution are used to obtain the relaxation problem from the path-based formulation of the QMCkSFP. The pricing problem is modeled as a Shortest Path Problem with Forbidden Paths with additional node-set resources on a time expansion of the original digraph and is solved via a tailored dynamic programming algorithm. Two branching rules are designed for restoring feasibility whenever k-splittable or binary variable domain constraints are violated. The results of an extensive batch of computational experiments conducted on small to medium-size reference instances are presented, showing a highly satisfactory performance of the proposed algorithm. The paper concludes with a discussion on further lines of research.
- Published
- 2020
17. An Improved Cooperative Control Method for Hybrid Unmanned Aerial-Ground System in Multitasks
- Author
-
Weidong Cao, Yinan Chen, Jianjun Ni, and Min Tang
- Subjects
0209 industrial biotechnology ,Article Subject ,Unmanned ground vehicle ,Computer science ,Real-time computing ,Aerospace Engineering ,TL1-4050 ,02 engineering and technology ,Energy consumption ,law.invention ,Dynamic programming ,020901 industrial engineering & automation ,Relay ,law ,Shortest path problem ,0202 electrical engineering, electronic engineering, information engineering ,020201 artificial intelligence & image processing ,Motion planning ,Cuckoo search ,Cluster analysis ,Motor vehicles. Aeronautics. Astronautics - Abstract
The cooperative control in complex multitasks using unmanned aerial vehicle and unmanned ground vehicle (UAV/UGV) is an important and challenging issue in the multirobot cooperative field. The main goal of the task studied in this paper is to minimize the time and energy consumed by the system to complete the assigned tasks. In this paper, a complex multitask problem using the hybrid UAV/UGV system is studied, which is divided into three stages, namely, the stage of finding the optimal locations of the relay stations for the UGV; the stage of solving the path planning problem for the UGV; and the stage of the task assignment for multi-UAVs. Furthermore, an improved integrated method is proposed to deal with the cooperative control problems in these three stages. Firstly, an adaptive clustering method is proposed to determine the locations of the UGV relay stations, and then an improved cuckoo search algorithm is used to find the shortest path for the UGV. Finally, a grouping method is presented to solve the multitask allocation problem of UAVs, based on an improved dynamic programming algorithm. In addition, some simulations are carried out and the results show that the proposed method has better performance when it comes to the time and energy consumption and can effectively guide the hybrid UAV/UGV system to carry out the complex multitasks.
- Published
- 2020
18. Adaptive Routing in Network-on-Chips Using a Dynamic-Programming Network.
- Author
-
Mak, Terrence, Cheung, Peter Y. K., Lam, Kai-Pui, and Luk, Wayne
- Subjects
- *
COMPUTER network architectures , *ADAPTIVE routing (Computer network management) , *DYNAMIC programming , *INTEGRATED circuits , *EQUATIONS , *HEURISTIC algorithms , *MATHEMATICAL optimization , *COMPUTER input-output equipment - Abstract
Dynamic routing is desirable because of its substantial improvement in communication bandwidth and intelligent adaptation to faulty links and congested traffic. However, implementation of adaptive routing in a network-on-chip system is not trivial and is further complicated by the requirements of deadlock-free and real-time optimal decision making. In this paper, we present a deadlock-free routing architecture which employs a dynamic programming (DP) network to provide on-the-fly optimal path planning and network monitoring for packet switching. Also, a new routing strategy called k-step look ahead is introduced. This new strategy can substantially reduce the size of routing table and maintain a high quality of adaptation which leads to a scalable dynamic-routing solution with minimal hardware overhead. Our results, based on a cycle-accurate simulator, demonstrate the effectiveness of the DP network, which outperforms both the deterministic and adaptive-routing algorithms in average delay on various traffic scenarios by 22.3%. Moreover, the hardware overhead for DP network is insignificant, based on the results obtained from the hardware implementations. [ABSTRACT FROM PUBLISHER]
- Published
- 2011
- Full Text
- View/download PDF
19. Real Time Motion Generation for Mobile Robot
- Author
-
Fabien Claveau, Philippe Chevrel, Jiuchun Gao, Anatol Pashkevich, Département Automatique, Productique et Informatique (IMT Atlantique - DAPI), IMT Atlantique Bretagne-Pays de la Loire (IMT Atlantique), Institut Mines-Télécom [Paris] (IMT)-Institut Mines-Télécom [Paris] (IMT), Commande (Commande), Laboratoire des Sciences du Numérique de Nantes (LS2N), Institut Mines-Télécom [Paris] (IMT)-Institut Mines-Télécom [Paris] (IMT)-Université de Nantes - UFR des Sciences et des Techniques (UN UFR ST), Université de Nantes (UN)-Université de Nantes (UN)-École Centrale de Nantes (ECN)-Centre National de la Recherche Scientifique (CNRS)-IMT Atlantique Bretagne-Pays de la Loire (IMT Atlantique), Université de Nantes (UN)-Université de Nantes (UN)-École Centrale de Nantes (ECN)-Centre National de la Recherche Scientifique (CNRS), Robotique Et Vivant (ReV), and Université de Nantes - UFR des Sciences et des Techniques (UN UFR ST)
- Subjects
motion generation ,0209 industrial biotechnology ,Computer science ,time-optimal systems ,020208 electrical & electronic engineering ,real time control ,Mobile robot ,02 engineering and technology ,mobile robot ,[SPI.MECA.GEME]Engineering Sciences [physics]/Mechanics [physics.med-ph]/Mechanical engineering [physics.class-ph] ,[SPI.AUTO]Engineering Sciences [physics]/Automatic ,Dynamic programming ,020901 industrial engineering & automation ,Control and Systems Engineering ,Real-time Control System ,Control theory ,Shortest path problem ,Path (graph theory) ,0202 electrical engineering, electronic engineering, information engineering ,Graph (abstract data type) ,State space ,ComputingMilieux_MISCELLANEOUS - Abstract
The paper proposes a new real time motion generation technique for a mobile robot, which is able to find time-optimal motions along a curved path taking into account capabilities of the driving motors and ensuring the wheels rolling without skidding. The problem is converted to a time-optimal control of a second-order dynamic system under constraints on the control input, the first derivative of output, and mixed constraint on the control variable and the output derivative. After the state space discretization, the original problem is presented as a combinatorial one where the desired robot trajectory corresponds to a shortest path on the relevant graph. To find this path and ensure its real time implementation, a moving window strategy combined with dynamic programming is proposed. Advantages of this approach and its suitability to real time control are illustrated by a case study dealing the fastest motion of the mobile robot along a sinusoidal path.
- Published
- 2019
20. The resource constrained shortest path problem with uncertain data: a robust formulation and optimal solution approach
- Author
-
Francesca Guerriero, Michael Poss, Luigi Di Puglia Pugliese, Dipartimento di Elettronica Informatica e Sistemistica [Rende] (DEIS), Università della Calabria, Méthodes Algorithmes pour l'Ordonnancement et les Réseaux (MAORE), Laboratoire d'Informatique de Robotique et de Microélectronique de Montpellier (LIRMM), and Centre National de la Recherche Scientifique (CNRS)-Université de Montpellier (UM)-Centre National de la Recherche Scientifique (CNRS)-Université de Montpellier (UM)
- Subjects
Constrained shortest path ,0209 industrial biotechnology ,Mathematical optimization ,021103 operations research ,General Computer Science ,Duality gap ,Uncertain data ,Computer science ,0211 other engineering and technologies ,Robust optimization ,02 engineering and technology ,[INFO.INFO-RO]Computer Science [cs]/Operations Research [cs.RO] ,Management Science and Operations Research ,Dynamic programming ,Upper and lower bounds ,symbols.namesake ,020901 industrial engineering & automation ,Lagrangian relaxation ,Modeling and Simulation ,Path (graph theory) ,Shortest path problem ,symbols ,Budgeted uncertainty - Abstract
International audience; The Resource Constrained Shortest Path Problem (RCSP P) models several applications in the fields of transportation and communications. The classical problem supposes that the resource consumptions and the costs are certain and looks for the cheapest feasible path. These parameters are however hardly known with precision in real applications, so that the deterministic solution is likely to be infeasible or suboptimal. We address this issue by considering a robust counterpart of the RCSP P. We focus here on resource variation and model its variability through the uncertainty set defined by Bertismas and Sim (2003,2004), which can model the risk aversion of the decision maker through a budget of uncertainty. We solve the resulting problem to optimality through the well-known three phase approach dealing with bounds computation, network reduction and gap closing. In particular, we compute robust bounds on the resource consumption and cost by solving the robust shortest path problem and the dual robust Lagrangian relaxation, respectively. Dynamic programming is used to close the duality gap. Upper and lower bounds are used to reduce the dimension of the network and incorporated in the dynamic programming in order to fathom unpromising states. An extensive computational phase is carried out in order to asses the behavior of the defined strategy comparing its performance with the state-of-the-art. The results highlight the effectiveness of our approach in solving to optimality * 1 benchmark instances for RCSP P when Γ is not too large, tailored for the robust counterpart. For larger values of Γ, we show that the most efficient method combines deterministic preprocesing with the iterative algorithm from Bertsimas and Sim (2003). We also illustrate the failure probability of the robust solutions through Monte Carlo sampling.
- Published
- 2019
21. Optimal Motion Generation for Mobile Robot with Non-Skidding Constraint
- Author
-
Fabien Claveau, Anatol Pashkevich, Jiuchun Gao, Philippe Chevrel, Commande (Commande), Laboratoire des Sciences du Numérique de Nantes (LS2N), IMT Atlantique Bretagne-Pays de la Loire (IMT Atlantique), Institut Mines-Télécom [Paris] (IMT)-Institut Mines-Télécom [Paris] (IMT)-Université de Nantes - UFR des Sciences et des Techniques (UN UFR ST), Université de Nantes (UN)-Université de Nantes (UN)-École Centrale de Nantes (ECN)-Centre National de la Recherche Scientifique (CNRS)-IMT Atlantique Bretagne-Pays de la Loire (IMT Atlantique), Université de Nantes (UN)-Université de Nantes (UN)-École Centrale de Nantes (ECN)-Centre National de la Recherche Scientifique (CNRS), Département Automatique, Productique et Informatique (IMT Atlantique - DAPI), Institut Mines-Télécom [Paris] (IMT)-Institut Mines-Télécom [Paris] (IMT), Robotique Et Vivant (ReV), and Université de Nantes - UFR des Sciences et des Techniques (UN UFR ST)
- Subjects
motion generation ,Computer science ,Control variable ,Mobile robot ,Optimal control ,mobile robot ,[SPI.AUTO]Engineering Sciences [physics]/Automatic ,Dynamic programming ,Control theory ,Path (graph theory) ,Shortest path problem ,Trajectory ,State space ,time-optimal control ,[MATH.MATH-OC]Mathematics [math]/Optimization and Control [math.OC] ,non-skidding constraint ,ComputingMilieux_MISCELLANEOUS - Abstract
The paper presents a new motion generation technique for a mobile robot that is able to find time-optimal motions along a curved path that takes into account limitations of the driving motors and also ensures the wheels rolling without skidding. Mathematically, the problem is presented as a time-optimal control of a second order dynamic system under constraints on the control input, the first derivative of output, and also mixed constraint on the control variable and the output derivative. After the state space discretization, the original problem is converted into the combinatorial one where the desired robot trajectory is presented a shortest path on the relevant graph. To find this path and ensure its physical implementation, dynamic programming is applied that allows creating a set of feasible trajectories, the best one of which is selected at the final stage. Advantages of the proposed technique and its suitability of real-time control are illustrated by several examples dealing the mobile robot motion along the elliptic and star-type paths.
- Published
- 2019
22. A branch-and-price algorithm for a vehicle routing with demand allocation problem
- Author
-
REIHANEH KARDEHI MOGHADDAM, Ahmed Ghoniem, Mohammad Reihaneh, Lille économie management - UMR 9221 (LEM), and Université d'Artois (UA)-Université catholique de Lille (UCL)-Université de Lille-Centre National de la Recherche Scientifique (CNRS)
- Subjects
Mathematical optimization ,Information Systems and Management ,General Computer Science ,Computer science ,0211 other engineering and technologies ,02 engineering and technology ,Management Science and Operations Research ,Dynamic programming ,Industrial and Manufacturing Engineering ,[SHS]Humanities and Social Sciences ,Set (abstract data type) ,0502 economics and business ,Vehicle routing problem ,Branch-and-price ,Column generation ,Routing ,050210 logistics & transportation ,021103 operations research ,Branch and price ,05 social sciences ,Vehicle routing-allocation problem ,Modeling and Simulation ,Shortest path problem ,Logistics and distribution ,[SHS.GESTION]Humanities and Social Sciences/Business administration ,Routing (electronic design automation) ,Heuristics - Abstract
International audience; We investigate the vehicle routing with demand allocation problem where the decision-maker jointly optimizes the location of delivery sites, the assignment of customers to (preferably convenient) delivery sites, and the routing of vehicles operated from a central depot to serve customers at their designated sites. We propose an effective branch-and-price (B&P) algorithm that is demonstrated to greatly outperform the use of commercial branch-and-bound/cut solvers such as CPLEX. Central to the efficacy of the proposed B&P algorithm is the development of a specialized dynamic programming procedure that extends works on elementary shortest path problems with resource constraints in order to solve the more complex column generation pricing subproblem. Our computational study demonstrates the efficacy of the proposed approach using a set of 60 problem instances. Moreover, the proposed methodology has the merit of providing optimal solutions in run times that are significantly shorter than those reported for decomposition-based heuristics in the literature.
- Published
- 2019
23. Time-dependent shortest path with discounted waits
- Author
-
Michael Poss, Jérémy Omer, Institut de Recherche Mathématique de Rennes (IRMAR), AGROCAMPUS OUEST, Institut national d'enseignement supérieur pour l'agriculture, l'alimentation et l'environnement (Institut Agro)-Institut national d'enseignement supérieur pour l'agriculture, l'alimentation et l'environnement (Institut Agro)-Université de Rennes 1 (UR1), Université de Rennes (UNIV-RENNES)-Université de Rennes (UNIV-RENNES)-Université de Rennes 2 (UR2), Université de Rennes (UNIV-RENNES)-École normale supérieure - Rennes (ENS Rennes)-Centre National de la Recherche Scientifique (CNRS)-Institut National des Sciences Appliquées - Rennes (INSA Rennes), Institut National des Sciences Appliquées (INSA)-Université de Rennes (UNIV-RENNES)-Institut National des Sciences Appliquées (INSA), Institut National des Sciences Appliquées - Rennes (INSA Rennes), Institut National des Sciences Appliquées (INSA)-Université de Rennes (UNIV-RENNES), Méthodes Algorithmes pour l'Ordonnancement et les Réseaux (MAORE), Laboratoire d'Informatique de Robotique et de Microélectronique de Montpellier (LIRMM), Centre National de la Recherche Scientifique (CNRS)-Université de Montpellier (UM)-Centre National de la Recherche Scientifique (CNRS)-Université de Montpellier (UM), Université de Rennes (UR)-Institut National des Sciences Appliquées - Rennes (INSA Rennes), Institut National des Sciences Appliquées (INSA)-Institut National des Sciences Appliquées (INSA)-École normale supérieure - Rennes (ENS Rennes)-Université de Rennes 2 (UR2)-Centre National de la Recherche Scientifique (CNRS)-INSTITUT AGRO Agrocampus Ouest, Institut national d'enseignement supérieur pour l'agriculture, l'alimentation et l'environnement (Institut Agro)-Institut national d'enseignement supérieur pour l'agriculture, l'alimentation et l'environnement (Institut Agro), Institut National des Sciences Appliquées (INSA), Methods, Algorithms for Operations REsearch (MAORE), Université de Montpellier (UM)-Centre National de la Recherche Scientifique (CNRS)-Université de Montpellier (UM)-Centre National de la Recherche Scientifique (CNRS), and ANR-11-LABX-0020,LEBESGUE,Centre de Mathématiques Henri Lebesgue : fondements, interactions, applications et Formation(2011)
- Subjects
Polynomial ,Mathematical optimization ,Computer Networks and Communications ,Computer science ,Shortest paths ,0211 other engineering and technologies ,02 engineering and technology ,Dynamic programming ,Waiting ,0502 economics and business ,Approximation ,050210 logistics & transportation ,021103 operations research ,Time-dependent shortest path ,05 social sciences ,[INFO.INFO-RO]Computer Science [cs]/Operations Research [cs.RO] ,NP-completeness ,N P-completeness ,Hardware and Architecture ,Shortest path problem ,Piecewise ,Time-dependent networks ,Graph (abstract data type) ,Affine transformation ,Completeness (statistics) ,Software ,Dy- namic programming ,Information Systems ,Integer (computer science) - Abstract
International audience; We study a variant of the shortest path problem in a congested environment. In this setting, the travel time of each arc is represented by a piecewise continuous affine function of departure time. Besides, the driver is allowed to wait at nodes to avoid wasting time in traffic. While waiting, the driver is able to perform useful tasks for her job or herself, so the objective is to minimize only driving time. Although optimal solutions may contain cycles and pseudo‐polynomially many arcs, we provide a representation of the solutions that is polynomial in the absolute value of the inverse of the slopes as well as in the dimensions of the graph. We further prove that the problem is NP‐Hard when the slopes are integer. We introduce a restriction of the problem where waits must be integer and propose pseudo‐polynomial algorithms for the latter. We also provide a pseudo‐FPTAS, polynomial in the ratio between the bound on the total waiting time and the minimum travel time. Finally, we discuss harder variants of the problem and show their inapproximability.
- Published
- 2019
24. An iterative two-step heuristic for the parallel drone scheduling traveling salesman problem
- Author
-
Nathalie Grangeon, Raïssa G. Mbiadou Saleu, Alain Quilliot, Laurent Deroussi, Dominique Feillet, Laboratoire d'Informatique, de Modélisation et d'Optimisation des Systèmes (LIMOS), Ecole Nationale Supérieure des Mines de St Etienne-Université Clermont Auvergne [2017-2020] (UCA [2017-2020])-Centre National de la Recherche Scientifique (CNRS), École des Mines de Saint-Étienne (Mines Saint-Étienne MSE), Institut Mines-Télécom [Paris] (IMT), Laboratoire d'Informatique, de Modélisation et d'optimisation des Systèmes (LIMOS), SIGMA Clermont (SIGMA Clermont)-Université d'Auvergne - Clermont-Ferrand I (UdA)-Ecole Nationale Supérieure des Mines de St Etienne-Centre National de la Recherche Scientifique (CNRS)-Université Blaise Pascal - Clermont-Ferrand 2 (UBP), Ecole Nationale Supérieure des Mines de St Etienne (ENSM ST-ETIENNE)-Université Clermont Auvergne [2017-2020] (UCA [2017-2020])-Centre National de la Recherche Scientifique (CNRS), and Université Blaise Pascal - Clermont-Ferrand 2 (UBP)-Université d'Auvergne - Clermont-Ferrand I (UdA)-SIGMA Clermont (SIGMA Clermont)-Ecole Nationale Supérieure des Mines de St Etienne (ENSM ST-ETIENNE)-Centre National de la Recherche Scientifique (CNRS)
- Subjects
Mathematical optimization ,Computer Networks and Communications ,Computer science ,0211 other engineering and technologies ,02 engineering and technology ,Travelling salesman problem ,Scheduling (computing) ,city logistics ,0502 economics and business ,Vehicle routing problem ,dynamic programming ,050210 logistics & transportation ,021103 operations research ,05 social sciences ,[INFO.INFO-RO]Computer Science [cs]/Operations Research [cs.RO] ,Drone ,Dynamic programming ,drone delivery ,Hardware and Architecture ,Shortest path problem ,heuristic ,vehicle routing problem ,PDSTSP ,Software ,Decoding methods ,Information Systems ,Coding (social sciences) - Abstract
International audience; A recent evolution in urban logistics involves the usage of drones. In this article, we address a heuristic solution of the parallel drone scheduling traveling salesman problem, recently introduced by Murray and Chu. In this problem, deliveries are split between a vehicle and drones. The vehicle performs a classical delivery tour, while the drones are constrained to perform back and forth trips. The objective is to minimize completion time. We propose an iterative two-step heuristic, composed of: a coding step that transforms a solution into a customer sequence, and a decoding step that decomposes the customer sequence into a tour for the vehicle and trips for the drones. Decoding is expressed as a bicriteria shortest path problem and is carried out by dynamic programming. Experiments conducted on benchmark instances confirm the efficiency of the approach and give some insights on this drone delivery system.
- Published
- 2018
25. Optimization of Robot and Positioner Motions in Manufacturing of High-pressure Composite Vessels
- Author
-
Marco Cicellini, Anatol Pashkevich, Stéphane Caro, Jiuchun Gao, Commande (Commande), Laboratoire des Sciences du Numérique de Nantes (LS2N), IMT Atlantique Bretagne-Pays de la Loire (IMT Atlantique), Institut Mines-Télécom [Paris] (IMT)-Institut Mines-Télécom [Paris] (IMT)-Université de Nantes - UFR des Sciences et des Techniques (UN UFR ST), Université de Nantes (UN)-Université de Nantes (UN)-École Centrale de Nantes (ECN)-Centre National de la Recherche Scientifique (CNRS)-IMT Atlantique Bretagne-Pays de la Loire (IMT Atlantique), Université de Nantes (UN)-Université de Nantes (UN)-École Centrale de Nantes (ECN)-Centre National de la Recherche Scientifique (CNRS), Département Automatique, Productique et Informatique (IMT Atlantique - DAPI), Institut Mines-Télécom [Paris] (IMT)-Institut Mines-Télécom [Paris] (IMT), Robotique Et Vivant (ReV), École Centrale de Nantes (ECN), Robots and Machines for Manufacturing, Society and Services (RoMas), Centre National de la Recherche Scientifique (CNRS), IFAC, Project with CETIM, and Université de Nantes - UFR des Sciences et des Techniques (UN UFR ST)
- Subjects
0209 industrial biotechnology ,Computer science ,Composite number ,02 engineering and technology ,Redundant robotic system ,Graph ,Time-optimal motion ,Task (project management) ,[SPI.MECA.GEME]Engineering Sciences [physics]/Mechanics [physics.med-ph]/Mechanical engineering [physics.class-ph] ,[SPI.AUTO]Engineering Sciences [physics]/Automatic ,Dynamic programming ,Acceleration ,020303 mechanical engineering & transports ,020901 industrial engineering & automation ,0203 mechanical engineering ,Control and Systems Engineering ,Control theory ,High pressure ,Shortest path problem ,Robot ,Graph (abstract data type) ,High-pressure composite vessel - Abstract
International audience; The paper proposes a technique for optimal motions generation in redundant robotic tape winding systems for manufacturing of high-pressure composite vessels. It also presents two industrial case studies dealing with the motion generation for basic types of winding lamina, helical and circumferential. The developed technique transforms the original continuous problem into a discrete one where the desired time-optimal motions are presented as a shortest path on the task graph satisfying the problem-specific acceleration and velocity constraints imposed on the joint coordinates. It allows generating the optimal trajectories using enhanced dynamic programming algorithm that considers both of these constraints. Efficiency of the developed technique is confirmed by simulation studies.
- Published
- 2018
26. Optimal Coordination of Robot Motions with Positioner and Linear Track in a Fiber Placement Workcell
- Author
-
Anatol Pashkevich, Jiuchun Gao, Marco Cicellini, Stéphane Caro, Commande (Commande), Laboratoire des Sciences du Numérique de Nantes (LS2N), Université de Nantes - UFR des Sciences et des Techniques (UN UFR ST), Université de Nantes (UN)-Université de Nantes (UN)-École Centrale de Nantes (ECN)-Centre National de la Recherche Scientifique (CNRS)-IMT Atlantique Bretagne-Pays de la Loire (IMT Atlantique), Institut Mines-Télécom [Paris] (IMT)-Institut Mines-Télécom [Paris] (IMT)-Université de Nantes - UFR des Sciences et des Techniques (UN UFR ST), Institut Mines-Télécom [Paris] (IMT)-Institut Mines-Télécom [Paris] (IMT), Département Automatique, Productique et Informatique (IMT Atlantique - DAPI), IMT Atlantique Bretagne-Pays de la Loire (IMT Atlantique), Robotique Et Vivant (ReV), Robots and Machines for Manufacturing, Society and Services (RoMas), and Centre National de la Recherche Scientifique (CNRS)
- Subjects
Computer science ,Composite Fiber Placement ,[SPI.MECA.GEME]Engineering Sciences [physics]/Mechanics [physics.med-ph]/Mechanical engineering [physics.class-ph] ,[SPI.AUTO]Engineering Sciences [physics]/Automatic ,Dynamic programming ,Computer Science::Robotics ,Redundant Robotic System ,Task (computing) ,Acceleration ,Control theory ,Shortest path problem ,Optimal Motion Coordination ,Robot ,Graph (abstract data type) ,Workcell ,Actuator - Abstract
International audience; The paper proposes a methodology for optimal coordination of motions in robotic systems with multiple redundant actuators. In contrast to our previous results dealing with a single redundant axis, the extended technique is proposed allowing the robot, positioner and linear track to be actuated simultaneously in order to reduce the total processing time. The developed technique transforms the original continuous problem into a discrete one where the desired time-optimal motions are presented as a shortest path on the task graph satisfying the problem-specific acceleration and velocity constraints imposed on the joint coordinates. The desired time optimal motions are generated using enhanced dynamic programming algorithm that considers both of these constraints. Two case studies are presented to demonstrate efficiency of the approach and evaluate benefits of simultaneous actuation of all robotic system axes.
- Published
- 2018
27. The dynamic shortest path problem with time-dependent stochastic disruptions
- Author
-
Derya D Sever, Emrah Demir, Lei Zhao, Tom Van Woensel, Ton de Kok, Nico Dellaert, Industrial Engineering and Innovation Sciences, and Operations Planning Acc. & Control
- Subjects
Mathematical optimization ,Computer science ,media_common.quotation_subject ,Approximate dynamic programming ,Lookahead policy ,0211 other engineering and technologies ,Transportation ,02 engineering and technology ,Dynamic shortest path problem ,Time-dependent disruption ,Value function approximation ,Bellman equation ,0502 economics and business ,Quality (business) ,Cluster analysis ,Civil and Structural Engineering ,media_common ,050210 logistics & transportation ,021103 operations research ,05 social sciences ,Finite horizon ,Computer Science Applications ,Dynamic programming ,Discrete time and continuous time ,Automotive Engineering ,Shortest path problem ,Markov decision process - Abstract
The dynamic shortest path problem with time-dependent stochastic disruptions consists of finding a route with a minimum expected travel time from an origin to a destination using both historical and real-time information. The problem is formulated as a discrete time finite horizon Markov decision process and it is solved by a hybrid Approximate Dynamic Programming (ADP) algorithm with a clustering approach using a deterministic lookahead policy and value function approximation. The algorithm is tested on a number of network configurations which represent different network sizes and disruption levels. Computational results reveal that the proposed hybrid ADP algorithm provides high quality solutions with a reduced computational effort.
- Published
- 2018
28. Optimal spare parts management for vessel maintenance scheduling
- Author
-
Djamila Ouelhadj, Ramez Kian, and Tolga Bektaş
- Subjects
021103 operations research ,Spare part management ,Shortest path ,Computer science ,Maritime logistics ,0211 other engineering and technologies ,Scheduling (production processes) ,General Decision Sciences ,Integer programming ,02 engineering and technology ,Management Science and Operations Research ,Dynamic programming ,Predictive maintenance ,Reliability engineering ,Spare part ,Shortest path problem ,S.I.: Advances in Theoretical and Applied Combinatorial Optimization ,Spare parts management - Abstract
Condition-based monitoring is used as part of predictive maintenance to collect real-time information on the healthy status of a vessel engine, which allows for a more accurate estimation of the remaining life of an engine or its parts, as well as providing a warning for a potential failure of an engine part. An engine failure results in delays and down-times in the voyage of a vessel, which translates into additional cost and penalties. This paper studies a spare part management problem for maintenance scheduling of a vessel operating on a given route that is defined by a sequence of port visits. When a warning on part failure is received, the problem decides when and to which port each part should be ordered, where the latter is also the location at which the maintenance operation would be performed. The paper describes a mathematical programming model of the problem, as well as a shortest path dynamic programming formulation for a single part which solves the problem in polynomial time complexity. Simulation results are presented in which the models are tested under different scenarios.
- Published
- 2018
29. A shortest-path-based approach for the stochastic knapsack problem with non-decreasing expected overfilling costs
- Author
-
Troels Martin Range, Dawid Kozlowski, and Niels Christian Petersen
- Subjects
Mathematical optimization ,General Computer Science ,0211 other engineering and technologies ,0102 computer and information sciences ,02 engineering and technology ,Management Science and Operations Research ,Expected value ,Dynamic programming ,01 natural sciences ,Upper and lower bounds ,Shortest path problem with resource constraints ,Penalty method ,Limit (mathematics) ,Special case ,Mathematics ,021103 operations research ,Regular polygon ,Stochastic Knapsack problem ,Function (mathematics) ,Constraint (information theory) ,010201 computation theory & mathematics ,Knapsack problem ,Modeling and Simulation ,Shortest path problem ,Mathematical economics - Abstract
The knapsack problem (KP) is concerned with the selection of a subset of multiple items with known positive values and weights such that the total value of selected items is maximized and their total weight does not exceed capacity. Item values, item weights, and capacity are known in the deterministic case. We consider the stochastic KP (SKP) with stochastic item weights. We combine the formulation of the SKP with a probabilistic capacity constraint (CKP) and the SKP with simple recourse (SRKP). Capacity is made an integral part of the constraint set in terms of a chance constraint as in the CKP. The chance constraint allows for a violation of capacity, but the probability of a violation beyond an imposed limit is constrained. The capacity constraint is also included in the objective function in terms of a penalty function as in the SRKP. Penalty is an increasing function of the expected number of units of violation with proportionality as a special case. We formulate the SKP as a network problem and demonstrate that it can be solved by a label-setting dynamic programming approach for the Shortest Path Problem with Resource Constraint (SPPRC). We develop a dominance criterion for an elimination of states in the dynamic programming approach using only the deterministic value of items along with mean and variance of the stochastic weight of items corresponding to the associated paths in the underlying network. It is shown that a lower bound for the impact of potential extensions of paths is available as an additional means to limit the number of states provided the penalty cost of expected overtime is convex. Our findings are documented in terms of a computational study.
- Published
- 2018
30. Shortest Path Problem variants for the Hydro Unit Commitment Problem
- Author
-
Claudia D’Ambrosio, Leo Liberti, Sonia Toubaline, Raouia Taktak, Dimitri Thomopulos, Wim van Ackooij, Optimisation, Simulation, Risque et Statistiques pour les Marchés de l’Energie (EDF R&D OSIRIS), EDF R&D (EDF R&D), EDF (EDF)-EDF (EDF), Laboratoire d'informatique de l'École polytechnique [Palaiseau] (LIX), Centre National de la Recherche Scientifique (CNRS)-École polytechnique (X), Institut Supérieur d'Informatique et de Multimédia de Sfax (ISIMS), Université de Sfax - University of Sfax, Laboratoire d'analyse et modélisation de systèmes pour l'aide à la décision (LAMSADE), Université Paris Dauphine-PSL, and Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Centre National de la Recherche Scientifique (CNRS)
- Subjects
Hydro Unit Commitment Problem ,Mathematical optimization ,020209 energy ,Applied Mathematics ,02 engineering and technology ,Time step ,Constrained Shortest Path Problem ,Dynamic programming ,Power system simulation ,Shortest path problem ,0202 electrical engineering, electronic engineering, information engineering ,time expanded graph representation ,Discrete Mathematics and Combinatorics ,020201 artificial intelligence & image processing ,[INFO]Computer Science [cs] ,State (computer science) ,Integer (computer science) ,Mathematics - Abstract
In this paper, we study the deterministic single-reservoir Hydro Unit Commitment Problem. Under some hypotheses, we present a time expanded graph representation for the problem, where, at each time step, nodes correspond to discrete operational points, and arcs refer to possible state changes. We show that our problem reduces to a Constrained Shortest Path Problem, propose and compare different approaches to solve the HUCP, based on mixed integer linear or dynamic programming.
- Published
- 2018
31. A branch-price-and-cut algorithm for the commodity constrained split delivery vehicle routing problem
- Author
-
M. Grazia Speranza, Nicola Bianchessi, Claudia Archetti, and Logistics
- Subjects
Mathematical optimization ,General Computer Science ,Vehicle routing problems ,Computer science ,Commodity ,Branch-price-and-cut algorithm ,Management Science and Operations Research ,Upper and lower bounds ,Dynamic programming ,Set (abstract data type) ,Order (exchange) ,Modeling and Simulation ,Shortest path problem ,Relaxation (approximation) ,SDG 7 - Affordable and Clean Energy ,Routing (electronic design automation) ,Multiple commodities ,Algorithm - Abstract
We consider the Commodity constrained Split Delivery Vehicle Routing Problem (C-SDVRP), a routing problem where customers may request multiple commodities. The vehicles can deliver any set of commodities and multiple visits to a customer are allowed only if the customer requests multiple commodities. If the customer is visited more than once, the different vehicles will deliver different sets of commodities. Allowing the splitting of the demand of a customer only for different commodities may be more costly than allowing also the splitting of each individual commodity, but at the same time it is easier to organize and more acceptable to customers. We model the C-SDVRP by means of a set partitioning formulation and present a branch-price-and-cut algorithm. In the pricing phase, the ng-path relaxation of a constrained elementary shortest path problem is solved with a label setting dynamic programming algorithm. Capacity cuts are added in order to strengthen the lower bound. We solve to optimality within 2h instances with up to 40 customers and 3 commodities per customer. HighlightsWe address the Commodity constrained Split Delivery Vehicle Routing Problem (C-SDVRP).We design an efficient branch-price-and-cut algorithm to solve the problem to optimality.We solve to optimality within 2h instances with up to 40 customers and 3 commodities per customer.
- Published
- 2015
32. Realtime power management of a multi-source hev using adaptive dynamic programing and probabilistic drive state model
- Author
-
Ahmed Ali and Dirk Söffker
- Subjects
Dynamic programming ,Power management ,Reduction (complexity) ,Physics ,Emulation ,Maschinenbau ,Control theory ,Shortest path problem ,Probabilistic logic ,Control engineering ,State (computer science) ,Optimal control - Abstract
Power management in multi-source hybrid electric vehicles (HEVs) is a nontrivial problem dealing with different forms of energy. Optimal-based approaches are not facile to apply in realtime due to their high computational requirements. Rule-based (RB) algorithms are suitable for realtime control; however, the solution provided is non-optimal. Development of applicable optimal-based solution in realtime control can ensure higher efficiency of HEVs. This paper presents a new method for realtime optimal control of multisource HEVs using adaptive dynamic programming (ADP). The developed concept is based on drive state recognition in terms of physics-based parameters. Vehicle operating conditions are offline optimized for each state using NSGA-II optimization tool. The optimized solution can be applied state-wise in realtime using adaptive RB method. To apply ADP, probabilistic drive state model is developed to provide a lookahead window and generate state transition network for the specified horizon. The algorithm is customized in terms of prediction stepsize/length to solve the shortest path problem in realtime. Experimental application is conducted using emulation test-rig to validate the results. Both simulation and experimental results show reduction of total cost function in terms of fuel consumption and on-board charge sustaining.Copyright © 2017 by ASME
- Published
- 2017
33. Hybrid metaheuristics for the clustered vehicle routing problem
- Author
-
Thibaut Vidal, Anand Subramanian, Maria Battarra, and Güneş Erdoğan
- Subjects
FOS: Computer and information sciences ,Mathematical optimization ,General Computer Science ,Computer Science - Artificial Intelligence ,Iterated local search ,business.industry ,Management Science and Operations Research ,Data structure ,Hamiltonian path ,Dynamic programming ,symbols.namesake ,Artificial Intelligence (cs.AI) ,Modeling and Simulation ,Shortest path problem ,Vehicle routing problem ,symbols ,Local search (optimization) ,business ,Metaheuristic ,Mathematics - Abstract
The Clustered Vehicle Routing Problem (CluVRP) is a variant of the Capacitated Vehicle Routing Problem in which customers are grouped into clusters. Each cluster has to be visited once, and a vehicle entering a cluster cannot leave it until all customers have been visited. This article presents two alternative hybrid metaheuristic algorithms for the CluVRP. The first algorithm is based on an Iterated Local Search algorithm, in which only feasible solutions are explored and problem-specific local search moves are utilized. The second algorithm is a Hybrid Genetic Search, for which the shortest Hamiltonian path between each pair of vertices within each cluster should be precomputed. Using this information, a sequence of clusters can be used as a solution representation and large neighborhoods can be efficiently explored by means of bi-directional dynamic programming, sequence concatenations, by using appropriate data structures. Extensive computational experiments are performed on benchmark instances from the literature, as well as new large scale ones. Recommendations on promising algorithm choices are provided relatively to average cluster size., Working Paper, MIT -- 22 pages
- Published
- 2015
34. Robust constrained shortest path problems under budgeted uncertainty
- Author
-
Francesca Guerriero, Michael Poss, Luigi Di Puglia Pugliese, Artur Alves Pessoa, Universidade Federal Fluminense [Rio de Janeiro] (UFF), Dipartimento di Elettronica Informatica e Sistemistica [Rende] (DEIS), Università della Calabria, Méthodes Algorithmes pour l'Ordonnancement et les Réseaux (MAORE), Laboratoire d'Informatique de Robotique et de Microélectronique de Montpellier (LIRMM), and Centre National de la Recherche Scientifique (CNRS)-Université de Montpellier (UM)-Centre National de la Recherche Scientifique (CNRS)-Université de Montpellier (UM)
- Subjects
Mathematical optimization ,time windows ,Computer Networks and Communications ,0211 other engineering and technologies ,robust optimization ,02 engineering and technology ,Reduction (complexity) ,Robustness (computer science) ,0502 economics and business ,constrained shortest path ,Mathematics ,dynamic programming ,050210 logistics & transportation ,021103 operations research ,np-hard ,05 social sciences ,Robust optimization ,[INFO.INFO-RO]Computer Science [cs]/Operations Research [cs.RO] ,Dynamic programming ,Variable (computer science) ,Hardware and Architecture ,Independent set ,Shortest path problem ,budgeted uncertainty ,label-setting algorithm ,Focus (optics) ,Algorithm ,Software ,Information Systems - Abstract
We study the robust constrained shortest path problem under resource uncertainty. After proving that the problem is NP-hard in the strong sense for arbitrary uncertainty sets, we focus on budgeted uncertainty sets introduced by Bertsimas and Sim 2003 and their extension to variable uncertainty by Poss 2013. We apply classical techniques to show that the problem with capacity constraints can be solved in pseudopolynomial time. However, we prove that the problem with time windows is NP-hard in the strong sense when NP is not fixed, using a reduction from the independent set problem. We introduce then new robust labels that yield dynamic programming algorithms for the problems with time windows and capacity constraints. The running times of these algorithms are pseudopolynomial when NP is fixed, exponential otherwise. We present numerical results for the problem with time windows which show the effectiveness of the label-setting algorithm based on the new robust labels. Our numerical results also highlight the reduction in price of robustness obtained when using variable budgeted uncertainty instead of classical budgeted uncertainty. © 2015 Wiley Periodicals, Inc.NETWORKS, Vol. 662, 98-111 2015
- Published
- 2015
35. On risk attitude and optimal yacht racing tactics
- Author
-
Francesca Tagliaferri, Andy Philpott, Richard G.J. Flay, and Ignazio Maria Viola
- Subjects
Strategic planning ,Engineering ,Environmental Engineering ,Markov chain ,Operations research ,business.industry ,Risk aversion ,Ocean Engineering ,Competitor analysis ,Wind direction ,Yacht race ,Dynamic programming ,Shortest path problem ,Tacking ,business ,Tactics - Abstract
When the future wind direction is uncertain, the tactical decisions of a yacht skipper involve a stochastic routing problem. The objective of this problem is to maximise the probability of reaching the next mark ahead of all the other competitors. This paper describes some numerical experiments that explore the effect of the skipper's risk attitude on their policy when match racing another boat. The tidal current at any location is assumed to be negligible, while the wind direction is modelled by a Markov chain. Boat performance in different wind conditions is defined by the output of a velocity prediction program, and we assume a known speed loss for tacking and gybing. We compare strategies that minimise the average time to sail the leg with those that seek to maximise the probability of winning, and show that by adopting different attitudes to risk when leading or trailing the competitor, a skipper can improve their chances of winning.
- Published
- 2014
36. Dijkstra meets Steiner: a fast exact goal-oriented Steiner tree algorithm
- Author
-
Jens Vygen, Jannik Silvanus, and Stefan Hougardy
- Subjects
FOS: Computer and information sciences ,Discrete Mathematics (cs.DM) ,0211 other engineering and technologies ,0102 computer and information sciences ,02 engineering and technology ,01 natural sciences ,Steiner tree problem ,Theoretical Computer Science ,symbols.namesake ,Computer Science - Data Structures and Algorithms ,Data Structures and Algorithms (cs.DS) ,Pruning (decision trees) ,Mathematics ,Discrete mathematics ,021103 operations research ,Rectilinear Steiner tree ,Dynamic programming ,Exact algorithm ,010201 computation theory & mathematics ,Shortest path problem ,Theory of computation ,symbols ,Algorithm ,Dijkstra's algorithm ,Software ,MathematicsofComputing_DISCRETEMATHEMATICS ,Computer Science - Discrete Mathematics - Abstract
We present a new exact algorithm for the Steiner tree problem in edge-weighted graphs. Our algorithm improves the classical dynamic programming approach by Dreyfus and Wagner. We achieve a significantly better practical performance via pruning and future costs, a generalization of a well-known concept to speed up shortest path computations. Our algorithm matches the best known worst-case run time and has a fast, often superior, practical performance: on some large instances originating from VLSI design, previous best run times are improved upon by orders of magnitudes. We are also able to solve larger instances of the d-dimensional rectilinear Steiner tree problem for $$d \in \{3, 4, 5\}$$ , whose Hanan grids contain up to several millions of edges.
- Published
- 2014
37. Exploiting Set-Based Structures to Accelerate Dynamic Programming Algorithms for the Elementary Shortest Path Problem with Resource Constraints
- Author
-
Troels Martin Range
- Subjects
Mathematical optimization ,Theoretical computer science ,jel:C61 ,Dynamic programming ,Euclidean shortest path ,Shortest Path Faster Algorithm ,Shortest path problem ,Path (graph theory) ,K shortest path routing ,Elementary shortest path problem ,resource constraints ,dynamic programming ,prefix tree ,Algorithm ,Yen's algorithm ,Constrained Shortest Path First ,Mathematics - Abstract
In this paper we consider a label-setting dynamic-programming algorithm for the Elementary Shortest Path Problem with Resource Constraints (ESPPRC). We use a pseudo resource to guarantee that labels are permanent. We observe that storing the states based on the subset of nodes visited by the associated path can improve the performance of the algorithm significantly. To this end we use a variant of a prefix tree to store the states and show by computational experiments that the performance of the dynamic programming algorithm is improved significantly when the number of undominated states is large.
- Published
- 2014
38. A Tabled Prolog Program for Solving Sokoban
- Author
-
Neng-Fa Zhou and Agostino Dovier
- Subjects
Shortest path problem ,Algebra and Number Theory ,Theoretical computer science ,Computational complexity theory ,Generalization ,Computer science ,Programming language ,Solver ,Sub-problems ,computer.software_genre ,Theoretical Computer Science ,Prolog ,Dynamic programming ,Prolog programs ,Computational Theory and Mathematics ,Simple (abstract algebra) ,Domain knowledge ,computer ,Domain knowledge, Prolog programs, Shortest path problem, Sub-problems ,Information Systems ,computer.programming_language - Abstract
This paper presents our program in B-Prolog submitted to the third ASP solver competition for the Sokoban problem. This program, based on dynamic programming, treats Sokoban as a generalized shortest path problem. It divides a problem into independent subproblems and uses mode-directed tabling to store subproblems and their answers. This program is very simple but quite efficient. Without use of any sophisticated domain knowledge, it easily solves 14 of the 15 instances used in the competition. We show that the approach can be easily applied to other optimization planning problems.
- Published
- 2013
39. The Capacity Expansion Path Problem in Networks
- Author
-
Juanping Zhu and Jianping Li
- Subjects
Discrete mathematics ,Polynomial ,Mathematical optimization ,Article Subject ,lcsh:Mathematics ,Applied Mathematics ,lcsh:QA1-939 ,Longest path problem ,Expansion path ,Dynamic programming ,Widest path problem ,TheoryofComputation_ANALYSISOFALGORITHMSANDPROBLEMCOMPLEXITY ,Shortest path problem ,K shortest path routing ,Canadian traveller problem ,Mathematics - Abstract
This paper considers the general capacity expansion path problem (GCEP) for the telecommunication operators. We investigate the polynomial equivalence between the GCEP problem and the constrained shortest path problem (CSP) and present a pseudopolynomial algorithm for the GCEP problem, no matter the graph is acyclic or not. Furthermore, we investigate two special versions of the GCEP problem. For the minimum number arc capacity expansion path problem (MN-CEP), we give a strongly polynomial algorithm based on the dynamic programming. For the minimum-cost capacity expansion shortest path problem (MCESP), we give a strongly polynomial algorithm by constructing a shortest paths network.
- Published
- 2013
- Full Text
- View/download PDF
40. Meta-Algorithms for Scheduling a Chain of Coarse-Grained Tasks on an Array of Reconfigurable FPGAs
- Author
-
Donald W. Bouldin, Carl Shetters, and Dinesh P. Mehta
- Subjects
Mathematical optimization ,Article Subject ,Problem Formulations ,Computer science ,MathematicsofComputing_GENERAL ,Control reconfiguration ,020207 software engineering ,02 engineering and technology ,Computer Graphics and Computer-Aided Design ,lcsh:QA75.5-76.95 ,020202 computer hardware & architecture ,Scheduling (computing) ,Exponential function ,Dynamic programming ,Hardware and Architecture ,Simulated annealing ,Shortest path problem ,0202 electrical engineering, electronic engineering, information engineering ,lcsh:Electronic computers. Computer science ,Electrical and Electronic Engineering ,Field-programmable gate array ,Algorithm - Abstract
This paper considers the problem of scheduling a chain of n coarse-grained tasks on a linear array of k reconfigurable FPGAs with the objective of primarily minimizing reconfiguration time. A high-level meta-algorithm along with two detailed meta-algorithms (GPRM and SPRM) that support a wide range of problem formulations and cost functions is presented. GPRM, the more general of the two schemes, reduces the problem to computing a shortest path in a DAG; SPRM, the less general scheme, employs dynamic programming. Both meta algorithms are linear in n and compute optimal solutions. GPRM can be exponential in k but is nevertheless practical because k is typically a small constant. The deterministic quality of this meta algorithm and the guarantee of optimal solutions for all of the formulations discussed make this approach a powerful alternative to other metatechniques such as simulated annealing and genetic algorithms.
- Published
- 2013
41. Least Squares Temporal Difference Actor-Critic Methods with Applications to Robot Motion Control
- Author
-
Calin Belta, Xu Chu Ding, Reza Moazzez Estanjini, Morteza Lahijanian, Jing Wang, and Ioannis Ch. Paschalidis
- Subjects
FOS: Computer and information sciences ,0209 industrial biotechnology ,Mathematical optimization ,Computer science ,Parameterized complexity ,Markov process ,02 engineering and technology ,Systems and Control (eess.SY) ,symbols.namesake ,Computer Science - Robotics ,020901 industrial engineering & automation ,0202 electrical engineering, electronic engineering, information engineering ,FOS: Electrical engineering, electronic engineering, information engineering ,FOS: Mathematics ,Temporal logic ,Mathematics - Optimization and Control ,Probabilistic logic ,Approximation algorithm ,Stationary point ,Dynamic programming ,Optimization and Control (math.OC) ,Shortest path problem ,symbols ,Computer Science - Systems and Control ,020201 artificial intelligence & image processing ,Markov decision process ,Temporal difference learning ,Robotics (cs.RO) - Abstract
We consider the problem of finding a control policy for a Markov Decision Process (MDP) to maximize the probability of reaching some states while avoiding some other states. This problem is motivated by applications in robotics, where such problems naturally arise when probabilistic models of robot motion are required to satisfy temporal logic task specifications. We transform this problem into a Stochastic Shortest Path (SSP) problem and develop a new approximate dynamic programming algorithm to solve it. This algorithm is of the actor-critic type and uses a least-square temporal difference learning method. It operates on sample paths of the system and optimizes the policy within a pre-specified class parameterized by a parsimonious set of parameters. We show its convergence to a policy corresponding to a stationary point in the parameters' space. Simulation results confirm the effectiveness of the proposed solution., Technical report accompanying an accepted paper to CDC 2011
- Published
- 2011
42. On Optimal Cooperator Selection Policies for Multi-Hop Ad Hoc Networks
- Author
-
Michele Rossi, Cristiano Tapparello, and Stefano Tomasin
- Subjects
Computer science ,Wireless ad hoc network ,Automatic repeat request ,Markov process ,optimal policies ,multi-hop communication ,Network topology ,Hop (networking) ,MIMO systems ,Ad hoc wireless networks ,automatic repeat request ,symbols.namesake ,cooperative communication ,Path loss ,Wireless ,Fading ,Electrical and Electronic Engineering ,Markov chain ,business.industry ,Applied Mathematics ,Computer Science Applications ,Dynamic programming ,Shortest path problem ,symbols ,business ,Computer network - Abstract
In this paper we consider wireless cooperative multihop networks, where nodes that have decoded the message at the previous hop cooperate in the transmission toward the next hop, realizing a distributed space-time coding scheme. Our objective is finding optimal cooperator selection policies for arbitrary topologies with links affected by path loss and multipath fading. To this end, we model the network behavior through a suitable Markov chain and we formulate the cooperator selection process as a stochastic shortest path problem (SSP). Further, we reduce the complexity of the SSP through a novel pruning technique that, starting from the original problem, obtains a reduced Markov chain which is finally embedded into a solver based on focused real time dynamic programming (FRTDP). Our algorithm can find cooperator selection policies for large state spaces and has a bounded (and small) additional cost with respect to that of optimal solutions. Finally, for selected network topologies, we show results which are relevant to the design of practical network protocols and discuss the impact of the set of nodes that are allowed to cooperate at each hop, the optimization criterion and the maximum number of cooperating nodes.
- Published
- 2011
43. A New Network Flow Model for Determining the Assortment of Roll Types in Packaging Industry
- Author
-
Ceren Atay, Ayşe Cilacı Tombuş, Önder Tombuş, Gizem Kokten, Gurdal Ertek, and Maltepe Üniversitesi
- Subjects
cutting stock ,dynamic programming ,Operations research ,Computer science ,Bin packing problem ,T055.4-60.8 Industrial engineering. Management engineering ,TS0155-194 Production management. Operations management ,Cost accounting ,Graph theory ,assortment problem ,T58.4 Managerial control systems ,Flow network ,T175 Industrial research. Research and development ,Dynamic programming ,T58.5 Information technology ,QA076 Computer software ,Shortest path problem ,T58.6-58.62 Management information systems ,Decision-making ,T57.6-57.97 Operations research. Systems analysis ,Fixed cost ,packaging industry ,shortest path problem - Abstract
IEEE International Conference on Systems, Man and Cybernetics -- OCT 10-13, 2010 -- Istanbul, TURKEY, WOS: 000295015300036, This paper reports work motivated by a real world assortment problem in packaging industry. A novel network flow model has been developed to solve the problem of selecting the optimal set of roll types for use in production. The model can incorporate fixed costs that depend on the number of elements in the assortment as well as the selected roll types. While the trade-off between inventory cost and cost of waste is resolved optimally through the model, graphical understanding of the trade-off can bring insights into the decision making process. This graphical analysis has been demonstrated on a computational example., IEEE
- Published
- 2010
44. Vehicle routing problems with alternative paths: an application to on-demand transportation
- Author
-
Christian Artigues, Didier Josselin, Dominique Feillet, Thierry Garaix, Laboratoire Informatique d'Avignon (LIA), Centre d'Enseignement et de Recherche en Informatique - CERI-Avignon Université (AU), Études des Structures, des Processus d’Adaptation et des Changements de l’Espace (ESPACE), Université de la Méditerranée - Aix-Marseille 2-Université de Provence - Aix-Marseille 1-Avignon Université (AU)-Centre National de la Recherche Scientifique (CNRS)-Université de Nice Sophia-Antipolis (UNSA), LAAS-MOGISA, Laboratoire d'analyse et d'architecture des systèmes (LAAS), Université Toulouse - Jean Jaurès (UT2J)-Université Toulouse 1 Capitole (UT1), Université Fédérale Toulouse Midi-Pyrénées-Université Fédérale Toulouse Midi-Pyrénées-Centre National de la Recherche Scientifique (CNRS)-Université Toulouse III - Paul Sabatier (UT3), Université Fédérale Toulouse Midi-Pyrénées-Institut National des Sciences Appliquées - Toulouse (INSA Toulouse), Institut National des Sciences Appliquées (INSA)-Institut National des Sciences Appliquées (INSA)-Institut National Polytechnique (Toulouse) (Toulouse INP), Université Fédérale Toulouse Midi-Pyrénées-Université Toulouse - Jean Jaurès (UT2J)-Université Toulouse 1 Capitole (UT1), Université Fédérale Toulouse Midi-Pyrénées, Département Sciences de la Fabrication et Logistique (SFL-ENSMSE), École des Mines de Saint-Étienne (Mines Saint-Étienne MSE), Institut Mines-Télécom [Paris] (IMT)-Institut Mines-Télécom [Paris] (IMT)-CMP-GC, Avignon Université (AU)-Centre d'Enseignement et de Recherche en Informatique - CERI, Université Toulouse Capitole (UT Capitole), Université de Toulouse (UT)-Université de Toulouse (UT)-Institut National des Sciences Appliquées - Toulouse (INSA Toulouse), Institut National des Sciences Appliquées (INSA)-Université de Toulouse (UT)-Institut National des Sciences Appliquées (INSA)-Université Toulouse - Jean Jaurès (UT2J), Université de Toulouse (UT)-Université Toulouse III - Paul Sabatier (UT3), Université de Toulouse (UT)-Centre National de la Recherche Scientifique (CNRS)-Institut National Polytechnique (Toulouse) (Toulouse INP), Université de Toulouse (UT)-Université Toulouse Capitole (UT Capitole), and Université de Toulouse (UT)
- Subjects
Mathematical optimization ,Information Systems and Management ,General Computer Science ,Computer science ,0211 other engineering and technologies ,Context (language use) ,02 engineering and technology ,Transportation theory ,Management Science and Operations Research ,Industrial and Manufacturing Engineering ,0502 economics and business ,Vehicle routing problem ,multigraph ,Simulation ,050210 logistics & transportation ,021103 operations research ,05 social sciences ,Multigraph ,Complete graph ,[INFO.INFO-RO]Computer Science [cs]/Operations Research [cs.RO] ,on-demand transportation ,Graph ,dial-a-ride problem ,Dynamic programming ,shortest path problem with resource constraints ,Modeling and Simulation ,Shortest path problem ,Graph (abstract data type) ,Routing (electronic design automation) ,vehicle routing ,MathematicsofComputing_DISCRETEMATHEMATICS - Abstract
20 pages; International audience; The class of vehicle routing problems involves the optimization of freight or passenger transportation activities. These problems are generally treated via the representation of the road network as a weighted complete graph. Each arc of the graph represents the shortest route for a possible origin-destination connection. Several attributes can be defined for one arc (travel time, travel cost . . . ), but the shortest route modelled by this arc is computed according to one single criterion, generally travel time. Consequently, some alternative routes proposing a different compromise between the attributes of the arcs are discarded from the solution space. In this work, we propose to represent the road network with a multigraph, so that these alternative routes are considered, and to evaluate how it impacts on solution algorithms and solution values. A simple insertion algorithm is proposed and illustrated in the context of a on-demand transportation system developed in a French area. Computational experiments on academic and realistic data underline the potential cost savings brought by the multigraph model.
- Published
- 2010
45. Multi-Objective and Multi-Constrained Non-Additive Shortest Path Problems
- Author
-
Reinhardt, Line Blander and Pisinger, David
- Subjects
dynamic programming ,non-additive objective ,shortest path problem ,multi objective programming - Abstract
Shortest path problems appear as subproblems in numerous optimization problems. In most papers concerning multiple objective shortest path problems, additivity of the objective is a de-facto assumption, but in many real-life situations objectives and criteria, can be non-additive. The purpose of this paper is to give a general framework for dominance tests for problems involving a number of non-additive criteria. These dominance tests can help eliminate paths in a dynamic programming framework when using multiple objectives. Results on real-life multi-objective problems containing non-additive criteria are reported. We show that in many cases the framework can be used to efficiently reduce the number of generated paths.
- Published
- 2009
46. Label-setting methods for Multimode Stochastic Shortest Path problems on graphs
- Author
-
Alexander Vladimirsky
- Subjects
0209 industrial biotechnology ,Mathematical optimization ,General Mathematics ,MathematicsofComputing_NUMERICALANALYSIS ,010103 numerical & computational mathematics ,02 engineering and technology ,Management Science and Operations Research ,01 natural sciences ,020901 industrial engineering & automation ,FOS: Mathematics ,Mathematics - Numerical Analysis ,0101 mathematics ,Mathematics - Optimization and Control ,Mathematics ,Stochastic control ,Partial differential equation ,Numerical Analysis (math.NA) ,Optimal control ,Computer Science Applications ,Dynamic programming ,Stochastic partial differential equation ,Optimization and Control (math.OC) ,Shortest path problem ,Stochastic optimization ,Dijkstra's algorithm ,90C39, 90C40, 93E20, 65K05, 65N22, 49L20, 49L25, 35B37 - Abstract
Stochastic shortest path (SSP) problems arise in a variety of discrete stochastic control contexts. An optimal solutions to such a problem is typically computed using the value function, which can be found by solving the corresponding dynamic programming equations. In the deterministic case, these equations can be often solved by the highly efficient label-setting methods (such as Dijkstra's and Dial's algorithms). In this paper we define and study a class of Multimode Stochastic Shortest Path problems and develop sufficient conditions for the applicability of label-setting methods. We illustrate our approach on a number of discrete stochastic control examples. We also discuss the relationship of SSPs with discretizations of static Hamilton-Jacobi equations and provide an alternative derivation for several fast (non-iterative) numerical methods for these PDEs., 20 pages; 7 figures; submitted to "Mathematics of Operations Research"; minor changes & restructuring in accordance with reviewers' suggestions
- Published
- 2007
47. Reachability Analysis for Uncertain SSPs
- Author
-
Olivier Buffet, Autonomous intelligent machine (MAIA), INRIA Lorraine, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-Laboratoire Lorrain de Recherche en Informatique et ses Applications (LORIA), Institut National de Recherche en Informatique et en Automatique (Inria)-Université Henri Poincaré - Nancy 1 (UHP)-Université Nancy 2-Institut National Polytechnique de Lorraine (INPL)-Centre National de la Recherche Scientifique (CNRS)-Université Henri Poincaré - Nancy 1 (UHP)-Université Nancy 2-Institut National Polytechnique de Lorraine (INPL)-Centre National de la Recherche Scientifique (CNRS), Statistical Machine Learning Group (SML), and Australian National University (ANU)-National ICT Australia [Sydney] (NICTA)
- Subjects
0209 industrial biotechnology ,Mathematical optimization ,Stochastic modelling ,Computer science ,0102 computer and information sciences ,02 engineering and technology ,Interval (mathematics) ,010501 environmental sciences ,01 natural sciences ,Symbolic data analysis ,[INFO.INFO-AI]Computer Science [cs]/Artificial Intelligence [cs.AI] ,020901 industrial engineering & automation ,Artificial Intelligence ,Reachability ,Reachability Analysis ,0202 electrical engineering, electronic engineering, information engineering ,Enumeration ,0105 earth and related environmental sciences ,Stochastic Shortest-Path problems ,Stochastic process ,Dynamic programming ,Uncertain Model ,010201 computation theory & mathematics ,Shortest path problem ,020201 artificial intelligence & image processing ,State (computer science) ,Critical path method - Abstract
International audience; Stochastic Shortest Path problems (SSPs) can be efficiently dealt with by the Real-Time Dynamic Programming algorithm (RTDP). Yet, RTDP requires that a goal state is always reachable. This article presents an algorithm checking for goal reachability, especially in the complex case of an uncertain SSP where only a possible interval is known for each transition probability. This gives an analysis method for determining if SSP algorithms such as RTDP are applicable, even if the exact model is not known. As this is a time-consuming algorithm, we also present a simple process that often speeds it up dramatically. Yet, the main improvement still needed is to turn to a symbolic analysis in order to avoid a complete state-space enumeration.
- Published
- 2007
48. Quantization as histogram segmentation: globally optimal scalar quantizer design in network systems
- Author
-
D. Muresan, Michelle Effros, Storer, James A., and Cohn, Martin
- Subjects
Optimal design ,Mathematical optimization ,Computational complexity theory ,Quantization (signal processing) ,ComputingMethodologies_IMAGEPROCESSINGANDCOMPUTERVISION ,Directed graph ,Data_CODINGANDINFORMATIONTHEORY ,Directed acyclic graph ,Dynamic programming ,General Relativity and Quantum Cosmology ,Histogram ,Shortest path problem ,Algorithm ,Caltech Library Services ,Mathematics - Abstract
We propose a polynomial-time algorithm for optimal scalar quantizer design on discrete-alphabet sources. Special cases of the proposed approach yield optimal design algorithms for fixed-rate and entropy-constrained scalar quantizers, multi-resolution scalar quantizers, multiple description scalar quantizers, and Wyner-Ziv scalar quantizers. The algorithm guarantees globally optimal solutions for fixed-rate and entropy-constrained scalar quantizers and constrained optima for the other coding scenarios. We derive the algorithm by demonstrating the connection between scalar quantization, histogram segmentation, and the shortest path problem in a certain directed acyclic graph.
- Published
- 2002
Catalog
Discovery Service for Jio Institute Digital Library
For full access to our library's resources, please sign in.