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

摘要

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.