Optimisation of Freight Train Routes with Transshipments
(2025) In Bachelor’s Theses in Mathematical Sciences NUMK11 20251Centre for Mathematical Sciences
Mathematics (Faculty of Sciences)
- Abstract
- This thesis investigates a version of the Vehicle Routing Problem: The pickup and delivery problem with transshipments. The aim was to construct a mathematical model, that finds optimal rail freight train routes according to specific requirements used in the industry. One challenge was that transshipments - the process of a request order changing trains at an intermediary station - were necessary to model. Another challenge was that the pickup and delivery problem has NP-hard complexity, meaning a polynomial-time algorithm for finding a solution was not used. Assuming the unproven but widely accepted theoretical computer science idea that complexity class P!=NP, it is unlikely that there exists a polynomial-time algorithm for NP-hard... (More)
- This thesis investigates a version of the Vehicle Routing Problem: The pickup and delivery problem with transshipments. The aim was to construct a mathematical model, that finds optimal rail freight train routes according to specific requirements used in the industry. One challenge was that transshipments - the process of a request order changing trains at an intermediary station - were necessary to model. Another challenge was that the pickup and delivery problem has NP-hard complexity, meaning a polynomial-time algorithm for finding a solution was not used. Assuming the unproven but widely accepted theoretical computer science idea that complexity class P!=NP, it is unlikely that there exists a polynomial-time algorithm for NP-hard problems. Thus, it was of interest to test the scale of a problem that could be solved in sucient time. The problem was formulated as an integer programming problem, which yields exact solutions. The mathematical model was implemented in Python and solved using the Gurobi solver, which internally uses a branch-and-bound algorithm with the Simplex method to find optimal solutions. The computational times for small cases (up to 16 stations, 3 trains, 5 delivery orders) were up to several minutes. However, larger instances (50+ stations) have prohibitively long computational times, often exceeding 6 hours. This suggests that a different problem approach should be considered for any real-life applications. Instead of searching for an exact solution to an integer programming problem, it could be beneficial to manually implement an algorithm that uses heuristics (techniques to find ”good”, but not necessarily optimal solutions quickly). (Less)
- Popular Abstract
- For logistics and transportation companies, eciently moving goods is crucial to minimising costs. One of the core cost-saving strategies is to plan optimal routes for the vehicles that deliver the goods. Mathematical models can be tailored to meet various specific business requirements, hence, there is great potential for economic savings when using mathematical optimisation techniques.
This thesis deals with optimisation of rail freight routes and involves some mathematically challenging requirements, such as transshipments - the process of a request order changing trains at an intermediary station. Transshipments allow for nearby trains to move an order closer to its destination, even if the trains cannot deliver the order to its final... (More) - For logistics and transportation companies, eciently moving goods is crucial to minimising costs. One of the core cost-saving strategies is to plan optimal routes for the vehicles that deliver the goods. Mathematical models can be tailored to meet various specific business requirements, hence, there is great potential for economic savings when using mathematical optimisation techniques.
This thesis deals with optimisation of rail freight routes and involves some mathematically challenging requirements, such as transshipments - the process of a request order changing trains at an intermediary station. Transshipments allow for nearby trains to move an order closer to its destination, even if the trains cannot deliver the order to its final delivery location. Using this strategy, the same number of orders could potentially be delivered with fewer trains, or the overall train mileage could be reduced. The problem was formulated as an integer programming problem. Using numerical solvers, exact solutions (optimal routes for trains and wagons of an order) were obtained.
However, this exact solution method was only suitable for small problem instances with fewer stations, trains, and orders. For larger instances resembling real-life situations, computational times exceeded 6h, making the model im- practical in a real-life setting. Therefore, we conclude that adapting a different algorithm, which yields "good" enough solutions quickly, rather than perfect solutions very slowly, could be of greater practical and economic value. (Less)
Please use this url to cite or link to this publication:
http://lup.lub.lu.se/student-papers/record/9208403
- author
- Deksnys, Jonas LU
- supervisor
- organization
- course
- NUMK11 20251
- year
- 2025
- type
- M2 - Bachelor Degree
- subject
- keywords
- Vehicle routing, transshipments, branch and bound algorithm, simplex method
- publication/series
- Bachelor’s Theses in Mathematical Sciences
- report number
- LUNFNA-4065-2025
- ISSN
- 1654-6229
- other publication id
- 2025:K19
- language
- English
- id
- 9208403
- date added to LUP
- 2025-08-06 15:45:06
- date last changed
- 2025-08-06 15:45:06
@misc{9208403,
abstract = {{This thesis investigates a version of the Vehicle Routing Problem: The pickup and delivery problem with transshipments. The aim was to construct a mathematical model, that finds optimal rail freight train routes according to specific requirements used in the industry. One challenge was that transshipments - the process of a request order changing trains at an intermediary station - were necessary to model. Another challenge was that the pickup and delivery problem has NP-hard complexity, meaning a polynomial-time algorithm for finding a solution was not used. Assuming the unproven but widely accepted theoretical computer science idea that complexity class P!=NP, it is unlikely that there exists a polynomial-time algorithm for NP-hard problems. Thus, it was of interest to test the scale of a problem that could be solved in sucient time. The problem was formulated as an integer programming problem, which yields exact solutions. The mathematical model was implemented in Python and solved using the Gurobi solver, which internally uses a branch-and-bound algorithm with the Simplex method to find optimal solutions. The computational times for small cases (up to 16 stations, 3 trains, 5 delivery orders) were up to several minutes. However, larger instances (50+ stations) have prohibitively long computational times, often exceeding 6 hours. This suggests that a different problem approach should be considered for any real-life applications. Instead of searching for an exact solution to an integer programming problem, it could be beneficial to manually implement an algorithm that uses heuristics (techniques to find ”good”, but not necessarily optimal solutions quickly).}},
author = {{Deksnys, Jonas}},
issn = {{1654-6229}},
language = {{eng}},
note = {{Student Paper}},
series = {{Bachelor’s Theses in Mathematical Sciences}},
title = {{Optimisation of Freight Train Routes with Transshipments}},
year = {{2025}},
}