On-demand bus routing problem with dynamic stochastic requests and prepositioning

Ying Lian, Flavien Lucas and Kenneth Sörensen

Working Papers from University of Antwerp, Faculty of Business and Economics

Abstract: The On-Demand Bus Routing Problem (ODBRP) is defined as a large-scale dial-a-ride problem with bus station assignment. Specifically, each passenger can have alternative stations to board and alight; then, station pairs with the smallest total User Ride Time (URT) are chosen for overall efficiency. In the dynamic ODBRP (DODBRP), buses are only dispatched to the stations with known requests. However, this paper considers prepositioning: buses are sent to stations where new requests are likely to appear if the expected number of served requests has increased consequently. A heuristic algorithm with variable neighborhood search (VNS) is proposed to solve this dynamic and stochastic ODBRP, with multiple scenarios representing different realizations of stochastic requests. Experimental data show the superiority of prepositioning compared to DODBRP. On average, 24.27% - 38.80% more passengers can be served with the use of prepositioning with a simultaneous reduction from 2.06% to 5.93% of the average URT. In addition, different parameters are investigated to test robustness, such as instance sizes, station distributions, ratios of dynamic requests, probabilities of stochastic requests, time windows, and levels of estimation accuracy of stochastic requests.

Keywords: Routing; Stochastic requests; Dynamic requests; Multiple scenarios; Prepositioning (search for similar items in EconPapers)
Pages: 24 pages
Date: 2022-05
New Economics Papers: this item is included in nep-dem, nep-tre and nep-ure
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (1)

Downloads: (external link)
https://repository.uantwerpen.be/docstore/d:irua:12521 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:ant:wpaper:2022004

Access Statistics for this paper

More papers in Working Papers from University of Antwerp, Faculty of Business and Economics Contact information at EDIRC.
Bibliographic data for series maintained by Joeri Nys ().