Joint optimization of multi-trip vehicle scheduling, passenger assignment, and timetable for on-demand customized bus services

On-demand customized bus (CB) services represent an emerging form of demand-responsive public transportation, providing unique advantages in addressing passengers’ diverse travel needs and advancing sustainable mobility. To enhance operational efficiency and improve passenger satisfaction, this paper investigates a new CB service problem. The goal is to minimize total vehicle operating costs and penalties for unserved orders by jointly optimizing multi-trip vehicle scheduling, passenger assignment, and timetabling. We first formulate the problem into a mixed-integer nonlinear programming model, which is then linearized into an equivalent one. To efficiently solve this model, we develop a tailored adaptive large neighborhood search algorithm, which incorporates a three-stage heuristic algorithm, a stop assignment strategy, and a set of customized operators. Extensive experiments on Sioux Falls and New York City cases validate the proposed algorithm’s effectiveness and efficiency. Furthermore, we demonstrate that multi-trip vehicle scheduling can reduce total costs compared to single-trip vehicle scheduling, with a reduction of 11.5%. Additionally, we derive management insights for CB operators by conducting sensitivity analysis experiments on critical parameters. Our findings indicate that adopting multi-trip scheduling, optimizing the number and spatial distribution of candidate stops, and adjusting trip frequency according to demand levels can effectively lower the operational costs of CB services.