A comparative study between dynamic adapted PSO and VNS for the vehicle routing problem with dynamic requests

Mostepha Redouane Khouadjia 1 Briseida Sarasola 2 Enrique Alba 2 Laetitia Jourdan 3 El-Ghazali Talbi 3
1 TAO - Machine Learning and Optimisation
LRI - Laboratoire de Recherche en Informatique, UP11 - Université Paris-Sud - Paris 11, Inria Saclay - Ile de France, CNRS - Centre National de la Recherche Scientifique : UMR8623
3 DOLPHIN - Parallel Cooperative Multi-criteria Optimization
LIFL - Laboratoire d'Informatique Fondamentale de Lille, Inria Lille - Nord Europe
Abstract : Combinatorial optimization problems are usually modeled in a static fashion. In this kind of problems, all data are known in advance, i.e. before the optimization process has started. However, in practice, many problems are dynamic, and change while the optimization is in progress. For example, in the dynamic vehicle routing problem (DVRP), new orders arrive when the working day plan is in progress. In this case, routes must be reconfigured dynamically while executing the current simulation. The DVRP is an extension of a conventional routing problem, its main interest being the connection to many real word applications (repair services, courier mail services, dial-a-ride services, etc.). In this article, a DVRP is examined, and solving methods based on particle swarm optimization and variable neighborhood search paradigms are proposed. The performance of both approaches is evaluated using a new set of benchmarks that we introduce here as well as existing benchmarks in the literature. Finally, we measure the behavior of both methods in terms of dynamic adaptation.
Type de document :
Article dans une revue
Applied Soft Computing, Elsevier, 2012, 12 (4), pp.1426-1439. 〈10.1016/j.asoc.2011.10.023〉
Liste complète des métadonnées

https://hal.inria.fr/hal-00750715
Contributeur : Talbi El-Ghazali <>
Soumis le : lundi 12 novembre 2012 - 10:34:17
Dernière modification le : vendredi 28 septembre 2018 - 16:18:07

Identifiants

Citation

Mostepha Redouane Khouadjia, Briseida Sarasola, Enrique Alba, Laetitia Jourdan, El-Ghazali Talbi. A comparative study between dynamic adapted PSO and VNS for the vehicle routing problem with dynamic requests. Applied Soft Computing, Elsevier, 2012, 12 (4), pp.1426-1439. 〈10.1016/j.asoc.2011.10.023〉. 〈hal-00750715〉

Partager

Métriques

Consultations de la notice

465