Home > Analysis and Design of Hybrid Systems > 4th IFAC Conference on Analysis and Design of Hybrid Systems > A Gossip Algorithm for Heterogeneous Multi-Vehicle Routing Problems
» Download Article
Document
Reference
A Gossip Algorithm for Heterogeneous Multi-Vehicle Routing Problems
Analysis and Design of Hybrid Systems, Volume # | Part#
Location: TU Eindhoven, Netherlands
National Organizing Committee Chair: Heemels, Maurice,
De Schutter, Bart
International Program Committee Chair: Giua, Alessandro,
Silva, Manuel,
Heemels, Maurice,
De Schutter, Bart
Conference Editor: Heemels, Maurice,
De Schutter, Bart,
Lazar, Mircea
Authors
Franceschelli, Mauro; Rosa, Daniele; Seatzu, Carla; Bullo, Francesco
Digital Object Identifier (DOI)
10.3182/20120606-3-NL-3011.00052
Page Numbers:
325-332
Index Terms
Complexity; Networks; Control
Abstract
In this paper we address the heterogeneous multi-vehicle routing problem by proposing a distributed algorithm based on gossip. We consider the case where a set of tasks arbitrarily distributed in a plane, each with a service cost, have to be served by a set of mobile robots, each with a given movement speed and task execution speed. Our goal is to minimize the maximum execution time of robots.
References
Bektas, T. (2006). The multiple traveling salesman problem:an overview of formulations and solution procedures. Omega, 34(3), 209–219. Bullo, F., Carli, R., and Frasca, P. (2011a). Gossip coverage control for robotic networks: Dynamical systems on the space of partitions. SIAM Journal on Control and Optimization. To appear. Bullo, F., Frazzoli, E., Pavone, M., Savla, K., and Smith, S.L. (2011b). Dynamic vehicle routing for robotic systems. Proceedings of the IEEE, 99(9), 1482–1504. Carli, R., Fagnani, F., Speranzon, A., and Zampieri, S. (2008). Communication constraints in the average consensus problem. Automatica, 44 (3), 671–684. Carlsson, J., Ge, D., Subramaniam, A., Wu, A., and Ye,Y. (2009). Solving min-max multi-depot vehicle routing problem. Lectures on global optimization, 55, 31–46. Few, L. (1955). The shortest path and the shortest road through n points. Mathematika, 2(2), 141–144. Franceschelli, M., Giua, A., and Seatzu, C. (2011). Quantized consensus in Hamiltonian graphs. Automatica, 47(11), 2495–2503. Gutin, G. and Punnen, A.P. (2002). The Traveling Saleman Problem and Its Variations, volume 12 of Series in Combinatorial Optimization, Springer. Kluwer Academic Publishers. Karloff, H.J. (1989). How long can a Euclidean traveling salesman tour be? SIAM Journal on Discrete Mathematics, 2(1), 91–99. Laporte, G. (1992a). The traveling salesman problem: An overview of exact and approximate algorithms. European Journal of Operational Research, 59(2), 231–247. Laporte, G. (1992b). The vehicle routing problem: An overview of exact and approximate algorithms. European Journal of Operational Research, 59(3), 345–358. Lawler, E.L., Lenstra, J.K., Rinnooy-Kan, A.H.G., and Shmoys, D.B. (1985). The Traveling Saleman Problem: A Guided Tour of Combinatorial Optimization. Wiley Series in Discrete Mathematics and Optimization. John Wiley and Sons. Pisinger, D. and Ropke, S. (2007). A general heuristic for vehicle routing problems. Computers & Operations Research, 34(8), 2403–2435. Toth, P. and Vigo, D. (2002). The Vehicle Routing Problem, volume 9 of monographs on Discrete Mathematics and Applications. SIAM.