Development of an Algorithm for Optimal Demand Responsive Relocatable Feeder Transit Networks Serving Multiple Trains and Stations

Abstract

Although demand responsive feeder bus operation is possible with human-driven vehicles, it has not been very popular and is mostly available as a special service because of its high operating costs due to intensive labor costs as well as requirement for advanced real-time information technology and complicated operation. However, once automated vehicles become available, small-sized flexible door-to-door feeder bus operation will become more realistic, so preparing for such automated flexible feeder services is necessary to take advantage of the rapid improvement of automated vehicle technology. Therefore, in this research, an algorithm for optimal flexible feeder bus routing, which considers relocation of buses for multiple stations and trains, was developed using a simulated annealing algorithm for future automated vehicle operation. An example was developed and tested to demonstrate the developed algorithm. The algorithm successfully handled relocation of buses when the optimal bus routings were not feasible using the buses available at certain stations. Furthermore, the developed algorithm limited the maximum degree of circuity for each passenger while minimizing the total cost, including total vehicle operating costs and total passenger in-vehicle travel time costs.

Keywords

Automated transit / Vehicle routing / Feeder bus / Simulated annealing / Demand responsive transit / First and last mile service

References

[1] Fazlollahtabar H, Saidi-Mehrabad M. Autonomous guided vehicles; methods and models for optimal path planning, 2015, Berlin: Springer

[2] Krueger R, Rashidi TH, Rose JM. Preferences for shared autonomous vehicles. Transp Res C: Emerg Technol, 2016, 69: 343-355

[3] Bizon N, Dascalescu L, Tabatabaei N. Autonomous vehicles: intelligent transport systems and smart technologies, 2014, New York: Nova Science

[4] Shang P, Li R, Guo J, Xian K, Zhou X. Integrating Lagrangian and Eulerian observations for passenger flow state estimation in an urban rail transit network: a space-time-state hyper network-based assignment approach. Transp Res B: Methodol, 2019, 121: 135-167

[5] Dantzig GB, Ramser JH. The truck dispatching problem. Manag Sci, 1959, 6(1): 80-91

[6] Min H. The multiple vehicle routing problem with simultaneous delivery and pick-up points. Transp Res A: Gen, 1989, 23(5): 377-386

[7] Angelelli E, Mansini R. The vehicle routing problem with time windows and simultaneous pick-up and delivery, 2002, Berlin: Springer

[8] Tasan AS, Gen M. A genetic algorithm based approach to vehicle routing problem with simultaneous pick-up and deliveries. Comput Ind Eng, 2012, 62(3): 755-761

[9] Montané FAT, Galvao RD. A tabu search algorithm for the vehicle routing problem with simultaneous pick-up and delivery service. Comput Oper Res, 2006, 33(3): 595-619

[10] Ai TJ, Kachitvichyanukul V. A particle swarm optimization for the vehicle routing problem with simultaneous pickup and delivery. Comput Oper Res, 2009, 36(5): 1693-1702

[11] Gajpal Y, Abad P. An ant colony system (ACS) for vehicle routing problem with simultaneous delivery and pickup. Comput Oper Res, 2009, 36(12): 3215-3223

[12] Souza MJF, Mine MT, Silva MDSA, Ochi LS, Subramanian A. A hybrid heuristic, based on iterated local search and genius, for the vehicle routing problem with simultaneous pickup and delivery. Int J Logist Syst Manag, 2011, 10(2): 142-157

[13] Wang C, Mu D, Zhao F, Sutherland JW. A parallel simulated annealing method for the vehicle routing problem with simultaneous pickup–delivery and time windows. Comput Ind Eng, 2015, 83: 111-122

[14] Montoya-Torres JR, Franco JL, Isaza SN, Jiménez HF, Herazo-Padilla N. A literature review on the vehicle routing problem with multiple depots. Comput Ind Eng, 2015, 79: 115-129

[15] Kuah GK, Perl J. The feeder-bus network-design problem. J Oper Res Soc, 1989, 40(8): 751-767

[16] Chowdhury SM, Chien S. Intermodal transit system coordination. Transp Plan Technol, 2002, 25(4): 257-287

[17] Gholami A, Shariat A. Economic conditions for minibus usage in a multimodal feeder network. Transp Plan Technol, 2011, 34(8): 839-856

[18] Shrivastava P, O’Mahony M. A model for development of optimized feeder routes and coordinated schedules—a genetic algorithms approach. Transp Policy, 2006, 13(5): 413-425

[19] Shrivastava P, O’Mahony M. Design of feeder route network using combined genetic algorithm and specialized repair heuristic. J Public Transp, 2007, 10: 99

[20] Shrivastava P, O’Mahony M. Use of a hybrid algorithm for modeling coordinated feeder bus route network at suburban railway station. J Transp Eng, 2009, 135(1): 1-8

[21] Dou X, Yan Y, Guo X, Gong X. Time control point strategy coupled with transfer coordination in bus schedule design. J Adv Transp, 2016, 50(7): 1336-1351

[22] Sivakumaran K, Li Y, Cassidy MJ, Madanat S. Cost-saving properties of schedule coordination in a simple trunk-and-feeder transit system. Transp Res A: Policy Pract, 2012, 46(1): 131-139.

[23] Wang H. Routing and scheduling for a last-mile transportation system. Transp Sci, 2017

[24] Mahéo A, Kilby P, Hentenryck PV. Benders decomposition for the design of a hub and shuttle public transit system. Transp Sci, 2017

[25] Tong L, Pan Y, Shang P, Guo J, Xian K, Zhou X. Open-source public transportation mobility simulation engine DTALite-S: a discretized space-time network-based modeling framework for bridging multi-agent simulation and optimization. Urban Rail Transit, 2019, 5(1): 1-16

[26] Dou X, Gong X, Guo X, Tao T. Coordination of feeder bus schedule with train service at integrated transport hubs. Transp Res Record: J Transp Res Board, 2017, 2648: 103-110

[27] Baldacci R, Bartolini E, Mingozzi A. An exact algorithm for the pickup and delivery problem with time windows. Oper Res, 2011, 59(2): 414-426

[28] Sun P, Veelenturf LP, Hewitt M, Van Woensel T. The time-dependent pickup and delivery problem with time windows. Transp Res B: Methodol, 2018, 116: 1-24

[29] Dumas Y, Desrosiers J, Soumis F. The pickup and delivery problem with time windows. Eur J Oper Res, 1991, 54(1): 7-22

[30] Nanry WP, Wesley Barnes J. Solving the pickup and delivery problem with time windows using reactive tabu search. Transp Res B: Methodol, 2000, 34(2): 107-121

[31] Bent R, Hentenryck PV. A two-stage hybrid algorithm for pickup and delivery vehicle routing problems with time windows. Comput Oper Res, 2006, 33(4): 875-893

[32] Ropke S, Pisinger D. An adaptive large neighborhood search heuristic for the pickup and delivery problem with time windows. Transp Sci, 2006, 40(4): 455-472

[33] Nagata Y, Kobayashi S. Guided ejection search for the pickup and delivery problem with time windows, 2010, Berlin: Springer

[34] Zhou X, Tong L, Mahmoudi M, Zhuge L, Yao Y, Zhang Y, Shang P, Liu J, Shi T. Open-source VRPLite package for vehicle routing with pickup and delivery: a path finding engine for scheduled transportation systems. Urban Rail Transit, 2018, 4(2): 68-85

[35] Li X, Quadrifoglio L. Feeder transit services: choosing between fixed and demand responsive policy. Transp Res C Emerg Technol, 2010, 18: 770

[36] Cordeau J-F, Laporte G. The dial-a-ride problem (DARP): variants, modeling issues and algorithms. Q J Belg Fr Ital Oper Res Soc, 2003, 1(2): 89-101

[37] Cordeau J-F, Laporte G. The dial-a-ride problem: models and algorithms. Ann Oper Res, 2007, 153(1): 29-46

[38] Tripathy T, Nagavarapu SC, Azizian K, Ramasamy Pandi R, Dauwels J. Solving dial-a-ride problems using multiple ant colony system with fleet size minimisation, 2018, Cham: Springer

[39] Cubillos C, Urra E, Rodríguez N. Application of genetic algorithms for the DARPTW problem. Int J Comput Commun Control, 2009, 4(2): 127-136

[40] Zidi I, Zidi K, Mesghouni K, Ghedira K (2011) A multi-agent system based on the multi-objective simulated annealing algorithm for the static dial a ride problem. In: Paper presented at the 18th World Congress of the international federation of automatic control (IFAC), Milan (Italy)

