Search Results

Documents authored by Flier, Holger

Document
DOI: 10.4230/OASIcs.ATMOS.2012.10
Optimal Freight Train Classification using Column Generation

Authors: Markus Bohlin, Florian Dahms, Holger Flier, and Sara Gestrelius

Published in: OASIcs, Volume 25, 12th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (2012)

Abstract
We consider planning of freight train classification at hump yards using integer programming. The problem involves the formation of departing freight trains from arriving trains subject to scheduling and capacity constraints. To increase yard capacity, we allow the temporary storage of early freight cars on specific mixed-usage tracks. The problem has previously been modeled using a direct integer programming model, but this approach did not yield lower bounds of sufficient quality to prove optimality. In this paper, we formulate a new extended integer programming model and design a column generation approach based on branch-and-price to solve problem instances of industrial size. We evaluate the method on historical data from the Hallsberg hump yard in Sweden, and compare the results with previous approaches. The new method managed to find optimal solutions in all of the 192 problem instances tried. Furthermore, no instance took more than 13 minutes to solve to optimality using fairly standard computer hardware.
Cite as

Markus Bohlin, Florian Dahms, Holger Flier, and Sara Gestrelius. Optimal Freight Train Classification using Column Generation. In 12th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems. Open Access Series in Informatics (OASIcs), Volume 25, pp. 10-22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2012)

Copy BibTex To Clipboard

@InProceedings{bohlin_et_al:OASIcs.ATMOS.2012.10,
  author =	{Bohlin, Markus and Dahms, Florian and Flier, Holger and Gestrelius, Sara},
  title =	{{Optimal Freight Train Classification using Column Generation}},
  booktitle =	{12th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems},
  pages =	{10--22},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-939897-45-3},
  ISSN =	{2190-6807},
  year =	{2012},
  volume =	{25},
  editor =	{Delling, Daniel and Liberti, Leo},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/OASIcs.ATMOS.2012.10},
  URN =		{urn:nbn:de:0030-drops-36997},
  doi =		{10.4230/OASIcs.ATMOS.2012.10},
  annote =	{Keywords: Column generation, integer programming, scheduling, shunting, classification, marshalling, transportation, railways}
}
Document
DOI: 10.4230/OASIcs.ATMOS.2011.38
Track Allocation in Freight-Train Classification with Mixed Tracks

Authors: Markus Bohlin, Holger Flier, Jens Maue, and Matús Mihalák

Published in: OASIcs, Volume 20, 11th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (2011)

Abstract
We consider the process of forming outbound trains from cars of inbound trains at rail-freight hump yards. Given the arrival and departure times as well as the composition of the trains, we study the problem of allocating classification tracks to outbound trains such that every outbound train can be built on a separate classification track. We observe that the core problem can be formulated as a special list coloring problem in interval graphs, which is known to be NP-complete. We focus on an extension where individual cars of different trains can temporarily be stored on a special subset of the tracks. This problem induces several new variants of the list-coloring problem, in which the given intervals can be shortened by cutting off a prefix of the interval. We show that in case of uniform and sufficient track lengths, the corresponding coloring problem can be solved in polynomial time, if the goal is to minimize the total cost associated with cutting off prefixes of the intervals. Based on these results, we devise two heuristics as well as an integer program to tackle the problem. As a case study, we consider a real-world problem instance from the Hallsberg Rangerbangard hump yard in Sweden. Planning over horizons of seven days, we obtain feasible solutions from the integer program in all scenarios, and from the heuristics in most scenarios.
Cite as

Markus Bohlin, Holger Flier, Jens Maue, and Matús Mihalák. Track Allocation in Freight-Train Classification with Mixed Tracks. In 11th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems. Open Access Series in Informatics (OASIcs), Volume 20, pp. 38-51, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2011)

Copy BibTex To Clipboard

@InProceedings{bohlin_et_al:OASIcs.ATMOS.2011.38,
  author =	{Bohlin, Markus and Flier, Holger and Maue, Jens and Mihal\'{a}k, Mat\'{u}s},
  title =	{{Track Allocation in Freight-Train Classification with Mixed Tracks}},
  booktitle =	{11th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems},
  pages =	{38--51},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-939897-33-0},
  ISSN =	{2190-6807},
  year =	{2011},
  volume =	{20},
  editor =	{Caprara, Alberto and Kontogiannis, Spyros},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/OASIcs.ATMOS.2011.38},
  URN =		{urn:nbn:de:0030-drops-32658},
  doi =		{10.4230/OASIcs.ATMOS.2011.38},
  annote =	{Keywords: algorithms, complexity, graph theory, railways, scheduling, shunting, train classification, train marshalling, transportation}
}
Document
DOI: 10.4230/OASIcs.ATMOS.2010.61
Vertex Disjoint Paths for Dispatching in Railways

Authors: Holger Flier, Matús Mihalák, Anita Schöbel, Peter Widmayer, and Anna Zych

Published in: OASIcs, Volume 14, 10th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS'10) (2010)

Abstract
We study variants of the vertex disjoint paths problem in planar graphs where paths have to be selected from a given set of paths. We study the problem as a decision, maximization, and routing-in-rounds problem. Although all considered variants are NP-hard in planar graphs, restrictions on the location of the terminals, motivated by railway applications, lead to polynomially solvable cases for the decision and maximization versions of the problem, and to a $p$-approximation algorithm for the routing-in-rounds problem, where $p$ is the maximum number of alternative paths for a terminal pair.
Cite as

Holger Flier, Matús Mihalák, Anita Schöbel, Peter Widmayer, and Anna Zych. Vertex Disjoint Paths for Dispatching in Railways. In 10th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS'10). Open Access Series in Informatics (OASIcs), Volume 14, pp. 61-73, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2010)

Copy BibTex To Clipboard

@InProceedings{flier_et_al:OASIcs.ATMOS.2010.61,
  author =	{Flier, Holger and Mihal\'{a}k, Mat\'{u}s and Sch\"{o}bel, Anita and Widmayer, Peter and Zych, Anna},
  title =	{{Vertex Disjoint Paths for Dispatching in Railways}},
  booktitle =	{10th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS'10)},
  pages =	{61--73},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-939897-20-0},
  ISSN =	{2190-6807},
  year =	{2010},
  volume =	{14},
  editor =	{Erlebach, Thomas and L\"{u}bbecke, Marco},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/OASIcs.ATMOS.2010.61},
  URN =		{urn:nbn:de:0030-drops-27508},
  doi =		{10.4230/OASIcs.ATMOS.2010.61},
  annote =	{Keywords: algorithms, approximation, complexity, graph theory, railways, routing, transportation}
}
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact