On the Benefit of Preprocessing and Heuristics for Periodic Timetabling

Christian Liebchen ()
Additional contact information
Christian Liebchen: Technische Hochschule Wildau, Ingenieur- und Naturwissenschaften, Verkehrsbetriebsführung

A chapter in Operations Research Proceedings 2017, 2018, pp 709-714 from Springer

Abstract: Abstract We consider the computation of periodic timetables, which is a key task in the service design process of public transportation companies. We are aware of only one collection of instances, the so-called PESPlib. In the present paper, we aim at providing good solutions for the smallest and the largest of its instances (R1L1 and R4L4). We run a standard MIP solver (CPLEX) on a very elementary problem formulation. To come up with MIP sizes that fit better for standard MIP solvers, we propose to simplify the instances first, by invoking some basic preprocessing, parts of which having a heuristic character. Doing so, we improve the previously best-known objective value for R1L1 from 37,338,904 down to 33,711,523, and for R4L4 from 47,283,768 down to 43,234,156, i.e. by 9.7% and 8.6%, respectively.

Date: 2018
References: Add references at CitEc
Citations: View citations in EconPapers (2)

There are no downloads for this item, see the EconPapers FAQ for hints about obtaining it.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:oprchp:978-3-319-89920-6_94

Ordering information: This item can be ordered from
http://www.springer.com/9783319899206

DOI: 10.1007/978-3-319-89920-6_94

Access Statistics for this chapter

More chapters in Operations Research Proceedings from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().