Optimization Methods for Customized Bus Routes in Random Environments

Abstract

The customized bus in operation faces numerous random factors that affect the service level and attractiveness to passengers. Therefore, this paper investigates the optimization problem of customized bus routes considering random vehicle travel times and the capability to respond to dynamic requests in real time. We developed a stochastic programming model that minimizes total cost and passenger travel time. The innovation lies in the model’s ability to respond to requests made by passengers during service and to model the randomness of vehicle travel times using a known distribution. Furthermore, we propose a heuristic algorithm combining the nondominated sorting genetic algorithm II (NSGA-II) and a variable neighborhood search operator. This algorithm starts by generating an optimized initial path based on initial reservation demands and then employs a dynamic adjustment mechanism to respond to real-time requests. The effectiveness and superiority of our algorithm are validated through an illustrative example. Finally, numerical experiments using taxi trajectory data demonstrate that considering both randomness and real-time aspects can significantly reduce the total cost and penalties for early and late arrivals and improve the bus service level.