[go: up one dir, main page]
IDEAS home Printed from https://ideas.repec.org/a/eee/transa/v49y2013icp178-194.html
   My bibliography  Save this article

The dynamic nearest neighbor policy for the multi-vehicle pick-up and delivery problem

Author

Listed:
  • Sheridan, Patricia Kristine
  • Gluck, Erich
  • Guan, Qi
  • Pickles, Thomas
  • Balcıog˜lu, Barış
  • Benhabib, Beno
Abstract
In this paper, a dynamic nearest neighbor (DNN) policy is proposed for operating a fleet of vehicles to serve customers, who place calls in a Euclidean service area according to a Poisson process. Each vehicle serves one customer at a time, who has a distinct origin and destination independently and uniformly distributed within the service area. The new DNN policy is a refined version of the nearest neighbor (NN) policy that is well known to perform sub-optimally when the frequency of customer requests is high. The DNN policy maintains geographically closest customer-to-vehicle assignments, due to its ability to divert/re-assign vehicles that may be already en-route to pick up other customers, when another vehicle becomes available or a new customer call arrives. Two other pertinent issues addressed include: the pro-active deployment of the vehicles by anticipating in which regions of the service area future calls are more likely to arise; and, imposition of limits to avoid prohibitively long customer wait times. The paper also presents accurate approximations for all the policies compared. Extensive simulations, some of which are included herein, clearly show the DNN policy to be tangibly superior to the first-come-first-served (FCFS) and NN policies.

