Sélection d'arcs et génération de colonnes pour le problème d'horaires d'autobus électriques

Dans un contexte de changement climatique, il est important de réduire l’émission de gaz à effet de serre. Dans ce but, il est intéressant d’avoir recours à des véhicules électriques, notamment pour les transports en commun. Pour avoir un réseau d’autobus efficace, il est nécessaire de planifier son fonctionnement. Cela peut se faire en résolvant des problèmes d’optimisation. Un de ces derniers est le problème d’horaires de véhicules électriques multidépôts qui est un des problèmes résolus par les solveurs d’optimisation de l’entreprise GIRO qui a financé ce travail. Le problème d’horaires de véhicules électriques a pour objectif de couvrir à moindre coût l’ensemble des trajets journaliers proposés aux usagers à l’aide d’une flotte d’autobus. Pour ce faire, on cherche à assigner à chaque autobus un horaire qui est composé d’une suite de trajets à effectuer en tenant compte des contraintes temporelles et de capacité des batteries électriques des véhicules. Du fait des nouvelles contraintes à prendre en compte pour les véhicules électriques, on ne peut pas utiliser directement les méthodes de résolution du problème classique d’horaires de véhicules. De plus, dans le but d’être au plus proche de la réalité, on choisit de modéliser le processus de recharge des véhicules avec une fonction non-linéaire définie par morceaux. On formule le problème d’horaires de véhicules électriques multi-dépôts comme un programme linéaire en nombres entiers. Une méthode efficace pour le résoudre est d’utiliser la génération de colonnes. Dans l’algorithme de génération de colonnes, on résout à chaque itération des sous-problèmes pour déterminer des nouveaux horaires d’autobus. Un tel sous-problème correspond à un problème de plus court chemin avec contraintes de ressources défini sur un graphe combinant un réseau de connexions et un réseau espace-temps. On associe un coût à chaque arc ainsi qu’une dépense d’énergie.

Abstract

With global warming on the rise, it is important to reduce greenhouse gas emissions. With this in mind, it makes sense to use electric vehicles, particularly for public transport. To have an efficient bus network, it is necessary to plan its operations. This can be done using optimisation problems. One of these is the multi-depot electric vehicle scheduling problem, which is one of the problems solved by the optimisation solvers of the company GIRO which funded this work. The aim of the electric vehicle scheduling problem is to cover all the daily trips offered to users at the lowest cost using a fleet of buses. To do this, we try to assign each bus a schedule which is a series of trips to make, taking into account the time constraints and the capacity of the vehicles’ electric batteries. Because of the new constraints to be taken into account for electric vehicles, we cannot directly use the methods for solving the classic vehicle scheduling problem. In order to be as close as possible to reality, we have chosen to model the vehicle recharging process using a piecewise non-linear function. We formulate the multi-depot electric vehicle scheduling problem as a linear integer program. An efficient way of solving it is to use column generation. In the column generation algorithm, subproblems are solved at each iteration to determine new bus schedules. Such a subproblem corresponds to a shortest path problem with resource constraints defined on a graph combining a network of connections and a space-time network. Each arc is assigned a cost and an energy consumption. The aim of this research work is to reduce the graph modelling the multi-depot electric vehicle scheduling problem in order to speed up its computation. This can be done at the expense of a loss of optimality of the solution. To this end, two arc selection methods are developed. They are based on the greedy randomized adaptive search procedure (GRASP) and beam search metaheuristics as well as a greedy algorithm but do not use learning unlike the method proposed in the literature by Gerbaux [1]. The proposed methods construct leastcost schedules for the different buses and the arcs contained in their selection are categorised as arcs with a good potential to belong to the optimal solution. This makes it possible to drastically reduce the size of the network given as input to column generation.