Metric Inequalities for Routings on Direct Connections with Application in Line Planning

Please always quote using this URN: urn:nbn:de:0297-zib-53507
  • We consider multi-commodity flow problems in which capacities are installed on paths. In this setting, it is often important to distinguish between flows on direct connection routes, using single paths, and flows that include path switching. We derive a feasibility condition for path capacities supporting such direct connection flows similar to the feasibility condition for arc capacities in ordinary multi-commodity flows. The concept allows to solve large-scale real-world line planning problems in public transport including a novel passenger routing model that favors direct connections over connections with transfers.

Download full text files

Export metadata

  • Export Bibtex
Metadaten
Author:Ralf Borndörfer, Marika Karbstein
Document Type:ZIB-Report
Tag:combinatorial optimization; direct connection; integer programming; line planning; metric inequalities; transfers
MSC-Classification:90-XX OPERATIONS RESEARCH, MATHEMATICAL PROGRAMMING / 90Bxx Operations research and management science / 90B20 Traffic problems
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:2015/01/27
Series (Serial Number):ZIB-Report (15-07)
ISSN:1438-0064
Published in:Appeared in: Discrete Optimization 18 (2015) 56-75
DOI:http://dx.doi.org/10.1016/j.disopt.2015.07.004

$Rev: 13581 $