Ant Colony Optimization for vehicle routing in advanced logistics systems



Luca Maria Gambardella,a,b, Andrea E. Rizzoli,a,b, Fabrizio Oliverio,b, Norman Casagrande,a, Alberto V. Donati,a, Roberto Montemanni,a, Enzo Lucibello,b
a, IDSIA, Galleria 2, 6928 Manno, Switzerland
b, AntOptima, via Fusoni 4, 6900 Lugano, Switzerland
URL: http://www.idsia.ch, http://www.antoptima.com
Email: luca@idsia.ch


ABSTRACT: Many distribution companies service their customers with non homogeneous fleets of trucks. Their problem is to find a set of routes minimising the number of travelled kilometres and the number of used vehicles, while satisfying customer demand. There are three major problems why traditional Operations Research techniques are not enough to deal with this problem, which is known as the Vehicle Routing Problem. First of all, it is inherently combinatorial, and exact algorithms fail when the dimension of the problem (number of customers and orders) reaches a reasonable size. Secondly, the problem can be extended and made more complex in many ways, for instance, adding more than one depot, considering more than one vehicle type, accounting for stochastic customer demand (the exact requested quantity is known only at delivery time), considering time windows during which the customers must be served, taking into account vehicle accessibility restrictions (some customers cannot be served by some vehicles). Finally, the problem can become very different when we consider on-line distribution, that is, we accept delivery orders for lorries which are en route. There, geolocation of customers and vehicles, online data transfer among lorries and the base station, have an impact as great as the solution strategy.

KEYWORDS: Supply chain optimisation, vehicle routing problem, ant colony optimisation

---

Back to MAS2003 Home Page