Heuristic approach for the multiobjective optimization of the customized bus scheduling problem

Abstract

Abstract Customized bus is a typical demand‐responsive transit (DRT) service that allows passengers to customize their bus route on demand and be picked up and dropped off at their desired location. A set of ride requests sent at various times by geographically dispersed passengers are operated in real time by the controller and then assigned to the shared bus with the assurance of maintaining the minimum vehicle and driver costs, which introduces a new challenge to scheduling. In this paper, a mixed integer linear programming (MILP) model is presented to solve the customized bus scheduling problem. To quickly generate satisfactory scheduling solutions in the case of single‐ and multi‐depots, a heuristic multi‐objective optimization algorithm based on preemptive scheduling is proposed, which can converge to the optimal solution among a set of vehicle blocks (consecutive trips by one bus). A real‐world customized bus scheduling problem from the public transport company of Chengdu, China that contains 2,000‐trip instances operated on a day is used to demonstrate that the proposed approach reduces total operating costs by 30.51% and 30.71%, compared with the simulated annealing algorithm and genetic algorithm, respectively.