L'une des tâches d'optimisation les plus courantes est le routage des véhicules. L'objectif est de trouver les meilleurs itinéraires pour un parc de véhicules se déplaçant dans un ensemble de lieux. En général, "meilleur" correspond aux itinéraires présentant le moins de distance ou le coût total. Voici quelques exemples de problèmes de calcul d'itinéraire:
- Une société de livraison de colis souhaite attribuer des itinéraires aux chauffeurs pour effectuer les livraisons.
- Une entreprise de télévision par câble souhaite attribuer des itinéraires aux techniciens pour qu'ils passent des appels à des services à domicile.
- Une entreprise de covoiturage souhaite attribuer des itinéraires aux conducteurs pour prendre en charge et déposer des passagers.
Le problème d'itinéraire le plus connu est le problème du commercial itinérant (TSP, Traveling Commercial Problem) : il s'agit de trouver l'itinéraire le plus court pour un vendeur qui doit rendre visite aux clients à différents endroits et revenir au point de départ. Un TSP peut être représenté par un graphique, dans lequel les nœuds correspondent aux emplacements, et les arêtes (ou arcs) indiquent un trajet direct entre des lieux. Par exemple, le graphique ci-dessous montre un TSP avec seulement quatre emplacements, étiquetés A, B, C et D. La distance entre deux emplacements est indiquée par le nombre situé à côté du bord qui les relie.
En calculant les distances de tous les itinéraires possibles, vous pouvez constater que l'itinéraire le plus court est ACDBA, pour lequel la distance totale est 35 + 30 + 15 + 10 = 90.
Plus il y a d'emplacements, plus le problème devient de plus en plus difficile. Dans l'exemple ci-dessus, il n'y a que six routes. Mais s'il y a 10 lieux (sans compter le point de départ), le nombre d'itinéraires est de 362 880. Pour 20 lieux, le nombre passe à 2432902008176640000. Il est garanti qu'une recherche exhaustive de tous les itinéraires possibles permet de trouver le plus court, mais cela n'est pas possible en termes de calcul pour tous les ensembles de lieux, sauf pour de petits ensembles. Pour les problèmes plus importants, des techniques d'optimisation sont nécessaires afin d'effectuer des recherches intelligentes dans l'espace de la solution et de trouver une solution optimale (ou presque optimale).
Une version plus générale du TSP est le problème de calcul d'itinéraire des véhicules (VRP), dans lequel il existe plusieurs véhicules. Dans la plupart des cas, les VRP présentent des contraintes: par exemple, les véhicules peuvent avoir des capacités pour le poids ou le volume maximum de marchandises qu'ils peuvent transporter, ou les chauffeurs peuvent être tenus de se rendre sur des sites pendant les périodes spécifiées demandées par les clients.
Les outils OR peuvent résoudre de nombreux types de VRP, y compris les suivants:
- Traveling Commercial Problem (Problème de commercial itinérant) : problème d'itinéraire classique dans lequel il n'y a qu'un seul véhicule.
- Problème d'itinéraire de véhicule : généralisation du TSP avec plusieurs véhicules.
- VRP avec contraintes de capacité, où les véhicules ont une capacité maximale pour les articles qu'ils peuvent transporter.
- VRP avec périodes de temps, pendant lesquelles les véhicules doivent visiter les sites à des intervalles de temps spécifiés.
- VRP avec des contraintes de ressources, telles que l'espace ou le personnel pour charger et décharger les véhicules dans le dépôt (point de départ des itinéraires).
- VRP avec visites abandonnées : les véhicules ne sont pas tenus de visiter tous les emplacements, mais doivent payer une pénalité pour chaque visite ajoutée.
Limites sur la résolution des problèmes de calcul d'itinéraire des véhicules
Les problèmes d'itinéraire d'un véhicule sont intrinsèquement insolubles: le temps nécessaire pour les résoudre augmente de façon exponentielle en fonction de l'ampleur du problème. En cas de problèmes suffisamment importants, il peut falloir des années pour trouver la solution optimale avec OR-Tools (ou tout autre logiciel de routage). Par conséquent, OR-Tools renvoie parfois des solutions qui sont bonnes, mais pas optimales. Pour trouver une meilleure solution, modifiez les options de recherche du résolveur. Pour obtenir un exemple, consultez la section Modifier la stratégie de recherche.