DROPS

Document

DOI: 10.4230/OASIcs.ATMOS.2026.13

Exploiting Treewidth to Solve the Pricing Problem in Column Generation for Non-Pool-Based Line Planning

Authors: Markus Niebisch and Tom C. van der Zanden

Published in: OASIcs, Volume 147, 26th Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2026)

Abstract

The line planning problem (LPP) involves determining a set of lines (routes for vehicles to travel on) for a transportation network that meet travel demands while minimizing both travel time and the line operation costs. Unfortunately, this problem is NP-hard. Recently, Heinrich et al. [Irene Heinrich et al., 2023] proposed using treewidth to solve (a variant of) this problem; however, the sizes of networks and values of treewidth for which it is practical are limited. We propose a different way of exploiting bounded treewidth in solving the LPP. We combine a column generation approach due to Borndörfer et al. [Ralf Borndörfer et al., 2007] with dynamic programming on tree decompositions to solve the pricing problem, which entails solving the NP-hard longest path problem. We show that this approach is feasible. We are able to apply our approach to graphs with both more vertices and higher treewidth (up to 9) than Heinrich et al. We experimentally evaluate our approach using artificial benchmarks (connected concentric ring graphs) and two practical examples, the Munich train/subway network and the Japanese railroad system.

Cite as

Markus Niebisch and Tom C. van der Zanden. Exploiting Treewidth to Solve the Pricing Problem in Column Generation for Non-Pool-Based Line Planning. In 26th Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2026). Open Access Series in Informatics (OASIcs), Volume 147, pp. 13:1-13:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{niebisch_et_al:OASIcs.ATMOS.2026.13,
  author =	{Niebisch, Markus and van der Zanden, Tom C.},
  title =	{{Exploiting Treewidth to Solve the Pricing Problem in Column Generation for Non-Pool-Based Line Planning}},
  booktitle =	{26th Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2026)},
  pages =	{13:1--13:20},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-95977-453-6},
  ISSN =	{2190-6807},
  year =	{2026},
  volume =	{147},
  editor =	{Cacchiani, Valentina and Funke, Stefan},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/OASIcs.ATMOS.2026.13},
  URN =		{urn:nbn:de:0030-drops-278093},
  doi =		{10.4230/OASIcs.ATMOS.2026.13},
  annote =	{Keywords: line planning, public transport, treewidth, integer programming, fixed parameter tractability, column generation}
}

Search Results

Documents authored by Niebisch, Markus

Exploiting Treewidth to Solve the Pricing Problem in Column Generation for Non-Pool-Based Line Planning

Abstract

Cite as

Thanks for your feedback!

Could not send message