IDEAS home Printed from https://ideas.repec.org/a/gam/jsusta/v11y2019i7p2060-d220652.html
   My bibliography  Save this article

A Dynamic Strategy for Home Pick-Up Service with Uncertain Customer Requests and Its Implementation

Author

Listed:
  • Yu Wu

    (Institutes of Science and Development, Chinese Academy of Sciences, Beijing 100190, China
    University of Chinese Academy of Sciences, Beijing 100049, China)

  • Bo Zeng

    (Department of Industrial Engineering, University of Pittsburgh, Pittsburgh, PA 15261, USA)

  • Siming Huang

    (Institutes of Science and Development, Chinese Academy of Sciences, Beijing 100190, China)

Abstract

In this paper, a home service problem is studied, where a capacitated vehicle collects customers’ parcels in one pick-up tour. We consider a situation where customers, who have scheduled their services in advance, may call to cancel their appointments, and customers, who do not have appointments, also need to be visited if they request for services as long as the capacity is allowed. To handle those changes that occurred over the tour, a dynamic strategy will be needed to guide the vehicle to visit customers in an efficient way. Aimed at minimizing the vehicle’s total expected travel distance, we model this problem as a multi-dimensional Markov Decision Process (MDP) with finite exponential scale state space. We exactly solve this MDP via dynamic programming, where the computing complexity is exponential. In order to avoid complexity continually increasing, we aim to develop a fast looking-up method for one already-examined state’s record. Although generally this will result in a huge waste of memory, by exploiting critical structural properties of the state space, we obtain an O ( 1 ) looking-up method without any waste of memory. Computational experiments demonstrate the effectiveness of our model and the developed solution method. For larger instances, two well-performed heuristics are proposed.

