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 to reduce costs even more for periods of low demand, for example. With increasing degrees of freedom, conventional solution approaches for the VSP-TW become computationally prohibitive, though. 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 when reasonable from a passenger's point of view.

Extending the VSP-TW, we propose the vehicle scheduling problem with time windows and balanced timetables (VSP-TW-BT). In addition to the cost-efficiency objective of the VSPTW, our objective function also ensures the quality of a timetable from a passenger's point of view. Timetables are generated by balancing consecutive departures on a line along predefined departure time windows. A weighted sum approach combines both objectives in terms of cost minimization and timetable quality. Our mathematical model and solution approach are based on efficient techniques known from the area of vehicle routing with time windows. For solution, we present a hybrid metaheuristic framework and decompose 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 above mentioned instances can be downloaded here.

The zip file contains general parameters (general.dat) as well as 10 small (inputData_v01_*.dat) and 10 large (inputData_v02_*.dat) instance sets. While the number of lines is the same in small and large instance sets, the total number of service trips is doubled. The file general.dat contains information on the discretization of the time horizon as well as the maximum driving and duty time of a vehicle and the deadhead matrix. The input data files containt the total number of trips and links as well as information on identifier, origin, destionation, time windows and durations of service trips.