Integrated optimization of sequential processes : general analysis and application to public transport

Planning in public transportation is traditionally done in a sequential process: After the network design process, the lines and their frequencies are planned. When these are fixed, a timetable is determined and based on the timetable, the vehicle and crew schedules are optimized. After each step, passenger routes are adapted to model the behavior of the passengers as realistically as possible. It has been mentioned in many publications that such a sequential process is sub-optimal, and integrated approaches, mainly heuristics, are under consideration. Sequential planning is not only common in public transportation planning but also in many other applied problems, among others in supply chain management, or in organizing hospitals efficiently. The contribution of this paper hence is two-fold: on the one hand, we develop an integrated integer programming formulation for the three planning stages line planning, (periodic) timetabling, and vehicle scheduling which also includes the integrated optimization of the passenger routes. This gives us an exact formulation rewriting the sequential approach as an integrated problem. We discuss properties of the integrated formulation and apply it experimentally to data sets from the LinTim library. On small examples, we get an exact optimal objective function value for the integrated formulation which can be compared with the outcome of the sequential process. On the other hand, we propose a mathematical formulation for general sequential processes which can be used to build integrated formulations. For comparing sequential processes with their integrated counterparts we analyze the price of sequentiality, i.e., the ratio between the solution obtained by the sequential process and an integrated solution. We also experiment with different possibilities for partial integration of a subset of the sequential problems and again illustrate our results using the case of public transportation. The obtained results may be useful for other sequential processes.