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

Poste (Doctorant) Poste pourvu

Tournée de véhicules avec fenêtre de temps et temps de parcours incertains : une réponse fondée sur les fonctions de croyance.

CDD (3 ans) Début : 01/10/2018

Dans cette thèse, nous poursuivrons nos travaux sur l’emploi de la théorie des fonctions de croyance dans le cadre du problème de tournée de véhicules avec fenêtre de temps. Nous formulerons une variante à ce problème classique dans lequel les temps de trajet entre les clients seront connus sous forme de fonctions de croyance.

Mots clés : Optimisation, Tournées de véhicules avec fenêtres de temps (VRPTW), Incertitudes, Théorie des fonctions de croyance

Description

Financement prévu : Contrat doctoral Université d’Artois

Sujet :
Les activités de transport jouent un rôle crucial tant dans le domaine de la production que dans celui des services. Elles permettent d’assurer la distribution de biens et de services entre fournisseurs, unités de production, entrepôts, distributeurs, et clients finaux. Améliorer l’efficacité des activités de transport est une étape critique pour augmenter la compétitivité et réduire l’impact environnemental des organisations.
Le problème de tournées de véhicules (VRP) [1] consiste alors à déterminer, en minimisant le coût, un ensemble de tournées pour un nombre limité de véhicules, commençant et finissant à un dépôt, de telle façon que chaque client soit visité exactement une fois par un véhicule. Ce problème a ensuite été décliné sous différentes formes par exemple :
• tournée de véhicules avec contraintes de capacité (CVRP) : les véhicules desservant (ou ramassant) les marchandises chez les clients ont une capacité limité.
• tournée de véhicules avec fenêtres de temps (VRPTW) : chaque client dispose d’une fenêtre de temps à l’intérieur de laquelle il désire être servi [2, 3, 4].
En pratique, le VRP implique bien souvent de travailler avec des paramètres connus de manière non exacte (imprécise et/ou incertaine). L’incertitude peut concerner les demandes des clients, leur présence ou le temps de déplacement et de service. Par exemple, une entreprise devant résoudre un problème de CVRP pour ses opérations de logistique, ne connait pas toujours à l’avance les demandes de ses clients.
Classiquement, la théorie des probabilités a été utilisée pour prendre en compte l’incertitude. On parle alors d’optimisation stochastique. Plus récemment, d’autres théories ont vu le jour pour gérer les données imparfaites : théories des probabilités imprécises [5], théorie des possibilités [6, 7] et théorie des fonctions de croyance [8, 9].
Dans le cadre de cette dernière théorie, nous avons étendu le problème de CVRP lorsque les demandes des clients sont connues sous la forme de fonction de croyance [10, 11]. Nous avons ainsi proposé deux modèles pour ce problème. Le premier est une extension de l’approche chance-constrained Programming, qui impose des bornes minimales pour la croyance et la plausibilité que la somme des demandes sur chaque route respecte la capacité des véhicules. Le deuxième modèle étend l’approche stochastic programming with recourse. Dans ce cas, l’incertitude sur les recours (actions correctives) possibles sur chaque route est représentée par une fonction de croyance et le coût d’une route est alors son coût classique (sans recours) additionné du pire coût espéré des recours.
Ces premiers travaux ont été réalisés en considérant que les incertitudes interviennent au niveau des contraintes. Toutefois, les incertitudes peuvent se trouver sur le calcul de la fonction objective. C’est le cas par exemple si les temps de déplacement ou de service sont incertains.
Ainsi dans le cadre de cette thèse, nous nous proposons de poursuivre nos travaux sur l’emploi de la théorie des fonctions de croyance, dans un premier temps, dans le cadre du problème de tournée de véhicules avec fenêtre de temps. Nous formulerons une variante à ce problème classique dans lequel les temps de trajet entre les clients seront connus sous forme de fonctions de croyance. Ceci implique la prise en compte de l’incertitude au niveau de la fonction objective mais également au niveau des contraintes afin de respecter les fenêtres de temps données par les clients.
Par ailleurs, dans nos travaux précédents, nous avions utilisé une méthode de type métaheuristique, appelé recuit simulé, afin de résoudre le problème de CVRP défini. Dans cette thèse, l’utilisation d’autres méthodes de résolution, comme par exemple les algorithmes évolutionnaires, sera étudié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.M. Solomon. “Algorithms for the Vehicle Routing and Scheduling Problems with Time Window Constraints”, Operations Research 35, pages 254-265, 1987.
[3] J.F. Cordeau, G. Desaulniers, J. Desrosiers, M.M. Solomon et F. Soumis, “The VRP with Time Windows”, SIAM Monographs on Discrete Mathematics and Applications, 9, P. Toth et D. Vigo (eds.), SIAM, Philadelphia, PA, pages 157-193, 2002.
[4] O. Bräysy et M. Gendreau, ”Vehicle routing problem with time windows, Part I : Route construction and local search algorithms”, Transportation Science, Vol. 39, n°1, pages 104-118, 2005.
[5] P .Walley, “Statistical reasoning with imprecise probabilities”, Chapman & Hall, 1991.
[6] L.A. Zadeh, “Fuzzy sets as a basis for a theory of possibility”, Fuzzy Sets and Systems, Vol. 1, pages 3–28, 1978.
[7] D. Dubois et H. Prade, “Théorie des possibilités : applications à la représentation des connaissances en informatique”, Masson, 1985.
[8] A. P. Dempster. “Upper and lower probabilities induced by a multivalued mapping”, The annals of mathematical statistics, Vol. 38, n° 2, pages 325–339, 1967.
[9] G. Shafer. “A mathematical theory of evidence. Princeton University Press, 1976.
[10] N. Helal, “An evidential answer for the capacitated vehicle routing problem with uncertain
demands”, Thèse de doctorat de l’Université d’Artois, Décembre 2017.
[11] 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.

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 intelligence artificielle seraient un plus.
Candidature :
Envoyer CV, lettre de motivation, relevés de notes et classements des deux dernières années d’études ainsi que des lettres de recommandation.

Contact : Eric LEFEVRE
+333 21.63.23.00
Contact : Frédéric PICHON
+333 21.63.71.89
Contact : Sohaib AFIFI