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

Ph.D. thesis of Tuan Anh VU

Models and solving methods for the vehicle routing problem with evidential uncertainty

Starting date: 1 October 2021
Keywords: Optimization, Vehicle Routing Problem, Uncertainty, Belief function theory
Advising:

The Vehicle Routing Problem (VRP) [1] consists in determining a set of tours for a fleet of vehicles, which must respect various constraints and be of least cost. This combinatorial optimization problem is particularly important due to its large set of applications.

In practice, the VRP often involves dealing with parameters that are known with some uncertainty. This uncertainty may concern for instance the customer demands or the travel times. Classically, probability theory has been used to take into account the uncertainty [2]. This is known as stochastic optimization.

In recent decades, alternative theories to probability theory have emerged to represent and more finely manage the different origins (randomness and lack of knowledge) of uncertainty. Among these, the Belief Function Theory (BFT) [3] enjoys a certain maturity, with various applications [4].

In previous work [5, 6], we have shown the relevance and feasibility of an evidential treatment, that is to say based on the BFT, of ​​uncertainties in the VRP. The proposed models were obtained by extending the main approaches (so-called chance constraints and recourse) developed in stochastic optimization. In addition, we have implemented approximate solving methods allowing us to find good quality solutions in a reasonable time to the complex optimization problems obtained.

Within the framework of this PhD project, we propose to pursue this work in three main directions. At the modelling level, refined approaches, taking more advantage of the expressiveness of the framework of belief functions, should be explored. This includes exploiting more cautious decision criteria, such as those analyzed in [7], in order to compare and order, potentially only partially, the solutions. The study of the proposed models is also to be deepened. In particular, it is necessary to determine the uncertain variables on which it would be interesting to act (for example to reduce the uncertainty or the value, in the sense of relations between belief functions [8]) in order to improve the solutions. Finally, at the solving level, the belief function approximation methods used [9], which reduce the complexity, need to be refined in order to obtain better quality solutions. The adaptation of exact solving methods [10] is also envisaged.

References:

  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.

Involved research themes:

Involved application areas:

No partner is associated with this element.

Defense

Defense took place the

Jury: