Optimal routing and request selection for multiple service routes in a demand-adaptive transit system

Abstract

The demand-adaptive system (DAS) has been recognized as a promising transit mode for demand with high fluctuations. In this paper, we optimize the routes and request selection for a DAS with multiple service routes. Currently, most studies on DAS focus on optimizing single-route systems, where each area is exclusively served by one route and heuristic pre-assignations of requests are made. In contrast, our study addresses a more generalized routing and request selection problem for a DAS with multiple service routes. This problem jointly assigns requests to the service routes and determines the resulting routes while considering the pickup and delivery locations and the reserved boarding time for each request. A mixed-integer linear programming (MILP) model is developed to minimize the sum of bus travel time cost, passenger in-vehicle and waiting time costs, and request rejection penalties. A tailored adaptive large neighborhood search algorithm (ALNS) solves this optimization model efficiently. The numerical experiments show that, under the same optimality conditions, the proposed algorithm outperforms the exact algorithm implemented by GORUBI in terms of solution quality and computation time. The ALNS algorithm also reports cost reductions of up to 50% in comparison with prevailing benchmark metaheuristics. Moreover, the multi-route DAS in this paper has a lower rejection rate and objective value than the single-route systems examined in previous studies.

Graphical abstract

Keywords

demand-adaptive systems / multi-route design / request selection / adaptive large neighborhood search heuristic

References

[1] Becker J, Teal R, Mossige R, (2013). Metropolitan transit agency’s experience operating general-public demand-responsive transit. Transportation Research Record: Journal of the Transportation Research Board, 2352( 1): 136–145

[2] Bi H, Shang W L, Chen Y, Wang K, Yu Q, Sui Y, (2021). GIS aided sustainable urban road management with a unifying queueing and neural network model. Applied Energy, 291: 116818

[3] Bi H, Shang W L, Chen Y, Yu K, Ochieng W Y, (2022). An incentive based road traffic control mechanism for Covid-19 pandemic alike emergency preparedness and response. IEEE Transactions on Intelligent Transportation Systems, 23( 12): 25092–25105

[4] Chen P W, Nie Y M, (2017). Analysis of an idealized system of demand adaptive paired-line hybrid transit. Transportation Research Part B: Methodological, 102: 38–54

[5] Crainic T G, Errico F, Malucelli F, Nonato M, (2010). Designing the master schedule for demand-adaptive transit systems. Annals of Operations Research, 194( 1): 151–166

[6] Crainic T G, Malucelli F, Nonato M, Guertin F, (2005). Meta-heuristics for a class of demand-responsive transit systems. INFORMS Journal on Computing, 17( 1): 10–24

[7] Errico F, Crainic T G, Malucelli F, Nonato M, (2013). A survey on planning semi-flexible transit systems: Methodological issues and a unifying framework. Transportation Research Part C, Emerging Technologies, 36: 324–338

[8] Errico F, Crainic T G, Malucelli F, Nonato M, (2021). The single-line design problem for demand-adaptive transit systems: A modeling framework and decomposition approach for the stationary-demand case. Transportation Science, 55( 6): 1300–1321

[9] Fittante S R, Lubin A, (2016). Adapting the Swedish service route model to suburban transit in the United States. Transportation Research Record: Journal of the Transportation Research Board, 2563( 1): 52–59

[10] Fu L, (2002). Planning and design of flex-route transit services. Transportation Research Record: Journal of the Transportation Research Board, 1791( 1): 59–66

[11] Guo R, Guan W, Zhang W, (2018). Route design problem of customized buses: Mixed integer programming model and case study. Journal of Transportation Engineering. Part A: Systems, 144( 11): 1–1

[12] Ho S C, Szeto W Y, Kuo Y H, Leung J M, Petering M, Tou T W, (2018). A survey of dial-a-ride problems: Literature review and recent developments. Transportation Research Part B: Methodological, 111: 395–421

[13] Jin W, Du H, Wu W, (2023). Semi-flexible demand responsive transit scheduling based on ALNS-TS algorithm. Journal of Shenzhen University Science and Engineering, 40( 4): 425–434

[14] (Edward) Kim M, Levy J, Schonfeld P, (2019). Optimal zone sizes and headways for flexible-route bus services. Transportation Research Part B: Methodological, 130: 67–81

[15] KoffmanD (2004). Operational experiences with flexible transit services (No. 53). Washington, D.C.: Transportation Research Board

[16] Li M, Tang J, (2023). Simulation-based optimization considering energy consumption for assisted station locations to enhance flex-route transit. Energy, 277: 127715

[17] Li M, Tang J, Zeng J, Huang H, (2023a). A Kriging-based optimization method for meeting point locations to enhance flex-route transit services. Transportmetrica. B, Transport Dynamics, 11( 1): 1281–1310

[18] Li X, Huang J, Guan Y, Li Y, Yuan Y, (2022). Electric demand-responsive transit routing with opportunity charging strategy. Transportation Research Part D, Transport and Environment, 110: 103427

[19] Li X, Liu W, Qiao J, Li Y, Hu J, (2023b). An enhanced semi-flexible transit service with introducing meeting points. Networks and Spatial Economics, 23( 3): 487–527

[20] Li X, Quadrifoglio L, (2009). Optimal zone design for feeder transit services. Transportation Research Record: Journal of the Transportation Research Board, 2111( 1): 100–108

