Skip to Main content Skip to Navigation

Quelques algorithmes de planification ferroviaire sur voie unique

Abstract : This thesis develops algorithms for rail transportation problems, conducted in relationship with the company Eurotunnel which operates the tunnel under the Channel. This partnership is a scientific chair with the École des Ponts et Chaussées, where this thesis was realized. We study three topics throughout the thesis: the first one is an operationalproblem faced by Eurotunnel, whereas the two other ones are prospective and theoretical problems inspired by their process.The planning process for rail transportation can be divided into several phases (demand estimation, line planning, scheduling of the departure times, rolling stock and crew planning). In a first part, we focus on the scheduling phase on a time interval, applied to the specific case of Eurotunnel. The objective is to compute the departure times of the trains for each of the two stations (Calais in France and Folkestone in England), satisfying operation constraints (security, loading, ...) and commercial agreements with their partners (Eurostar, ...). Moreover, taking into account the delays in the scheduling phase is essential to limit the propagation of the disturbances from train to train in the network. We develop scheduling algorithms for Eurotunnel taking into account the operation and commercial constraints, and the random distributions of the delays for each train. These algorithms use standard tools of Operations Research to model and solve these optimization problems.Pricing is a main issue for transportation companies. Many algorithms have been proposed to help airline companies to define optimized prices of the plane tickets for different classes of passengers. In a second part, we apply some standard pricing frameworks (discrete choice models) in order to optimize in a global way the prices and the departure times of the trains for rail transportation companies. Standard tools of stochastic optimization, discrete choice models, and some heuristics are used in our algorithms to compute the best possible solutions in a limited computation time.We focus in a last part on a class of transportation problems, inspired form Eurotunnel. We give efficient algorithms to solve exactly or to approximate the optimal solutions of these problems. These algorithms give an upper bound of the time complexity of this class of problems. The problems studied consist in scheduling the departure times of shuttles on a fixed trip, to transport passengers, arriving continuously at an initial station, to a given destination. The shuttles are potentially allowed to perform several rotations to transport several groups of passengers. The objective is to minimize the waiting time of the passengers before the depart of their shuttle. Original combinations of convex optimization and graph theory (shortest path problems) are used in our algorithms
Document type :
Complete list of metadata

Cited literature [72 references]  Display  Hide  Download
Contributor : ABES STAR :  Contact
Submitted on : Friday, May 11, 2018 - 6:11:05 PM
Last modification on : Thursday, May 16, 2019 - 6:00:39 PM
Long-term archiving on: : Monday, September 24, 2018 - 10:26:24 PM


Version validated by the jury (STAR)


  • HAL Id : tel-01790264, version 1



Laurent Daudet. Quelques algorithmes de planification ferroviaire sur voie unique. Optimisation et contrôle [math.OC]. Université Paris-Est, 2017. Français. ⟨NNT : 2017PESC1222⟩. ⟨tel-01790264⟩



Record views


Files downloads