[41] Belhaiza S (2017). A data driven hybrid heuristic for the dial-a-ride problem with time windows. In: Paper presented at the 2017 IEEE symposium series on computational intelligence (SSCI)

[42] Molenbruch Y, Braekers K, Caris A. Typology and literature review for dial-a-ride problems. Ann Oper Res, 2017, 259(1): 295-325

[43] Horn MET. Fleet scheduling and dispatching for demand-responsive passenger services. Transp Res C: Emerg Technol, 2002, 10(1): 35-63

[44] Diana M, Dessouky MM, Xia N. A model for the fleet sizing of demand responsive transportation services with time windows. Transp Res B: Methodol, 2006, 40(8): 651-666

[45] Cordeau J-F. A branch-and-cut algorithm for the dial-a-ride problem. Oper Res, 2006, 54(3): 573-586

[46] Pavone M, Frazzoli E, Bullo F. Adaptive and distributed algorithms for vehicle routing in a stochastic and dynamic environment. IEEE Trans Autom Control, 2011, 56(6): 1259-1274

[47] Arbex RO, da Cunha CB. Efficient transit network design and frequencies setting multi-objective optimization by alternating objective genetic algorithm. Transp Res B: Methodol, 2015, 81: 355-376

[48] Pternea M, Kepaptsoglou K, Karlaftis MG. Sustainable urban transit network design. Transp Res A: Policy Pract, 2015, 77: 276-291

[49] van Engelen M, Cats O, Post H, Aardal K (2018) Demand-anticipatory flexible public transport service. Transportation Research Board 97th Annual Meeting, Washington DC, United States

[50] Mahéo A, Kilby P, Hentenryck PV. Benders decomposition for the design of a hub and shuttle public transit system. Transp Sci, 2019, 53(1): 77-88

[51] Davendra D, Zelinka I, Onwubolu G Zelinka I Chaotic attributes and permutative optimization. Evolutionary algorithms and chaotic systems, 2010, Berlin: Springer 481-517

[52] Hasija S, Rajendran C. Scheduling in flowshops to minimize total tardiness of jobs. Int J Prod Res, 2004, 42(11): 2289-2301

[53] Kirkpatrick S, Gelatt CD Jr Vecchi MP. Optimization by simulated annealing. Science, 1983, 220(4598): 671-680

[54] Bräysy O, Gendreau M. Vehicle routing problem with time windows. Part II: metaheuristics. Transp Sci, 2005, 39(1): 119-139

[55] Potvin J-Y. A review of bio-inspired algorithms for vehicle routing. Bio-inspired algorithms for the vehicle routing problem, 2009, Berlin: Springer 1-34

[56] Van Breedam A (1996) An analysis of the effect of local improvement operators in genetic algorithms and simulated annealing for the vehicle routing problem. 1996, RUCA working paper 96/14: University of Antwerp, Belgium

[57] Azad AS, Islam M, Chakraborty S. A heuristic initialized stochastic memetic algorithm for MDPVRP with interdependent depot operations. IEEE Trans Cybern, 2017, 47(12): 4302-4315

[58] Deng A-M, Mao C, Zhou Y-T. Optimizing research of an improved simulated annealing algorithm to soft time windows vehicle routing problem with pick-up and delivery. Syst Eng Theory Pract, 2009, 29(5): 186-192

[59] Lin Y, Li W, Qiu F, Xu H. Research on optimization of vehicle routing problem for ride-sharing taxi. Proc Soc Behav Sci, 2012, 43: 494-502

[60] Rochat Y, Taillard ÉD. Probabilistic diversification and intensification in local search for vehicle routing. J Heuristics, 1995, 1(1): 147-167

[61] Adewole A, Otubamowo K, Egunjobi T, Ng K. A comparative study of simulated annealing and genetic algorithm for solving the travelling salesman problem. Int J Appl Inf Syst (IJAIS), 2012, 4(4): 6-12

[62] Lee Y-J. Comparative measures for transit network performance analysis. J Transp Res Forum, 2012

[63] Lee Y-J, Choi JY, Yu JW, Choi K. Geographical applications of performance measures for transit network directness. J Public Transp, 2015, 18(2): 7

[64] Shang P, Li R, Liu Z, Yang L, Wang Y. Equity-oriented skip-stopping schedule optimization in an oversaturated urban rail transit network. Transp Res C: Emerg Technol, 2018, 89: 321-343

Funding

Urban Mobility and Equity Center