Résumé
Quantum computing has been a ground-breaking domain for several years. Its new computational paradigm promises to impact the railway transports domain through quantum algorithms that solve hard combinatorial problems where a good or optimal solution is needed. It could open interesting applications for hard real-time problems, integrated problems, etc. Thus, it is crucial to study the type of railway decision or optimization problems quantum computation could tackle and to what extent their solving could be improved. In this paper, we characterize the quantum approaches over classical methods on a problem of optimal timetabling design. This problem consists of finding the transportation plan maximizing the operating profit according to the customers' demand and the availability and cost of the network and the rolling stock. The combinatorial complexity of this problem prevents its efficient solving by current classical computers on large perimeters. Quantum computers could overcome this issue and provide better solutions within less time. We present two families of quantum algorithms for solving combinatorial problems: meta-heuristics (Quantum Approximate Optimization Algorithm, Quantum Annealing) and exact search algorithms (Grover's algorithm). First, we simplify the initial timetabling problem so that the current quantum technology can handle it. Then, we reformulate it for each kind of algorithm. Finally, a small case study and a real-life instance illustrate the implementation of quantum algorithms on available quantum devices.