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
作者： Monirehalsadat Mahmoudi , Xuesong Zhou , None
DOI: 10.1016/J.TRB.2016.03.009
关键词: Reduction (complexity) 、 Routing (electronic design automation) 、 Mathematical optimization 、 Flow network 、 Lagrange multiplier 、 Lagrangian relaxation 、 Dynamic programming 、 Vehicle routing problem 、 Computer science 、 State space
摘要: Optimization of on-demand transportation systems and ride-sharing services involves solving a class of complex vehicle routing problems with pickup and delivery with time windows (VRPPDTW). This paper first proposes a new time-discretized multi-commodity network flow model for the VRPPDTW based on the integration of vehicles' carrying states within space–time transportation networks, so as to allow a joint optimization of passenger-to-vehicle assignment and turn-by-turn routing in congested transportation networks. Our …
arxiv.org
harvard.edu
elsevier.com
socionet.ru参考文章(59)
HARVEY J. MILLER, Modelling accessibility using space-time prism concepts within geographical information systems International Journal of Geographic Information Systems. ,vol. 5, pp. 287- 301 ,(1991) , 10.1080/02693799108927856
Michel Gendreau, François Guertin, Jean-Yves Potvin, René Séguin, Neighborhood Search Heuristics for a Dynamic Vehicle Dispatching Problem with Pick-ups and Deliveries Transportation Research Part C-emerging Technologies. ,vol. 14, pp. 157- 174 ,(2006) , 10.1016/J.TRC.2006.03.002
Jacques Desrosiers, Yvan Dumas, François Soumis, A Dynamic Programming Solution of the Large-Scale Single-Vehicle Dial-A-Ride Problem with Time Windows American Journal of Mathematical and Management Sciences. ,vol. 6, pp. 301- 325 ,(1986) , 10.1080/01966324.1986.10737198
Marielle Christiansen, Decomposition of a Combined Inventory and Time Constrained Ship Routing Problem Transportation Science. ,vol. 33, pp. 3- 16 ,(1999) , 10.1287/TRSC.33.1.3
Arthur J. Swersey, Wilson Ballard, Scheduling School Buses Management Science. ,vol. 30, pp. 844- 853 ,(1984) , 10.1287/MNSC.30.7.844
Walter J. Bell, Louis M. Dalberto, Marshall L. Fisher, Arnold J. Greenfield, R. Jaikumar, Pradeep Kedia, Robert G. Mack, Paul J. Prutzman, Improving the Distribution of Industrial Gases with an On-Line Computerized Routing and Scheduling Optimizer Interfaces. ,vol. 13, pp. 4- 23 ,(1983) , 10.1287/INTE.13.6.4
Yvan Dumas, Jacques Desrosiers, François Soumis, The pickup and delivery problem with time windows European Journal of Operational Research. ,vol. 54, pp. 7- 22 ,(1991) , 10.1016/0377-2217(91)90319-Q
Emmanouil E. Zachariadis, Christos D. Tarantilis, Chris T. Kiranoudis, The load-dependent vehicle routing problem and its pick-up and delivery extension Transportation Research Part B-methodological. ,vol. 71, pp. 158- 181 ,(2015) , 10.1016/J.TRB.2014.11.004
Jean-François Cordeau, A Branch-and-Cut Algorithm for the Dial-a-Ride Problem Operations Research. ,vol. 54, pp. 573- 586 ,(2006) , 10.1287/OPRE.1060.0283
Xiubin Wang, Amelia C. Regan, Local truckload pickup and delivery with hard time window constraints Transportation Research Part B: Methodological. ,vol. 36, pp. 97- 112 ,(2002) , 10.1016/S0965-8564(00)00037-9