Open-source VRPLite Package for Vehicle Routing with Pickup and Delivery: A Path Finding Engine for Scheduled Transportation Systems

Abstract

Recently, automation, shared use, and electrification are viewed as the “three revolutions” in the future transportation sector, and the traditional scheduled public transit system will be greatly enhanced with flexible services and autonomous vehicle scheduling capabilities. Many emerging scheduled transportation applications include the fully automatic operation system in urban rail transit, joint line planning, and timetabling for high-speed rail as well as emerging self-driving vehicle dispatching. The vehicle routing problem (VRP) holds promise for seeking an optimal set of vehicle routes and schedules to meet customers’ requirements and plays a vital role in optimizing services for feature scheduled transportation systems. Due to the difficulty of finding optimal solutions for large-scale instances, enormous research efforts have been dedicated to developing efficient algorithms, while our paper presents a unique perspective based on a time-dependent and state-dependent path searching framework. An open-source and light-weight VRP with pickup and delivery with time windows (VRPPDTW) modeling package, namely VRPLite, has been developed in this research to provide a high-quality and computationally efficient solution engine for transportation on demand applications. This paper describes the space–time–state modeling process of VRPPDTW using a hyper-network representation. This solution framework can be embedded in a column generation or Lagrangian relaxation framework to handle many general applications. A number of illustrated examples are presented to demonstrate the effectiveness of the path search algorithm under various traffic conditions and passenger travel requirements.

Keywords

Vehicle routing problem with pickup and delivery / Space–time–state network modeling / Column generation / Lagrangian relaxation

References

[1] Cordeau JF, Laporte G, Potvin JY, Savelsbergh MWP. Chapter 7 transportation on demand. Handbooks in operations research and management science, 2007, New York: Elsevier B.V

[2] Parragh SN, Doerner KF, Hartl RF. A survey on pickup and delivery problems. Journal Für Betriebswirtschaft, 2008, 58(1): 21-51

[3] Psaraftis HN, Wen M, Kontovas CA. Dynamic vehicle routing problems: three decades and counting. Networks, 2016, 67(1): 3-31

[4] Cheng WC, Schonfeld P. A Method for optimizing the phased development of rail transit lines. Urban Rail Transit, 2015, 1(4): 227-237

[5] Lu K, Han B, Zhou X. Smart urban transit systems: from integrated framework to interdisciplinary perspective. Urban Rail Transit, 2018

[6] Bao X. Urban rail transit present situation and future development trends in China: overall analysis based on national policies and strategic plans in 2016–2020. Urban Rail Transit, 2018, 4(1): 1-12

[7] Kelly J, Marinov M. Innovative interior designs for urban freight distribution using light rail systems. Urban Rail Transit, 2017, 3(4): 238-254

[8] Wang Y, Zhang M, Ma J, Zhou X. Survey on driverless train operation for urban rail transit systems. Urban Rail Transit, 2016, 2(3–4): 106-113

[9] He L, Liang Q, Fang S. Challenges and innovative solutions in urban rail transit network operations and management: China’s Guangzhou metro experience. Urban Rail Transit, 2016, 2(1): 33-45

[10] Niu H, Zhou X. Optimizing urban rail timetable under time-dependent demand and oversaturated conditions. Transp Res Part C Emerg Technol, 2013, 36: 212-230

[11] 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 Part C Emerg Technol, 2018, 89: 321-343

[12] Dampier A, Marinov M. A study of the feasibility and potential implementation of metro-based freight transportation in Newcastle upon Tyne. Urban Rail Transit, 2015, 1(3): 164-182

[13] Toth P, Vigo D. The vehicle routing problem, 2002, Philadelphia: Society for Industrial and Applied Mathematics

[14] Tong L, Zhou L, Liu J, Zhou X. Customized bus service design for jointly optimizing passenger-to-vehicle assignment and vehicle routing. Transp Res Part C Emerg Technol, 2017, 85: 451-475

[15] Niu H, Zhou X, Tian X. Coordinating assignment and routing decisions in transit vehicle schedules: a variable-splitting Lagrangian decomposition approach for solution symmetry breaking. Transp Res Part B Methodol, 2018, 107: 70-101

[16] Pallottino S, Scutellà MG. Shortest path algorithms in transportation models: classical and innovative aspects. equilibrium and advanced transportation modelling, 1998, Berlin: Springer

[17] Ahuja RK, Magnanti TL, Orlin JB. Network flows: theory, algorithms, and applications, 1993, Upper Saddle River: Prentice Hall

