Laboratoire de Génie Informatique et d’Automatique de l’Artois

Tuan Anh VU

Doctorant
Travaille dans les thèmes :
Contact :
Aucune publication ne correspond aux critères fournis.

Sujet de thèse : "Modèles et méthodes de résolution pour le problème de tournées de véhicules sous incertitude crédibiliste"

2021

Le problème de tournées de véhicules (VRP, pour Vehicle Routing Problem) [1] consiste à déterminer un ensemble de tournées pour une flotte de véhicules, devant respecter diverses contraintes et de moindre coût. Ce problème d’optimisation combinatoire est particulièrement important de par son large éventail d’applications.

En pratique, le VRP implique bien souvent de travailler avec des paramètres connus de manière incertaine. L’incertitude peut concerner par exemple les demandes des clients ou encore les temps de trajet. Classiquement, la théorie des probabilités a été utilisée pour prendre en compte l’incertitude [2]. On parle alors d’optimisation stochastique.

Ces dernières décennies, des théories alternatives à la théorie des probabilités ont vu le jour pour représenter et gérer plus finement les différentes origines (aléatoire et épistémique) de l’incertitude. Parmi celles-ci, la théorie des fonctions de croyance (TFC) [3] bénéficie d’une certaine maturité, avec des applications variées [4].

Lors de précédents travaux [5, 6], nous avons montré la pertinence et la faisabilité d’un traitement crédibiliste, c’est-à-dire fondé sur la TFC, des incertitudes dans le VRP. Les modèles proposés ont été obtenus en étendant les approches principales (dites par contraintes de chance et par recours) développées en optimisation stochastique. De plus, nous avons mis en place des méthodes de résolution approchées permettant de trouver dans un temps raisonnable des solutions de bonne qualité aux problèmes d’optimisation complexes obtenus.

Dans le cadre de cette thèse, nous nous proposons de poursuivre ces travaux dans trois directions principales. Au niveau de la modélisation, des approches plus fines, tirant davantage parti de l’expressivité du cadre des fonctions de croyance, sont à explorer. Il s’agit notamment d’exploiter des critères de décision plus prudents, tels que ceux analysés dans [7], afin de comparer et d’ordonner, potentiellement seulement partiellement, les solutions. L’étude des modèles proposés est également à approfondir. Il faut en particulier déterminer les variables incertaines sur lesquelles il serait intéressant d’agir (par exemple diminuer l’incertitude ou la valeur, au sens de relations entre fonctions de croyance [8]) afin d’améliorer les solutions. Enfin, au niveau de la résolution, les méthodes d’approximation de fonctions de croyance utilisées [9], qui permettent de réduire la complexité, sont à affiner afin d’obtenir des solutions de meilleure qualité. L’adaptation de méthodes de résolution exactes [10] est également envisagée.

Références :

  1. G. B. Dantzig et J. H. Ramser, “The truck dispatching problem”, Management Science, Vol. 6, n°1, pages 80–91, 1959
  2. M. Gendreau, G. Laporte, and R. Séguin, “Stochastic vehicle routing” European Journal of Operations Research, 88:3-12, 1996.
  3. G. Shafer, “A mathematical theory of evidence”, Princeton University Press, 1976.
  4. T. Denoeux, “40 years of Dempster–Shafer theory”, International Journal of Approximate Reasoning, Vol. 79, pages 1-6, 2016.
  5. N. Helal, F. Pichon, D. Porumbel, D. Mercier et É. Lefèvre. “The capacitated vehicle routing problem with evidential demands”, International Journal of Approximate Reasoning, Vol. 95, pages 124-151, 2018.
  6. T. Tedjini, S. Afifi, F. Pichon et E. Lefèvre, “A belief-constrained programming model for the VRPTW with evidential service and travel times”, Actes des 28e rencontres Francophones sur la Logique Floue et ses Applications, pages 217–224, Novembre 2019.
  7. M. Troffaes, “Decision making under uncertainty using imprecise probabilities”, International Journal of Approximate Reasoning, Vol. 45, pages 17–29, 2007.
  8. S. Destercke, F. Pichon et J. Klein, “From set relations to belief function relations”, International Journal of Approximate Reasoning, Vol. 110, pages 46–63, 2019.
  9. T. Tedjini, S. Afifi, F. Pichon et E. Lefèvre, “Vers une généralisation de l’approximation des fonctions de croyance”, Actes des 29e rencontres Francophones sur la Logique Floue et ses Applications, Octobre 2020.
  10. F. Errico, G. Desaulniers, M. Gendreau, W. Rei, L.-M. Rousseau, "The vehicle routing problem with hard time windows and stochastic service times", EURO J. Transp. Logist. Vol. 7, Issue 3, pages 223-251, 2018.