Integrated Optimization of Timetabling and Electric Vehicle Scheduling: A Case Study of Aachen, Germany
Authors: Vladimir Stadnichuk, Jenny Segschneider, Arie M.C.A. Koster, Grit Walther
Pre-print available at: optimization online
Full article: published in EURO Journal on Transportation and Logistics, doi: https://doi.org/10.1016/j.ejtl.2025.100168
src/
├── algorithm/
│ └── BinPacking.java
├── data/
│ ├── EnergyFunctions.java
│ └── ScheduleGenerator.java
├── datenstructure/
│ ├── Busline.java
│ ├── Bustype.java
│ ├── ConflictGraph.java
│ ├── DetailedTimetable.java
│ ├── EVSP_Binpacking.java
│ ├── Location.java
│ ├── PartitionAlgorithm.java
│ ├── PeriodicTimetable.java
│ ├── Scheduletype.java
│ ├── TimeHorizon.java
│ ├── TimetablingAndEVSP.java
│ ├── TransferEvent.java
│ ├── Trip.java
│ └── Trip_Relationship_DAG.java
├──statistics/
│ ├── StatisticsEVSP.java
│ └── StatisticsTTMIP.java
├── ui/
│ ├── Auxilliary_Funktions.java
│ ├── Graph_vis.java
│ └── Run.java
└── vs.ebusse2023/
└── EBusse2023.java # this is the main
- Java 17 or higher
- Gurobi for MILP solving (requires a license)
- Gurobi
- jgrapht core and ext
- commons-lang3 by apache
- Jackson Databind
Clone the repository:
git clone https://github.com/JennySegschneider/Timetabling_and_EVSP.gitChoose instances and algorithms:
All Settings for the computation as well as the generation and instance size can be set in config.json. An explanation of all settings and options can be found below.
Compile and run using maven:
mvn clean install
java -jar target/TimetablingAndEVSP-1.0-SNAPSHOT.jarThe results as a csv as well as all logs are written to output_runs/runx/. Running the python script summarize_info_for_all_runs.py in the output_runs folder creates a csv with the results from all runs.
The file config.json includes all settings and configuration for the study, including general run settings, settings for the algorithms used, and settings for the instance generation. Here, I will quickly go over the settings and what they do.
"part_alg": "CHORDAL_GRAPH_COLORING", "bpAlg": "STRICT_FIRST_FIT",
These set the algorithms used to find a partitioning of trips and the algorithm used to solve the Bin Packing (with conflicts) problem. For partition, there are two options: CHORDAL_GRAPH_COLORING is based on computing a vertex color on the chordal conflict graph, and SINGLE_BUS_TYPE_OPT uses single gasoline bus optimization. For bin packing, there are 9 algorithms:
- With GUROBI or ALL_COLORS_GUROBI, an optimal solution to the bin packing problem is computed by solving the MIP formulation with Gurobi on each color class seperate or for all color classes at once respectively.
- NEXT_FIT use the next fit heuristic on each color class separately, i.e., put each item in the next, fitting bin. Items are sorted by starting time of the corresponding trip.
- FIRST_FIT and FIRST_FIT_DECREASING uses the first fit heuristic on each color class, i.e., put each item in the first, fitting bin. Items are sorted by starting time of the corresponding trip or by energy consumption for _DECREASING
- STRICT_FIRST_FIT and STRICT_FIRST_FIT_DECREASING uses the first fit heuristic on all trips at once. Items are sorted by starting time of the corresponding trip or by energy consumption for _DECREASING
- ALL_COLORS_FIRST_FIT and ALL_COLORS_FIRST_FIT_DECREASING uses the first fit heuristic on all trips at once. Items are sorted by their color and within the colors by their starting time of the corresponding trip or by energy consumption for _DECREASING
"UNIQUE_BUSTYPE": "ELECTRIC_BUS_RECHARGE",
This setting defines the type of buses used. There are three options:
- GASOLINE_BUS for gasoline buses without range restriction
- ELECTRIC_BUS for electric buses with range restriction
- ELECTRIC_BUS_RECHARGE for electric buses with range restriction and recharge capability
"inputSchedule": "Aachen", "numberLines": 8,
These settings control the instance. The second one defines the number of periodic lines that are included. The first one defines the type of instance considered. Randomised generates randomised lines, Aachen includes 11 lines from the bus plan of Aachen, Germany, and testing includes some fixed lines for testing new algorithms.
"maximumDeviation": 900,
This is the maximum deviation in seconds that the new timetable may have from the input timetable.
"timestepsDiscretization": 12, "adaptiveSteps": 1,
We consider a discretized time window. timestepsDiscretization sets the number of discretization steps for one hour. Setting this to 12 results in discretization steps of 5 minutes. The adaptiveSteps setting is used for an approach that is not mentioned in the paper: we tried to, adaptively and recursively refine the discretization. Beginning with a rough discretization, we would compute an optimal timetabling. Then, we would refine the discretization but restrict the maximum deviation to the old discretization steps. Setting the number of these steps to one corresponds to not refining the discretization. Since this approach did not improve the found solution and took considerably longer, we did not include it in the paper.
"batteryCapacity": 10800, "fullChargeSpeed": 10800
Finally, these two setting influence the battery Capacity and charge duration for electric buses. The battery capacity is expressed as the time a bus can drive with a full charge in seconds. A battery Capacity of 10800 means that an electric bus can drive for 3h. The charge speed is also expressed as the time it takes to fully charge a battery in seconds. A charge speed of 10800 means that the battery of an electric bus can be charged from completely empty to full within 3h.
These are exemplary results of one run:
Run;1 Run_time_sec;4.919 Best Solutions for each adaptive step;[23] Worst Solutions for each adaptive step;[26] Gasoline Buses required;14 Electric Buses for original schedule using Heuristic;24 Run_Parameters[part_alg=CHORDAL_GRAPH_COLORING, bpAlg=STRICT_FIRST_FIT, UNIQUE_BUSTYPE=ELECTRIC_BUS_RECHARGE, inputSchedule=Aachen, numberLines=5, timestepsDiscretization=12, adaptiveSteps=1, maximumDeviation=900, batteryCapacity=10800, fullChargeSpeed=10800]
The best and worst solutions for each adaptive step include the number of electric buses needed in the best and worst schedules found during all EVSP subproblems solved in that adaptive step. Here, only one adaptive step was used; thus, the lists contain only one element. The best schedule required only 23 electric buses, which is the optimal solution for this instance. The worst schedule needed 26 electric buses. The number of gasoline buses refers to those required to serve the original (input) schedule with gasoline buses. Similarly, we provide the number of electric buses needed for the original schedule as computed by the chosen heuristic for comparison. Since the original schedule would have required 24 buses, the integrated approach saved one electric bus.
- By applying our integrated framework, we observed significant reductions in the number of required vehicles under full‐electric fleet scenarios, compared to baseline scheduling.
- The theoretical bounds we derived provide practical insight into when the heuristics perform near-optimally in practice.
- In the Aachen case study, even small timetable adjustments led to measurable benefits in EV scheduling, suggesting practical value for transit operators.
Vladimir Stadnichuk 📧 vladimir.stadnichuk@om.rwth-aachen.de 💼 Website
Jenny Segschneider 📧 segschneider@math2.rwth-aachen.com 💼 Website
If you use this code or build upon it, please cite:
@misc{segschneider2025drpbm,
author = {Jenny Segschneider, Vladimir Stadnichuk},
title = {Integrated Timetabling and Electric Vehicle Scheduling Problem},
year = {2025},
howpublished = {\url{[https://github.com/<your-username>/drpbm-benders-java](https://github.com/JennySegschneider/Timetabling_and_EVSP.git)}}
}