Time-dependent customized bus routing problem of large transport terminals considering the impact of late passengers

Document Type

Journal Article

Publication Date


Subject Area

place - asia, place - urban, mode - bus, ridership - demand, planning - route design, planning - methods, economics - operating costs


Customized bus, Time-dependent, Late customer handling, Periodic optimization, Heuristics


Customized bus (CB) provides convenient door-to-door transportation services to passengers through a subscription-based model. To ease the problem of insufficient taxis and private hire services at large transport terminals, we propose and evaluate a customized CB service for railway stations and airports in China. The proposed CB problem considers a routing problem with time-dependent travel time and late-customers. A periodic optimization approach is adopted to periodically collect passenger demands, optimize customized bus routes for the period, and re-optimize the routes to cater to late-coming customers. The static problem for each period is modeled as a time-dependent customized bus routing problem with time windows and release date (TDCBRPTW-R), which is solved with a hybrid meta-heuristic algorithm combining adaptive large neighborhood search (ALNS) with variable neighborhood descent (VND). An acceleration method is developed for insertion feasibility check for the TDCBRPTW-R. The stability and accuracy of the proposed algorithm is evaluated in the numerical experiments derived from Solomon’s data set. For the periodic re-optimization procedure, four methods are proposed to handle late customers according to different application scenarios. The re-optimization procedure is tested on the road network in Chengdu with passenger data provided by Didi Chuxing. The experiments demonstrate that a loose time window allows the service to serve more passengers and reduces operational costs. Lastly, the experiments also show the effectiveness of the proposed methods in handling late customers.


Permission to publish the abstract has been given by Elsevier, copyright remains with them.


Transportation Research Part C Home Page: