Vehicle Routing Problems with road-network information

Résumé : Les problèmes de tournées de véhicules (VRPs) ont fait l’objet de plusieurs travaux de recherche depuis maintenant plus de 50 ans. La plupart des approches trouvées dans la littérature s’appuient sur un graphe complet ou un nœud est introduit pour tout point d’intérêt du réseau routier (typiquement les clients et le dépôt). Cette modélisation est, implicitement, basée sur l’hypothèse que le meilleur chemin entre toute paire de points du réseau routier est bien défini. Cependant, cette hypothèse n’est pas toujours valide dans de nombreuses situations. Souvent, plus d’informations sont nécessaires pour modéliser et résoudre correctement le problème. Nous commençons par examiner ces situations et définir les limites de la modélisation basée sur un graphe complet. Nous proposons un état de l’art des travaux qui examinent ces limites et qui traitent des VRPs en considérant plus d’informations issues du réseau routier. Nous décrivons les approches alternatives proposées, à savoir la modélisation utilisant un multi-graphe et celle utilisant la résolution directe sur un graph représentant le réseau routier. Dans une seconde étude, nous nous intéressons à l’approche basée sur la construction d’un multi-graphe. Nous proposons, d’abord, un algorithme qui permet de calculer d’une manière efficace la représentation par multi-graph du réseau routier. Puis, nous présentons une analyse empirique sur l’impact de cette modélisation sur la qualité de la solution. Pour ce faire, nous considérons le problème classique VRPTW comme un problème de pilote. Par la suite, nous développons une méthode heuristique efficace afin de résoudre le VRPTW basée sur une représentation par un multi-graphe.Dans une troisième étape, nous nous concentrons sur l’approche basée sur la résolution directe du problème sur un graphe représentant le réseau routier. Nous développons un algorithme de type branch-and-price pour la résolution de cette variante du problème. Une étude expérimentale est, ensuite, menée afin d’évaluer l’efficacité relative des deux approches. Enfin, nous étudions les problèmes de tournées de véhicules dans lesquels les temps de parcours varient au cours de la journée. Nous proposons un algorithme de type branch-and-price afin de résoudre le problème avec des fenêtres de temps directement sur le graphe représentant le réseau routier. Une analyse empirique sur l’impact de l’approche proposée sur la qualité de la solution est proposée.
Type de document :
Thèse
Other [cs.OH]. Université Clermont Auvergne, 2017. English. 〈NNT : 2017CLFAC071〉
Liste complète des métadonnées

Littérature citée [198 références]  Voir  Masquer  Télécharger

https://tel.archives-ouvertes.fr/tel-01793702
Contributeur : Abes Star <>
Soumis le : mercredi 16 mai 2018 - 18:40:06
Dernière modification le : jeudi 17 mai 2018 - 01:23:11

Fichier

2017CLFAC071_BEN_TICHA.pdf
Version validée par le jury (STAR)

Identifiants

  • HAL Id : tel-01793702, version 1

Citation

Hamza Ben Ticha. Vehicle Routing Problems with road-network information. Other [cs.OH]. Université Clermont Auvergne, 2017. English. 〈NNT : 2017CLFAC071〉. 〈tel-01793702〉

Partager

Métriques

Consultations de la notice

59

Téléchargements de fichiers

9