Periodic Stop Skipping: NP-hardness and computational limitations.

Research output: Contribution to conferencePaperpeer-review

59 Downloads (Pure)


Stop-skipping (also known as expressing) is a typical control strategy in public transit operations with a dual objective: (i) reduce the trip delays, and (ii) improve the travel times of onboard passengers. Stop-skipping approaches decide about the stop-skipping strategy of each bus trip in isolation, neglecting the effect of the skipped stops to future trips. To rectify this, we introduce a rolling-horizon stop-skipping model that determines the skipped stops of several trips within a
rolling horizon. Then, we model the rolling-horizon stop-skipping problem as an integer nonlinear program, and we prove that it is an NP-Hard problem which can be solved to global optimality for small-scale scenarios. Extensive numerical experiments in a high frequency bus line in Singapore investigate the number of trips that can be optimized in a rolling horizon subject to the number of candidate stops that can be skipped. This investigation reveals the computational limitations of this problem and provides useful lessons to public transport practitioners that want to introduce periodic stop-skipping control to their daily operations.
Original languageEnglish
Number of pages23
Publication statusPublished - Jan 2020
Event99th Transportation Research Board (TRB) Annual Meeting 2020 - Walter E. Washington Convention Center, Washington, United States
Duration: 12 Jan 202016 Jan 2020
Conference number: 99


Conference99th Transportation Research Board (TRB) Annual Meeting 2020
Abbreviated titleTRB 2020
CountryUnited States
Internet address


Dive into the research topics of 'Periodic Stop Skipping: NP-hardness and computational limitations.'. Together they form a unique fingerprint.

Cite this