Problème de tournées de véhicules

vignette|Figure illustrant une des solutions d'un problème de tournées avec un dépôt central et 3 véhicules disponibles. Le problème de tournées de véhicules (aussi appelé VRP pour Vehicle Routing Problem) est une classe de problèmes de recherche opérationnelle et d'optimisation combinatoire. Il s'agit de déterminer les tournées d'une flotte de véhicules afin de livrer une liste de clients, ou de réaliser des tournées d'interventions (maintenance, réparation, contrôles) ou de visites (visites médicales, commerciales). Le but est de minimiser le coût de livraison des biens. Ce problème est une extension classique du problème du voyageur de commerce, et fait partie de la classe des problèmes NP-complet. Variantes Quelques variantes classiques du problème de tournées de véhicules :

tournées de véhicules avec profits (aussi appelé VRPP pour Vehicle Routing Problem with Profits) : Un problème de maximisation de collecte de profits où il faut sélectionner quels clients visiter

Problèmes de cheminements optimaux dans les réseaux avec contraintes associées aux arcs

In this thesis we consider two optimal routing problems in networks. Both are NP-hard and are often used to modelize real life problems of large size. We first present the capacitated arc routing problem (CARP). In this problem, we have to serve a set of customers represented by the arcs of a network with vehicles of restricted capacity. The aim is to design a set of vehicle routes of least total cost. We describe two heuristic methods for the CARP based on local search techniques. The first one is a Tabu Search heuristic using an original post-optimization procedure. Principles appearing in this procedure are used to define a class of neighborhoods we combine in a Variable Neighborhood Descent method. Our algorithms compare favorably with some of her methods. They were initially developed to deal with the undirected CARP. We describe how to transform them so that they can be applied to the directed CARP. We also propose an adaptation to the directed case of a lower bound originally developed for the undirected CARP. This lower bound is used to evaluate the quality of the solutions produced by our algorithms for the directed CARP. Our methods obtain solutions whose value is, on average, close to known lower bounds. We use the CARP to tackle a real life problem of boat routing and scheduling. This problem can be viewed as a directed CARP with time windows. We describe in detail its modeling process and we analyze our first results. We obtain solutions that require less boats than the present schedule. Nevertheless, these solutions are not completely feasible in practice. We suggest some ways to improve them. The second problem treated in this thesis is the shortest capacitated paths problem (SCPP). We present a Tabu Search heuristic and some post-optimization procedures for the SCPP. These procedures are called in our Tabu Search algorithm. Two versions of this algorithm are considered. In the first one, post-optimization procedures are intensively used. In the second one, they are less frequently applied. This second version is faster. Compared with a greedy approach, the two versions of our Tabu Search heuristic obtain solutions which are, on average, of better quality. The SCPP was proposed to us by EDF (Electricité de France) in order to minimize the total length of the paths followed by cables in a nuclear power-station. It can also be viewed as a subproblem of the bandwidth packing problem (BWP) appearing in telecommunications.

EPFL2000

Integrating a heterogeneous fixed fleet and a flexible assignment of destination depots in the waste collection VRP with intermediate facilities

Michel Bierlaire, Iliya Dimitrov Markov, Sacha Varone

We consider a complex recyclable waste collection problem that extends the class of vehicle routing problems with intermediate facilities by integrating a heterogeneous fixed fleet and a flexible assignment of destination depots. Several additional side constraints, such as a mandated break period contingent on tour start time, multiple vehicle capacities, and site dependencies are also included. This specific problem was inspired by a real-world application and does not appear in the literature. It is modeled as an MILP which is enhanced with several valid inequalities. Due to the rich nature of the problem, state-of-the-art solvers are only able to tackle instances of small to medium size. To solve realistic instances, we propose a multiple neighborhood search heuristic capable of systematically treating all problem features and general enough to respond to the varying characteristics of the case study regions for which it is intended. The results show that the heuristic achieves optimality on small instances, exhibits competitive performance in comparison to state-of-the-art solution methods for special cases of our problem, and leads to important savings in the state of practice. Moreover, it highlights and quantifies the savings from allowing a flexible depot assignment. The data from the state of practice comes from a company in the waste collection industry in Geneva, Switzerland. (C) 2015 Elsevier Ltd. All rights reserved.

Pergamon-Elsevier Science Ltd2016

The waste collection VRP with intermediate facilities, a heterogeneous fixed fleet and a flexible assignment of origin and destination depot

Michel Bierlaire, Iliya Dimitrov Markov, Sacha Varone

We consider a complex recyclable waste collection problem that extends the class of vehicle routing problems with intermediate facilities by integrating a heterogeneous fixed fleet and a flexible assignment of origin and destination depot. Several additional side constraints, such as a mandated break period contingent on tour start time, multiple vehicle capacities and site dependencies are also included. This specific problem was inspired by a real-world application and does not appear in the literature. It is modeled as an MILP which is enhanced with several valid inequalities. Due to the rich nature of the problem, state-of-the-art commercial solvers are only able to tackle instances of small to medium size. To solve realistic instances, we propose a local search heuristic capable of systematically treating all problem features and general enough to respond to the varying characteristics of the case study regions for which it is intended. The results show that the heuristic achieves optimality on small random instances, exhibits competitive performance in comparison to state-of-the-art solution methods for special cases of our problem, and leads to important savings in the state of practice. Moreover, it highlights and quantifies the savings from allowing a flexible assignment of origin and destination depot. The data from the state of practice comes from a recyclable waste collection company in Geneva, Switzerland.

2015

Problèmes de cheminements optimaux dans les réseaux avec contraintes associées aux arcs

EPFL2000