Bus rescheduling in rolling horizons for regularity-based services

Research output: Contribution to journalArticleAcademicpeer-review

4 Downloads (Pure)

Abstract

Given the unstable nature of the bus operations, the regularity of the bus services cannot be maintained throughout the day. Especially in densely populated areas, the inherent variability of the trip travel times affects the regularity of the daily services since the arrival times of several trips at stops might oscillate significantly from their expected values. Because of the high level of uncertainty, this work proposes a periodic rescheduling of the dispatching times of the daily bus trips to adjust continuously to the operational changes. A key differentiator from previous works is that a periodic rescheduling does not focus only on the running buses, but also reschedules the dispatching times of all remaining daily trips while considering operational constraints related to layover times and capacity limits. Typical scheduling problems (such as a bus scheduling problem) are NP-hard because of the discrete nature of the decision variables. Hence, the computational burden prohibits their solution with analytical methods. Catering for capacity limits increases further the complexity of our problem because it results in a non-smooth objective function which is not differentiable at every point of its domain. For this reason, this work proposes a sequential hill climbing method to search the solution space more efficiently and reschedule the dispatching times of trips in near real time. This approach is tested using real-time data from bus line 15L in Denver, USA. Critical issues, such as to what extent can the periodic dispatching time rescheduling improve the regularity of daily operations, are investigated.
Original languageEnglish
Pages (from-to)1-20
JournalJournal of intelligent transportation systems
DOIs
Publication statusE-pub ahead of print/First online - 29 Oct 2019

Fingerprint

Rescheduling
Horizon
Dispatching
Regularity
Scheduling Problem
Scheduling
Nonsmooth Function
Hill Climbing
Time of Arrival
Travel Time
Travel time
Expected Value
Analytical Methods
Differentiable
Computational complexity
NP-complete problem
Objective function
Unstable
Real-time
Uncertainty

Cite this

@article{a6df5c6ded0c471c928bf176940e12cd,
title = "Bus rescheduling in rolling horizons for regularity-based services",
abstract = "Given the unstable nature of the bus operations, the regularity of the bus services cannot be maintained throughout the day. Especially in densely populated areas, the inherent variability of the trip travel times affects the regularity of the daily services since the arrival times of several trips at stops might oscillate significantly from their expected values. Because of the high level of uncertainty, this work proposes a periodic rescheduling of the dispatching times of the daily bus trips to adjust continuously to the operational changes. A key differentiator from previous works is that a periodic rescheduling does not focus only on the running buses, but also reschedules the dispatching times of all remaining daily trips while considering operational constraints related to layover times and capacity limits. Typical scheduling problems (such as a bus scheduling problem) are NP-hard because of the discrete nature of the decision variables. Hence, the computational burden prohibits their solution with analytical methods. Catering for capacity limits increases further the complexity of our problem because it results in a non-smooth objective function which is not differentiable at every point of its domain. For this reason, this work proposes a sequential hill climbing method to search the solution space more efficiently and reschedule the dispatching times of trips in near real time. This approach is tested using real-time data from bus line 15L in Denver, USA. Critical issues, such as to what extent can the periodic dispatching time rescheduling improve the regularity of daily operations, are investigated.",
author = "Konstantinos Gkiotsalitis",
year = "2019",
month = "10",
day = "29",
doi = "10.1080/15472450.2019.1681992",
language = "English",
pages = "1--20",
journal = "Journal of intelligent transportation systems",
issn = "1547-2450",
publisher = "Taylor & Francis",

}

Bus rescheduling in rolling horizons for regularity-based services. / Gkiotsalitis, Konstantinos.

In: Journal of intelligent transportation systems, 29.10.2019, p. 1-20.

Research output: Contribution to journalArticleAcademicpeer-review

TY - JOUR

T1 - Bus rescheduling in rolling horizons for regularity-based services

AU - Gkiotsalitis, Konstantinos

PY - 2019/10/29

Y1 - 2019/10/29

N2 - Given the unstable nature of the bus operations, the regularity of the bus services cannot be maintained throughout the day. Especially in densely populated areas, the inherent variability of the trip travel times affects the regularity of the daily services since the arrival times of several trips at stops might oscillate significantly from their expected values. Because of the high level of uncertainty, this work proposes a periodic rescheduling of the dispatching times of the daily bus trips to adjust continuously to the operational changes. A key differentiator from previous works is that a periodic rescheduling does not focus only on the running buses, but also reschedules the dispatching times of all remaining daily trips while considering operational constraints related to layover times and capacity limits. Typical scheduling problems (such as a bus scheduling problem) are NP-hard because of the discrete nature of the decision variables. Hence, the computational burden prohibits their solution with analytical methods. Catering for capacity limits increases further the complexity of our problem because it results in a non-smooth objective function which is not differentiable at every point of its domain. For this reason, this work proposes a sequential hill climbing method to search the solution space more efficiently and reschedule the dispatching times of trips in near real time. This approach is tested using real-time data from bus line 15L in Denver, USA. Critical issues, such as to what extent can the periodic dispatching time rescheduling improve the regularity of daily operations, are investigated.

AB - Given the unstable nature of the bus operations, the regularity of the bus services cannot be maintained throughout the day. Especially in densely populated areas, the inherent variability of the trip travel times affects the regularity of the daily services since the arrival times of several trips at stops might oscillate significantly from their expected values. Because of the high level of uncertainty, this work proposes a periodic rescheduling of the dispatching times of the daily bus trips to adjust continuously to the operational changes. A key differentiator from previous works is that a periodic rescheduling does not focus only on the running buses, but also reschedules the dispatching times of all remaining daily trips while considering operational constraints related to layover times and capacity limits. Typical scheduling problems (such as a bus scheduling problem) are NP-hard because of the discrete nature of the decision variables. Hence, the computational burden prohibits their solution with analytical methods. Catering for capacity limits increases further the complexity of our problem because it results in a non-smooth objective function which is not differentiable at every point of its domain. For this reason, this work proposes a sequential hill climbing method to search the solution space more efficiently and reschedule the dispatching times of trips in near real time. This approach is tested using real-time data from bus line 15L in Denver, USA. Critical issues, such as to what extent can the periodic dispatching time rescheduling improve the regularity of daily operations, are investigated.

U2 - 10.1080/15472450.2019.1681992

DO - 10.1080/15472450.2019.1681992

M3 - Article

SP - 1

EP - 20

JO - Journal of intelligent transportation systems

JF - Journal of intelligent transportation systems

SN - 1547-2450

ER -