[18] Ziliaskopoulos AK, Mahmassani HS. A time dependent shortest path algorithm for real time intelligent vehicle/highway systems. Transp Res Rec J Transp Res Board, 1993, 1408: 94-100.

[19] Chabini I. Discrete dynamic shortest path problems in transportation applications: complexity and algorithms with optimal run time. Transp Res Rec J Transp Res Board, 1998, 1645: 170-175

[20] Mahmoudi M, Zhou X. Finding optimal solutions for vehicle routing problem with pickup and delivery services with time windows: a dynamic programming approach based on state–space–time network representations. Transp Res Part B, 2016, 89: 19-42

[21] Liu J, Kang JE, Zhou X, Pendyala R. Network-oriented household activity pattern problem for system optimization. Transp Res Part C, 2017

[22] Zhou L, Tong L, Chen J, Tang J, Zhou X. Joint optimization of high-speed train timetables and speed profiles: a unified modeling approach using space-time-speed grid networks. Transp Res Part B Methodol, 2017, 97: 157-181

[23] Lu G, Zhou X, Mahmoudi M, Shi T, Peng Q (2018) Optimizing resource recharging location-routing plans: A resource-space-time network modeling framework for railway locomotive refueling applications. Computers & Industrial Engineering (in press)

[24] Ruan JM, Liu B, Wei H, Qu Y, Zhu N, Zhou X. How many and where to locate parking lots? A space–time accessibility-maximization modeling framework for special event traffic management. Urban Rail Transit, 2016, 2(2): 59-70

[25] Mahmoudi M, Chen J, Shi T, Zhang Y, Zhou X (2018) A cumulative service state representation for the pickup and delivery problem with synchronized transfers (Submitted)

[26] Chen R, Zhou L, Yue Y, Tang J, Lu C. The integrated optimization of robust train timetabling and electric multiple unit circulation and maintenance scheduling problem. Adv Mech Eng, 2018, 10(3): 1-16.

[27] Fisher ML, Jörnsten KO. Vehicle routing with time windows: two optimization algorithms, 1997, Catonsville: INFORMS

[28] Lübbecke ME, Desrosiers J. Selected topics in column generation. Oper Res, 2005, 53(6): 1007-1023

[29] Arslan A, Agatz N, Kroon L, Zuidwijk R (2016) Crowdsourced delivery: A dynamic pickup and delivery problem with ad-hoc drivers. Technical report, ERIM Report Series Reference. http://ssrn.com/abstract2726731

[30] Savelsbergh M, Van Woensel T. 50th anniversary invited article—city logistics: challenges and opportunities. Transp Sci, 2016, 50(2): 579-590

[31] Muñoz-Villamizar A, Montoya-Torres JR, Faulin J. Impact of the use of electric vehicles in collaborative urban transport networks: a case study. Transp Res Part D Transp Environ, 2017, 50: 40-54

[32] Qiu L, Hsu WJ, Huang SY, Wang H. Scheduling and routing algorithms for AGVs: a survey. Int J Prod Res, 2002, 40(3): 745-760

[33] Chen X, Li Y. Smooth formation navigation of multiple mobile robots for avoiding moving obstacles. Int J Control Autom Syst, 2006, 4(4): 466-479.

[34] Ota J. Multi-agent robot systems as distributed autonomous systems. Adv Eng Inform, 2006, 20(1): 59-70

[35] Yin J, Tang T, Yang L, Gao Z, Ran B. Energy-efficient metro train rescheduling with uncertain time-variant passenger demands: an approximate dynamic programming approach. Transp Res Part B Methodol, 2016, 91: 178-210

[36] Rao X, Montigel M, Weidmann U. A new rail optimisation model by integration of traffic management and train automation. Transp Res Part C Emerg Technol, 2016, 71: 382-405

[37] Yin J, Yang L, Tang T, Gao Z, Ran B. Dynamic passenger demand oriented metro train scheduling with energy-efficiency and waiting time minimization: mixed-integer linear programming approaches. Transp Res Part B Methodol, 2017, 97: 182-213

[38] Fazlollahtabar H, Saidi-Mehrabad M. Methodologies to optimize automated guided vehicle scheduling and routing problems: a review study. J Intell Robot Syst, 2015, 77(3–4): 525-545

[39] Huang Y, Zhao L, Van Woensel T, Gross JP. Time-dependent vehicle routing problem with path flexibility. Transp Res Part B Methodol, 2017, 95: 169-195