Dynamic vehicle routing problem for flexible buses considering stochastic requests. (March 2023) - Ma, Wanjing; Zeng, Lin; An, Kun
Highlights: A demand responsive flexible bus system is proposed using minibuses and the bus route changes in real-time to service the dynamic demand. A two-stage stochastic programming model with recourse is constructed to handle the dynamic current requests and stochastic future requests. A vector-similarity-based clustering and adaptive large neighborhood searching solution algorithm is proposed to solve the problem. The proposed framework is tested under four real cases in Shanghai based on the taxi order data. Abstract: Flexible buses provide on-demand services to one or more local communities in a specific geographical area. Bus routes can be adjusted dynamically according to real-time passenger demand in a cost-effective manner. This study investigated the dynamic bus-routing problem considering stochastic future passenger demand. A two-stage stochastic programming model was formulated to minimise the total vehicle travel time cost and penalty for rejecting requests. A rolling horizon scheme was adopted to handle the dynamic changes in passenger requests and vehicle routes. A vector-similarity-based clustering and adaptive large neighbourhood searching (VSC-ALNS) algorithm was developed to solve this problem. Vehicles and passengers were matched and clustered into groups based on vector similarity, and vehicle routes were generated using an adaptive large-neighbourhood search algorithm for each cluster. The effectiveness of the proposed method was evaluated in four cases with different demand intensities using Shanghai taxi order data. The results indicate that flexible buses are more suitable for moderate demand cases, ranging from 20 to 50 requests per square kilometre per hour.