A matheuristic approach for solving the Integrated Timetabling and Vehicle Scheduling Problem

Joao Filipe Paiva Fonseca, Allan Larsen, Evelien van der Hurk, Stefan Røpke, Roberto Roberti

    Research output: Contribution to conferenceConference abstract for conferenceResearchpeer-review

    149 Downloads (Pure)

    Abstract

    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.
    Original languageEnglish
    Publication date2017
    Publication statusPublished - 2017
    EventVeRoLog 2017: 6th Vehicle Routing and Logistics Optimization Conference - Vrije Universiteit Amsterdam, Amsterdam, Netherlands
    Duration: 10 Jul 201712 Jul 2017
    Conference number: 6
    https://verolog2017.sciencesconf.org/

    Conference

    ConferenceVeRoLog 2017: 6th Vehicle Routing and Logistics Optimization Conference
    Number6
    LocationVrije Universiteit Amsterdam
    CountryNetherlands
    CityAmsterdam
    Period10/07/201712/07/2017
    Internet address

    Fingerprint Dive into the research topics of 'A matheuristic approach for solving the Integrated Timetabling and Vehicle Scheduling Problem'. Together they form a unique fingerprint.

    Cite this