Wednesday 26
Heuristics and meta-heuristics
Nicolas Dupin
› 11:30 - 12:00 (30min)
› Bât. C - Sigalas
Résolution du DARP avec un schéma d'optimisation de type ELS
Maxime Chassaing  1@  , Philippe Lacomme  1@  , Christian Laforest  1  
1 : Laboratoire d'Informatique, de Modélisation et d'optimisation des Systèmes  (LIMOS)  -  Website
Institut Français de Mécanique Avancée, Université Blaise Pascal - Clermont-Ferrand II, Université d'Auvergne - Clermont-Ferrand I, CNRS : UMR6158
Bât ISIMA Campus des Cézeaux BP 10025 63173 AUBIERE cedex -  France

Cette présentation concerne la résolution du DARP sur les instances proposées par Cordeau et Laporte en 2003 [1]. Notre méthode de résolution tire profit de l'algorithme d'évaluation proposé par Cordeau et Laporte[1] pour prendre en compte efficacement les contraintes du problème notamment les contraintes de fenêtres de temps.

Nous avons proposé une méthode de recherche locale dédiée, qui constitue un élément de base de notre metaheuristique.

Les résultats obtenus sont meilleurs que ceux proposés par S.N. Parragh et al [2] en terme de qualité de solutions pour des temps comparables. De nouvelles meilleures solutions ont été obtenues sur 2 instances. Sur l'instance pr18 la meilleure solution connue était de 461.39 et nous avons obtenu 459.69 soit une amélioration de 0.37%.

Sur l'ensemble des 20 instances, l'écart moyen sur 5 exécutions par rapport à la meilleure solution connue est de : 0.49 % avec notre méthode, 1.42% par S.N. Parragh et al [2] et 1.42% par S.N. Parragh et V. Schmid[3].

Les solutions trouvées sont disponibles à l'adresse suivante : http://fc.isima.fr/~chassain/Phd/ELSapproachDARP.php

Notre approche ELS a aussi été combinée à du multi-start pour obtenir un nouveau schéma d'optimisation de type GRASPxELS mais nous avons constaté que cette version était moins efficace. Ceci pose les questions spécifiques de la génération de solutions initiales pertinentes et de l'adaptation de la recherche locale.

Notre travail est financé par le LABEX imobS3, DÉFI2 : "services et système de mobilité intelligente", action « Gestion de Véhicules Partagés »

[1]. Cordeau J-F, Laporte G. A tabu search heuristic for the static multi-vehicle dial-a-ride problem. Transportation Research Part B Methodological, 37 (2003), pp. 579–94.
[2]. S.N. Parragh, K.F. Doerner, R.F. Hartl. Variable neighborhood search for the dial-a-ride problem. Computers & Operations Research, 37 (2010), pp. 1129–1138
[3]. S.N. Parragh, V. Schmid. Hybrid column generation and large neighborhood search for the dial-a-ride problem.
Computers & Operations Research, 40 (2013), pp. 490–497


Online user: 2