On-Demand Customized Bus Line Optimization in Large-Scale Traffic Networks: A Column Generation Approach

As travel demand becomes more diversified and personalized, traditional bus operation struggles to meet the requirements of high-quality service. The customized bus, with its flexibility, has garnered significant attention. However, optimizing customized bus lines involves multiple decision variables. As the scale of transportation networks continues to expand, traditional methods struggle to find the optimal solution within a limited time. In this paper, we propose an innovative customized bus line optimization model and an efficient solving algorithm. In terms of modeling, we aim to maximize the number of passengers served by jointly optimizing bus routes, stop locations, departure time, and service capacity, while considering various constraints such as tolerance time to ensure the service efficiency of customized buses. Since the problem is intractable by exhaustive search, we design a column generation-based algorithm to acquire the optimal solution efficiently. We compare the proposed algorithm with direct solving using the Gurobi solver in small-scale, medium-scale, and large-scale scenarios. The experimental results show that the proposed algorithm can effectively find the optimal solution, even in the large-scale scenario where the Gurobi solver fails to deliver a solution.