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

Thèse de Tekwa TEDJINI

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

Date de début : 1er octobre 2018
Financement : Contrat doctoral
Mots clés : Optimisation, Tournées de véhicules avec fenêtres de temps (VRPTW), Incertitudes, Théorie des fonctions de croyance
Encadrement :

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)
  • tournée de véhicules avec fenêtres de temps (VRPTW)

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 [2], théorie des possibilités [3, 4] et théorie des fonctions de croyance [5, 6].

Des premiers travaux ont été réalisés sur le CVRP [7, 8] 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 ces 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] P .Walley, “Statistical reasoning with imprecise probabilities”, Chapman & Hall, 1991.

[3] L.A. Zadeh, “Fuzzy sets as a basis for a theory of possibility”, Fuzzy Sets and Systems, Vol. 1, pages 3–28, 1978.

[4] D. Dubois et H. Prade, “Théorie des possibilités : applications à la représentation des connaissances en informatique”, Masson, 1985.

[5] 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.

[6] G. Shafer. “A mathematical theory of evidence. Princeton University Press, 1976.

[7] 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.

[8] 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.

Thèmes scientifiques impliqués :

Domaines d'application impliqués :

Aucun partenaire n'est associé à ces travaux.

Soutenance

Soutenance ayant eu lieu le

Jury :