6454
eng
reportzib
0
--
2017-07-17
--
Demand-Driven Line Planning with Selfish Routing
Bus rapid transit systems in developing and newly industrialized countries are often operated at the limits of passenger capacity. In particular, demand during morning and afternoon peaks is hardly or even not covered with available line plans. In order to develop demand-driven line plans, we use two mathematical models in the form of integer programming problem formulations. While the actual demand data is specified with origin-destination pairs, the arc-based model considers the demand over the arcs derived from the origin-destination demand. In order to test the accuracy of the models in terms of demand satisfaction, we simulate the optimal solutions and compare number of transfers and travel times. We also question the effect of a selfish route choice behavior which in theory results in a Braess-like paradox by increasing the number of transfers when system capacity is increased with additional lines.
1438-0064
urn:nbn:de:0297-zib-64547
10.1007/978-3-319-89920-6_91
appeared in: Operations Research Proceedings 2017
Malte Renken
Thomas Schlechte
Amin Ahmadi
Ralf Borndörfer
Guvenc Sahin
Thomas Schlechte
ZIB-Report
17-38
OPERATIONS RESEARCH, MATHEMATICAL PROGRAMMING
Mathematical Optimization
Borndörfer, Ralf
Schlechte, Thomas
ECMath-MI3
MODAL-RailLab
MODAL-Gesamt
ECMath-MI7
https://opus4.kobv.de/opus4-zib/files/6454/ZR-17-38.pdf
6491
2017
eng
235
241
conferenceobject
0
--
--
--
Line Planning on Path Networks with Application to the Istanbul Metrobüs
Bus rapid transit systems in developing and newly industrialized countries often consist of a trunk with a path topology. On this trunk, several overlapping lines are operated
which provide direct connections. The demand varies heavily over the day, with morning and afternoon peaks typically in reverse directions. We propose an integer programming model for this problem, derive a structural property of line plans in the static (or single period) ``unimodal demand'' case, and consider approaches to the solution of the multi-period version that rely on clustering the demand into peak and off-peak service periods. An application to the Metrobüs system of Istanbul is discussed.
Operations Research Proceedings 2016
10.1007/978-3-319-55702-1_32
yes
urn:nbn:de:0297-zib-60119
Ralf Borndörfer
Thomas Schlechte
Oytun Arslan
Ziena Elijazyfer
Hakan Güler
Malte Renken
Guvenc Sahin
Thomas Schlechte
Mathematical Optimization
Borndörfer, Ralf
Schlechte, Thomas
ECMath-MI3
MODAL-RailLab
MODAL-Gesamt
6011
eng
reportzib
0
--
2016-09-08
--
Line Planning on Path Networks with Application to the Istanbul Metrobüs
Bus rapid transit systems in developing and newly
industrialized countries often consist of a trunk with a path
topology. On this trunk, several overlapping lines are operated
which provide direct connections. The demand varies heavily over the
day, with morning and afternoon peaks typically in reverse
directions. We propose an integer programming
model for this problem, derive a structural property of line plans
in the static (or single period) ``unimodal demand'' case, and
consider approaches to the solution of the multi-period version that
rely on clustering the demand into peak and off-peak service
periods. An application to the Metrobüs system of Istanbul is
discussed.
1438-0064
urn:nbn:de:0297-zib-60119
Ralf Borndörfer
Thomas Schlechte
Oytun Arslan
Ziena Elijazyfer
Hakan Güler
Malte Renken
Güvenc Sahin
Thomas Schlechte
ZIB-Report
16-38
eng
uncontrolled
line planning
eng
uncontrolled
unimodal demand
OPERATIONS RESEARCH, MATHEMATICAL PROGRAMMING
Mathematical Optimization
Borndörfer, Ralf
Schlechte, Thomas
ECMath-MI3
https://opus4.kobv.de/opus4-zib/files/6011/ZR-16-38.pdf
7466
eng
reportzib
0
--
2019-09-11
--
Multi-Period Line Planning with Resource Transfers
Urban transportation systems are subject to a high level of variation and fluctuation in demand over the day. When this variation and fluctuation are observed in both time and space, it is crucial to develop line plans that are responsive to demand. A multi-period line planning approach that considers a changing demand during the planning horizon is proposed. If such systems are also subject to limitations of resources, a dynamic transfer of resources from one line to another throughout the planning horizon should also be considered. A mathematical modelling framework is developed to solve the line planning problem with transfer of resources during a finite length planning horizon of multiple periods. We analyze whether or not multi-period solutions outperform single period solutions in terms of feasibility and relevant costs. The importance of demand variation on multi-period solutions is investigated. We evaluate the impact of resource transfer constraints on the effectiveness of solutions. We also study the effect of line type designs and question the choice of period lengths along with the problem parameters that are significant for and sensitive to the optimality of solutions.
1438-0064
urn:nbn:de:0297-zib-74662
Guvenc Sahin
Thomas Schlechte
Amin Ahmadi
Ralf Borndörfer
Thomas Schlechte
ZIB-Report
19-51
OPERATIONS RESEARCH, MATHEMATICAL PROGRAMMING
Mathematical Optimization
Borndörfer, Ralf
Schlechte, Thomas
MODAL-RailLab
MODAL-Gesamt
ECMath-MI7
https://opus4.kobv.de/opus4-zib/files/7466/ZR-19-51.pdf
7075
2018
eng
687
692
conferenceobject
Springer International Publishing
0
--
--
--
Demand-Driven Line Planning with Selfish Routing
Bus rapid transit systems in developing and newly industrialized countries are often operated at the limits of passenger capacity. In particular, demand during morning and afternoon peaks is hardly or even not covered with available line plans. In order to develop demand-driven line plans, we use two mathematical models in the form of integer programming problem formulations. While the actual demand data is specified with origin-destination pairs, the arc-based model considers the demand over the arcs derived from the origin-destination demand. In order to test the accuracy of the models in terms of demand satisfaction, we simulate the optimal solutions and compare number of transfers and travel times. We also question the effect of a selfish route choice behavior which in theory results in a Braess-like paradox by increasing the number of transfers when system capacity is increased with additional lines.
Operations Research Proceedings 2017
10.1007/978-3-319-89920-6_91
yes
urn:nbn:de:0297-zib-64547
Malte Renken
Niels Lindner
Amin Ahmadi
Ralf Borndörfer
Guvenc Sahin
Thomas Schlechte
Mathematical Optimization
Borndörfer, Ralf
Schlechte, Thomas
MODAL-RailLab
MODAL-Gesamt
ECMath-MI7
8406
2021
2021
eng
17:1
17:6
96
article
0
2021-09-27
--
--
Efficient Algorithms for the Multi-Period Line Planning Problem in Public Transportation
In order to plan and schedule a demand-responsive public transportation system, both temporal and spatial changes in demand should be taken into account even at the line planning stage. We study the multi-period line planning problem with integrated decisions regarding dynamic allocation of vehicles among the lines. Given the NP-hard nature of the line planning problem, the multi-period version is clearly difficult to solve for large public transit networks even with advanced solvers. It becomes necessary to develop algorithms that are capable of solving even the very-large instances in reasonable time. For instances which belong to real public transit networks, we present results of a heuristic local branching algorithm and an exact approach based on constraint propagation.
Open Access Series in Informatics (OASIcs), 21st Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2021)
10.4230/OASIcs.ATMOS.2021.17
yes
publish
Guvenc Sahin
Ralf Borndörfer
Amin Ahmadi Digehsara
Ralf Borndörfer
Mathematical Optimization
Borndörfer, Ralf
Network Optimization
MODAL-MobilityLab
8039
2020
eng
102726
119
article
0
--
--
--
Multi-period line planning with resource transfers
Urban transportation systems are subject to a high level of variation and fluctuation in demand over the day. When this variation and fluctuation are observed in both time and space, it is crucial to develop line plans that are responsive to demand. A multi-period line planning approach that considers a changing demand during the planning horizon is proposed. If such systems are also subject to limitations of resources, a dynamic transfer of resources from one line to another throughout the planning horizon should also be considered. A mathematical modelling framework is developed to solve the line planning problem with a cost-oriented approach considering transfer of resources during a finite length planning horizon of multiple periods. We use real-life public transportation network data for our computational results. We analyze whether or not multi-period solutions outperform single period solutions in terms of feasibility and relevant costs. The importance of demand variation on multi-period solutions is investigated. We evaluate the impact of resource transfer constraints on the effectiveness of solutions. We also study the effect of period lengths along with the problem parameters that are significant for and sensitive to the optimality of solutions.
Transportation Research Part C: Emerging Technologies
10.1016/j.trc.2020.102726
yes
2020-07-13
urn:nbn:de:0297-zib-74662
Ralf Borndörfer
Guvenc Sahin
Amin Ahmadi
Ralf Borndörfer
Thomas Schlechte
Mathematical Optimization
Borndörfer, Ralf
Schlechte, Thomas
MATHEON-B15
MODAL-RailLab
MODAL-Gesamt
MathPlus-Incubator-Timetabling
Network Optimization
MODAL-MobilityLab
9282
2023
eng
1
6
bookpart
Springer International Publishing
Cham
0
--
--
--
Line Planning Problem
Encyclopedia of Optimization
978-3-030-54621-2
10.1007/978-3-030-54621-2_782-1
yes
publish
false
true
Güvenç Şahin
Niels Lindner
P. M. Pardalos
Niels Lindner
O. A. Prokopyev
Thomas Schlechte
Schlechte, Thomas
Lindner, Niels
Network Optimization
SymLPP