Ifsttar PhD subject

French version
Detailed form :

Title : Models and algorithms for the optimised management of a freight yard

Main host Laboratory - Referent Advisor COSYS - ESTAS  -  RODRIGUEZ Joaquin      tél. : +33 320438332

Director of the main host Laboratory RODRIGUEZ Joaquin  -

Laboratory 2 - Referent Advisor COSYS - LEOST  -  PELLEGRINI Paola  -    -  tél. : +33 320438404

PhD Speciality Informatique et Recherche Opérationnelle

Axis of the performance contract 1 - COP2017 - Efficient transport and safe travel

Main location Lille-Villeneuve d'Ascq

Doctoral affiliation ECOLE CENTRALE LILLE

PhD school MADIS

Planned PhD supervisor RODRIGUEZ Joaquin  -  Université Gustave Eiffel  -  COSYS - ESTAS

Planned PhD co-supervisor PELLEGRINI Paola  -  Université Gustave Eiffel  -  COSYS - ESTAS

Planned financing Contrat doctoral  - Université Gustave Eiffel

Abstract

Context:
Freight transportation is a key subject for sustainable growth. The volume of French railway freight transportation has heavily declined from a volume of 75 billion t.km in 1974 down to 40 billion t.km in 2005. However, projections from the IEA predict a 43% increase between 2017 and 2050 (International Energy Agency (2019)). Numerous initiatives have been recently promoted to boost railway freight transportation and make it more competitive. One crucial element for this purpose is the management of operations in freight yards, in order to minimise the travel time of goods and maximise the system reliability. Such yards are often complex infrastructures where many interdependent operational decisions must be taken at regular intervals, often using basic rules adopted empirically. Moreover, these decisions make up for difficult problems computaionally speaking.
Moreover, the specific decisions to be taken depend on the topology of the yard and the type of operations it must undertake, which can vary greatly from yard to yard. We can indeed distinguish two main types of yards with very different structure: on the one hand shunting yards must handle wagons which will be decoupled, pushed over a hump and reassembled on classification tracks to form new outbound trains (Boysen et al (2012)); while on the other hand, transshipment yards will handle standardised containers which are transfered from one mean of transportation to another (rail-rail, rail-road, rail-sea) by specific cranes and rail-cars (Boysen et al (2013)).

PhD objectives:
The subject of this PhD is to propose mathematical models and optimisation algorithms for an efficient management of a generic freight yard, over all its operational aspects. It will take place in the Traffic group of laboratories ESTAS and LEOST. Such a generic approach does not exist yet in the scientific literature, due to two main difficulties:
1) The sometimes important difference in the organisation of freight yards makes it a difficult task to provide a unified mathematical model which can take into account all their specificities.
2) The integrated management of all yard operations presents a great computational complexity. Indeed, the number of decision variables and constraints is quite large when all operational subproblems are considered simultaneously. Each such subproblem has been shown to be NP-hard (see, e.g., Fedtke and Boysen (2017)), which makes the whole problem particulary complex to solve.

State of the art:
The theme of yard management has been explored by several works in the literature but with clear limitations from the operational point of view.
First of all, existing approaches are limited to studying one or two (rarely three) subproblems, independently from the others. For example, Cichenski et al. (2017) treat at the same time the problems of trains partitioning for occupying the tracks under the cranes, trains positioning on the traks and containers location on those trains. Nevertheless, the management of cranes and rail-cars operations is ignored, even though it is highly impacted by the previous subproblems.
Second of all, most approaches focus on a specific yard topology. Concrete solutions to formulate optimisation algorithms for different yard layouts have been proposed during the european project OPTIYARD (financed by the H2020 program under the Joint Undertaking Shift2Rail) which involved the Traffic group supervising the PhD. The project aimed at the optimised management of a freight yard (Licciardello et al. (2020)): a generic modelling of the yard resources allowed us to consider both a shunting yard and a rail-sea transhipment yard, using a constrained task scheduling framework to handle the yard resources. We developed a stochastic greedy algorithm which was integrated to a closed loop with a microscopic simulator to verify the feasibility of the selected solutions.

