Vehicle Routing Problem with Time Windows: From mathematical models to computing science Tools

Abstract

Cette thèse s’intéresse à la résolution de deux variantes du problème de tournées de véhicules, qui intègrent des contraintes ou des objectifs de maîtrise des risques : le problème de tournées de véhicules avec contraintes de temps déterministe (VRPTW), et le problème de tournées de véhicules avec contraintes de temps sous incertitudes de temps de service et de déplacement (RVRPTW). Les applications ciblées sont du domaine de la logistique et du transport. Le problème de tournées de véhicules avec fenêtres de temps a fait l’objet de la majeure partie des travaux de la recherche opérationnelle. Il consiste à définir un ensemble de routes de véhicules de coût total minimal, afin de collecter ou de livrer des marchandises à des clients en respectant des fenêtres de temps. Ces clients sont généralement représentés par des noeuds sur un réseau, et doivent être visités une et une seule fois par un véhicule, leur demande doit être satisfaite par cette seule visite. Le VRPTW a été très étudié et de nombreux algorithmes de résolution ont été proposés. Le mémoire se découpe en quatre parties. Le chapitre 1 est une introduction intégrant une revue de littérature qui recense les principaux travaux sur les problèmes de tournées de véhicules ainsi que les méthodes de résolution, il définit également le problème étudié dans sa version déterministe et robuste. Le chapitre 2 est une définition générale du problème de VRPTW ainsi qu’une présentation de l’algorithme de la recherche adaptive à voisinage large (ALNS) pour le VRPTW qui sera modifié dans le cadre de cette recherche. La recherche adaptive à voisinage large (ALNS) de Pisinger and Ropke, 2007, exploite les bénéfices des voisinages variés, à base des opérateurs de type destruction/reconstruction de Shaw, 1998, en adaptant la fréquence d’utilisation de chaque opérateur en fonction de leur performance dans l’historique de la recherche. Autrement dit, ALNS utilise de nombreux opérateurs de destruction et de reconstruction afin de diversifier la recherche. Elle est nommée adaptative puisqu’elle rajoute une évaluation de chaque opérateur de destruction ou de reconstruction, basée sur ses performances aux itérations précédentes. Ainsi, chaque opérateur reçoit un score qui est régulièrement mis à jour. La probabilité de choisir un opérateur à l’itération courante dépend de ce score. En effet, les modifications apportées à l’ALNS ont pour objectif l’amélioration de la fonction objectif ainsi que la diminution du temps d’exécution. Pour cette raison, on propose dans la section 2.3 deux techniques pour améliorer la qualité de la solution obtenue. Le principal défi de la première méthode est de mettre xi en évidence l’intensification par rapport à la diversification dans le processus de recherche heuristique. Dans ce contexte, nous incorporons la fonction de choix proposé par Drake, Özcan, and Burke, 2012 dans le processus de la méthode ALNS comme étant un critère de sélection de l’opérateur adéquat à chaque itération. Par conséquent, plusieurs méthodes de destruction / réparation sont combinées pour explorer plusieurs voisinages au sein d’une même recherche. Lors de la deuxième alternative, nous proposons une nouvelle approche qui s’inscrit dans la classe des algorithmes Cluster first - Route second pour traiter le problème VRPTW. Cette stratégie comme son nom l’indique, se compose de deux phases : • La phase Cluster : établir un certain nombre de clusters (k clusters lorsque k véhicules sont disponibles). • La phase route : Nous relions tous les clients d’un même cluster par un seul tour, autrement, on résout un problème VRPTW sur chaque cluster. La première phase vise à définir un ensemble de groupes faisables et rentables à l’aide l’algorithme k-Medoid en se basant sur une distance spatio-temporelle efficace qui est totalement appropriée à la nature du VRPTW, étant donné qu’il prend en compte à la fois les dimensions spatiales et temporelles du problème, alors que la deuxième phase est consacrée à la sélection des routes adéquates. En considérant que chaque cluster correspond à un sous-problème VRPTW spécifique, nous essayons de le résoudre en appliquant trois algorithmes de routage différents à savoir (La recherche adaptive à voisinage large (ALNS), la recherche à voisinage variable (VNS), et l’algorithme génétique (GA)) séparément afin de valider les résultats trouvés au premier niveau. Il est à noter que le choix du K-Medoid n’était pas arbitraire car il est plus robuste et il est plus flexible pour être utilisé avec toute mesure de similitude contrairement à d’autres techniques de partitionnement qui ne sont pas sensibles aux données bruyantes ou doivent être utilisées uniquement avec des distances cohérentes avec la moyenne (par exemple K-Means). La mesure de similarité utilisée dans l’algorithme K-Medoid a été comparée à certains algorithmes de partitionnement de la littérature tels que l’algorithme K-Means, et conduit à des solutions avec des coûts minimaux, quelles que soient les métaheuristiques utilisées pour le routage. Dans la section 2.4, nous proposons une nouvelle approche de parallélisation de l’algorithme de recherche adaptive à voisinage large conçu pour résoudre le xii problème de tournées des véhicules avec des fenêtres de temps. Notre objectif est d’obtenir une solution en temps réel réduit sans compromettre la qualité de la solution spécialement pour les grandes instances. Notre principale contribution introduit une procédure pour la parallélisation de la méthode Greedy utilisée dans le bloc d’initialisation, ainsi que les opérateurs de destruction / réparation impliqués dans le processus de la méta-heuristique ALNS. Pour améliorer notre approche, nous utilisons un algorithme de clustering itératif comme prétraitement pour affecter les clients aux threads de calcul. Pour ceci, nous adoptons le K-Means comme prototype, ce qui n’est pas une méthode restrictive, nous pouvons adopter d’autres techniques telles que les K-Medoids ou le clustering spatial basé sur la densité d’applications, (voir par exemple Cömert et al., 2017). Les résultats sont élaborés de telle manière à trouver un compromis entre la qualité de la solution et le temps d’exécution. Dans le chapitre 3, nous considérons une variante du problème de tournées de véhicules avec fenêtres de temps (VRPTW) ou les temps de service et les temps de trajet sont incertains et représentés par des ensembles discrets de valeurs incertaines. Notre contribution à tous les travaux antérieurs réside, tout d’abord, dans la modélisation du problème, en se basant sur l’approche de Bertsimas and Sim, 2003, le choix de la métaheuristique Adaptive Large Neighbourhood Search (ALNS) pour l’intégrer dans notre approche afin de traiter le VRPTW robuste. De plus, les résultats numériques ont été testés sur un ensemble de petites instances basées sur le benchmark de Solomon et de grandes instances du benchmark de Gehring & Homberger. Le problème étudié a généré différents scénarios et chaque scénario est réalisé en utilisant la meilleure méthode d’échantillonnage connue, qui est la version Metropolis de la simulation de Monte Carlo. Afin d’améliorer cette approche et étudier l’effet de la parallélisation sur le temps d’exécution et la fonction objectif. Nous avons intégré la version parallèle e l’ALNS développée par Røpke, 2009, qui conduit à une réduction du temps de fonctionnement. De plus, nous avons utilisé notre version parallèle de l’algorithme Metropolis Monte Carlo pour générer toutes les réalisations possibles et pour transformer le problème sous incertitudes en un ensemble de sous-problèmes déterministes. Sur la base de la mise en œuvre efficace de Røpke, 2009, différentes combinaisons (séquentielles / parallèles) de l’algorithme de Monte Carlo et de l’ALNS sont effectuées. De cette façon, notre stratégie offre aux décideurs le choix de la combinaison en fonction de leurs préférences et de la situation. Enfin, le quatrième chapitre n’est que la conclusion de cette recherche reprenant xiii les résultats importants ainsi que l’originalité des méthodes développées, et elle décrit quelques orientations pour les futures recherches