Optimization of Train Schedules
Typ
Examensarbete för masterexamen
Program
Publicerad
2020
Författare
Dahlén, Christoffer John
Mårtensson, Anton
Modellbyggare
Tidskriftstitel
ISSN
Volymtitel
Utgivare
Sammanfattning
Logistics and transportation are extremely important to modern society. In this thesis
we investigate how to optimize the pathing and scheduling of trains, particularly targeting
automated mining transports, what we call Path Conflict Resolution (PCR). A restriction
imposed is that solutions to this problem must be deadlock-free, which implies that trains may
not be treated separately but must be scheduled together. We approach this problem using a
combination of Alternative Graphs, Mixed Integer Linear Programming (MILP), and Variable
Neighbourhood Search (VNS), building upon previous work on the scheduling of passenger
trains. Our model extends the previous work by including additional complications in the
scheduling, different objective functions, modelling of train lengths and moving blocks, and
improvements in the MILP problem generation. We successfully schedule trains on a large
realistic rail network within acceptable computation times. The strongest improvement is the
development of couplings in the alternative graph, which in our experiments leads to a tenfold
reduction in the number of binary variables.
Beskrivning
Ämne/nyckelord
Trains, Routing, Scheduling, Mathematical Optimization, Stochastic Optimization, Mixed Integer Linear Programming, Variable Neighbourhood Search, Alternative Graphs