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.

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

FRANCESCHELLI, MAURO;SEATZU, CARLA;
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.
2012
978-390282322-9
File in questo prodotto:
Non ci sono file associati a questo prodotto.

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11584/107753
 Attenzione

Attenzione! I dati visualizzati non sono stati sottoposti a validazione da parte dell'ateneo

Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus ND
  • ???jsp.display-item.citation.isi??? ND
social impact