Vous êtes ici : Accueil » Kiosque » Annonce

Identification

Identifiant: 
Mot de passe : 

Mot de passe oublié ?
Détails d'identification oubliés ?

Annonce

27 mars 2021

Modèles et méthodes de résolution pour le problème de tournées de véhicules sous incertitude crédibiliste.


Catégorie : Doctorant


Titre

Modèles et méthodes de résolution pour le problème de tournées de véhicules sous incertitude crédibiliste.
 
Date de début
Octobre 2021
 
Mots clés
Optimisation, Tournées de véhicules, Incertitudes, Théorie des fonctions de croyance.
 
Financement attendu
Contrat doctoral de l’Université d'Artois
 
Encadrement
Directeurs de thèse : Eric Lefèvre (PR, eric.lefevre@univ-artois.fr) et Frédéric Pichon (PR, frederic.pichon@univ-artois.fr)
Co-encadrant : Sohaib Afifi (MCF, sohaib.lafifi@univ-artois.fr)
 
Sujet
 
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.
 
Environnement
Les travaux seront menés au sein du Laboratoire de Génie Informatique et d'Automatique de l'Artois (https://www.lgi2a.univ-artois.fr/spip/fr) situé à Béthune.
 
Profil recherché
Le candidat devra être titulaire d'un master ou d'un titre d'ingénieur en informatique, recherche opérationnelle ou optimisation. Des connaissances en représentation des incertitudes seront un atout.
 
Candidature
Envoyer CV, lettre de motivation, relevés de notes et classements des trois dernières années d'études ainsi que des lettres de recommandation à : eric.lefevre@univ-artois.fr, frederic.pichon@univ-artois.fr et sohaib.lafifi@univ-artois.fr.
 
 

Dans cette rubrique

(c) GdR 720 ISIS - CNRS - 2011-2020.