Integrated timetabling and vehicle scheduling with balanced departure times

Sequential planning of public transportation services can lead to inefficient vehicle schedules. Integrating timetabling and vehicle scheduling, the vehicle scheduling problem with time windows (VSP-TW) aims at minimizing costs of public transport operations by allowing small shifts of service trips’ departure times. Within the scope of tactical planning, a larger flexibility of departure times following predefined departure time windows may be desirable. However, with increasing degrees of freedom, conventional solution approaches for the VSP-TW become computationally prohibitive. Furthermore, a sole focus on cost minimization might produce timetables of insufficient quality, while public transport agencies expect high-quality timetables with service trips scheduled at times reasonable from a passenger’s point of view. Extending the VSP-TW, we propose the vehicle scheduling problem with time windows and balanced departure times (VSP-TW-BT). In addition to the cost-efficiency objective of the VSP-TW, our objective function considers the quality of a timetable from a passenger’s point of view. Timetables are generated by balancing consecutive departures on a line according to predefined departure time intervals. We use a weighted sum approach to combine both objectives, namely costs of operation and quality of timetables. Our mathematical model and solution approach are based on efficient techniques known from the area of vehicle routing with time windows. A hybrid metaheuristic framework is proposed, which decomposes the problem into a scheduling and a balancing component. Real-world-inspired instances allow for the evaluation of quality and performance of the solution approach. The proposed solution approach is able to outperform a commercial solver in terms of run time and solution quality.