[21] Liu X, Qu X, Ma X, (2021). Improving flex-route transit services with modular autonomous vehicles. Transportation Research Part E, Logistics and Transportation Review, 149: 102331

[22] Lu B, He X, Diao S, Shu Q, (2020). Study on coordinated scheduling of multi-route flexible buses in urban periphery in off-peak period. Journal of Highway and Transportation Research and Development, 37( 5): 131–139

[23] MalucelliFNonatoMPallottinoS (1999). Demand adaptive systems: some proposals on flexible transit1. In Operational Research in Industry. London: Palgrave Macmillan UK

[24] Millward H, Spinney J, Scott D, (2013). Active-transport walking behavior: destinations, durations, distances. Journal of Transport Geography, 28: 101–110

[25] Galarza Montenegro B D, Sörensen K, Vansteenwegen P, (2021). A large neighborhood search algorithm to optimize a demand-responsive feeder service. Transportation Research Part C, Emerging Technologies, 127: 103102

[26] Galarza Montenegro B D, Sörensen K, Vansteenwegen P, (2022). A column generation algorithm for the demand-responsive feeder service with mandatory and optional, clustered bus-stops. Networks, 80( 3): 274–296

[27] Galarza Montenegro B D, Sörensen K, Vansteenwegen P, (2023). A demand‐responsive feeder service with a maximum headway at mandatory stops. Networks, 83( 1): 100–130

[28] Nourbakhsh S M, Ouyang Y, (2012). A structured flexible transit system for low demand areas. Transportation Research Part B: Methodological, 46( 1): 204–216

[29] Palmer K, Dessouky M, Abdelmaguid T, (2004). Impacts of management practices and advanced technologies on demand responsive transit systems. Transportation Research Part A, Policy and Practice, 38( 7): 495–509

[30] Pang M, Chen M, Zhang N, (2017). Scheduling optimization of intelligent public transport system based on MAST. Journal of Transportation Systems Engineering and Information Technology, 17( 1): 143–163

[31] Pei M, Lin P, Liu R, Ma Y, (2019). Flexible transit routing model considering passengers’ willingness to pay. IET Intelligent Transport Systems, 13( 5): 841–850

[32] Pisinger D, Ropke S, (2007). A general heuristic for vehicle routing problems. Computers & Operations Research, 34( 8): 2403–2435

[33] PottsJ FMarshallM ACrockettE CWashingtonJ (2010). A guide for planning and operating flexible public transportation services. Washington, D.C. Transportation Research Board

[34] Qiu F, Li W, Haghani A, (2014a). A methodology for choosing between fixed-route and flex-route policies for transit services. Journal of Advanced Transportation, 49( 3): 496–509

[35] Qiu F, Li W, Zhang J, (2014b). A dynamic station strategy to improve the performance of flex-route transit services. Transportation Research Part C, Emerging Technologies, 48: 229–240

[36] Quadrifoglio L, Dessouky M M, Ordóñez F, (2008). Mobility allowance shuttle transit (MAST) services: MIP formulation and strengthening with logic constraints. European Journal of Operational Research, 185( 2): 481–494

[37] Quadrifoglio L, Dessouky M M, Palmer K, (2007). An insertion heuristic for scheduling mobility allowance shuttle transit (MAST) services. Journal of Scheduling, 10( 1): 25–40

[38] Quadrifoglio L, Li X, (2009). A methodology to derive the critical demand density for designing and operating feeder transit services. Transportation Research Part B: Methodological, 43( 10): 922–935

[39] Ropke S, Pisinger D, (2006). An adaptive large neighborhood search heuristic for the pickup and delivery problem with time windows. Transportation Science, 40( 4): 455–472

[40] Sacramento D, Pisinger D, Ropke S, (2019). An adaptive large neighborhood search metaheuristic for the vehicle routing problem with drones. Transportation Research Part C: Emerging Technologies, 102: 289–315

[41] Sipetas C, Gonzales E J, (2021). Continuous approximation model for hybrid flexible transit systems with low demand density. Transportation Research Record: Journal of the Transportation Research Board, 2675( 8): 198–214

[42] Tang C, Liu J, Ceder A, Jiang Y, (2023). Optimisation of a new hybrid transit service with modular autonomous vehicles. Transportmetrica A: Transport Science, 20( 2): 1–1

[43] Yang H, Cherry C R, Zaretzki R, Ryerson M S, Liu X, Fu Z, (2016). A GIS-based method to identify cost-effective routes for rural deviated fixed route transit. Journal of Advanced Transportation, 50( 8): 1770–1784

[44] Zhao J, Dessouky M, (2008). Service capacity design problems for mobility allowance shuttle transit systems. Transportation Research Part B: Methodological, 42( 2): 135–146

[45] Zheng Y, Li W, Qiu F, (2018a). A methodology for choosing between route deviation and point deviation policies for flexible transit services. Journal of Advanced Transportation, 2018: 1–12

[46] Zheng Y, Li W, Qiu F, (2018b). A slack arrival strategy to promote flex-route transit services. Transportation Research Part C, Emerging Technologies, 92: 442–455

[47] Zheng Y, Li W, Qiu F, Wei H, (2019). The benefits of introducing meeting points into flex-route transit services. Transportation Research Part C, Emerging Technologies, 106: 98–112

RIGHTS & PERMISSIONS

Higher Education Press