Rail schedule optimisation in the hunter valley coal chain
RAIRO - Operations Research - Recherche Opérationnelle, Tome 49 (2015) no. 2, pp. 413-434.

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.

Reçu le :
Accepté le :
DOI : 10.1051/ro/2014049
Classification : 90B06, 90B35
Mots clés : Mixed integer programming, coal supply chain, rail scheduling, lagrangian relaxation
Singh, Gaurav 1 ; Ernst, Andreas T. 1 ; Baxter, Matthew 1 ; Sier, David 1

1 CSIRO Mathematics, Informatics and Statistics Private Bag 33, Clayton South MDC, 3168 Victoria, Australia.
@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://www.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://www.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://www.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, Tome 49 (2015) no. 2, pp. 413-434. doi : 10.1051/ro/2014049. http://www.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.

G. Singh, D. Sier, A. Ernst, O. Gavriliouk, R. Oyston, T. Giles and P. Welgama, 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

J.-F. Cordeau, P. Toth and D. Vigo, A Survey of Optimization Models for Train Routing and Scheduling. Trans. Sci. 32 (1998) 380–404. | DOI | Zbl

R. Lusby, J. Larsen, M. Ehrgott and D. Ryan, 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.

R.K Ahuja, J. Liu, J.B. Orlin, D. Sharma and L.A. Shughart, Solving real-life locomotive-scheduling problems. Trans. Sci. 39 (2005) 503–517. | DOI

A. D’Ariano, F. Corman, D. Pacciarelli and M. Pranzo, 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.

S.Q. Liu and E. Kozan, Optimising a coal rail network under capacity constraints. Flexible Services and Manufacturing Journal 23 (2011) 90–110. | DOI | Zbl

R. Lusby, J. Larsen, D. Ryan and M. Ehrgott, 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.

A. Capone, G. Carello, I. Filippini, S. Gualandi and F. Malucelli, 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

E. Choi and D.-W. Tcha, A column generation approach to the heterogeneous fleet vehicle routing problem. Comput. Oper. Res. 34 (2007) 2080–2095. | DOI | Zbl

H.M.T. Ben Amor, J. Desrosiers and A. Frangioni, 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

G. Singh and A.T. Ernst, Resource constraint scheduling with a fractional shared resource. Oper. Res. Lett. 39 (2011) 363–368. | MR | Zbl

A. Thomas, G. Singh, M. Krishnamoorthy and J. Venkateswaran, Distributed optimisation method for multi-resource constrained scheduling in coal supply chains. Int. J. Prod. Res. 51 (2013) 2740–2759. | DOI

M.L. Fisher, The lagrangian relaxation method for solving integer programming problems. Manag. Sci. 50 (2004) 1861–1871. | DOI | Zbl

F. Barahona and R. Anbil, The volume algorithm: producing primal solutions with a subgradient method. Math. Program. 87 (2000) 385–399. | DOI | MR | Zbl

Cité par Sources :