OPtimal Scheduling for next-generation intelligent TRAnsport systems.

Scheduling consists in timing the movements of vehicles in transport systems. It appears at all level of the planning process: Strategical, to identify optimal infrastructure investments; Tactical, to establish robust timetables ensuring coordination among different modes of transport; and Operational, to allow re-planning in real-time to recover from delays and disruptions. Scheduling is performed by experts with little support from automatic tools. To implement such tools, one needs to develop optimization methods. Current methods can only tackle small instances but are still already showing the tremendous impact of optimization on system performance. The challenge is that the current technology does not scale well. We need new models/algorithms to tackle large scale instances of scheduling problems arising, e.g., in dispatching large networks as the Norwegian railway. Our objective in OPSTRA was to develop ground-breaking mathematical models and solution methods for scheduling problems in transportation. These models provide the foundations for new tools capable of tackling yet unsolvable instances arising in real-life systems. During the four years of the project, we managed to reach and go beyond the original goals. The basic mathematical models and results have been completed and published in class A (Norwegian level 2) journals. The main new modelling and algorithmic approach, called Path&Cycle formulation, is indeed outperforming classical approaches to scheduling problems in transportation. The basic model was developed in the contest of train dispatching and the founding paper appeared in the flagship journal of operations research analysis. This was extended in several directions. 1. Extensions to different transportation modes. We extended the original approach to tackle problems from air traffic control, namely different versions of the "hotspot problem". 2. Extensions to complex networks. As for the railway application, we have started extending the Path&Cycle approach to another critical problem in train re-scheduling, namely train dispatching in large stations. 3. Extensions to learning. A major development concerns the dynamic version of the traffic management problems addressed in our studies, where one must solve a sequence of instances over time. Then, at each iteration, we can exploit the computations performed in the previous iteration(s) to speed up the current solution process. We call it "combinatorial learning" because it somewhat learns the structure of the current problem from information collected during the past iterations. Our idea led to a significant improvement in performance when solving realistic instances of traffic management problems. Other, connected problems popped up, generating new questions, and triggering novel research lines. 1. Our Path&Cycle formulation is outperforming other more traditional approaches in our target application, namely train/airplane scheduling and re-scheduling. But there are individual transportation problems where it can still make sense to apply (revisited) traditional approaches: we did this by successfully applying a Time-Indexed formulation in scheduling and routing vessels in maritime surveillance. 2. Identifying spatial conflicts between vehicles is a central function of all automatic approaches to vehicle scheduling. We developed a new approach based on conflict diagrams to represent movements and conflicts. 3. The central element of transportation systems, often ignored in basic scheduling models, are passengers. We developed a novel approach to reschedule trains in metro-system during disruptions so to minimize expected waiting times for passengers queuing at the stations. 4. When routing and scheduling vehicles in transportation networks one may provoke "deadlocks", where vehicles prevent each other from proceeding. Deadlocks may require painful and costly human intervention and must be avoided. Identifying potential deadlocks is a hard-mathematical task. We developed new effective approaches to detect (and avoid) deadlocks: a. the tick formulation, which is a special version of time-indexed models, b. a specialization of the path&cycle formulation to deadlock detection, c. an ad-hoc, fast method for the case of two-train deadlocks. 5. For tackling large and congested networks like greater Oslo area, one needs to decompose the original problem into smaller problems and then recombine the solutions. We studied a "hub" decomposition approach, where the subproblems correspond to Oslo S and each of the lines incident to it. The high quality of the research produced during the project life is certified by the large number of publications on high-impact and flagship journals. Many algorithmic developments are embedded in software tools for scheduling trains in real-time and for tactical and strategic timetables. These tools were developed in cooperation with the national railway infrastructure manager.

For research. The basic model studied in the project is the only recent genuine alternative to the classical ones. This opens up for new research directions. With more than 15 scientists active in foreign institutions, the project allowed to build a strong international network and to disseminate the new ideas in the scientific community worldwide. For trade and industry. First, modeling and algorithmic developments carried out in the project are currently being implemented in software tools which will allow a significant reduction of workload for human operators and improvements in the quality of the plans. Better plans will imply greater satisfaction for transport customers and reduced environmental impact. The methodologies can be exported to other transportation modes (maritime transportation, drones, AGV), and to other real-life applications, for instance in the context of industrial production (for sequencing and scheduling processes on machines).

Our objective is to develop ground-breaking mathematical models and solution methods for scheduling problems in transport. They will provide the foundations for new tools capable of tackling yet unsolvable instances arising in real-life systems. The expected impact is remarkable, in terms of reduced costs, congestion and operators workload, improved reliability, punctuality, resilience to disruptions and quality of service. Scheduling consists in timing the movements of vehicles in transport systems. It appears at all level of the planning process: Strategical, to identify optimal infrastructure investments; Tactical, to establish robust timetables ensuring coordination among different modes of transport; Operational, to allow re-planning in real-time to recover from delays and disruptions. Scheduling is performed by experts with little support from automatic tools. To implement such tools one needs to develop optimization methods. Current methods can only tackle small instances, still already showing the tremendous impact of optimization on system performance. The current technology does not scale well. We need new models/algorithms to tackle large scale instances of scheduling problems arising, e.g., in dispatching large networks as the Norwegian railway (as required by Jernbaneverket in a current tender); or in coordinating multiple transport modes in freight corridors (e.g. Kiruna-Narvik-Rotterdam). Our research will be founded on three solid legs: 1. Very recently, our group developed a new, ground-breaking approach to scheduling problems in transport, which differs substantially from previous approaches. 2. We led research activities in international award winning projects on scheduling in railway and aviation, defining the state-of-the-art for these applications 3. We dispose of a large set of real-life instances from different applications: multi-mode transport in freight corridors, infrastructure planning in railway, surface scheduling in aviation.