Optimization of Customized Bus Routes with Spatial-Temporal Constraints under Multi-Depot Conditions

This study proposes a mixed integer programming model for the customized bus routing problem with full spatial-temporal constraints under multi-depot conditions. Specifically, taking vehicle fixed cost, route running cost, and penalty cost of unserved passengers as the optimization objective, considering constraints such as the number of unserved passengers, time window, route length, depot location, and customized bus service, this paper jointly models the process of depot location, passenger assignment, and vehicle scheduling. An efficient modified three-stage hybrid coding genetic algorithm is proposed to solve the formulated model. To study the performance of the algorithm under different station distribution scenarios, the centralized and decentralized distribution of the stations are considered, respectively. With two kinds of examples based on the Sioux Falls network, we validate the proposed model and solution algorithm compared with the branch-and-cut algorithm and conduct the sensitivity analysis.