Freight Train Threading with Different Algorithms
The problem addressed in this paper, of routing and scheduling freight trains within a scheduled passenger rail network, prevails in many large countries. The actual departure and arrival times of freight trains are not important, and nor are their routes
- PDF / 336,180 Bytes
- 17 Pages / 439.37 x 666.142 pts Page_size
- 66 Downloads / 220 Views
Faculty of Information Technology, Monash University, Wellinghton Road, Clayton, VIC 3800, Australia {ilankaikone.senthooran,mark.wallace}@monash.edu 2 Opturion pty ltd, Melbourne, VIC 3006, Australia [email protected]
Abstract. The problem addressed in this paper, of routing and scheduling freight trains within a scheduled passenger rail network, prevails in many large countries. The actual departure and arrival times of freight trains are not important, and nor are their routes. Only a starting station and destination station are specified on the day of travel. The current paper addresses the problem of how to thread the maximum number of freight trains through the passenger network, minimising the latest arrival time of the last freight train. This problem contrasts with the more traditional rail scheduling requirement of matching as closely as possible an ideal schedule. The rail network is modelled topologically, so the size of the network does not grow as the temporal granularity is made finer. Our use of the modelling language MiniZinc enables us to compare several different solvers and solving approaches applied to the model. In particular we investigate constraint programming, using global constraints and constraint propagation; mathematical programming naively, without using any of the decomposition techniques; and finally a hybrid of constraint propagation, learning, and dynamic search control called lazy clause generation. The paper describes two kinds of experiments. Firstly it gives results for a series of benchmark tests to investigate the flexibility and scalability of the algorithm, and secondly it is applied to a freight train scheduling problem on the Victorian rail network in Australia. Keywords: MiniZinc clause generation
1
·
Algorithms
·
Freight train scheduling
·
Lazy
Introduction
The demand for rail transport is increasing in many countries, both for passengers and freight. In Melbourne, passenger demand has been increasing at 10% per year. According to the European commission, a single freight train on a track can replace 280 trucks on a road, reducing fuel use, congestion, and emissions, and passenger travel by rail produces three to ten times less CO2 than cars or airplanes 1 . 1
http://ec.europa.eu/digital-agenda/futurium/en/content/trends-rail-transport
c Springer International Publishing Switzerland 2015 L. Michel (Ed.): CPAIOR 2015, LNCS 9075, pp. 393–409, 2015. DOI: 10.1007/978-3-319-18008-3 27
394
I. Senthooran et al.
Passenger trains run to a specific published timetable, planned months in advance, while freight trains are scheduled on-demand at shorter timescales. Passenger and freight trains often share the same rail network. The problem addressed in this paper, of routing and scheduling freight trains within a scheduled passenger rail network, prevails in many large countries. The actual departure and arrival times of freight trains are not important, and nor are their routes. Only a starting station and destination station are specified on the day of travel. The
Data Loading...
