Explorant les aspects combinatoires du problème du nombre d'arrêts

Le Problème du Nombre d'Arrêts se présente dans la gestion d'un système de transport à la demande utilisant des véhicules électriques autonomes. Dans un tel système, une flotte de véhicules identiques parcourt un circuit prédéfini avec des stations fixes afin de desservir un ensemble de clients qui demandent un trajet entre une station d'origine et une station de destination. Notez que plusieurs clients peuvent partager les mêmes stations d'origine et/ou de destination. Le Problème du Nombre d'Arrêts consiste à affecter chaque demande à un véhicule de façon à ce qu'aucun véhicule ne soit surchargé. L'objectif est de minimiser le nombre d'arrêts effectués par la flotte de véhicules pour la collecte et la livraison des clients. Lorsque chaque client demande exactement une place dans un véhicule, le Problème du Nombre d'Arrêts est appelé Problème du Nombre d'Arrêts Unitaire. Dans cette thèse, le Problème du Nombre d'Arrêts Unitaire est traité comme un problème d'optimisation combinatoire.Tout d'abord, nous examinons la complexité du problème. D'une part, nous étudions certaines propriétés des solutions optimales et dérivons une série de cas particuliers dont la résolution peut être réalisée en temps polynomial. D'autre part, nous montrons que le Problème du Nombre d'Arrêts Unitaire est NP-Difficile même lorsqu'il est restreint au cas où chaque véhicule peut prendre au maximum deux clients à la fois et que le graphe induit par les demandes des clients est planaire bipartie. Ce résultat - qui répond positivement à une conjecture connue dans la littérature - est ensuite étendu à d'autres problèmes associés tels que le k-Edge Partitioning et le Traffic Grooming, améliorant ainsi leurs standards de complexité connus dans la littérature.Dans une deuxième partie, nous considérons une formulation de programmation linéaire en nombres entiers connue dans la littérature pour résoudre le Problème du Nombre d'Arrêts Unitaire. Une analyse préliminaire est effectuée afin de prouver la faiblesse de cette formulation. Par la suite, cette formulation est renforcée à l'aide d'une approche polyédrale. Nous fournissons une étude de faciale du polytope associée aux solutions de ce problème. De nouvelles inégalités valides sont introduites et les conditions nécessaires et suffisantes pour lesquelles elles définissent des facettes sont indiquées.Enfin, sur la base des résultats de l'approche polyédrale discutée, nous dérivons un nouvel algorithme de coupes et branchements efficace. Des fonctionnalités améliorant les performances de l’algorithme, telles que les méthodes de rupture de symétrie et l'élimination/relaxation des variables, sont également étudiées et mises en œuvre. Les résultats démontrent de manière convaincante la pertinence du renforcement des inégalités valides et donc de notre algorithme de coupes et branchements.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. Notice that multiple clients may share the same origin and/or destination stations. The Stop Number Problem consists of assigning each client request to avehicle 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. Such result -- which positively answers a conjecture known in the literature -- is then extended to other related problems such as the k-Edge Partitioning and the Traffic Grooming problem, improving their respective state-of-the-art complexity standards.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 prove 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