Suggested Citation

  • Sheridan, Patricia Kristine & Gluck, Erich & Guan, Qi & Pickles, Thomas & Balcıog˜lu, Barış & Benhabib, Beno, 2013. "The dynamic nearest neighbor policy for the multi-vehicle pick-up and delivery problem," Transportation Research Part A: Policy and Practice, Elsevier, vol. 49(C), pages 178-194.
    • Handle: RePEc:eee:transa:v:49:y:2013:i:c:p:178-194
    DOI: 10.1016/j.tra.2013.01.032
    as

    Download full text from publisher

    File URL: http://www.sciencedirect.com/science/article/pii/S0965856413000396
    Download Restriction: Full text for ScienceDirect subscribers only
    File URL: https://libkey.io/10.1016/j.tra.2013.01.032?utm_source=ideas
    LibKey link: if access is restricted and if your library uses this service, LibKey will redirect you to where you can use your library subscription to access this item
    ---><---

    As the access to this document is restricted, you may want to search for a different version of it.

    References listed on IDEAS

    as
    1. Bertsimas, Dimitris & Van Ryzin, Garrett., 1991. "A stochastic and dynamic vehicle routing problem in the Euclidean plane," Working papers 3286-91., Massachusetts Institute of Technology (MIT), Sloan School of Management.
    2. Dimitris J. Bertsimas & Garrett van Ryzin, 1993. "Stochastic and Dynamic Vehicle Routing in the Euclidean Plane with Multiple Capacitated Vehicles," Operations Research, INFORMS, vol. 41(1), pages 60-76, February.
    3. Berbeglia, Gerardo & Cordeau, Jean-François & Laporte, Gilbert, 2010. "Dynamic pickup and delivery problems," European Journal of Operational Research, Elsevier, vol. 202(1), pages 8-15, April.
    4. Dimitris J. Bertsimas & Garrett van Ryzin, 1991. "A Stochastic and Dynamic Vehicle Routing Problem in the Euclidean Plane," Operations Research, INFORMS, vol. 39(4), pages 601-615, August.
    5. Cordeau, Jean-François & Laporte, Gilbert, 2003. "A tabu search heuristic for the static multi-vehicle dial-a-ride problem," Transportation Research Part B: Methodological, Elsevier, vol. 37(6), pages 579-594, July.
    6. David L. Jagerman & Benjamin Melamed, 2003. "Models and Approximations for Call Center Design," Methodology and Computing in Applied Probability, Springer, vol. 5(2), pages 159-181, June.
    7. Xiang, Zhihai & Chu, Chengbin & Chen, Haoxun, 2008. "The study of a dynamic dial-a-ride problem under time-dependent and stochastic environments," European Journal of Operational Research, Elsevier, vol. 185(2), pages 534-551, March.
    8. Jean-François Cordeau & Gilbert Laporte, 2007. "The dial-a-ride problem: models and algorithms," Annals of Operations Research, Springer, vol. 153(1), pages 29-46, September.
    9. Swihart, Michael R. & Papastavrou, Jason D., 1999. "A stochastic and dynamic model for the single-vehicle pick-up and delivery problem," European Journal of Operational Research, Elsevier, vol. 114(3), pages 447-464, May.
    10. Ghiani, Gianpaolo & Guerriero, Francesca & Laporte, Gilbert & Musmanno, Roberto, 2003. "Real-time vehicle routing: Solution concepts, algorithms and parallel computing strategies," European Journal of Operational Research, Elsevier, vol. 151(1), pages 1-11, November.
    11. Soumia Ichoua & Michel Gendreau & Jean-Yves Potvin, 2000. "Diversion Issues in Real-Time Vehicle Dispatching," Transportation Science, INFORMS, vol. 34(4), pages 426-438, November.
    Full references (including those not matched with items on IDEAS)

    Citations

    Citations are extracted by the CitEc Project, subscribe to its RSS feed for this item.
    as


    Cited by:

    1. Bosse, Alexander & Ulmer, Marlin W. & Manni, Emanuele & Mattfeld, Dirk C., 2023. "Dynamic priority rules for combining on-demand passenger transportation and transportation of goods," European Journal of Operational Research, Elsevier, vol. 309(1), pages 399-408.
    2. Zhang, Jian & Woensel, Tom Van, 2023. "Dynamic vehicle routing with random requests: A literature review," International Journal of Production Economics, Elsevier, vol. 256(C).
    3. Stacy A. Voccia & Ann Melissa Campbell & Barrett W. Thomas, 2019. "The Same-Day Delivery Problem for Online Purchases," Service Science, INFORMS, vol. 53(1), pages 167-184, February.
    4. Soeffker, Ninja & Ulmer, Marlin W. & Mattfeld, Dirk C., 2022. "Stochastic dynamic vehicle routing in the light of prescriptive analytics: A review," European Journal of Operational Research, Elsevier, vol. 298(3), pages 801-820.

    Most related items

    These are the items that most often cite the same works as this one and are cited by the same works as this one.
    1. Diego Muñoz-Carpintero & Doris Sáez & Cristián E. Cortés & Alfredo Núñez, 2015. "A Methodology Based on Evolutionary Algorithms to Solve a Dynamic Pickup and Delivery Problem Under a Hybrid Predictive Control Approach," Transportation Science, INFORMS, vol. 49(2), pages 239-253, May.
    2. Zhang, Jian & Woensel, Tom Van, 2023. "Dynamic vehicle routing with random requests: A literature review," International Journal of Production Economics, Elsevier, vol. 256(C).
    3. Pillac, Victor & Gendreau, Michel & Guéret, Christelle & Medaglia, Andrés L., 2013. "A review of dynamic vehicle routing problems," European Journal of Operational Research, Elsevier, vol. 225(1), pages 1-11.
    4. Barrett W. Thomas, 2007. "Waiting Strategies for Anticipating Service Requests from Known Customer Locations," Transportation Science, INFORMS, vol. 41(3), pages 319-331, August.
    5. Kergosien, Y. & Lenté, Ch. & Piton, D. & Billaut, J.-C., 2011. "A tabu search heuristic for the dynamic transportation of patients between care units," European Journal of Operational Research, Elsevier, vol. 214(2), pages 442-452, October.
    6. Soeffker, Ninja & Ulmer, Marlin W. & Mattfeld, Dirk C., 2022. "Stochastic dynamic vehicle routing in the light of prescriptive analytics: A review," European Journal of Operational Research, Elsevier, vol. 298(3), pages 801-820.
    7. Barrett W. Thomas & Chelsea C. White, 2004. "Anticipatory Route Selection," Transportation Science, INFORMS, vol. 38(4), pages 473-487, November.
    8. Stefan Vonolfen & Michael Affenzeller, 2016. "Distribution of waiting time for dynamic pickup and delivery problems," Annals of Operations Research, Springer, vol. 236(2), pages 359-382, January.
    9. Jürgen Branke & Martin Middendorf & Guntram Noeth & Maged Dessouky, 2005. "Waiting Strategies for Dynamic Vehicle Routing," Transportation Science, INFORMS, vol. 39(3), pages 298-312, August.
    10. Ghiani, Gianpaolo & Guerriero, Francesca & Laporte, Gilbert & Musmanno, Roberto, 2003. "Real-time vehicle routing: Solution concepts, algorithms and parallel computing strategies," European Journal of Operational Research, Elsevier, vol. 151(1), pages 1-11, November.
    11. Wang, Xuping & Ruan, Junhu & Shi, Yan, 2012. "A recovery model for combinational disruptions in logistics delivery: Considering the real-world participators," International Journal of Production Economics, Elsevier, vol. 140(1), pages 508-520.
    12. Ritzinger, Ulrike & Puchinger, Jakob & Rudloff, Christian & Hartl, Richard F., 2022. "Comparison of anticipatory algorithms for a dial-a-ride problem," European Journal of Operational Research, Elsevier, vol. 301(2), pages 591-608.
    13. Stefan Vonolfen & Michael Affenzeller, 2016. "Distribution of waiting time for dynamic pickup and delivery problems," Annals of Operations Research, Springer, vol. 236(2), pages 359-382, January.
    14. Russell W. Bent & Pascal Van Hentenryck, 2004. "Scenario-Based Planning for Partially Dynamic Vehicle Routing with Stochastic Customers," Operations Research, INFORMS, vol. 52(6), pages 977-987, December.
    15. Nikola Mardešić & Tomislav Erdelić & Tonči Carić & Marko Đurasević, 2023. "Review of Stochastic Dynamic Vehicle Routing in the Evolving Urban Logistics Environment," Mathematics, MDPI, vol. 12(1), pages 1-44, December.
    16. Hai Wang & Amedeo Odoni, 2016. "Approximating the Performance of a “Last Mile” Transportation System," Transportation Science, INFORMS, vol. 50(2), pages 659-675, May.
    17. Berbeglia, Gerardo & Cordeau, Jean-François & Laporte, Gilbert, 2010. "Dynamic pickup and delivery problems," European Journal of Operational Research, Elsevier, vol. 202(1), pages 8-15, April.
    18. Marlin W. Ulmer & Justin C. Goodson & Dirk C. Mattfeld & Marco Hennig, 2019. "Offline–Online Approximate Dynamic Programming for Dynamic Vehicle Routing with Stochastic Requests," Service Science, INFORMS, vol. 53(1), pages 185-202, February.
    19. Roberto Tadei & Guido Perboli & Francesca Perfetti, 2017. "The multi-path Traveling Salesman Problem with stochastic travel costs," EURO Journal on Transportation and Logistics, Springer;EURO - The Association of European Operational Research Societies, vol. 6(1), pages 3-23, March.
    20. Cristián E. Cortés & Doris Sáez & Alfredo Núñez & Diego Muñoz-Carpintero, 2009. "Hybrid Adaptive Predictive Control for a Dynamic Pickup and Delivery Problem," Transportation Science, INFORMS, vol. 43(1), pages 27-42, February.

    Corrections

    All material on this site has been provided by the respective publishers and authors. You can help correct errors and omissions. When requesting a correction, please mention this item's handle: RePEc:eee:transa:v:49:y:2013:i:c:p:178-194. See general information about how to correct material in RePEc.

    If you have authored this item and are not yet registered with RePEc, we encourage you to do it here. This allows to link your profile to this item. It also allows you to accept potential citations to this item that we are uncertain about.

    If CitEc recognized a bibliographic reference but did not link an item in RePEc to it, you can help with this form .

    If you know of missing items citing this one, you can help us creating those links by adding the relevant references in the same way as above, for each refering item. If you are a registered author of this item, you may also want to check the "citations" tab in your RePEc Author Service profile, as there may be some citations waiting for confirmation.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: Catherine Liu (email available below). General contact details of provider: http://www.elsevier.com/wps/find/journaldescription.cws_home/547/description#description .

    Please note that corrections may take a couple of weeks to filter through the various RePEc services.

    IDEAS is a RePEc service. RePEc uses bibliographic data supplied by the respective publishers.