Adaptation de la méthode GRASP (« Greedy Randomized Adaptive Search Procedure » ). Le problème de tournées de véhicules avec fenêtres du temps

7 Conclusion

Dans notre travail on a introduit un concept qui simplifie le calcul du temps du passage entre deux clients par l'ajout de la notion de vitesse, aussi l'introduction du temps du service dans le temps de roulement. Pendant la construction des listes de clients à affecter, le processus introduit un principe qui permet de distinguer les points les plus distants et ceux les plus urgents, en termes du dernier temps du service, Au niveau de la phase de construction, la méthode adoptée vise à affecter deux clients voisins dans deux véhicules différents afin de réduire la distance parcourue. Pour la phase d'amélioration, on choisit un processus assez simple et qui traite toutes les permutations possibles.

Vu sa simplicité et son aspect adaptative, la méthode GRASP peut être aisément adoptée pour plusieurs extensions de la problématique et toucher au cas de dépôts multiples avec des légères modifications ; aussi pour le problème de transport civil la qualité du service à fournir est primordiale donc la minimisation du nombre des véhicules devient un objectif auxiliaire. Pour le cas du problème de chargement et de déchargement, une simple modification permet l'adaptation de cette méthode pour les exigences de la situation.

Références

[ 1 ]- C. Rebeiro «La métaheuristique GRASP » Université Catholique de département d'informatique RJ 22453-990 Rio de Janeiro Brésil.

[ 2 ]- C. Rebeiro «Heuristiques et métaheuristiques » Rapport 1S1MA Clermont-Ferrand, France 2002.

[ 3 ]- Chabrier, E. Danna et C.Lepape. « Coopération entre génération de colonnes avec tournées sans cycle et recherche locale appliquée au routage de véhicules » Acte JNPC'02.

[ 4 ]- Dimitris et D.Sichi-Levi «A new generation of vehicle routing research: robust algorithms, addressing uncertainty» Research By ONR December 1993.

[ 5 ]- Duhamel « Un Cadre Formel pour les Méthodes par Amélioration Itérative - Application à deux problèmes d'Optimisation dans les Réseaux » Ecole Doctorale des Sciences pour l'1ngénieur de Clermont-Ferrand, France Mars 2001.

[ 6 ]- É. Taillard «Principes d'implémentation des métaheuristiques » Métaheuristiques et outils nouveaux en R. O.

[ 7 ]- G. Kontoravdis G. et J. Bard «A GRASP for the VRPTW» ORSA Journal on Computing V 7 No 1 Winter 1995

[ 8 ]- J. Berger B. et M. Barkaoui «An improved hybrid genetic algorithm for the vehicle routing problem with time windows » Defence Research Establishment Valcartier, Decision Support Technology Section Val-Bélair, PQ, Canada.

[ 9 ]- J. Bramel. et D.Sichi-Levi. «Probabilistic Analysises and Practical Algorithms for the Vehicle Routing with Time Windows» Research supported in part by ONR et NSF July 1993.

[ 10 ]- Le Bouthelier «Modélisation UML pour une architecture coopérative appliquée au problème de tournées de véhicules avec fenêtres de temps » Département d'informatique et de recherche opérationnelle Faculté des arts et des sciences Université de Montréal (2000)

[ 1 1 ] - M. Baker Barrie, A.C. Carreto Carlos «A visual interactive approach to vehicle routing» Computers & Operations Research 30. 321-337 (2003).

[ 12 ]- M. G. C. Resende « Combinatorial Optimisation in Telecommunications » AT et T Labs Research technical Report: 01.15.3. July 2001.

[ 13 ]- M. G. C. Resende et C. C. Rebeiro . « Greedy randomized adaptive search procedures » AT et T Labs Research. Technical Report , Florham Park, NJ 07932 USA,August 2002.

[ 14 ]- M. G.C. Resende « Greedy Randomized Adaptive Search Procedures » AT et T Labs Research Technical Report: 98.41.1. Décembre 1998.

[ 15 ]- M. G.C. Resende et J. V. Luis Gonzalez « Greedy randomized adaptive search procedures ». 1nteligencia Artificial, Revista 1beroamericana de 1nteligencia Artificial. No.19 (2003).

[ 16 ]- M. Swihart, J. Papastavrou «A stochastic and dynamic model for the single-vehicle pick-up and delivery problem » European Journal of Operational Research 114 (1999) 447- 464.

[ 17 ]- M.Gendreau, Laporte G. et D. Yigo «Heuristics for the travelling salesman problem with pickup and delivery » Computers et Operations Research, 26 (1999) 699 -- ] 714.

[ 18 ]- P. Hansen et C. Ribeiro «Essays and Surveys in Metaheuristics » Operations Research / Computer Science 1nterfaces 15, October 2001.

[ 19 ]- Righini «approximation algorithms for VRPPD » Dipartimento di scienze dell _1nformazione Polo Didattico e di Ricerca di Crema Milano 2000.

[ 20 ]- S. R Thangiah, S. Tong et O. H. 1brahim « Hybrid genetic algorithm, simulated annealing and tabu search methods for VRPTW» Artificial 1ntelligence and Robotics Laboratory, Computer Science Department Slippery Rock University, Slippery Rock, PA 16057, U.S.A.

[ 21 ]- Solomon, and J. Desrosiers «Time window constrained routing and scheduling problems ». Transportation Science 22 1-13. (1988)

[ 221- T. Ralphs, L. Kopman, W. Pulleyblank et L. Trotter. « On the capacitated vehicle routing problem »

Resarch Report; University of Arkansas. December 2001

[ 23 1- T. Sexton and L. Bodin «The multiple-vehicle subscriber dial-a-ride problem» Working paper MS /S 83-009, College of Business and Management, University of Maryland (1983).

[ 24 1- X. Delorme, X. Gandibleux et J. Rodriguez. «GRASP for set packing problems». à paraître EJOR

[ 25 1- X. Gandibleux, D. Vancoppenolle . et D.Tuyttens. «A first making use of GRASP for solving MOCO

problems». 14th 1nternational Conference in Multiple Criteria Decision-Making, June 8-12, 1998.