Optimal on-demand bus operation with passenger split and time window flexibility under fare incentives

This paper investigates an optimal operation problem for on-demand bus services within an advanced demand-responsive service platform, where passengers reserve their trip requests online. Each request specifies the passenger’s pickup and dropoff locations, service time window, and number of passengers. To enhance bus utilization, the operator incentivizes passengers within the same request to accept split pickup or delivery services and tolerate limited time window violations by offering specific fare discounts. The problem is formulated as a mixed-integer model that jointly optimizes the route and schedule for each bus, with the objective of minimizing the total system cost. To address this problem, a time-window-backward-induction approach is initially introduced to efficiently formulate the bus schedule while accounting for time window flexibility. Building on this approach, a variable neighborhood search with customized operators is developed to optimize bus routes while adhering to bus capacity and time window constraints, particularly in scenarios involving passenger split pickups and deliveries. Algorithm comparisons across extended benchmark instances demonstrate the superior performance of the proposed algorithm in scenarios characterized by narrow time windows, high request volumes, and limited fleet sizes. Subsequently, large-scale experiments based on real-world ride-hailing data are conducted to provide managerial insights and guide operators in designing a cost-efficient on-demand bus system.