This paper describes a method for scheduling trains on the Hunter Valley Coal Chain rail network. Coal for a particular ship is railed from different mines to stockpiles at one of the Port’s terminals. The coal producers decide which mines will supply each order in what proportion, so there is no flexibility in the allocation of mines to cargoes. We are presented with a list of tonnes of coal which need to be transported from specified load points at mines to specified stockpiles at the port. The operators of the rail network provide a number of paths, with specified arrival and departure times, that can be used for coal movement. The requirement to assign coal trains to these existing paths makes this rail scheduling problem different to most of those discussed in the literature. In this paper we describe the problem in detail, demonstrate that it is very large making it difficult to solve with commercial MILP solvers, and show that our Lagrangian heuristic is able to produce high quality solutions in a reasonable amount of time.
Accepté le :
DOI : 10.1051/ro/2014049
Mots-clés : Mixed integer programming, coal supply chain, rail scheduling, lagrangian relaxation
@article{RO_2015__49_2_413_0,
author = {Singh, Gaurav and Ernst, Andreas T. and Baxter, Matthew and Sier, David},
editor = {Blazewicz, Jacek and Pesch, Erwin and Philipps, Cynthia and Trystram, Denis and Zhang, Guochuan},
title = {Rail schedule optimisation in the hunter valley coal chain},
journal = {RAIRO - Operations Research - Recherche Op\'erationnelle},
pages = {413--434},
publisher = {EDP-Sciences},
volume = {49},
number = {2},
year = {2015},
doi = {10.1051/ro/2014049},
mrnumber = {3349157},
zbl = {1310.90016},
language = {en},
url = {http://archive.numdam.org/articles/10.1051/ro/2014049/}
}
TY - JOUR AU - Singh, Gaurav AU - Ernst, Andreas T. AU - Baxter, Matthew AU - Sier, David ED - Blazewicz, Jacek ED - Pesch, Erwin ED - Philipps, Cynthia ED - Trystram, Denis ED - Zhang, Guochuan TI - Rail schedule optimisation in the hunter valley coal chain JO - RAIRO - Operations Research - Recherche Opérationnelle PY - 2015 SP - 413 EP - 434 VL - 49 IS - 2 PB - EDP-Sciences UR - http://archive.numdam.org/articles/10.1051/ro/2014049/ DO - 10.1051/ro/2014049 LA - en ID - RO_2015__49_2_413_0 ER -
%0 Journal Article %A Singh, Gaurav %A Ernst, Andreas T. %A Baxter, Matthew %A Sier, David %E Blazewicz, Jacek %E Pesch, Erwin %E Philipps, Cynthia %E Trystram, Denis %E Zhang, Guochuan %T Rail schedule optimisation in the hunter valley coal chain %J RAIRO - Operations Research - Recherche Opérationnelle %D 2015 %P 413-434 %V 49 %N 2 %I EDP-Sciences %U http://archive.numdam.org/articles/10.1051/ro/2014049/ %R 10.1051/ro/2014049 %G en %F RO_2015__49_2_413_0
Singh, Gaurav; Ernst, Andreas T.; Baxter, Matthew; Sier, David. Rail schedule optimisation in the hunter valley coal chain. RAIRO - Operations Research - Recherche Opérationnelle, New challenges in scheduling theory, Tome 49 (2015) no. 2, pp. 413-434. doi : 10.1051/ro/2014049. http://archive.numdam.org/articles/10.1051/ro/2014049/
N. Boland and M. Savelsbergh, Optimizing the hunter valley coal chain. In H. Gurani and S. Ray Mehrotra (eds.), Supply Chain Disruptions: Theory and Practice of Managing Risk. Springer London, 2012, pp. 275–302.
, , , , , and , A mixed integer programming model for long term capacity expansion planning: A case study from The Hunter Valley Coal Chain. Eur. J. Oper. Res. 220 (2012) 210–224. | DOI | MR | Zbl
, and , A Survey of Optimization Models for Train Routing and Scheduling. Trans. Sci. 32 (1998) 380–404. | DOI | Zbl
, , and , Railway track allocation: models and methods. OR Spectrum 33 (2011) 843–883. | DOI | MR | Zbl
M.A. Salido, F. Barber, M. Abril, P. Tormos, A. Lova and L. Ingolotti, A Topological Model Based on Railway Capacity to Manage Periodic Train Scheduling, in Applications and Innovations in Intelligent Systems XII, Proceedings of AI-2004, the Twenty-fourth SGAI International Conference on Innovative Techniques and Applications of Artificial Intelligence, edited by A. Macintosh, R. Ellis, and T. Allen. Springer, London, 2005, Vol. 2, pp. 107–120.
, , , and , Solving real-life locomotive-scheduling problems. Trans. Sci. 39 (2005) 503–517. | DOI
, , and , Reordering and local rerouting strategies to manage train traffic in real time. Trans. Sci. 42 (2008) 405–419. | DOI
G.Şahin, R.K. Ahuja and C.B. Cunha, Integer programming based solution approaches for the train dispatching problem. Technical report, Sabanci University, 2010.
and , Optimising a coal rail network under capacity constraints. Flexible Services and Manufacturing Journal 23 (2011) 90–110. | DOI | Zbl
, , and , Routing trains through railway junctions: a new set-packing approach. Trans. Sci. 45 (2011) 228–245. | DOI
P.S. Welgama and R. Oyston, Study of options to increase the throughput of the hunter valley coal chain, in Proc. of MODSIM (2003) 14–17.
, , , and , Solving a resource allocation problem in wireless mesh networks: A comparison between a CP-based and a classical column generation. Networks 55 (2010) 221–233. | MR | Zbl
and , A column generation approach to the heterogeneous fleet vehicle routing problem. Comput. Oper. Res. 34 (2007) 2080–2095. | DOI | Zbl
, and , On the choice of explicit stabilizing terms in column generation. Discrete Appl. Math. 157 (2009) 1167–1184. | DOI | MR | Zbl
L.A. Wolsey and G.L. Nemhauser, Integer and combinatorial optimization. Wiley-Interscience. | MR | Zbl
and , Resource constraint scheduling with a fractional shared resource. Oper. Res. Lett. 39 (2011) 363–368. | MR | Zbl
, , and , Distributed optimisation method for multi-resource constrained scheduling in coal supply chains. Int. J. Prod. Res. 51 (2013) 2740–2759. | DOI
, The lagrangian relaxation method for solving integer programming problems. Manag. Sci. 50 (2004) 1861–1871. | DOI | Zbl
and , The volume algorithm: producing primal solutions with a subgradient method. Math. Program. 87 (2000) 385–399. | DOI | MR | Zbl
Cité par Sources :
