Abstract
In this paper we consider a dynamic full truckload pickup and delivery problem with time-windows. Jobs arrive over time and are offered in a second-price auction. Individual vehicles bid on these jobs and maintain a schedule of the jobs they have won. We propose a pricing and scheduling strategy based on dynamic programming where not only the direct costs of a job insertion are taken into account, but also the impact on future opportunities. Simulation is used to evaluate the benefits of pricing opportunities compared to simple pricing strategies in various market settings. Numerical results show that the proposed approach provides high quality solutions, in terms of profits, capacity utilization, and delivery reliability.
Article PDF
Similar content being viewed by others
References
Bertsimas D, van Ryzin G (1991) A stochastic and dynamic vehicle routing problem in the euclidian plane. Oper Res 39(4): 601–615
Bertsimas D, van Ryzin G (1993) Stochastic and dynamic vehicle routing in the euclidean plane with multiple capacitated vehicles. Oper Res 41(1): 60–76
Brandt F, Weiß G (2002) Antisocial agents and Vickrey auctions, In: Tambe J, Meyer M (eds) Intelligent agents VIII, vol 2333 of lecture notes in computer science. Springer, New York, pp 335–347
Branke J, Middendorf M, Noeth G, Dessouky M (2005) Waiting strategies for dynamic vehicle routing. Transp Sci 39(3): 298–312
Carvalho T, Powell W (2000) A multiplier adjustment method for dynamic resource allocation problems. Transp Sci 34(2): 150–164
Figliozzi M (2004) Performance and analysis of spot truck-load procurement markets using sequential auctions. PhD thesis, School of Engineering, University of Maryland
Figliozzi M, Mahmassani H, Jaillet P (2006) Quantifying opportunity costs in sequential transportation auctions for truckload acquisition. Transp Res Rec 1964: 247–252
Ghiani G, Guerriero F, Laporte G, Musmanno R (2003) Real time vehicle routing: solution concepts, algorithms and parallel computing strategies. Eur J Oper Res 151(1): 1–11
Godfrey G, Powell W (2002) An adaptive dynamic programming algorithm for dynamic fleet management, I: single period travel times. Transp Sci 36(1): 21–39
Gumbel E (1958) Statistics of extremes. Columbia University Press, New York
Ichoua S, Gendreau M, Potvin J (2006) Exploiting knowledge about future demands for real-time vehicle dispatching. Transp Sci 40(2): 211–225
Larsen A, Madsen O, Solomon M (2004) The a priori dynamic traveling salesman problem with time windows. Transp Sci 38(4): 459–472
Law A, Kelton W (2000) Simulation modeling and analysis, vol 3. McGraw-Hill, Singapore
Mes M (2008) Sequential auctions for full truckload allocation. PhD thesis, School of Management and Governance, University of Twente, The Netherlands
Mes M, van der Heijden M, van Harten A (2007) Comparison of agent-based scheduling to look-ahead heuristics for real-time transportation problems. Eur J Oper Res 181(1): 59–75
Mes M, van der Heijden M, van Hillegersberg J (2008) Design choices for agent-based control of AGVs in the dough making process. Decis Support Syst 44(4): 983–999
Mitrović-Minić S, Laporte G (2004) Waiting strategies for the dynamic pickup and delivery problem with time windows. Transp Res B 38(7): 635–655
Powell W, Sheffi Y, Nickerson K, Atherton S (1988) Maximizing profits for north american van lines truckload division a new framework for pricing and operations. Interfaces 18(1): 21–41
Reiss R, Thomas M (1997) Statistical analysis of extreme values. Birkhauser Verlag, Basel
Sandholm T (2002) Algorithm for optimal winner determination in combinatorial auctions. Artif Intell 135(1-2): 1–54
Song J, Regan A (2002) Combinatorial auctions for transportation service procurement: the carrier perspective. Transp Res Rec 1833: 40–46
Swihart M, Papastavrou J (1999) A stochastic and dynamic model for the single-vehicle pick-up and delivery problem. Eur J Oper Res 114(3): 447–464
Thomas B (2007) Waiting strategies for anticipating service requests from known customer locations. Transp Sci 41(3): 319–331
Thomas B, White C (2004) Anticipatory route selection. Transp Sci 38(4): 473–487
Vickrey W (1961) Counterspeculation, auctions, and competitive sealed tenders. J Finance 16(1): 8–37
Wellman M, Walsh W, Wurman P, MacKie-Mason J (2001) Auction protocols for decentralized scheduling. Games Econ Behav 35(1): 271–303
Wooldridge M (1999) Intelligent agents. In: Weiss G(eds) Multiagent systems. The MIT Press, Cambridge, pp 27–77
Open Access
This article is distributed under the terms of the Creative Commons Attribution Noncommercial License which permits any noncommercial use, distribution, and reproduction in any medium, provided the original author(s) and source are credited.
Author information
Authors and Affiliations
Corresponding author
Additional information
This research is supported by the BSIK project “Transition Sustainable Mobility” (TRANSUMO).
Rights and permissions
Open Access This is an open access article distributed under the terms of the Creative Commons Attribution Noncommercial License (https://creativecommons.org/licenses/by-nc/2.0), which permits any noncommercial use, distribution, and reproduction in any medium, provided the original author(s) and source are credited.
About this article
Cite this article
Mes, M., van der Heijden, M. & Schuur, P. Look-ahead strategies for dynamic pickup and delivery problems. OR Spectrum 32, 395–421 (2010). https://doi.org/10.1007/s00291-008-0146-3
Published:
Issue Date:
DOI: https://doi.org/10.1007/s00291-008-0146-3