×

zbMATH — the first resource for mathematics

Rail schedule optimisation in the Hunter valley coal chain. (English) Zbl 1310.90016
Summary: 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.

MSC:
90B06 Transportation, logistics and supply chain management
90B35 Deterministic scheduling theory in operations research
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] 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.
[2] 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. · Zbl 1253.90157 · doi:10.1016/j.ejor.2012.01.012
[3] J.-F. Cordeau, P. Toth and D. Vigo, A Survey of Optimization Models for Train Routing and Scheduling. Trans. Sci.32 (1998) 380-404. · Zbl 0987.90507 · doi:10.1287/trsc.32.4.380
[4] R. Lusby, J. Larsen, M. Ehrgott and D. Ryan, Railway track allocation: models and methods. OR Spectrum33 (2011) 843-883. · Zbl 1229.90037 · doi:10.1007/s00291-009-0189-0
[5] 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. · Zbl 1151.90594
[6] 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:10.1287/trsc.1050.0115
[7] 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:10.1287/trsc.1080.0247
[8] G.Şahin, R.K. Ahuja and C.B. Cunha, Integer programming based solution approaches for the train dispatching problem. Technical report, Sabanci University, 2010.
[9] S.Q. Liu and E. Kozan, Optimising a coal rail network under capacity constraints. Flexible Services and Manufacturing Journal23 (2011) 90-110. · Zbl 1230.90035 · doi:10.1007/s10696-010-9069-9
[10] 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:10.1287/trsc.1100.0362
[11] 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.
[12] 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. Networks55 (2010) 221-233. · Zbl 1200.90038
[13] E. Choi and D.-W. Tcha, A column generation approach to the heterogeneous fleet vehicle routing problem. Comput. Oper. Res.34 (2007) 2080-2095. · Zbl 1187.90094 · doi:10.1016/j.cor.2005.08.002
[14] 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. · Zbl 1169.90395 · doi:10.1016/j.dam.2008.06.021
[15] L.A. Wolsey and G.L. Nemhauser, Integer and combinatorial optimization. Wiley-Interscience. · Zbl 0944.90001
[16] G. Singh and A.T. Ernst, Resource constraint scheduling with a fractional shared resource. Oper. Res. Lett.39 (2011) 363-368. · Zbl 1235.90067
[17] 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:10.1080/00207543.2012.737955
[18] M.L. Fisher, The lagrangian relaxation method for solving integer programming problems. Manag. Sci.50 (2004) 1861-1871. · doi:10.1287/mnsc.1040.0263
[19] F. Barahona and R. Anbil, The volume algorithm: producing primal solutions with a subgradient method. Math. Program.87 (2000) 385-399. · Zbl 0961.90058 · doi:10.1007/s101070050002
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.