Integrated optimization of timetabling and Electric Vehicle Scheduling

EURO Journal on Transportation and Logistics, vol. 14, pp. 100168

Abstract

We tackle the integrated planning problem of periodic timetabling and electric vehicle scheduling, crucial for cities transitioning to electric bus fleets. Given existing timetables, we allow only minor modifications and propose an iterative solution approach that addresses the Electric Vehicle Scheduling Problem (EVSP) in each iteration. Due to the NP-hard nature of EVSP, we employ well-established heuristics and evaluate the quality of the solutions obtained. Specifically, we establish tight approximation bounds for certain iterative heuristics that first solve the Vehicle Scheduling Problem and subsequently adjust solutions to meet battery constraints. We make several key contributions: We provide general insights into heuristic solution quality, establish theoretical performance bounds, and validate these findings through a case study using real-world data from Aachen, Germany. Additionally, we employ our iterative framework to derive managerial insights for bus operators in Aachen by quantifying potential gains from adjusting the timetable to support the transition to a fully electric bus fleet. • We tackle integrated planning for timetabling and electric vehicle scheduling. • Novel iterative framework to solve the integrated planning problem. • We prove new, tight approximation bounds for some types of heuristics in electric vehicle scheduling. • Real-world case study for Aachen, Germany. • Managerial insights quantify gains from timetable adjustments for a fully electric bus fleet transition.

Authors 3

1. Jenny Segschneider Aachen Research Area Discrete Optimization

   RWTH Aachen University

   Affiliation as printed

   Research Area Discrete Optimization, RWTH Aachen University, Pontdriesch 10-12, 52056, Aachen, Germany

2. Arie M. C. A. Koster Aachen Research Area Discrete Optimization

   RWTH Aachen University

   Affiliation as printed

   Research Area Discrete Optimization, RWTH Aachen University, Pontdriesch 10-12, 52056, Aachen, Germany

3. Grit Walther Aachen School of Business and Economics

   RWTH Aachen University

   Affiliation as printed

   School of Business and Economics, RWTH Aachen University, Kackertstraße 7, 52072, Aachen, Germany