Les problèmes de tournées de véhicules et leurs variantes

Professeur Roberto Wolfler Calvo,
LIPN, Université Paris 13

Les problèmes de tournées de véhicules présentent un caractère spécifique et typiquement opérationnel des problèmes de logistique et de transport. D’autre part, ils constituent une famille particulière et très étudiée des problèmes d’optimisation combinatoire. Le nombre d’articles et de monographies consacrés au Traveling Salesman Problem (TSP) et/ou au Vehicle Routing Problem (VRP) est énorme. De plus, depuis quelques années, les chercheurs se sont intéressés à des variantes plus réalistes et donc plus complexes de problèmes de tournées de véhicules comme certaines qui combinent à la fois les aspects stratégiques et tactiques, ou d’autres qui introduisent les fenêtres horaires, les chargements et déchargements, ou plusieurs piles de rangement. Dans cet exposé nous souhaitons faire un survol des méthodes utilisées pour résoudre cette grande famille de problèmes d’optimisation combinatoire, et nous concentrer particulièrement sur les algorithmes exacts de type génération de colonnes qui se sont avérés, ces dernières années, être les méthodes de résolution les plus efficaces.

Etant donnés un graphe valué, non-orienté pour simplifier, G=(X,E,C), contenant un noeud-dépôt avec des véhicules de capacité Q et des noeuds-clients avec des demandes q_i, il s’agit de déterminer un ensemble de cycles (tournées) visitant une seul fois chaque client, de coût total minimal, et tels que la quantité servie par chaque tournée n’excède pas la capacité des véhicules. Deux familles d’heuristiques connues sont "cluster-first, route second" et "route-first, cluster-second". La première définit des groupes de clients compatibles avec la capacité d’un véhicule puis résout un problème de voyageur de commerce pour chaque groupe. La seconde famille, encore peu utilisée en pratique, relaxe la capacité des véhicules et détermine, exactement ou heuristiquement, une tournée unique qui visite tous les clients. Ce "tour géant" peut ensuite être découpé optimalement (sous contrainte de la séquence) en tournées réalisables pour le problème de départ. Ce principe peut être utilisé dans des heuristiques simples, en deux phases, ou dans des métaheuristiques comme des algorithmes génétiques, dans lesquels les chromosomes sont définis par des permutations des clients (tours géants), évaluées grâce à la procédure de découpage. La procédure de découpage équivaut à calculer un chemin de coût minimal dans un graphe auxiliaire qui représente toutes les façons de découper le tour géant. Ce problème de chemin se complique vite si le problème de tournées a des contraintes supplémentaires. Le but de l’exposé serait de montrer le principe de la procédure de découpage et comment gérer des contraintes additionnelles.

La régulation des sytèmes de vélos en libre-service, comme Vélib’, soulève de nombreux problèmes opérationnels. L’un des plus naturels est celui du repositionnement des vélos par un ou plusieurs camions.

On s’intéresse ici au cas statique, mono-camion. On se donne un réseau dont les sommets sont des stations. On connaît la répartition courante des vélos dans les stations et on veut les déplacer à l’aide d’un camion de manière à atteindre une répartition-cible, et ce, au coût minimum. La motivation opérationnelle correspond à la situation rencontrée en fin de nuit, lorsque quasiment aucun vélo ne se déplace.

Une partie de l’exposé traitera des cas particuliers polynomiaux et des algorithmes d’approximation. Une méthode efficace pour résoudre en pratique des instances de taille raisonnable sera également présentée : cette méthode combine le calcul exact d’une borne inférieure naturelle et une recherche locale exploitant certaines propriétés théoriques du problème. Enfin, des questions ouvertes seront discutées.

Travail résultant d’une collaboration avec Daniel Chemla, Roberto Wolfler Calvo, et divers étudiants en stage.

Application of the Nested Rollout Policy Adaptation Algorithm to the Traveling Salesman Problem with Time Windows

Fabien Teytaud
Université Paris-Dauphine

In this work, we are interested in the minimization of the travel cost of the traveling salesman problem with time windows. In order to do this minimization we use a Nested Rollout Policy Adaptation (NRPA) algorithm. NRPA has multiple levels and maintains the best tour at each level. It consists in learning a rollout policy at each level. We also show how to improve the original algorithm with a modified rollout policy that helps NRPA to avoid time windows violations.

The Uncapacitated Asymmetric Traveling Salesman Problem with Multiple Stacks

Mathieu Lacroix
LIPN, Université Paris 13

In the uncapacitated asymmetric traveling salesman problem with multiple stacks, we perform a hamiltonian circuit to pick up n items, storing them in a vehicle with k stacks satisfying last-in-first-out constraints, and then we deliver every item by performing a hamiltonian circuit. We are interested in the convex hull of the (arc-)incidence vectors of such couples of hamiltonian circuits. For the general case, we determine the dimension of this polytope, and show that every facet of the asymmetric traveling salesman polytope defines one of its facets. For the special case with two stacks, we provide an integer linear programming formulation whose linear relaxation is polynomial-time solvable, and we propose new families of valid inequalities to reinforce this linear relaxation.