Tournées de véhicules - L'épreuve du réel

1. Introduction

Les tournées de véhicules sont largement étudiées. Dans la littérature, les variantes sont légions, mais les instances de référence sont pour la plupart idéalisées avec des distances à vol d'oiseau et des répartitions uniformes ou géométriques. Quels sont les différences entre ces instances et les problèmes rencontrés par les acteurs du dernier kilomètre ? Comment assurer ainsi le passage à la réalité et à l'échelle des méthodes mises en place pour les résoudre ? En utilisant les solveurs actuels aux problèmes actuels quels sont les volumes que l'on peut manipuler ?

2. Méthodologie

En partant d'une sélection de scénarios rencontrés par les acteurs du dernier kilomètre, nous appliquons différents niveaux de modélisation. Tout d'abord pour projeter les points à visiter sur le graphe routier. Ensuite nous sélectionnons et interprétons ce graphe pour effectuer le calcul des itinéraires. Enfin nous modélisons les contraintes considérées lors de la résolution. Il est à noter que durant la phase de résolution, nous avons plusieurs outils à notre disposition. Nous utilisons en particulier, VROOM, une bibliothèque d'heuristiques, pour le problème de voyageur de commerce. Également, nous utilisons OR-Tools, un solveur de programmation par contrainte et sa librairie dédiée au routing, pour les autres variantes de tournées de véhicules que nous gérons. Nous utilisons par ailleurs diverses heuristiques développées en interne pour certains types de problèmes, en particulier avec un grand nombre de points à visiter. Nous illustrerons notre propos avec différentes problématiques rencontrées pour lesquelles nous mettons en place des méthodes adaptées et permettant de garder un panel large de variantes. Nous aborderons entre autres les problèmes de tournées de véhicules riches pour lesquels nous appliquons une approche Divide and Conquer avec aquelle nous traitons facilement des problèmes comportant 2000 points de visite. Une seconde problématique nous permettra d'évoquer les tournées de véhicules périodiques, demandant des visites régulières à certains clients, pour laquelle nous utilisons une heuristique mettant en avant les visites fréquentes, ici nous traitons des instances avec 55000 visites répartis sur 4500 points géographiques sur un horizon de 12 semaines.

Télécharger les slides

Revoir le live :