A multiple ant colony system with random variable neighborhood descent for the dynamic vehicle routing problem with time
- PDF / 968,280 Bytes
- 14 Pages / 595.276 x 790.866 pts Page_size
- 69 Downloads / 210 Views
(0123456789().,-volV)(0123456789(). ,- volV)
METHODOLOGIES AND APPLICATION
A multiple ant colony system with random variable neighborhood descent for the dynamic vehicle routing problem with time windows Orivalde Soares da Silva Ju´nior1
•
Jose´ Eugeˆnio Leal2 • Marc Reimann3
Springer-Verlag GmbH Germany, part of Springer Nature 2020
Abstract This paper proposes a framework to solve the dynamic vehicle routing problem with time windows. This problem involves determining the minimum cost routes of a homogeneous fleet for meeting the demand for a set of customers within time windows. In addition, new customers can be assigned to vehicles during the execution of the routes. A framework is based on two phases: a priori where the routes are obtained for the known customers using static routing, and a posteriori where routes are re-optimized repeatedly during the planning horizon either continuously or periodically. The framework was validated using seven algorithm variants based on insertion heuristic, ant colony optimization, variable neighborhood descent, and random variable neighborhood descent, which were adapted to solve a posteriori phase. The best algorithm is a hybrid version that combines an improved version of the multiple ant colony systems with a random variable neighborhood descent. Computational results show that most of the algorithms are competitive regarding the state of the art with the best results in the objective of minimizing the number of unserved customers. Keywords Dynamic vehicle routing Time windows Ant colony optimization Random variable neighborhood descent
1 Introduction
Communicated by V. Loia.
Electronic supplementary material The online version of this article (https://doi.org/10.1007/s00500-020-05350-4) contains supplementary material, which is available to authorized users. & Orivalde Soares da Silva Ju´nior [email protected] Jose´ Eugeˆnio Leal [email protected] Marc Reimann [email protected] 1
Department of Fortification and Construction Engineering, Military Institute of Engineering, Prac¸a General Tibu´rcio, 80, Urca, Rio de Janeiro, RJ, Brazil
2
Department of Industrial Engineering, Pontifical Catholic University of Rio de Janeiro, Rua Marqueˆs de Sa˜o Vicente, 225, Ga´vea, Rio de Janeiro, RJ 22451-900, Brazil
3
Department for Production and Operations Management, University of Graz, Universita¨tsstrasse 15/E3, 8010 Graz, Austria
Investment in vehicle routing research is relevant from both theoretical and practical viewpoints. Regarding the theoretical viewpoint, the vehicle routing problems and their variants belong to the NP-hard class (Lenstra and Rinnooy Kan, 1981). Thus, the efficient solution of these problems represents a challenge for researchers who need to develop methods to achieve good-quality solutions in the least possible computational time. From a practical viewpoint, with advances in information technology, it has become possible to manage the fleet in real time. In this environment, dispatchers often need to reconfigure the routes of v
Data Loading...
