Optimisation d'itinéraires

Le problème intégrant les contraintes listées ci-après est innovant et n’a, à notre connaissance, jamais été étudié en l’état. Le développement de nouveaux algorithmes pour résoudre efficacement ce problème combinatoire est donc un challenge scientifique.

Description du problème

Les hypothèses sur les données disponibles pour la planification d’un parcours touristique optimisé sont les suivantes :

• Données sur les sites touristiques :

o L’ensemble des sites pouvant être visités est connu à l’avance. Un site peut être aussi bien un château, un musée, un restaurant qu’un quartier touristique.

o La durée de visite. Elle dépend de divers critères tels que la météo (un temps pluvieux limitera fortement les visites extérieures par exemple) et le profil utilisateur.

o La localisation géographique.

o Le coût d’entrée.

o Les horaires d’ouvertures. Une ou plusieurs fenêtres de temps sont associées à chaque site pour représenter ses horaires d’ouverture.

o La catégorie touristique. Les sites sont classés dans une ou plusieurs catégories. Par exemple, le château de Chenonceau sera classé dans les catégories « Jardin » et « Château ».

o Un score. Cette donnée représente le score d’intérêt du touriste pour ce site touristique. Il est spécifique à chaque touriste et est déterminé à partir du profil touristique et des données connues sur le site.

• Contraintes spécifiques aux sites :

o Exclusion de sites. Par exemple : A ou B signifie que le parcours ne peut pas contenir le site A et B. Ce type de contrainte permet d’éviter les visites trop redondantes (deux caves trop similaires par exemple) ou des visites uniques dans une catégorie imposée par l’utilisateur (cas des restaurants).

o La précédence entre sites. Par exemple A avant B indique que si l’utilisateur souhaite visiter les sites A et B, il doit commencer par le site A puis B dans son itinéraire. Ce type de contrainte permet de modéliser des relations d’ordre importantes entre visites de sites d’un même thème mais plus généralement d’ordre de visite pour rendre le parcours plus agréable (exemple : le site ``saut en parachute’’ avant le site ``cave avec dégustation à volonté’’).

o L’implication entre sites : Par exemple si A alors B signifie que si l’utilisateur visite A alors il faut prévoir B plus tard dans son parcours. Ce type de contrainte rend possible le groupement de site à faire ensemble soit pour des raisons de proximité ou pour des raisons de thèmes ou nature des visites.

Cet ensemble de contraintes de visites entre sites peut dépendre du profil utilisateur.

• Données et contraintes sur les touristes :

o Budget du touriste. Le parcours proposé doit respecter le budget maximum fixé par le touriste.

o Points de départ et d’arrivée. Le lieu d’où part le touriste et le lieu où il souhaite terminer son itinéraire (généralement les hôtels dans lesquels le touriste réside). Les points de départ et d’arrivée peuvent être confondus et sont pris en compte dans la génération de l’itinéraire.

o Temps de visite et de trajet maximal. Le parcours doit assurer un temps de visites touristiques total inférieur à celui spécifié par le touriste.

o Heure de début au plus tôt et de fin au plus tard. Le parcours touristique doit respecter les heures de début et de fin.

o Catégories. Le touriste peut spécifier pour chaque catégorie touristique combien de sites au minimum et au maximum il souhaite visiter (par exemple au maximum 2 châteaux et au moins un jardin).

Le problème consiste alors à calculer un parcours touristique respectant l’ensemble des contraintes données et en cherchant à maximiser le score total des sites visités.

Formalisation et résolution du problème

Le problème est très complexe et fortement combinatoire (il existe un nombre très élevé de parcours possibles). Il demande l’utilisation de méthodes de résolutions innovantes pour obtenir les meilleures solutions. Tout d’abord, nous avons proposé une modélisation mathématique du problème qui a servi comme base de comparaison pour de futurs algorithmes de type exact (c.-à-d. retournant toujours la solution optimale).

Nous avons appliqué un algorithme de résolution classique de type « branch-and-bound » (procédure par séparation et évaluation) et avons évalué les performances de l’algorithme sur différentes instances du problème. Les résultats obtenus ont permis de valider le modèle mathématique proposé mais ont montré les limites de l’approche pour résoudre des instances complexes.

