Search Results

Documents authored by Tian, Huaining

Document
DOI: 10.4230/OASIcs.ATMOS.2016.6
Multi-Column Generation Model for the Locomotive Assignment Problem

Authors: Brigitte Jaumard and Huaining Tian

Published in: OASIcs, Volume 54, 16th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2016)

Abstract
We propose a new decomposition model and a multi-column generation algorithm for solving the Locomotive Assignment Problem (LAP). The decomposition scheme relies on consist configurations, where each configuration is made of a set of trains pulled by the same set of locomotives. We use the concept of conflict graphs in order to reduce the number of trains to be considered in each consist configuration generator problem: this contributes to significantly reduce the fraction of the computational times spent in generating new potential consists. In addition, we define a column generation problem for each set of variables, leading to a multi-column generation process, with different types of columns. Numerical results, with different numbers of locomotives, are presented on adapted data sets coming from Canada Pacific Railway (CPR). They show that the newly proposed algorithm is able to solve exactly realistic data instances for a timeline spanning up to 6 weeks, in very reasonable computational times.
Cite as

Brigitte Jaumard and Huaining Tian. Multi-Column Generation Model for the Locomotive Assignment Problem. In 16th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2016). Open Access Series in Informatics (OASIcs), Volume 54, pp. 6:1-6:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)

Copy BibTex To Clipboard

@InProceedings{jaumard_et_al:OASIcs.ATMOS.2016.6,
  author =	{Jaumard, Brigitte and Tian, Huaining},
  title =	{{Multi-Column Generation Model for the Locomotive Assignment Problem}},
  booktitle =	{16th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2016)},
  pages =	{6:1--6:13},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-95977-021-7},
  ISSN =	{2190-6807},
  year =	{2016},
  volume =	{54},
  editor =	{Goerigk, Marc and Werneck, Renato F.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/OASIcs.ATMOS.2016.6},
  URN =		{urn:nbn:de:0030-drops-65302},
  doi =		{10.4230/OASIcs.ATMOS.2016.6},
  annote =	{Keywords: Railway optimization, Locomotive assignment, Column Generation}
}
Document
DOI: 10.4230/OASIcs.ATMOS.2012.108
A Dynamic Row/Column Management Algorithm for Freight Train Scheduling

Authors: Brigitte Jaumard, Thai H. Le, Huaining Tian, Ali Akgunduz, and Peter Finnie

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

Abstract
We propose a new dynamic row/column management algorithm for freight train scheduling in a single track railway system. While many papers have already been devoted to train scheduling, previously published optimization models still suffer from scalability issues, even for single track railway systems. Moreover, very few of them take into account the capacity constraints, i.e., the number of alternate tracks in the railway stations/sidings in order for the trains to meet/bypass. We propose an optimization model which takes such constraints into account, while still handling efficiently the other meaningful constraints. We design an original solution scheme with iterative additions/removals of constraints/variables in order to remain with a manageable sized mixed integer linear program at each iteration, without threatening to reach the optimal solution. Numerical results are presented on several data instances of CPR (Canadian Pacific Railway) on the Vancouver-Calgary corridor, one of the most busy corridor in their railway system. Therein, the proposed model and algorithm are used as a planning tool to evaluate the network capacity, i.e., how much the number of trains can be increased without impacting significantly the average travel times between the source and destination stations of the various trains in the corridor. Larger data instances than those previously published are solved accurately (epsilon-optimal solutions) for the schedule of freight trains.
Cite as

Brigitte Jaumard, Thai H. Le, Huaining Tian, Ali Akgunduz, and Peter Finnie. A Dynamic Row/Column Management Algorithm for Freight Train Scheduling. In 12th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems. Open Access Series in Informatics (OASIcs), Volume 25, pp. 108-119, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2012)

Copy BibTex To Clipboard

@InProceedings{jaumard_et_al:OASIcs.ATMOS.2012.108,
  author =	{Jaumard, Brigitte and Le, Thai H. and Tian, Huaining and Akgunduz, Ali and Finnie, Peter},
  title =	{{A Dynamic Row/Column Management Algorithm for Freight Train Scheduling}},
  booktitle =	{12th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems},
  pages =	{108--119},
  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.108},
  URN =		{urn:nbn:de:0030-drops-37074},
  doi =		{10.4230/OASIcs.ATMOS.2012.108},
  annote =	{Keywords: Railway optimization, Train scheduling, Single track}
}
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