Prepositioning can improve the performance of a dynamic stochastic on-demand public bus system

This paper presents the first application of prepositioning in the context of the dynamic stochastic on-demand bus routing problem (DODBRP). The DODBRP is a large-scale dial-a-ride problem that involves bus station assignment and aims to minimize the total user ride time (URT) by simultaneously assigning passengers to alternative stations and determining optimal bus routes. In the DODBRP, transportation requests are introduced dynamically, and buses are dispatched to stations with known requests. This paper investigates the concept of prepositioning, which involves sending buses not only to currently known requests but also to requests that are likely to appear in the future, based on a given probability. To solve this dynamic and stochastic ODBRP, the paper proposes a heuristic algorithm based on variable neighborhood search (VNS). The algorithm considers multiple scenarios to represent different realizations of the stochastic requests. Experimental results demonstrate the superiority of the prepositioning approach over the DODBRP across various levels of forecast accuracy, lengths of time bucket, and probabilities of realization. Furthermore, the paper shows that removing empty stations as a recourse action can further enhance solution quality. Additionally, in situations with low prediction accuracy, increasing the number of scenarios can lead to improved solutions. Finally, a combination of prepositioning, empty station removal, and the insertion of dynamic requests proves to be effective. Overall, the findings of this paper provide valuable insights into the application of prepositioning in the dynamic stochastic on-demand bus routing problem, highlighting its potential for addressing real-world transportation challenges.