Bohlin, Markus ;
Dahms, Florian ;
Flier, Holger ;
Gestrelius, Sara
Optimal Freight Train Classification using Column Generation
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.
BibTeX - Entry
@InProceedings{bohlin_et_al:OASIcs:2012:3699,
author = {Markus Bohlin and Florian Dahms and Holger Flier and Sara Gestrelius},
title = {{Optimal Freight Train Classification using Column Generation}},
booktitle = {12th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems},
pages = {10--22},
series = {OpenAccess Series in Informatics (OASIcs)},
ISBN = {978-3-939897-45-3},
ISSN = {2190-6807},
year = {2012},
volume = {25},
editor = {Daniel Delling and Leo Liberti},
publisher = {Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2012/3699},
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}
}
|
Keywords: |
|
Column generation, integer programming, scheduling, shunting, classification, marshalling, transportation, railways |
|
Seminar: |
|
12th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems
|
|
Issue date: |
|
2012 |
|
Date of publication: |
|
2012 |
2012
