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 :