Dans les années 1800, les commerciaux étaient sur les routes, à dos de cheval, et devaient parcourir de nombreuses villes souvent très éloignées entre elles. Connaître l’itinéraire le plus rapide pour visiter ces villes et retourner ensuite chez soi était alors primordial. Cet itinéraire fut par la suite appelé “un tour”. À cette époque, on pouvait trouver un grand nombre de livres, tel que “ein alter Commis-Voyageur [3]”, proposant différents tours pour différents ensembles de villes à visiter. Ce problème d’itinéraire est connu comme le problème du voyageur de commerce, en anglais “Travelling Salesman Problem” (TSP).

De nos jours, les besoins en matière d’optimisation ont évolué, mais les problèmes sous-jacents restent les mêmes. Par exemple, nous pouvons modéliser un problème de planification comme un TSP où les villes sont des tâches à effectuer et les liens entre ces villes sont des temps de transition entre les tâches.

Dans la logistique, le problème du TSP est souvent associé au problème des tournées de véhicules. Les clients à livrer sont alors comparables aux villes dans ce problème et les camions deviennent alors les commerciaux. Au lieu d’optimiser la route pour une seule personne, on cherche plutôt à optimiser la route pour un ensemble de personnes.

La question que l’on peut se poser serait alors, lors des tournées de véhicules, quel est l’ensemble optimal des routes à traverser pour livrer un ensemble de clients

Définition du problème

D’un point de vue logistique, les données suivantes sont nécessaires à la résolution du problème :

• Un ou plusieurs dépôts
• Un ou plusieurs camions
• Une ou plusieurs commandes

En pratique, les besoins des entreprises impliquent souvent des contraintes annexes. Des contraintes de capacité, chaque camion de la flotte a une capacité limitée, il ne peut donc pas contenir un nombre infini de biens à livrer. Des contraintes de fenêtres de temps pour que le client puisse être livré dans la plage horaire qu’il souhaite. A cela s'ajoutent également des contraintes métiers, le nombre de camions pouvant être chargés simultanément ou le type de biens pouvant être chargés simultanément dans un même camion.

Optimisation

L’ensemble optimal des routes à traverser peut être différent selon les applications. On peut vouloir minimiser la tournée la plus longue, le nombre de véhicules, la distance totale parcourue, la consommation d’essence, son impact carbone …

On notera qu’il est possible d’avoir plusieurs objectifs, pondérés ou non, afin d’obtenir une solution optimale correspondant parfaitement aux besoins.

Ainsi, une solution est une affectation des clients aux camions partant d’un des dépôts respectant les contraintes spécifiées au préalable minimisant l’objectif préalablement défini.

Résolution

Lorsqu’on souhaite résoudre ce problème, deux options s’offrent à nous : trouver la solution optimale ou une solution presque optimale satisfaisant les contraintes imposées. Chaque type de résolution a ses avantages et ses inconvénients, nous allons voir cela dans la suite.

Résolution exacte

La solution optimale peut être trouvée à l’aide d’algorithmes de résolution exacte tels que des branch-and-bound ou des branch-and cut [1]. Souvent, l’idée est de résoudre successivement une relaxation de ce problème qui est simple à résoudre jusqu’à obtenir une solution au problème initial. L’avantage de ce type de résolution est qu’on trouve la meilleure solution. Cependant, les temps de résolutions sont généralement beaucoup plus grands (plusieurs ordres de grandeur) que les temps de résolutions obtenues avec une résolution heuristique, qui elle trouve de moins bonnes solutions (mais relativement proche de l’optimale).

Résolution heuristique

Les méthodes heuristiques fonctionnent souvent de la manière suivante : on définit une première solution loin de l’optimale, puis itérativement on l’améliore. Par exemple, on peut trouver une solution ne contenant pas tous les clients, puis itérativement les ajouter. Ou bien échanger l’ordre de certains clients pour améliorer la solution. Ainsi, diverses méthodes de recherche locale sont utilisées [2]. On peut aussi utiliser du Machine Learning dans la résolution en apprenant par exemple les échanges de clients efficaces. Cela peut s’avérer utile puisque pour une solution donnée, il existe un grand nombre de combinaison possible (O($n^k$) où n est le nombre de clients et k le nombre de clients à échanger). Un tel procédé produit souvent des solutions très proches de l’optimal, mais avec aucune garantie qu’on ait trouvé la meilleure solution. Dans certains cas cela peut être suffisant (par exemple, trouver le chemin le plus rapide pour un taxi à la seconde près n’est pas toujours nécessaire).

On notera que la plupart des solveurs (logiciels résolvant des problèmes mathématiques) actuels résolvent les problèmes de tournées de véhicules contenant plusieurs dizaines voire centaines de clients à livrer.

Aujourd’hui, ce problème est parfois résolu à la main par des logisticiens : cela peut s’avérer pénible et sous optimal. L’avantage d’utiliser un solveur pour résoudre ce problème est qu’on peut obtenir une très bonne solution bien plus rapidement qu’à la main. Un autre avantage est que les solutions peuvent être modifiées rapidement si des modifications doivent être effectuées (par exemple, un client absent perturbant le planning, une route bloquée...). Un solveur permet aussi de résoudre des problèmes de plus grande taille, car comme souvent traiter un grand nombre de données est plus simple à l’aide d’une machine.

Avoir un solveur permet aussi d’obtenir plus facilement une visibilité sur les futures livraisons et sur les créneaux disponibles sans avoir à demander à plusieurs humains s’ils pensent que cette livraison peut être effectuée : cela améliore ainsi le temps de réponse pour le client et la flexibilité.

Conclusion

Finalement, l’utilisation d’un solveur permet d’obtenir de meilleures solutions que des solutions produites à la main et plus rapidement. Dans certains cas, l’expertise d’un humain peut être nécessaire, et peut être utilisée pour obtenir des solutions de plus en plus satisfaisantes. Le plus complexe, souvent, est de bien réussir à modéliser son problème, certaines contraintes ne sont pas toujours simples à mettre en œuvre. Par exemple, la satisfaction client. Néanmoins, ce genre de choses peut être pris en compte sans forcément avoir à les spécifier avec des outils de Machine Learning et autres.

Références

[1] TOTH, Paolo et VIGO, Daniele. Exact solution of the vehicle routing problem. In : Fleet management and logistics. Springer, Boston, MA, 1998. p. 1-31. https://doi.org/10.1007/978-1-4615-5755-5_1

[2] GOLDEN, Bruce L., RAGHAVAN, Subramanian, WASIL, Edward A., et al. (ed.). The vehicle routing problem: latest advances and new challenges. New York : Springer, 2008. https://doi.org/10.1007/978-0-387-77778-8

[3] ein alter Commis-Voyageur (1832). "Der Handlungsreisende – wie er sein soll und was er zu tun hat, um Aufträge zu erhalten und eines glücklichen Erfolgs in seinen Geschäften gewiß zu sein – von einem alten Commis-Voyageur".