Dynamic pickup and delivery problems. (English) Zbl 1176.90048

Summary: In the last decade, there has been an increasing body of research in dynamic vehicle routing problems. This article surveys the subclass of those problems called dynamic pickup and delivery problems, in which objects or people have to be collected and delivered in real-time. It discusses some general issues as well as solution strategies.


90B06 Transportation, logistics and supply chain management
90B35 Deterministic scheduling theory in operations research
90C35 Programming involving graphs or networks
Full Text: DOI


[1] Anily, S.; Hassin, R., The swapping problem, Networks, 22, 419-433 (1992) · Zbl 0763.90080
[3] Attanasio, A.; Cordeau, J.-F.; Ghiani, G.; Laporte, G., Parallel tabu search heuristics for the dynamic multi-vehicle dial-a-ride problem, Parallel Computing, 30, 377-387 (2004)
[5] Berbeglia, G.; Cordeau, J.-F.; Gribkovskaia, I.; Laporte, G., Static pickup and delivery problems: A classification scheme and survey, Top, 15, 1-31 (2007) · Zbl 1121.90001
[6] Borodin, A.; El-Yaniv, R., Online Computation and Competitive Analysis (2005), Cambridge University Press: Cambridge University Press Cambridge
[7] Branke, J.; Middendorf, M.; Noeth, G.; Dessouky, M., Waiting strategies for dynamic vehicle routing, Transportation Science, 39, 298-312 (2005)
[8] Cordeau, J.-F.; Laporte, G., The dial-a-ride problem: Models and algorithms, Annals of Operations Research, 153, 29-46 (2007) · Zbl 1157.90353
[9] Cordeau, J.-F.; Laporte, G.; Potvin, J.-Y.; Savelsbergh, M. W.P., Transportation on demand, (Barnhart, C.; Laporte, G., Transportation. Handbooks in Operations Research and Management Science, vol. 14 (2007), North-Holland: North-Holland Amsterdam), 429-466
[10] Coslovich, L.; Pesenti, R.; Ukovich, W., A two-phase insertion technique of unexpected customers for a dynamic dial-a-ride problem, European Journal of Operational Research, 175, 1605-1615 (2006) · Zbl 1142.90323
[11] Feuerstein, E.; Stougie, L., On-line single-server dial-a-ride problems, Theoretical Computer Science, 268, 91-105 (2001) · Zbl 0984.68003
[12] Gendreau, M.; Guertin, F.; Potvin, J.-Y.; Séguin, R., Neighborhood search heuristics for a dynamic vehicle dispatching problem with pick-ups and deliveries, Transportation Research Part C, 14, 157-174 (2006)
[13] Ghiani, G.; Guerriero, F.; Laporte, G.; Musmanno, R., Real-time vehicle routing: Solution concepts, algorithms and parallel computing strategies, European Journal of Operational Research, 151, 1-11 (2003) · Zbl 1033.90014
[14] Ghiani, G.; Manni, E.; Quaranta, A.; Triki, C., Anticipatory algorithms for same-day courier dispatching, Transportation Research Part E, 45, 96-106 (2009)
[15] Gutenschwager, K.; Niklaus, C.; Voß, S., Dispatching of an electric monorail system: Applying metaheuristics to an online pickup and delivery problem, Transportation Science, 38, 434-446 (2004)
[17] Horn, M. E.T., Fleet scheduling and dispatching for demand-responsive passenger services, Transportation Research Part C, 10, 35-63 (2002)
[18] Hvattum, L. M.; Løkketangen, A.; Laporte, G., Solving a dynamic and stochastic vehicle routing problem with a sample scenario hedging heuristic, Transportation Science, 40, 421-438 (2006)
[19] Hvattum, L. M.; Løkketangen, A.; Laporte, G., A branch-and-regret heuristic for stochastic and dynamic vehicle routing problems, Networks, 49, 330-340 (2007) · Zbl 1141.90337
[20] Ichoua, S.; Gendreau, M.; Potvin, J.-Y., Diversion issues in real-time vehicle dispatching, Transportation Science, 34, 426-438 (2000) · Zbl 0991.90529
[21] Ichoua, S.; Gendreau, M.; Potvin, J.-Y., Exploiting knowledge about future demands for real-time vehicle dispatching, Transportation Science, 40, 211-225 (2006)
[22] Jaillet, P.; Wagner, M. R., Online routing problems: Value of advanced information as improved competitive ratios, Transportation Science, 40, 200-210 (2006)
[23] Jaillet, P.; Wagner, M. R., Online vehicle routing problems: A survey, (Golden, B.; Raghavan, S.; Wasil, E., The Vehicle Routing Problem: Latest Advances and New Challenges (2008), Springer: Springer Berlin), 221-237 · Zbl 1187.90055
[24] Jaw, J. J.; Odoni, A. R.; Psaraftis, H. N.; Wilson, N. H.M., A heuristic algorithm for the multi-vehicle advance request dial-a-ride problem with time windows, Transportation Research Part B, 20, 243-257 (1986)
[26] Lipmann, M.; Lu, X.; de Paepe, W. E.; Sitters, R. A.; Stougie, L., On-line dial-a-ride problems under restricted information model, Algorithmica, 40, 319-329 (2004) · Zbl 1070.90072
[28] Madsen, O. B.G.; Ravn, H. F.; Rygaard, J. M., A heuristic algorithm for a dial-a-ride problem with time windows multiple capacities and multiple objectives, Annals of Operations Research, 60, 193-208 (1995) · Zbl 0839.90033
[29] Mes, M.; van der Heijden, M.; van Harten, A., Comparison of agent-based scheduling to look-ahead heuristics for real-time transportation problems, European Journal of Operational Research, 181, 59-75 (2007) · Zbl 1121.90023
[30] Mitrović-Minić, S.; Krishnamurti, R.; Laporte, G., Double-horizon based heuristics for the dynamic pickup and delivery problem with time windows, Transportation Research Part B, 38, 669-685 (2004)
[31] Mitrović-Minić, S.; Laporte, G., Waiting strategies for the dynamic pickup and delivery problem with time windows, Transportation Research Part B, 38, 635-655 (2004)
[32] Powell, W. B., An operational planning model for the dynamic vehicle allocation problem with uncertain demands, Transportation Research Part B, 21, 217-232 (1987)
[33] Powell, W. B.; Bouzanene-Ayari, B.; Simpo, H. P., Dynamic models for freight transportation, (Barnhart, C.; Laporte, G., Handbooks in Operations Research and Management Science: Transportation, vol. 14 (2007), North Holland), 285-365
[34] Powell, W. B.; Sheffi, Y.; Nickerson, K. S.; Butterbaugh, K.; Atherton, S., Maximizing profits for North American Van Lines’ truckload division: A new framework for pricing and operations, Interfaces, 18, 1, 21-41 (1988)
[35] Psaraftis, H. N., A dynamic programming approach to the single-vehicle many-to-many immediate request dial-a-ride problem, Transportation Science, 14, 130-154 (1980)
[36] Psaraftis, H. N., Dynamic vehicle routing problems, (Golden, B. L.; Assad, A. A., Vehicle Routing: Methods and Studies (1988), North-Holland: North-Holland Amsterdam), 223-248
[37] Pureza, V.; Laporte, G., Waiting and buffering strategies for the dynamic pickup and delivery problem with time windows, INFOR, 46, 165-175 (2008) · Zbl 07683691
[38] Regan, A. C.; Mahmassani, H. S.; Jaillet, P., Evaluation of dynamic fleet management systems, Transportation Research Record, 1645, 176-184 (1998)
[39] Sáez, D.; Cortés, C.; Núñez, A., Hybrid adaptive predictive control for the multi-vehicle dynamic pick-up and delivery problem based on genetic algorithms and fuzzy clustering, Computers and Operations Research, 35, 3412-3438 (2008) · Zbl 1159.90314
[40] Savelsbergh, M. W.P.; Sol, M., DRIVE: Dynamic routing of independent vehicles, Operations Research, 46, 474-490 (1998) · Zbl 0987.90511
[41] Swihart, M. R.; Papastavrou, J. D., A stochastic and dynamic model for the single-vehicle pick-up and delivery problem, European Journal of Operational Research, 114, 447-464 (1999) · Zbl 0949.90006
[42] Thomas, B. W., Waiting strategies for anticipating service requests from known customer locations, Transportation Science, 41, 319-331 (2007)
[43] Tjokroamidjojo, D.; Kutanoglu, E.; Taylor, G. D., Quantifying the value of advance load information in truckload trucking, Transportation Research Part E, 42, 340-357 (2006)
[44] Van Hentenryck, P.; Bent, R. W., Online stochastic combinatorial optimization, Operations Research, 52, 977-987 (2004) · Zbl 1165.90600
[45] Waisanen, H. A.; Shah, D.; Dahleh, M. A., A dynamic pickup and delivery problem in mobile networks under information constraints, IEEE Transactions on Automatic Control, 53, 1419-1433 (2008) · Zbl 1367.90034
[47] Xiang, Z.; Chu, C.; Chen, H., The study of a dynamic dial-a-ride problem under time-dependent and stochastic environments, European Journal of Operational Research, 185, 534-551 (2008) · Zbl 1137.90339
[48] Yang, J.; Jaillet, P.; Mahmassani, H. S., On-line algorithms for truck fleet assignment and scheduling under real-time information, Transportation Research Record, 1667, 107-113 (1998)
[49] Yang, J.; Jaillet, P.; Mahmassani, H. S., Real-time multivehicle truckload pickup and delivery problems, Transportation Science, 38, 135-148 (2004)
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.