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

Alfa, 1986, Scheduling of vehicles for transportation of elderly, Transportation Planning and Technology, 11, 203, 10.1080/03081068608717342 Azi, 2007, An exact algorithm for a single vehicle routing problem with time windows and multiple routes, European Journal of Operational Research, 178, 755, 10.1016/j.ejor.2006.02.019 Baldacci, 2011, An exact algorithm for the pickup and delivery problem with time windows, Operations Research, 59, 414, 10.1287/opre.1100.0881 Bell, 1983, Improving the distribution of industrial gases with an on-line computerized routing and scheduling optimizer, Interfaces, 13, 4, 10.1287/inte.13.6.4 Bellman, 1962, Dynamic programming treatment of the traveling salesman problem, Journal of the Association for Computing Machinery, 9, 61, 10.1145/321105.321111 Bodin, 1986, The multi-vehicle subscriber dial-a-ride problem, TIMS Studies in the Management Sciences, 22, 73 Bramel, 1995, A location based heuristic for general routing problems, Operations Research, 43, 649, 10.1287/opre.43.4.649 Chabini, 1998, Discrete dynamic shortest path problems in transportation applications: Complexity and algorithms with optimal run time, Transportation Research Record: Journal of the Transportation Research Board, 1645, 170, 10.3141/1645-21 Chandra, 2000 Christiansen, 1999, Decomposition of a combined inventory routing and time constrained ship routing problem, Transportation Science, 33, 3, 10.1287/trsc.33.1.3 Cordeau, 2006, A branch-and-cut algorithm for the dial-a-ride problem, Operations Research, 54, 573, 10.1287/opre.1060.0283 Cullen, 1981, Set partitioning based heuristics for interactive routing, Networks, 11, 125, 10.1002/net.3230110206 Desaulniers, 2002, The VRP with pickup and delivery, 225 Desrosiers, 1986, A dynamic programming solution of the large-scale single-vehicle dial-a-ride problem with time windows, American Journal of Mathematical and Management Sciences, 6, 301, 10.1080/01966324.1986.10737198 Desrosiers, J., Dumas, Y., Soumis, F., Taillefer, S., and Villeneuve, D. (1991). An algorithm for miniclustering in handicapped transport. Technical Report G-91-22, GERAD, HEC Montréal. Diana, 2004, A new regret insertion heuristic for solving large-scale dial-a-ride problems with time windows, Transportation Research Part B: Methodological, 38, 539, 10.1016/j.trb.2003.07.001 Dumas, 1989 Dumas, 1991, The pickup and delivery problem with time windows, European Journal of Operations Research, 54, 7, 10.1016/0377-2217(91)90319-Q Fisher, 1982, A computerized vehicle routing application, Interfaces, 12, 42, 10.1287/inte.12.4.42 Fisher, 1997, Vehicle routing with time windows: Two optimization algorithms, Operations Research, 45, 488, 10.1287/opre.45.3.488 Fisher, 1989, An interactive optimization system for bulk-cargo ship scheduling, Naval Research Logistic Quarterly, 35, 27, 10.1002/1520-6750(198902)36:1<27::AID-NAV3220360103>3.0.CO;2-0 Furuhata, 2013, Ridesharing: The state-of-the-art and future directions, Transportation Research Part B: Methodological, 57, 28, 10.1016/j.trb.2013.08.012 Gendreau, 1998 Gromicho, 2012, Restricted dynamic programming: A flexible framework for solving realistic VRPs, Computers and Operations Research, 39, 902, 10.1016/j.cor.2011.07.002 Hägerstrand, 1970, What about people in regional science?, Regional Science Association Papers, 24, 7, 10.1111/j.1435-5597.1970.tb01464.x Häme, 2011, An adaptive insertion algorithm for the single-vehicle dial-a-ride problem with narrow time windows, European Journal of Operational Research, 209, 11, 10.1016/j.ejor.2010.08.021 Häme, 2015, A maximum cluster algorithm for checking the feasibility of dial-d-ride instances, Transportation Science, 49, 295, 10.1287/trsc.2013.0495 Held, 1962, A dynamic-programming approach to sequencing problems, Journal of the Society for Industrial and Applied Mathematics, 10, 196, 10.1137/0110015 Hernández-Pérez, 2009, The multi-commodity one-to-one pickup-and-delivery traveling salesman problem, European Journal of Operational Research, 196, 987, 10.1016/j.ejor.2008.05.009 Hosni, 2014, The shared-taxi problem: formulation and solution methods, Transportation Research Part B: Methodological, 70, 303, 10.1016/j.trb.2014.09.011 Ioachim, 1995, A request clustering algorithm for door-to-door handicapped transportation, Transportation Science, 29, 63, 10.1287/trsc.29.1.63 Jaw, 1986, A heuristic algorithm for the multi-vehicle advance-request dial-a-ride problem with time windows, Transportation Research Part B: Methodological, 20, 243, 10.1016/0191-2615(86)90020-2 Kok, 2012, Vehicle routing under time-dependent travel times: the impact of congestion avoidance, Computers and Operations Research, 39, 910, 10.1016/j.cor.2011.05.027 Lu, 2004, An exact algorithm for the multiple vehicle pickup and delivery problem, Transportation Science, 38, 503, 10.1287/trsc.1030.0040 Miller, 1991, Modelling accessibility using space–time prism concepts within geographical information systems, International Journal of Geographical Systems, 5, 287, 10.1080/02693799108927856 Mitrovic-Minic’, 2004, Double-horizon based heuristics for the dynamic pickup and delivery problem with time windows, Transportation Research Part B: Methodological, 38, 669, 10.1016/j.trb.2003.09.001 Paquette, 2013, Combining multicriteria analysis and tabu search for dial-a-ride problems, Transportation Research Part B: Methodological, 52, 1, 10.1016/j.trb.2013.02.007 Psaraftis, 1980, A dynamic programming approach to the single-vehicle, many-to-many immediate request dial-a-ride problem, Transportation Science, 14, 130, 10.1287/trsc.14.2.130 Psaraftis, 1983, An exact algorithm for the single-vehicle many-to-many dial-a-ride problem with time windows, Transportation Science, 17, 351, 10.1287/trsc.17.3.351 Psaraftis, 1985 Rappoport, 1992, A planning heuristic for military airlift, Interfaces, 22, 73, 10.1287/inte.22.3.73 Rappoport, 1994, A transportation problem formulation for the MAC airlift planning problem, Annals of Operations Research, 50, 505, 10.1007/BF02085656 Ropke, 2007, Models and branch-and-cut algorithms for pickup and delivery problems with time windows, Networks, 49, 258, 10.1002/net.20177 Ropke, 2009, Branch and cut and price for the pickup and delivery problem with time windows, Transportation Science, 43, 267, 10.1287/trsc.1090.0272 Ruland, 1995 Ruland, 1997, The pickup and delivery problem: Faces and branch and-cut algorithm, Computers and Mathematics with Applications, 33, 1, 10.1016/S0898-1221(97)00090-4 Savelsbergh, 1998, Drive: Dynamic routing of independent vehicles, Operations Research, 46, 474, 10.1287/opre.46.4.474 Sexton, 1985, Optimizing single vehicle many-to-many operation with desired delivery times: I, Scheduling. Transportation Science, 19, 378, 10.1287/trsc.19.4.378 Sexton, 1985, Optimizing single vehicle many-to-many operation with desired delivery times: II, Routing Transportation Science, 19, 411, 10.1287/trsc.19.4.411 Shen, 1995, A computer assistant for vehicle dispatching with learning capabilities, Annals of Operations Research, 61, 189, 10.1007/BF02098288 Solanki, 1991, An execution planning algorithm for military airlift, Interfaces, 21, 121, 10.1287/inte.21.4.121 Solomon, 1992, An application of vehicle routing methodology to large-scale larvicide control programs, Interfaces, 22, 88, 10.1287/inte.22.3.88 Swersey, 1983, Scheduling school buses, Management Science, 30, 844, 10.1287/mnsc.30.7.844 Toth, 1997, Heuristic algorithms for the handicapped persons transportation problem, Transportation Science, 31, 60, 10.1287/trsc.31.1.60 Wang, 2015, A Pickup and delivery problem for ridesharing considering congestion, Transportation Letters The International Journal of Transportation Research Wang, 2002, Local truckload pickup and delivery with hard time window constraints, Transportation Research Part B: Methodological, 36, 97, 10.1016/S0965-8564(00)00037-9 Yang, 2014, Constraint reformulation and a Lagrangian relaxation-based solution algorithm for a least expected time path problem, Transportation Research Part B: Methodological, 59, 22, 10.1016/j.trb.2013.10.012 Zachariadis, 2015, The load-dependent vehicle routing problem and its pick-up and delivery extension, Transportation Research Part B: Methodological, 71, 158, 10.1016/j.trb.2014.11.004 Zhou, 2014, DTALite: a queue-based mesoscopic traffic simulator for fast model evaluation and calibration, Cogent Engineering, 1, 10.1080/23311916.2014.961345 Ziliaskopoulos, 1993, Time-dependent, shortest-path algorithm for real-time intelligent vehicle highway system application, Transportation Research Record, 1408, 94