Decentralized algorithms for stochastic and dynamic vehicle routing with general demand distribution
Authors:
- 1 January 2007
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- No. 01912216,p. 4869-4874
Abstract
We present decentralized algorithms for a class of stochastic and dynamic vehicle routing problems, known as the multiple-vehicle dynamic traveling repairperson problem (m-DTRP), in which demands arrive randomly over time and their locations have an arbitrary distribution, and the objective is to minimize the average waiting time between the appearance of a demand and the time it is visited by a vehicle. The best previously known control algorithms rely on centralized, a-priori task assignment, and are therefore of limited applicability in scenarios involving large ad-hoc networks of autonomous vehicles. By combining results from geometric probability and locational optimization, we provide a policy that solves, providing a constant-factor approximation to the optimal achievable performance, the decentralized version of the m-DTRP; such policy (i) does not rely on centralized and a priori task assignment, (ii) is spatially distributed, scalable to large networks, and adaptive to network changes. Simulation results are presented and discussed.Keywords
This publication has 11 references indexed in Scilit:
- Decentralized Vehicle Routing in a Stochastic and Dynamic Environment with Customer Impatience2007
- A Cooperative Receding Horizon Controller for Multivehicle Uncertain EnvironmentsIEEE Transactions on Automatic Control, 2006
- Coverage Control for Mobile Sensing NetworksIEEE Transactions on Robotics and Automation, 2004
- Decentralized algorithms for vehicle routing in a stochastic time-varying environment2004
- Coordinated target assignment and intercept for unmanned air vehiclesIEEE Transactions on Robotics and Automation, 2002
- UAV cooperative path planning2000
- Finite Size and Dimensional Dependence in the Euclidean Traveling Salesman ProblemPhysical Review Letters, 1996
- Stochastic and dynamic vehicle routing with general demand and interarrival time distributionsAdvances in Applied Probability, 1993
- Stochastic and Dynamic Vehicle Routing in the Euclidean Plane with Multiple Capacitated VehiclesOperations Research, 1993
- Probabilistic and Worst Case Analyses of Classical Problems of Combinatorial Optimization in Euclidean SpaceMathematics of Operations Research, 1990