An exact approach for the multi-depot electric vehicle scheduling problem
Xenia Haslinger ([email protected]), Elisabeth Gaar ([email protected]), Sophie N. Parragh ([email protected]) · 2025
Read An exact approach for the multi-depot electric vehicle scheduling problem by Xenia Haslinger ([email protected]), Elisabeth Gaar ([email protected]), Sophie N. Parragh ([email protected]) (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2504-13063.txt.
Introduction
Xenia Haslinger, Elisabeth Gaar, and Sophie Parragh wrote this 2025 paper on scheduling electric buses across several depots. Cities are swapping diesel fleets for electric ones, pushed by clean vehicle rules in Europe. Regional lines add a wrinkle: their long routes strain battery range.
The authors model the scheduling problem with three goals ranked in order. First, use as few buses as possible. Second, keep charging stops low. Third, cut total energy use. Their graph model allows partial charging without tracking time directly, which keeps the math lean. They build two mixed-integer programming forms of the model, with three-index and two-index variables. The work aims to give bus operators hard numbers for planning a zero-emission fleet, depot by depot.
Catalog record
| CREATOR | Xenia Haslinger ([email protected]), Elisabeth Gaar ([email protected]), Sophie N. Parragh ([email protected]) |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 108 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2504-13063
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
An exact approach for the multi-depot electric vehicle scheduling problem Xenia Haslinger ([email protected]), Elisabeth Gaar ([email protected]), Sophie N. Parragh ([email protected]) Abstract The “avoid - shift - improve” framework and the European Clean Vehicles Directive set the path for improving the efficiency and ultimately decarbonizing the transport sector. While electric buses have already been adopted in several cities, regional bus lines may pose additional challenges due to the potentially longer distances they have to travel. In this work, we model and solve the electric bus scheduling problem, lexicographically minimizing the size of the bus fleet, the number of charging stops, and the total energy consumed, to provide decision support for bus operators planning to replace their diesel-powered fleet with zero emission vehicles. We propose a graph representation which allows partial charging without explicitly relying on time variables and derive 3-index and 2-index mixed-integer linear programming formulations for the multi-depot electric vehicle scheduling problem. While the 3-index model can be solved by an off-the-shelf solver directly, the 2-index model relies on an exponential number of constraints to ensure the correct depot pairing. These are separated in a cutting plane fashion. We propose a set of instances with up to 80 service trips to compare the two approaches, showing that, with a small number of depots, the compact 3-index model performs very well. However, as the number of depots increases, the developed branch-and-cut algorithm proves to be of value. The inclusion of realistic instances and technology-specific scenarios for diesel, battery-electric, and fuel cell-electric buses further strengthens the practical relevance of our results, offering concrete guidance for sustainable fleet planning. Keywords: electric bus scheduling, electric vehicle scheduling problem, branch-and-cut, multiple depots, partial charging, integer programming Declaration of competing interest The authors declare that they have no known competing financial interests or personal relationships that could have appeared to influence the work reported in this paper. 1 Introduction CO 2 -emissions from transport accounted for about 21% of the global CO 2 -emissions in 2023, increasing by almost 80% between 1990 and 2023 ( Statista, 2024a, ; Statista, 2024b, ) . Following the “avoid - shift - improve” framework to meet the Paris Climate Agreement, Austria’s 2030 Mobility Masterplan promotes active modes of transport, like walking and biking, public modes of transport, and shared mobility as well as decarbonizing the transportation sector in general ( BMK,, 2021 ) . The implementation of the European Clean Vehicles Directive ( EU,, 2019 ) requires all member states to meet at least half of their procurement targets for clean buses via zero emission buses. E.g., Austria’s target for heavy duty vehicles (including buses) is currently 45% and will rise to 65% with January 2026. The Austrian research project “Zero Emission Mobility Salzburg” (ZEMoS) is a collaborative effort of several public and private institutions and research organizations to support the transition from diesel-powered to zero emission public bus transport and waste collection vehicles. The main focus is the decarbonization of the regional public bus system ( ZEMoS,, 2023 ; Peters et al.,, 2024 ; Haslinger et al.,, 2023 ) . In order to support the transformation of the public bus system in European countries and beyond, high-quality decision support is necessary, especially, concerning the bus operators’ important strategic decision of how many and which types of zero emission buses to invest in. Given an available line plan, switching from diesel-powered buses to zero emission vehicles without changes in the plan, requires solving an (electric) vehicle scheduling problem, minimizing the number of buses required to serve the line. Since battery-electric zero emission vehicles are currently still only available with rather limited driving ranges compared to diesel-powered vehicles, and have the disadvantage of taking a long time to recharge, it is not straightforward to substitute conventional diesel buses with zero emission technology, in particular for regional bus lines. Recharging stops during the day are usually required and have to be planned. From an operator’s perspective, charging on their own premises, potentially relying on their own photovoltaic energy, is in many cases the cheapest and sometimes the only option, since chargers for heavy duty vehicles are not yet available on a larger scale, resulting in a rather small number of possible charging locations. The problem we address can be cast as a Multi-Depot Electric Vehicle Scheduling Problem (MDEVSP): each bus line operator has to serve a set of service trips with a fleet of electric or fuel cell-electric vehicles. Each service trip has to be covered by exactly one schedule, which is performed by one vehicle. Each vehicle is required to begin and end its trip at the same depot, chosen from a predefined set of depots. Given the use of electric vehicles and the regional setting with relatively long bus routes, charging may need to be planned throughout the day to ensure that the battery level never drops below a specified threshold and remains above a certain limit upon returning to the depot. Recharging requires vehicles to drive to a charging station, where charging facilities are usually available. Partial recharging is allowed. The aim of our approach is to provide decision support for transitioning from diesel-powered to zero emission vehicles, particularly electric buses. The key issue to resolve is determining how many buses are necessary to serve all service trips. Service trips follow a timetable and, therefore, they have fixed start and end times, durations, and lengths. We also assume that the fleet is limited to a single vehicle type, i.e., buses of a specific length and technology. This reflects the situation currently encountered in Salzburg, where individual lines are tendered and assigned to different operators based on their bids. However, various bus types can be evaluated and compared to select the most suitable option. Since minimizing the total number of vehicles usually results in several alternative optimal solutions, we lexicographically minimize (1) the number of vehicles, (2) the number of charging events during the day, and (3) the total energy consumed, while all scheduled service trips during daily operations are covered. The contribution of this paper is as follows: • We develop a graph representation that only allows time-feasible paths (or vehicle schedules), including charging events. • We formulate a 3-index and a 2-index mixed-integer linear program (MILP), relying on our graph representation, allowing partial recharge without explicitly modeling time. • The 3-index model is compact and can be solved directly with an off-the-shelf solver. The 2-index model requires depot-pairing constraints of exponential size. We propose two different ways to model these constraints (infeasible path constraints and connectivity constraints) and separate them in a branch-and-cut fashion. • We present a computational study on a large set of instances that mimic realistic settings and illustrate the advantages and drawbacks of the two approaches. • We compare propulsion technologies (diesel, battery-electric, and fuel cell-electric) using realistic instances, conducting a parameter study to examine the impact of cold weather conditions as well as battery degradation on fleet size and operational feasibility. The remainder of this paper is structured as follows. We first give an overview of the work related to the problem setting considered in this paper in Section 2 . We then formally define the MDEVSP with partial recharging and detail a