A gossip based heuristic algorithm for heterogeneous multi-vehicle routing problems

Rosa D;FRANCESCHELLI, MAURO;SEATZU, CARLA;Bullo F.

2012-01-01

---

Abstract

In this paper we propose a novel algorithm based on gossip to solve the Heterogeneous Multi-Vehicle Routing (HMVR) problem. A set of tasks is arbitrarily placed in a plane and a set of robots has to cooperate to minimize the maximum time required to visit and execute all tasks. Each task and each robot has different cost/speed. The proposed algorithm exploits only pairwise asynchronous communications between robots and attempts to balance the routing and execution cost of the tasks assignment of each robot through an heuristic. The proposed heuristic exploits polynomial time approximation algorithms to solve the Travelling Salesman Problem (TSP). Some characterization of the convergence properties of the algorithm are given together with extensive simulations to corroborate the results.