Abstract

extabstractThe use of electric buses is expected to rise due to its environmental benefits. However, electric vehicles are less exible than conventional diesel buses due to their limited driving range and longer recharging times. Therefore, scheduling electric vehicles adds further operational dificulties. Additionally, various labor regulations challenge public transport companies to find a cost-effcient crew schedule. Vehicle and crew scheduling problems essentially define the cost of operations. In practice, these two problems are often solved sequentially. In this paper, we introduce the integrated electric vehicle and crew scheduling problem (E-VCSP). Given a set of timetabled trips and recharging stations, the E-VCSP is concerned with finding vehicle and crew schedules that cover the timetabled trips and satisfy operational constraints, such as limited driving range of electric vehicles and labor regulations for the crew while minimizing total operational cost. An adaptive large neighborhood search that utilizes branch-and-price heuristics is proposed to tackle the E-VCSP. The proposed method is tested on real-life instances from public transport companies in Denmark and Sweden that contain up to 1,109 timetabled trips. The heuristic approach provides evidence of improving efficiency of transport systems when the electric vehicle and crew scheduling aspects are considered simultaneously. By comparing to the traditional sequential approach, the heuristic finds improvements in the range of 1.17-4.37% on average. A sensitivity analysis of the electric bus technology is carried out to indicate its implications for the crew schedule and the total operational cost. The analysis shows that the operational cost decreases with increasing driving range (120 to 250 kilometers) of electric vehicles.

Abstract

International audience; Air traffic generates workload for the air traffic controllers in charge of the airspace. For a large airspace, a single air traffic controller is not able to manage all this workload and the airspace is divided into sectors, each of them being assigned to a controller. When the traffic demand is decreasing during the night, the sectors are gathered together into groups to reduce the number of controllers in operation. Nowadays, this regrouping is performed empirically by airspace experts. In this paper, we show how the branch-and-price method can be used to compute a balanced grouping of air traffic control sectors to optimally reduce the number of controller teams during daily low flow periods.

Abstract

Segment Routing (SR) is a powerful tool to solve traffic engineering in large networks. It enables steering the traffic along any arbitrary network path while limiting scalability issues as routers do not need to maintain a global state. Mathematical programming approaches proposed so far for SR either do not scale well with the size of topology or impose a strong limit on the number of possible detours (typically at most one). Moreover they do not support Segment Routing fully by ignoring the adjacency segments. This paper leverages column generation, a widely used technique for solving large scale linear programs, combined with a novel dynamic program for solving the pricing problem. Our approach reaches near optimal solutions with gap guarantees by also computing a strong lower-bound tighter than the multi-commodity flow relaxation. It scales even on large topologies and exploits the full expressiveness of SR including adjacency segments. Our experiments compared with existing traffic engineering techniques on various topologies and demand matrices demonstrate the advantages of our approach in terms of scalability, any-time behavior and quality of the solutions.

Abstract

This thesis aims at modelling and solving optimization problems related to the management of one-way-electric-car-sharing systems, where users can take a car from a station, use it, and then return it to another station. This generally leads to an imbalanced distribution of cars, with some full stations and other empty ones. A solution to this problem, implemented by car-sharing operators, is to employ staff agents to move cars as needed. However, identifying this need is a non-trivial optimization problem, especially since the system may be more constrained when the vehicles used are electric, which generates battery recharging and autonomy constraints. The global optimization problem addressed is then divided into two sub-problems. The first one is assigning the cars to customers, as well as their routing; it is denoted by ROCSP (Recharging OneWay Car Sharing Problem). The second problem involves agents planning and routing; it is denoted by ESRP (Employee Scheduling Routing Problem). 1. For the ROCSP, we propose two Mixed-integer linear programming (MILP) modelizations of the problem: One based on flows and the other based on paths. This means that the two models include the battery-recharging constraints in two different ways. As the exact resolution through the MILP models is quite expensive in terms of computational time and is not adapted for the resolution of real-size car-sharing instances, we introduce heuristics that enable the optimization of cars-redistribution and service management of the service within a reasonable amount of time. These heuristics allows the calculation of the number of cars and the various redistribution operations to be performed on a given day. 2. For the ESRP, this second problem is also addressed with MILP models for the exact resolution, and some heuristics are suggested for an approximate resolution. This process has reasonable calculation time and aims at finding the minimum number of agents to perform the necessary relocation operations that stem from the first problem, namely, the ROCSP. Once the ROCSP and ESRP solved in their static versions, we then focus on the ROCSP by exploring another variant of the problem : ROCSP with dynamic reservation. We also suggest to explore a new concept : Auto-CoPartage, which is a hybridization of car-sharing and carpooling. The stated algorithms are validated on the Auto Bleue electrical vehicles fleet in the network of the city of Nice, essentially by relying on flow generation models to estimate the demand, but also using other instances that we have generated for other cities. All the data are handled using a Geographical Information System.; Cette thèse a pour objectif de modéliser et résoudre des problèmes d’optimisation d’un système d’auto-partage avec des voitures électriques dit « à un seul sens », où les utilisateurs peuvent prendre une voiture dans une station et la laisser ensuite dans une autre. Ce fonctionnement conduit généralement à une situation de déséquilibre dans la répartition des voitures avec certaines stations pleines et d’autres vides. Une des solutions utilisées par les opérateurs d’autopartage pour pallier ce problème est le recours à des agents pour déplacer les voitures selon le besoin. Identifier et répondre à ce besoin est un problème d’optimisation non trivial, notamment à cause de l’usage de véhicules électriques, ce qui engendre des contraintes de rechargement de batteries et d’autonomie. Le problème d’optimisation est décomposé en deux sous-problèmes : le premier est le problème d’affectation des voitures aux clients, ainsi que leurs routages, que nous nommons ROCSP pour Recharging One way Car Sharing Problem ; le second problème est celui du planning des agents et leurs routages que nous nommons ESRP pour Employee Scheduling Routing Problem. 1. Résolution du ROCSP : deux modélisations en Programmation Linéaire en Nombres Entiers (PLNE) sont proposées, la première basée sur les flots et la deuxième sur les chemins, ce qui fait que les deux modèles intègrent de manière différente les contraintes de recharge électrique. Comme la résolution exacte à travers les modèles PLNE s’avère très gourmande en temps de calcul et non adaptée aux instances d’auto-partage de taille réelle, nous proposons des heuristiques qui permettent dans un temps raisonnable d’optimiser la redistribution des voitures et la gestion du service. Ces heuristiques permettent de calculer le nombre de voitures et les différentes opérations de relocalisation (redistribution des voitures) à réaliser sur une journée donnée. 2. Résolution du ESRP : un modèle PLNE est proposé pour la résolution exacte du ESRP, et, en complément, des heuristiques sont proposées pour une résolution approchée et relativement rapide. L’objectif est la détermination du nombre minimal d’agents nécessaire pour effectuer les opérations de relocalisation qui découlent du premier problème, le ROCSP. Dans une partie prospective, et une fois les ROCSP et ESRP résolus dans leur version statique, nous nous focaliserons sur une autre variante du problème avec réservation dynamique. Nous proposons également d’explorer un nouveau concept - l’auto-copartage - qui se veut une hybridation entre autopartage et covoiturage. Les algorithmes proposés ont été validés sur le réseau Auto Bleue de la ville de Nice essentiellement, qui gère une flotte de véhicules électriques, en s’appuyant sur des modèles de génération de flux pour estimer la demande, mais aussi d’autres instances que nous avons générées pour simuler d’autres villes, au sein d’un Système d’Information Géographique.