Nous avons donc proposé une approche alternative pour améliorer la résolution du problème. Cette approche est basée sur la méthode innovante du branch-and-check. Elle tire parti de la structure du problème afin de le diviser en deux sous problèmes (le maître et l’esclave) chacun moins complexe à résoudre que le problème dans son intégralité. La résolution du problème maître permet d’explorer les solutions (itinéraires touristiques) qui satisfont l’intégralité des contraintes à l’exception des contraintes temporelles (c.-à-d. vérifiant si l’enchaînement des visites est réalisable) afin de trouver la solution optimale. Lors de l’exploration des solutions intéressantes, on vérifie pour chacune d’entre elle la satisfiabilité du problème esclave : l’enchainement des sites sélectionnés par la solution du problème maitre est-il réalisable ou non. Différentes améliorations de cette approche ont été proposées, développées et testées. Elles sont détaillées dans les communications listées ci-après.

Les résultats obtenus avec le branch-and-check ont été comparés avec ceux obtenus par l’approche du branch-and-bound. La Figure 4 résume les résultats obtenus par les différentes approches sur différents jeux de données. L’approche CPLEX correspond à notre première approche, les approches E-B&C et E-B&S sont deux versions de l’approche branch-and-check. Le temps maximum de résolution alloué est de 5h pour toutes les approches. Nous pouvons constater que dans presque tous les cas le branch-and-check fonctionne mieux que l’approche de base.


Il est toutefois nécessaire de tempérer les résultats obtenus. En effet, aucune des approches proposées n’a permis de résoudre de manière optimale l’intégralité des instances et le temps de résolution est bien trop important pour permettre une application opérationnelle. Cependant, les approches proposées ont le mérite de trouver de très bonnes solutions, proches de l’optimal.

Communications & Publications

Les travaux réalisés ont été valorisés dans plusieurs communications et publications. Pour un détail de l’intégralité des travaux réalisés, nous conseillons de consulter l’article publié en revue.

Vu, D. M., Kergosien, Y., Mendoza, J. E., & Desport, P. (2019, June). A Branch-and-Check Approach for the Tourist Trip Design Problem with Rich Constraints. In Workshop of the EURO Working Group on Vehicle Routing and Logistics optimization.
Vu, D. M., Kergosien, Y., Mendoza, J. E., & Desport, P. (2020) A Branch-and-Check Approach for the Tourist Trip Design Problem with Rich Constraints. PREPRINT HAL – Submitted to Computer and Operation Research
Vu, D. M., Kergosien, Y., Mendoza, J. E., & Desport, P. (2019, February). A Branch-And-Check Solution Method for a Tourist Trip Design Problem with Rich Constraints. In 20ème conférence de la Société française de recherche opérationnelle et aide à la décision-ROADEF'19.

Perspectives

Ces premiers travaux de recherche ont ouvert de nouvelles perspectives très intéressantes :

• Proposer et développer de nouvelles approches de résolution très rapides. Nous avons présenté des approches de résolution exacte qui sont des approches intéressantes mais qui sont limitées par la taille des instances et par le temps de résolution et ne peuvent pas être utilisées opérationnellement. Il serait intéressant de proposer des méthodes alternatives de résolution qui permettent la génération de solutions de qualité en un temps très limité. Nous pensons notamment à l’utilisation de métaheuristiques telles que les approches à base de population ou de recherche locale.

• Travailler sur des extensions pour accroitre la généricité du problème :

o Gestion des aléas. Lors de la réalisation d’un parcours touristique il est possible que des aléas surviennent (e.g., Bouchons, retard de visite, …). Dans ce cas, il est nécessaire de modifier le parcours prévu initialement. Il serait intéressant de proposer une approche permettant la prise en compte des aléas et la modification à la volée d’un parcours touristique pour perturber le moins possible l’itinéraire prévu et limiter le désagrément du touriste.

o Multi-modalité. Actuellement, nous considérons que les touristes se déplacent entre les sites en voiture. Avec le développement du slow-tourisme et des mobilités douces, il serait pertinent de pouvoir intégrer dans la planification d’un parcours l’utilisation de plusieurs moyens de transport. Par exemple, l’utilisateur se rend sur un site en voiture, il récupère un vélo, va visiter un site en vélo puis revient récupérer sa voiture. L’intégration dans le problème de la multi-modalité rend le problème plus complexe puisqu’il augmente la variété de temps de trajet et demande de prendre en compte des points d’échange de véhicules.

o Multi-objectifs. Dans la version actuelle du problème, l’objectif est de maximiser le score total des sites touristiques visités. D’autres objectifs pourraient être ajoutés tels que la minimisation du budget ou la minimisation des émissions de CO2. Il s’agit alors de considérer plusieurs objectifs à la fois et d’appliquer des approches de l’optimisation multi-objective.