Vehicle Routing Problems with road-network information
Problèmes de tournées de véhicules avec des informations du réseau routier
Résumé
Vehicle routing problems (VRPs) have drawn many researchers’ attention for more than fifty years. Most approaches found in the literature are, implicitly, based on the key assumption that the best path between each two points of interest in the road network (customers, depot, etc.) can be easily defined. Thus, the problem is tackled using the so-called customer-based graph, a complete graph representation of the road network. In many situations, such a graph may fail to accurately represent the original road network and more information are needed to address correctly the routing problem.We first examine these situations and point out the limits of the traditional customer-based graph. We propose a survey on works investigating vehicle routing problems by considering more information from the road network. We outline the proposed alternative approaches, namely the multigraph representation and the road network approach.Then, we are interested in the multigraph approach. We propose an algorithm that efficiently compute the multigraph representation for large sized road networks. We present an empirical analysis on the impact of the multigraph representation on the solution quality for the VPR with time windows (VRPTW) when several attributes are defined on road segments. Then, we develop an efficient heuristic method for the multigraph-based VRPTW.Next, we investigate the road network approach. We develop a complete branch-and-price algorithm that can solve the VRPTW directly on the original road network. We evaluate the relative efficiency of the two approaches through an extensive computational study.Finally, we are interested in problems where travel times vary over the time of the day, called time dependent vehicle routing problems (TDVRPs). We develop a branch-and-price algorithm that solves the TDVRP with time windows directly on the road network and we analyze the impact of the proposed approach on the solution quality.
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.
Origine : Version validée par le jury (STAR)
Loading...