Ant Colony System for a Dynamic Vehicle Routing Problem

By R. Montemanni, Luca Maria Gambardella, A. Rizzoli, Alberto V. Donati. Journal of combinatorial optimization, 2005

424 citations recorded by the source corpus.

An aboundant literature on vehicle routing problems is available. However, most of the work deals with static problems, where all data are known in advance, i.e. before the optimization has started.The technological advances of the last few years give rise to a new class of problems, namely the dynamic vehicle routing problems, where new orders are received as time progresses and must be dynamically incorporated into an evolving schedule.In this paper a dynamic vehicle routing problem is examined and a solving strategy, based on the Ant Colony System paradigm, is proposed.Some new public domain benchmark problems are defined, and the algorithm we propose is tested on them.Finally, the method we present is applied to a realistic case study, set up in the city of Lugano (Switzerland).

Subfields: Artificial Intelligence, Industrial and Manufacturing Engineering

View Paper: https://www.semanticscholar.org/paper/bf2504e3f3b2461f56ce2bcabba0bb4e70db5543

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Industrial and Manufacturing Engineering

Citations in the corpus

A Survey on the Vehicle Routing Problem and Its Variants (2012, methodology): “In their article, [47] propose an ant colony system (ACS) meta heuristic procedure to solve the DVRP.”
A survey of swarm intelligence for dynamic optimization: Algorithms and applications (2017, background): “[67, 122, 123, 124, 125, 48, 49, 37, 33, 126, 127] [128, 129, 130, 131, 132, 133, 134, 47, 135] – – – –”
Ant colony optimization (2006, positive): “More recently, an ACS algorithm has also been applied to dynamic vehicle routing problems [80], showing good behavior on randomly generated as well as realworld instances.”
A review of dynamic vehicle routing problems (2013, methodology): “[102] developed an Ant Colony System (ACS) to solve the D-VRP.”
Ant Colony Optimization: Overview and Recent Advances (2018, background): “More recently, applications of ACS to dynamic vehicle routing problems are reported in [54, 117], showing good results on academic instances of the problem as well as on real-world instances.”
Classification With Ant Colony Optimization (2007, methodology): “ACO has been applied to a variety of different problems [8], such as vehicle routing [17]–[19], scheduling [20], [21], timetabling [22], traveling salesman problem [12], [14], [23], and routing in packet-switched networks [24].”