Metric inequalities for routings on direct connections with application to line planning

  • 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 well-known feasibility condition for arc capacities in ordinary multi-commodity flows. The condition can be expressed in terms of a class of metric inequalities for routings on direct connections. We illustrate the concept on the example of the line planning problem in public transport and present an application to large-scale real-world problems.

Export metadata

  • Export Bibtex
Metadaten
Author:Ralf Borndörfer, Marika Karbstein
Document Type:Article
Parent Title (English):Discrete Optimization
Volume:18
First Page:56
Last Page:73
Year of first publication:2015
Preprint:urn:nbn:de:0297-zib-53507

$Rev: 13581 $