A Gossip Based Heuristic Algorithm for Heterogeneous Multi-Vehicle Routing Problems*

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