A matheuristic approach for solving the Integrated Timetabling and Vehicle Scheduling Problem
Joao Paiva Fonseca  1@  , Allan Larsen  1@  , Evelien Van Der Hurk  1@  , Roberto Roberti  2@  , Stefan Ropke  1@  
1 : DTU Management Engineering, Technical University of Denmark  -  Website
Anker Engelunds Vej 1 Building 101A 2800 Kgs. Lyngby -  Denmark
2 : VU University Amsterdam

The Integrated Timetabling and Vehicle Scheduling Problem (IT-VSP) is a generalization of the well-known Vehicle Scheduling Problem (VSP). In the IT-VSP the trips in the original timetables may be modified in terms of arrival and departure times in order to minimize a new objective function that considers both operational costs and passenger transfer costs. Starting from a base timetable, the allowed modifications include shifting the departure time from the first station of each trip and also the extension of dwell times at important stops where large flows of passengers are expected to transfer between different trips. We consider transfers between bus trips scheduled by the model, but also transfers to other fixed lines that intersect the lines considered in the IT-VSP. We present a MIP formulation of the IT-VSP able to solve small instances of the problem, and a matheuristic approach that uses the compact MIP to solve larger instances of the problem. The idea is to iteratively solve restricted versions of the MIP selecting at each step a subset of trips where modifications are allowed, while all other trips remain fixed. The performance of the proposed matheuristic is shown on a case study with real-life instances provided by the main service provider in the greater Copenhagen area. The effect of allowing dwell times is compared to previous approaches to the problem where trips are only allowed to be shifted in time.


Online user: 1 RSS Feed