Methodology:
The PhD will be based on the results from the project OPTIYARD, using its unified modelling framework. It will first consider mathematical programming tools, which is a powerful and consolidated methodology. These tools will need to handle several problems in an integrated manner, which produces a large number of variables and constraints. A yet unexplored possibility is to use advanced mathematical programming methods which allow for a decomposition into a master and a slave problem and to exploit existing methods to solve each subproblem. We propose to explore the use of Column Generation or Benders Decomposition for which the Traffic team exhibits a recognised competence (Keita et al (2020), Hosteins and Scatamacchia (2020)).
Afterwards, the PhD will tackle the yard management problem in its dynamic version, i.e. by recomputing regularly solutions when new incoming trains are announced. This situation implies frequent reoptimisations and defines a real-time problem, which calls for the very quick production of operational solutions. Such problems require the use of heuristic algorithms which do not require to find the optimal solution. When the yard resources are limited, heuristic algorithms tend to have difficulties to produce feasible solutions, so that adapted strategies will need to be devised to treat the problem efficiently. The Traffic team has advanced skills for real-time railway optimisation problems, demonstrated within the european projects ONTIME (Quaglietta et al (2016)) and OPTIYARD (Licciardello et al (2020)), which will be useful to conceive efficient heuristic algorithms.

Working plan:
The PhD will start with the study of the state-of-the-art regarding optimisation methods for freight yards. It will then start on building on the results of the OPTIYARD project by implementing a mixed integer linear model to solve the unified yard model. Advanced mathematical programming methods will be developed to handle the resolution of this complex problem and heuristic algorithms will be devised to provide real-time solutions in an operational context, if the exact approaches are not fast enough. Numerical experiments on real case studies will reveal the potential gain of these approaches on different yard configurations. The results will be divulged in national and international conferences (for example, MT-ITS - International Conference on Models and Technologies for Intelligent Transportation Systems). When the models and algorithms will reach a sufficient level of maturity, they will be published in international peer reviewed journals (e.g., Transportation Research Part B : Methodological, or IEEE Transactions on intelligent transportation systems).

Candidate's profile:
The candidate must have a Master in operational research, computer science, artificial intelligence, applied mathematics or an equivalent degree. Important prerequisites are good programming skills (preferably C++ language) and a good level of english (written and oral). Knowledge of tools and softwares for mathematical programming or railway transportation will be a plus.

Bibliography

N. Boysen et al (2012), Shunting yard operations: Theoretical aspects and applications, European Journal of Operational Research, 220(1):1–14.
N. Boysen et al (2013), A survey on container processing in railway yards, Transportation Science, 47(3):312–329.
M. Cichenski et al (2017), An integrated model for the transshipment yard scheduling problem. Journal of Scheduling, 20:57–65.
S. Fedtke and N. Boysen (2017), Gantry crane and shuttle car scheduling in modern rail–rail transshipment yards, OR Spectrum, 39:473–503.
P. Hosteins and R. Scatamacchia (2020), The stochastic Critical Node Problem over trees, Networks, 76(3):381–401.
International Energy Agency (2019), The Future of Rail Opportunities for energy and the environment.
K. Keita, P. Pellegrini, J. Rodriguez (2020), A three-step Benders decomposition for the real-time Railway Traffic Management Problem, Journal of Rail Transport Planning and Management, 13:100170.
R. Licciardello, N. Adamko, S. Deleplanque, P. Hosteins, R. Liu, P. Pellegrini, A. Peterson, M. Wahlborg, M. Za’tko (2020), Integrating yards, network and optimisation models towards real-time rail freight yard operations, Ingegneria Ferroviaria, 75(6):417–447.
E. Quaglietta et al (2016), The ON-TIME real-time railway traffic management framework: A proof-of-concept using a scalable standardised data communication architecture, Transportation Research Part C: Emerging Technologies, 63:23-50.

