Search Results

Documents authored by Bohlin, Markus

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.2009.2141
MILP formulations of cumulative constraints for railway scheduling - A comparative study

Authors: Martin Aronsson, Markus Bohlin, and Per Kreuger

Published in: OASIcs, Volume 12, 9th Workshop on Algorithmic Approaches for Transportation Modeling, Optimization, and Systems (ATMOS'09) (2009)

Abstract
This paper introduces two Mixed Integer Linear Programming (MILP) models for railway traffic planning using a cumulative scheduling constraint and associated pre-processing filters. We compare standard solver performance for these models on three sets of problems from the railway domain and for two of them, where tasks have unitary resource consumption, we also compare them with two more conventional models. In the experiments, the solver performance of one of the cumulative models is clearly the best and is also shown to scale very well for a large scale practical railway scheduling problem.
Cite as

Martin Aronsson, Markus Bohlin, and Per Kreuger. MILP formulations of cumulative constraints for railway scheduling - A comparative study. In 9th Workshop on Algorithmic Approaches for Transportation Modeling, Optimization, and Systems (ATMOS'09). Open Access Series in Informatics (OASIcs), Volume 12, pp. 1-13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2009)

Copy BibTex To Clipboard

@InProceedings{aronsson_et_al:OASIcs.ATMOS.2009.2141,
  author =	{Aronsson, Martin and Bohlin, Markus and Kreuger, Per},
  title =	{{MILP formulations of cumulative constraints for railway scheduling - A comparative study}},
  booktitle =	{9th Workshop on Algorithmic Approaches for Transportation Modeling, Optimization, and Systems (ATMOS'09)},
  pages =	{1--13},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-939897-11-8},
  ISSN =	{2190-6807},
  year =	{2009},
  volume =	{12},
  editor =	{Clausen, Jens and Di Stefano, Gabriele},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/OASIcs.ATMOS.2009.2141},
  URN =		{urn:nbn:de:0030-drops-21413},
  doi =		{10.4230/OASIcs.ATMOS.2009.2141},
  annote =	{Keywords: Railway transport scheduling, Cumulative scheduling, Mixed Integer Linear Programming (MILP) modelling and pre-processing Railway transport scheduling, Cumulative scheduling, Mixed Integer Linear Programming (MILP) modelling and pre-processing}
}
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 Imprint Privacy Contact