Periodic Stop Skipping: NP-hardness and computational limitations.

Research output: Contribution to conferencePaper

24 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
EventTransportation Research Board (TRB) 99th Annual Meeting - Walter E. Washington Convention Center, Washinton, United States
Duration: 12 Jan 202016 Jan 2020
Conference number: 99


ConferenceTransportation Research Board (TRB) 99th Annual Meeting
Abbreviated titleTRB 2020
CountryUnited States
Internet address

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

  • Cite this

    Gkiotsalitis, K. (2020). Periodic Stop Skipping: NP-hardness and computational limitations.. Paper presented at Transportation Research Board (TRB) 99th Annual Meeting, Washinton, United States.