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, p...
| Main Authors: | , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Elsevier
2022-01-01
|
| Series: | EURO Journal on Transportation and Logistics |
| Subjects: | |
| Online Access: | http://www.sciencedirect.com/science/article/pii/S2192437622000024 |
| _version_ | 1811179087346008064 |
|---|---|
| author | Philine Schiewe Anita Schöbel |
| author_facet | Philine Schiewe Anita Schöbel |
| author_sort | Philine Schiewe |
| collection | DOAJ |
| description | 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. |
| first_indexed | 2024-04-11T06:28:40Z |
| format | Article |
| id | doaj.art-c9e7d9cd663642d3ae4a56e50d2edca0 |
| institution | Directory Open Access Journal |
| issn | 2192-4384 |
| language | English |
| last_indexed | 2024-04-11T06:28:40Z |
| publishDate | 2022-01-01 |
| publisher | Elsevier |
| record_format | Article |
| series | EURO Journal on Transportation and Logistics |
| spelling | doaj.art-c9e7d9cd663642d3ae4a56e50d2edca02022-12-22T04:40:15ZengElsevierEURO Journal on Transportation and Logistics2192-43842022-01-0111100073Integrated optimization of sequential processes: General analysis and application to public transportPhiline Schiewe0Anita Schöbel1Department of Mathematics, Technische Universität Kaiserslautern, Paul-Ehrlich-Straße 14, 67663 Kaiserslautern, Germany; Corresponding author.Department of Mathematics, Technische Universität Kaiserslautern, Gottlieb-Daimler-Straße 48, 67663 Kaiserslautern, Germany; Faunhofer Institute for Industrial Mathematics ITWM, Fraunhofer Platz 1, 67663 Kaiserslautern, GermanyPlanning 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.http://www.sciencedirect.com/science/article/pii/S2192437622000024Public transport planningLine planningTimetableVehicle schedulingPassenger routesSequential process |
| spellingShingle | Philine Schiewe Anita Schöbel Integrated optimization of sequential processes: General analysis and application to public transport EURO Journal on Transportation and Logistics Public transport planning Line planning Timetable Vehicle scheduling Passenger routes Sequential process |
| title | Integrated optimization of sequential processes: General analysis and application to public transport |
| title_full | Integrated optimization of sequential processes: General analysis and application to public transport |
| title_fullStr | Integrated optimization of sequential processes: General analysis and application to public transport |
| title_full_unstemmed | Integrated optimization of sequential processes: General analysis and application to public transport |
| title_short | Integrated optimization of sequential processes: General analysis and application to public transport |
| title_sort | integrated optimization of sequential processes general analysis and application to public transport |
| topic | Public transport planning Line planning Timetable Vehicle scheduling Passenger routes Sequential process |
| url | http://www.sciencedirect.com/science/article/pii/S2192437622000024 |
| work_keys_str_mv | AT philineschiewe integratedoptimizationofsequentialprocessesgeneralanalysisandapplicationtopublictransport AT anitaschobel integratedoptimizationofsequentialprocessesgeneralanalysisandapplicationtopublictransport |