A Configuration Model for the Line Planning Problem

Please always quote using this URN: urn:nbn:de:0297-zib-41903
  • We propose a novel extended formulation for the line planning problem in public transport. It is based on a new concept of frequency configurations that account for all possible options to provide a required transportation capacity on an infrastructure edge. We show that this model yields a strong LP relaxation. It implies, in particular, general classes of facet defining inequalities for the standard model.

Download full text files

Export metadata

  • Export Bibtex
Metadaten
Author:Ralf Borndörfer, Heide Hoppmann, Marika Karbstein
Document Type:ZIB-Report
Tag:combinatorial optimization; line planning; polyhedral combinatorics
MSC-Classification:90-XX OPERATIONS RESEARCH, MATHEMATICAL PROGRAMMING / 90Bxx Operations research and management science / 90B06 Transportation, logistics
90-XX OPERATIONS RESEARCH, MATHEMATICAL PROGRAMMING / 90Cxx Mathematical programming [See also 49Mxx, 65Kxx] / 90C10 Integer programming
90-XX OPERATIONS RESEARCH, MATHEMATICAL PROGRAMMING / 90Cxx Mathematical programming [See also 49Mxx, 65Kxx] / 90C27 Combinatorial optimization
Date of first Publication:2013/01/08
Series (Serial Number):ZIB-Report (13-40)
ISSN:1438-0064
DOI:http://dx.doi.org/10.4230/OASIcs.ATMOS.2013.68

$Rev: 13581 $