Suggested Citation

  • Yu Wu & Bo Zeng & Siming Huang, 2019. "A Dynamic Strategy for Home Pick-Up Service with Uncertain Customer Requests and Its Implementation," Sustainability, MDPI, vol. 11(7), pages 1-21, April.
  • Handle: RePEc:gam:jsusta:v:11:y:2019:i:7:p:2060-:d:220652
    as

    Download full text from publisher

    File URL: https://www.mdpi.com/2071-1050/11/7/2060/pdf
    Download Restriction: no

    File URL: https://www.mdpi.com/2071-1050/11/7/2060/
    Download Restriction: no
    ---><---

    References listed on IDEAS

    as
    1. Majid Salavati-Khoshghalb & Michel Gendreau & Ola Jabali & Walter Rei, 2019. "A hybrid recourse policy for the vehicle routing problem with stochastic demands," EURO Journal on Transportation and Logistics, Springer;EURO - The Association of European Operational Research Societies, vol. 8(3), pages 269-298, September.
    2. Vuong, Quan-Hoang, 2005. "Central Limit Theorem for Functional of Jump Markov Processes," OSF Preprints vq3b6, Center for Open Science.
    3. Sotiris P. Gayialis & Grigorios D. Konstantakopoulos & Ilias P. Tatsiopoulos, 2019. "Vehicle Routing Problem for Urban Freight Transportation: A Review of the Recent Literature," Springer Proceedings in Business and Economics, in: Angelo Sifaleras & Konstantinos Petridis (ed.), Operational Research in the Digital Era – ICT Challenges, pages 89-104, Springer.
    4. Luc Mercier & Pascal Hentenryck, 2011. "An anytime multistep anticipatory algorithm for online stochastic combinatorial optimization," Annals of Operations Research, Springer, vol. 184(1), pages 233-271, April.
    5. Salavati-Khoshghalb, Majid & Gendreau, Michel & Jabali, Ola & Rei, Walter, 2019. "An exact algorithm to solve the vehicle routing problem with stochastic demands under an optimal restocking policy," European Journal of Operational Research, Elsevier, vol. 273(1), pages 175-189.
    6. Christos H. Papadimitriou & John N. Tsitsiklis, 1987. "The Complexity of Markov Decision Processes," Mathematics of Operations Research, INFORMS, vol. 12(3), pages 441-450, August.
    7. Fink, Martin & Desaulniers, Guy & Frey, Markus & Kiermaier, Ferdinand & Kolisch, Rainer & Soumis, François, 2019. "Column generation for vehicle routing problems with multiple synchronization constraints," European Journal of Operational Research, Elsevier, vol. 272(2), pages 699-711.
    8. Maximilian Schiffer & Michael Schneider & Grit Walther & Gilbert Laporte, 2019. "Vehicle Routing and Location Routing with Intermediate Stops: A Review," Transportation Science, INFORMS, vol. 53(2), pages 319-343, March.
    9. Stavropoulou, F. & Repoussis, P.P. & Tarantilis, C.D., 2019. "The Vehicle Routing Problem with Profits and consistency constraints," European Journal of Operational Research, Elsevier, vol. 274(1), pages 340-356.
    10. 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.
    11. Soumia Ichoua & Michel Gendreau & Jean-Yves Potvin, 2006. "Exploiting Knowledge About Future Demands for Real-Time Vehicle Dispatching," Transportation Science, INFORMS, vol. 40(2), pages 211-225, May.
    12. Ulrike Ritzinger & Jakob Puchinger & Richard F. Hartl, 2016. "A survey on dynamic and stochastic vehicle routing problems," International Journal of Production Research, Taylor & Francis Journals, vol. 54(1), pages 215-231, January.
    13. Rodríguez-Martín, Inmaculada & Salazar-González, Juan-José & Yaman, Hande, 2019. "The periodic vehicle routing problem with driver consistency," European Journal of Operational Research, Elsevier, vol. 273(2), pages 575-584.
    14. Fianu, Sefakor & Davis, Lauren B., 2018. "A Markov decision process model for equitable distribution of supplies under uncertainty," European Journal of Operational Research, Elsevier, vol. 264(3), pages 1101-1115.
    15. Kenan Karagul & Yusuf Sahin & Erdal Aydemir & Aykut Oral, 2019. "A Simulated Annealing Algorithm Based Solution Method for a Green Vehicle Routing Problem with Fuel Consumption," International Series in Operations Research & Management Science, in: Turan Paksoy & Gerhard-Wilhelm Weber & Sandra Huber (ed.), Lean and Green Supply Chain Management, pages 161-187, Springer.
    16. 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.
    17. Macrina, Giusy & Laporte, Gilbert & Guerriero, Francesca & Di Puglia Pugliese, Luigi, 2019. "An energy-efficient green-vehicle routing problem with mixed vehicle fleet, partial battery recharging and time windows," European Journal of Operational Research, Elsevier, vol. 276(3), pages 971-982.
    18. Amalia I. Nikolopoulou & Panagiotis P. Repoussis & Christos D. Tarantilis & Emmanouil E. Zachariadis, 2019. "Adaptive memory programming for the many-to-many vehicle routing problem with cross-docking," Operational Research, Springer, vol. 19(1), pages 1-38, March.
    19. Pascal Hentenryck & Russell Bent & Eli Upfal, 2010. "Online stochastic optimization under time constraints," Annals of Operations Research, Springer, vol. 177(1), pages 151-183, June.
    Full references (including those not matched with items on IDEAS)

    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. Zhang, Jian & Woensel, Tom Van, 2023. "Dynamic vehicle routing with random requests: A literature review," International Journal of Production Economics, Elsevier, vol. 256(C).
    2. 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.
    3. Zhang, Jian & Luo, Kelin & Florio, Alexandre M. & Van Woensel, Tom, 2023. "Solving large-scale dynamic vehicle routing problems with stochastic requests," European Journal of Operational Research, Elsevier, vol. 306(2), pages 596-614.
    4. Vidal, Thibaut & Laporte, Gilbert & Matl, Piotr, 2020. "A concise guide to existing and emerging vehicle routing problem variants," European Journal of Operational Research, Elsevier, vol. 286(2), pages 401-416.
    5. Mustafa Demirbilek & Juergen Branke & Arne Strauss, 2019. "Dynamically accepting and scheduling patients for home healthcare," Health Care Management Science, Springer, vol. 22(1), pages 140-155, March.
    6. Mustafa Demirbilek & Juergen Branke & Arne K. Strauss, 2021. "Home healthcare routing and scheduling of multiple nurses in a dynamic environment," Flexible Services and Manufacturing Journal, Springer, vol. 33(1), pages 253-280, March.
    7. Gregorio Tirado & Lars Magnus Hvattum, 2017. "Determining departure times in dynamic and stochastic maritime routing and scheduling problems," Flexible Services and Manufacturing Journal, Springer, vol. 29(3), pages 553-571, December.
    8. Marlin W. Ulmer & Alan Erera & Martin Savelsbergh, 2022. "Dynamic service area sizing in urban delivery," OR Spectrum: Quantitative Approaches in Management, Springer;Gesellschaft für Operations Research e.V., vol. 44(3), pages 763-793, September.
    9. Marlin W. Ulmer & Leonard Heilig & Stefan Voß, 2017. "On the Value and Challenge of Real-Time Information in Dynamic Dispatching of Service Vehicles," Business & Information Systems Engineering: The International Journal of WIRTSCHAFTSINFORMATIK, Springer;Gesellschaft für Informatik e.V. (GI), vol. 59(3), pages 161-171, June.
    10. Fleckenstein, David & Klein, Robert & Steinhardt, Claudius, 2023. "Recent advances in integrating demand management and vehicle routing: A methodological review," European Journal of Operational Research, Elsevier, vol. 306(2), pages 499-518.
    11. Zolfagharinia, Hossein & Haughton, Michael, 2016. "Effective truckload dispatch decision methods with incomplete advance load information," European Journal of Operational Research, Elsevier, vol. 252(1), pages 103-121.
    12. Côté, Jean-François & Alves de Queiroz, Thiago & Gallesi, Francesco & Iori, Manuel, 2023. "A branch-and-regret algorithm for the same-day delivery problem," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 177(C).
    13. Zhaoxia Guo & Stein W. Wallace & Michal Kaut, 2019. "Vehicle Routing with Space- and Time-Correlated Stochastic Travel Times: Evaluating the Objective Function," INFORMS Journal on Computing, INFORMS, vol. 31(4), pages 654-670, October.
    14. Saint-Guillain, Michael & Paquay, Célia & Limbourg, Sabine, 2021. "Time-dependent stochastic vehicle routing problem with random requests: Application to online police patrol management in Brussels," European Journal of Operational Research, Elsevier, vol. 292(3), pages 869-885.
    15. Alonso Tabares, Diego & Mora-Camino, Felix & Drouin, Antoine, 2021. "A multi-time scale management structure for airport ground handling automation," Journal of Air Transport Management, Elsevier, vol. 90(C).
    16. Marlin W. Ulmer & Dirk C. Mattfeld & Felix Köster, 2018. "Budgeting Time for Dynamic Vehicle Routing with Stochastic Customer Requests," Transportation Science, INFORMS, vol. 52(1), pages 20-37, January.
    17. Aziez, Imadeddine & Côté, Jean-François & Coelho, Leandro C., 2022. "Fleet sizing and routing of healthcare automated guided vehicles," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 161(C).
    18. María I. Restrepo & Frédéric Semet & Thomas Pocreau, 2019. "Integrated Shift Scheduling and Load Assignment Optimization for Attended Home Delivery," Transportation Science, INFORMS, vol. 53(4), pages 1150-1174, July.
    19. 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.
    20. Györgyi, Péter & Kis, Tamás, 2019. "A probabilistic approach to pickup and delivery problems with time window uncertainty," European Journal of Operational Research, Elsevier, vol. 274(3), pages 909-923.

    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:gam:jsusta:v:11:y:2019:i:7:p:2060-:d:220652. 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: MDPI Indexing Manager (email available below). General contact details of provider: https://www.mdpi.com .

    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.