Keywords : Freight yards, railway infrastructures, resource management, optimisation, dynamic algorithms

Main host Laboratory - Referent Advisor	COSYS - ESTAS - RODRIGUEZ Joaquin tél. : +33 320438332
Director of the main host Laboratory	RODRIGUEZ Joaquin -
Laboratory 2 - Referent Advisor	COSYS - LEOST - PELLEGRINI Paola - - tél. : +33 320438404
PhD Speciality	Informatique et Recherche Opérationnelle
Axis of the performance contract	1 - COP2017 - Efficient transport and safe travel
Main location	Lille-Villeneuve d'Ascq
Doctoral affiliation	ECOLE CENTRALE LILLE
PhD school	MADIS
Planned PhD supervisor	RODRIGUEZ Joaquin - Université Gustave Eiffel - COSYS - ESTAS
Planned PhD co-supervisor	PELLEGRINI Paola - Université Gustave Eiffel - COSYS - ESTAS
Planned financing	Contrat doctoral - Université Gustave Eiffel
Abstract Context: Freight transportation is a key subject for sustainable growth. The volume of French railway freight transportation has heavily declined from a volume of 75 billion t.km in 1974 down to 40 billion t.km in 2005. However, projections from the IEA predict a 43% increase between 2017 and 2050 (International Energy Agency (2019)). Numerous initiatives have been recently promoted to boost railway freight transportation and make it more competitive. One crucial element for this purpose is the management of operations in freight yards, in order to minimise the travel time of goods and maximise the system reliability. Such yards are often complex infrastructures where many interdependent operational decisions must be taken at regular intervals, often using basic rules adopted empirically. Moreover, these decisions make up for difficult problems computaionally speaking. Moreover, the specific decisions to be taken depend on the topology of the yard and the type of operations it must undertake, which can vary greatly from yard to yard. We can indeed distinguish two main types of yards with very different structure: on the one hand shunting yards must handle wagons which will be decoupled, pushed over a hump and reassembled on classification tracks to form new outbound trains (Boysen et al (2012)); while on the other hand, transshipment yards will handle standardised containers which are transfered from one mean of transportation to another (rail-rail, rail-road, rail-sea) by specific cranes and rail-cars (Boysen et al (2013)). PhD objectives: The subject of this PhD is to propose mathematical models and optimisation algorithms for an efficient management of a generic freight yard, over all its operational aspects. It will take place in the Traffic group of laboratories ESTAS and LEOST. Such a generic approach does not exist yet in the scientific literature, due to two main difficulties: 1) The sometimes important difference in the organisation of freight yards makes it a difficult task to provide a unified mathematical model which can take into account all their specificities. 2) The integrated management of all yard operations presents a great computational complexity. Indeed, the number of decision variables and constraints is quite large when all operational subproblems are considered simultaneously. Each such subproblem has been shown to be NP-hard (see, e.g., Fedtke and Boysen (2017)), which makes the whole problem particulary complex to solve. State of the art: The theme of yard management has been explored by several works in the literature but with clear limitations from the operational point of view. First of all, existing approaches are limited to studying one or two (rarely three) subproblems, independently from the others. For example, Cichenski et al. (2017) treat at the same time the problems of trains partitioning for occupying the tracks under the cranes, trains positioning on the traks and containers location on those trains. Nevertheless, the management of cranes and rail-cars operations is ignored, even though it is highly impacted by the previous subproblems. Second of all, most approaches focus on a specific yard topology. Concrete solutions to formulate optimisation algorithms for different yard layouts have been proposed during the european project OPTIYARD (financed by the H2020 program under the Joint Undertaking Shift2Rail) which involved the Traffic group supervising the PhD. The project aimed at the optimised management of a freight yard (Licciardello et al. (2020)): a generic modelling of the yard resources allowed us to consider both a shunting yard and a rail-sea transhipment yard, using a constrained task scheduling framework to handle the yard resources. We developed a stochastic greedy algorithm which was integrated to a closed loop with a microscopic simulator to verify the feasibility of the selected solutions. Methodology: The PhD will be based on the results from the project OPTIYARD, using its unified modelling framework. It will first consider mathematical programming tools, which is a powerful and consolidated methodology. These tools will need to handle several problems in an integrated manner, which produces a large number of variables and constraints. A yet unexplored possibility is to use advanced mathematical programming methods which allow for a decomposition into a master and a slave problem and to exploit existing methods to solve each subproblem. We propose to explore the use of Column Generation or Benders Decomposition for which the Traffic team exhibits a recognised competence (Keita et al (2020), Hosteins and Scatamacchia (2020)). Afterwards, the PhD will tackle the yard management problem in its dynamic version, i.e. by recomputing regularly solutions when new incoming trains are announced. This situation implies frequent reoptimisations and defines a real-time problem, which calls for the very quick production of operational solutions. Such problems require the use of heuristic algorithms which do not require to find the optimal solution. When the yard resources are limited, heuristic algorithms tend to have difficulties to produce feasible solutions, so that adapted strategies will need to be devised to treat the problem efficiently. The Traffic team has advanced skills for real-time railway optimisation problems, demonstrated within the european projects ONTIME (Quaglietta et al (2016)) and OPTIYARD (Licciardello et al (2020)), which will be useful to conceive efficient heuristic algorithms. Working plan: The PhD will start with the study of the state-of-the-art regarding optimisation methods for freight yards. It will then start on building on the results of the OPTIYARD project by implementing a mixed integer linear model to solve the unified yard model. Advanced mathematical programming methods will be developed to handle the resolution of this complex problem and heuristic algorithms will be devised to provide real-time solutions in an operational context, if the exact approaches are not fast enough. Numerical experiments on real case studies will reveal the potential gain of these approaches on different yard configurations. The results will be divulged in national and international conferences (for example, MT-ITS - International Conference on Models and Technologies for Intelligent Transportation Systems). When the models and algorithms will reach a sufficient level of maturity, they will be published in international peer reviewed journals (e.g., Transportation Research Part B : Methodological, or IEEE Transactions on intelligent transportation systems). Candidate's profile: The candidate must have a Master in operational research, computer science, artificial intelligence, applied mathematics or an equivalent degree. Important prerequisites are good programming skills (preferably C++ language) and a good level of english (written and oral). Knowledge of tools and softwares for mathematical programming or railway transportation will be a plus. Bibliography N. Boysen et al (2012), Shunting yard operations: Theoretical aspects and applications, European Journal of Operational Research, 220(1):1–14. N. Boysen et al (2013), A survey on container processing in railway yards, Transportation Science, 47(3):312–329. M. Cichenski et al (2017), An integrated model for the transshipment yard scheduling problem. Journal of Scheduling, 20:57–65. S. Fedtke and N. Boysen (2017), Gantry crane and shuttle car scheduling in modern rail–rail transshipment yards, OR Spectrum, 39:473–503. P. Hosteins and R. Scatamacchia (2020), The stochastic Critical Node Problem over trees, Networks, 76(3):381–401. International Energy Agency (2019), The Future of Rail Opportunities for energy and the environment. K. Keita, P. Pellegrini, J. Rodriguez (2020), A three-step Benders decomposition for the real-time Railway Traffic Management Problem, Journal of Rail Transport Planning and Management, 13:100170. R. Licciardello, N. Adamko, S. Deleplanque, P. Hosteins, R. Liu, P. Pellegrini, A. Peterson, M. Wahlborg, M. Za’tko (2020), Integrating yards, network and optimisation models towards real-time rail freight yard operations, Ingegneria Ferroviaria, 75(6):417–447. E. Quaglietta et al (2016), The ON-TIME real-time railway traffic management framework: A proof-of-concept using a scalable standardised data communication architecture, Transportation Research Part C: Emerging Technologies, 63:23-50.
Keywords :	Freight yards, railway infrastructures, resource management, optimisation, dynamic algorithms

List of topics

Applications closed