Time dependent vehicle routing problem with a multi ant colony system

By Alberto V. Donati, R. Montemanni, Norman Casagrande, A. Rizzoli, Luca Maria Gambardella. European Journal of Operational Research, 2008

409 citations recorded by the source corpus.

The Time Dependent Vehicle Routing Problem (TDVRP) consists in optimally routing a fleet of vehicles of fixed capacity when travel times are time dependent, in the sense that the time employed to traverse each given arc, depends on the time of the day the travel starts from its originating node. The optimization method consists in finding solutions that minimize two hierarchical objectives: the number of tours and the total travel time. Optimization of total travel time is a continuous optimization problem that in our approach is solved by discretizing the time space in a suitable number of subspaces. New time dependent local search procedures are also introduced, as well as conditions that guarantee that feasible moves are sought for in constant time. This variant of the classic Vehicle Routing Problem is motivated by the fact that in urban contexts variable traffic conditions play an essential role and can not be ignored in order to perform a realistic optimization. In this paper it is shown that when dealing with time constraints, like hard delivery time windows for customers, the known solutions for the classic case become unfeasible and the degree of unfeasibility increases with the variability of traffic conditions, while if no hard time constraints are present, the classic solutions become suboptimal. Finally an application of the model to a real case is presented. The model is integrated with a robust shortest path algorithm to compute time dependent paths between each customer pairs of the time dependent model.

Subfields: Artificial Intelligence, Industrial and Manufacturing Engineering, Transportation

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

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

1. Marco Dorigo
2. Thomas Stützle
3. Christian Blum
4. Seyedali Mirjalili
5. Manuel López-Ibáñez
6. Xin-She Yang
7. Holger H. Hoos
8. Xiaodong Li

In Industrial and Manufacturing Engineering

1. Marco Dorigo
2. Thomas Stützle
3. Jesús González-Feliu
4. Erwin W. Hans
5. Dominique Feillet
6. Diego Cattaruzza
7. Nabil Absi
8. Adrianus Leendert Kok

In Transportation

1. Jesús González-Feliu
2. Dominique Feillet
3. Diego Cattaruzza
4. Nabil Absi

Citations in the corpus

• Vehicle routing problems for city logistics (2017, background): “[28]).”
• 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.”
• Vehicle routing under time-dependent travel times: The impact of congestion avoidance (2012, methodology): “[13] propose an ant colony optimization algorithm for the TDVRP, which they test on some theoretical benchmarks, and a test case in the district of Padua in Italy.”