Date : Dec. 2, 2019, 2 p.m. - BREVET David - Salle du conseil
Exploring Combinatorial Aspects of the Stop Number Problem
The Stop Number Problem arises in the management of a dial-a-ride system with small autonomous electric vehicles. In such a system, a fleet of identical capacitated vehicles travels along a predefined circuit with fixed stations in order to serve clients requesting for a ride from an origin station to a destination station. The Stop Number Problem consists of assigning each client request to a vehicle such that no vehicle gets overloaded. The goal is to minimize the number of times the fleet of vehicles stops for picking up or delivering clients. When every client requests for exactly one seat in a vehicle, Stop Number Problem is called Unit Stop Number Problem. In this thesis, Unit Stop Number Problem is addressed as a combinatorial optimization problem.
First, we investigate the complexity of such problem. On the one hand, we study some properties of optimal solutions and derive a series of particular cases that are shown to be solvable in polynomial time. On the other hand, we show that Unit Stop Number Problem is NP-hard even when restricted to case where each vehicle can take at most two clients at once and the graph induced by the client requests is planar bipartite. In a second part, we consider an integer-programming formulation known in the literature for solving the Unit Stop Number Problem. A preliminary analysis is conducted in order to show the weakness of such formulation. Afterwards, such formulation is reinforced through a polyhedral approach. We provide a facial study of the polytope associated with the solutions of this problem. New valid inequalities are introduced and necessary and sufficient conditions for which they are facet-defining are given. Finally, based on the discussed polyhedral results, we derive a new efficient branch-and-cut algorithm. Performance boosting features such as symmetry-breaking methods and variable elimination/relaxation are also investigated and implemented into the developed framework. Results convincingly demonstrate the strength of the reinforcing valid inequalities and therefore of our branch-and-cut algorithm.
- M. Ali Ridha Mahjoub (PR, LAMSADE Paris Dauphine, Paris) - Rapporteur ;
- M. Walid Ben-Ameur (PR, TELECOM Paris-Sud, Paris) - Rapporteur ;
- Mme. Hande Yaman (PR, KU Leuven, Leuven - Belgique) - Examinatrice ;
- M. Gautier Stauffer (PR, K-Edge Business School, Bordeaux) - Examinateur ;
- Mme. Aurélie Lagoutte (MCF, LIMOS, Clermont-Ferrand) - Examinatrice ;
- M. Mourad Baïou (DR CNRS, LIMOS, Clermont-Ferrand) - Directeur de thèse ;
- M. Hervé Kerivin (MCF, LIMOS, Clermont-Ferrand) - Co-directeur de thèse.