Document Open Access Logo

Solving the Home Service Assignment, Routing, and Appointment Scheduling (H-SARA) Problem with Uncertainties

Authors Syu-Ning Johnn , Yiran Zhu , Andrés Miniguano-Trujillo , Akshay Gupte

PDF
Thumbnail PDF

File

OASIcs.ATMOS.2021.4.pdf
  • Filesize: 0.99 MB
  • 21 pages

Document Identifiers

Author Details

Syu-Ning Johnn
  • School of Mathematics, The University of Edinburgh, UK
Yiran Zhu
  • School of Mathematics, The University of Edinburgh, UK
Andrés Miniguano-Trujillo
  • The University of Edinburgh, UK
  • Heriot-Watt University, Edinburgh, UK
  • Maxwell Institute for Mathematical Sciences, Edinburgh, UK
Akshay Gupte
  • School of Mathematics, The University of Edinburgh, UK

Cite AsGet BibTex

Syu-Ning Johnn, Yiran Zhu, Andrés Miniguano-Trujillo, and Akshay Gupte. Solving the Home Service Assignment, Routing, and Appointment Scheduling (H-SARA) Problem with Uncertainties. In 21st Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2021). Open Access Series in Informatics (OASIcs), Volume 96, pp. 4:1-4:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
https://doi.org/10.4230/OASIcs.ATMOS.2021.4

Abstract

The Home Service Assignment, Routing, and Appointment scheduling (H-SARA) problem integrates the strategic fleet-sizing, tactical assignment, operational vehicle routing and scheduling problems at different decision levels, with a single period planning horizon and uncertainty (stochasticity) from the service duration, travel time, and customer cancellation rate. We propose a stochastic mixed-integer linear programming model for the H-SARA problem. Additionally, a reduced deterministic version is introduced which allows to solve small-scale instances to optimality with two acceleration approaches. For larger instances, we develop a tailored two-stage decision support system that provides high-quality and in-time solutions based on information revealed at different stages. Our solution method aims to reduce various costs under stochasticity, to create reasonable routes with balanced workload and team-based customer service zones, and to increase customer satisfaction by introducing a two-stage appointment notification system updated at different time stages before the actual service. Our two-stage heuristic is competitive to CPLEX’s exact solution methods in providing time and cost-effective decisions and can update previously-made decisions based on an increased level of information. Results show that our two-stage heuristic is able to tackle reasonable-size instances and provides good-quality solutions using less time compared to the deterministic and stochastic models on the same set of simulated instances.

Subject Classification

ACM Subject Classification
  • Mathematics of computing → Combinatorial optimization
  • Mathematics of computing → Combinatorial algorithms
  • Applied computing → Transportation
  • Mathematics of computing → Probabilistic algorithms
Keywords
  • Home Health Care
  • Mixed-Integer Linear Programming
  • Two-stage Stochastic
  • Uncertainties A Priori Optimisation
  • Adaptive Large Neighbourhood Search
  • Monte-Carlo Simulation

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

Related Versions

References

  1. Jonathan F Bard and Ahmad I Jarrah. Large-scale constrained clustering for rationalizing pickup and delivery operations. Transportation Research Part B, 43(5):542-561, 2009. URL: https://doi.org/10.1016/j.trb.2008.10.003.
  2. Jacques F Benders. Partitioning procedures for solving mixed-variables programming problems. Numerische Mathematik, 4(1):238-252, 1962. Google Scholar
  3. Dimitris J Bertsimas, Patrick Jaillet, and Amedeo R Odoni. A priori optimization. Operations Research, 38(6):1019-1033, 1990. URL: https://doi.org/10.1287/opre.38.6.1019.
  4. Kris Braekers, Katrien Ramaekers, and Inneke Van Nieuwenhuyse. The vehicle routing problem: State of the art classification and review. Computers & industrial engineering, 99:300-313, 2016. URL: https://doi.org/10.1016/j.cie.2015.12.007.
  5. Paola Cappanera, Maria Grazia Scutellà, Federico Nervi, and Laura Galli. Demand uncertainty in robust home care optimization. Omega, 80:95-110, 2018. URL: https://doi.org/10.1016/j.omega.2017.08.012.
  6. Mohamed Cissé, Semih Yalçındağ, Yannick Kergosien, Evren Şahin, Christophe Lenté, and Andrea Matta. Or problems related to home health care: A review of relevant routing and scheduling problems. Operations research for health care, 13-14:1-22, 2017. URL: https://doi.org/10.1016/j.orhc.2017.06.001.
  7. George B Dantzig, Delbert R Fulkerson, and Selmer M Johnson. Solution of a large-scale traveling-salesman problem. Journal of the Operations Research Society of America, 2(4):393-410, 1954. URL: https://doi.org/10.1287/opre.2.4.393.
  8. Chris Dawson. Royal mail day before delivery time notifications launched. URL: https://tamebay.com/2019/04/royal-mail-day-before-delivery-time-notifications-launched.html, April 2019.
  9. DPD. Guide to dpd. https://www.dpd.co.uk/pdf/dpd_sales_guide_2020_v3.pdf, 2020.
  10. Christian Fikar and Patrick Hirsch. A matheuristic for routing real-world home service transport systems facilitating walking. Journal of Cleaner Production, 105:300-310, 2015. URL: https://doi.org/10.1016/j.jclepro.2014.07.013.
  11. Christian Fikar and Patrick Hirsch. Home health care routing and scheduling: A review. Computers & Operations Research, 77:86-95, 2017. URL: https://doi.org/10.1016/j.cor.2016.07.019.
  12. The National Association for Home Care & Hospice. Basic statistics about home care, 2010. URL: http://www.nahc.org/wp-content/uploads/2017/10/10hc_stats.pdf.
  13. Bruce Golden, Arjang Assad, Larry Levy, and Filip Gheysens. The fleet size and mix vehicle routing problem. Computers & Operations Research, 11(1):49-66, 1984. URL: https://doi.org/10.1016/0305-0548(84)90007-8.
  14. Diwakar Gupta and Brian Denton. Appointment scheduling in health care: Challenges and opportunities. IIE transactions, 40(9):800-819, 2008. Google Scholar
  15. Elena Valentina Gutiérrez and Carlos Julio Vidal. Home health care logistics management problems: A critical review of models and methods. Revista Facultad de Ingeniería Universidad de Antioquia, 68:160-175, 2013. Google Scholar
  16. Sandra Gutiérrez, Andrés Miniguano-Trujillo, Diego Recalde, Luis M Torres, and Ramiro Torres. The integrated vehicle and pollster routing problem. arXiv, 2019. URL: http://arxiv.org/abs/1912.07356.
  17. Shuihua Han, Ling Zhao, Kui Chen, Zong-wei Luo, and Deepa Mishra. Appointment scheduling and routing optimization of attended home delivery system with random customer behavior. European Journal of Operational Research, 262(3):966-980, 2017. URL: https://doi.org/10.1016/j.ejor.2017.03.060.
  18. Vera C Hemmelmayr, Jean-François Cordeau, and Teodor Gabriel Crainic. An adaptive large neighborhood search heuristic for two-echelon vehicle routing problems arising in city logistics. Computers & operations research, 39(12):3215-3228, 2012. URL: https://doi.org/10.1016/j.cor.2012.04.007.
  19. S. W Hess, J. B Weaver, H. J Siegfeldt, J. N Whelan, and P. A Zitlau. Nonpartisan political redistricting by computer. Operations Research, 13(6):998-1006, 1965. URL: https://doi.org/10.1287/opre.13.6.998.
  20. Solrun G Holm and Ragnhild O Angelsen. A descriptive retrospective study of time consumption in home care services: How do employees use their working time? BMC Health Services Research, 14(1):439-439, 2014. URL: https://doi.org/10.1186/1472-6963-14-439.
  21. Simge Küçükyavuz and Suvrajeet Sen. An introduction to two-stage stochastic mixed-integer programming. In Leading Developments from INFORMS Communities, pages 1-27. INFORMS, 2017. URL: https://doi.org/10.1287/educ.2017.0171.
  22. Ettore Lanzarone and Andrea Matta. A cost assignment policy for home care patients. Flexible Services and Manufacturing Journal, 24(4):465-495, November 2011. URL: https://doi.org/10.1007/s10696-011-9121-4.
  23. Gilbert Laporte. Fifty years of vehicle routing. Transportation Science, 43(4):408-416, 2009. URL: https://doi.org/10.1287/trsc.1090.0301.
  24. Canhong Lin, K.L Choy, G.T.S Ho, S.H Chung, and H.Y Lam. Survey of green vehicle routing problem: Past and future trends. Expert Systems with Applications, 41(4):1118-1138, 2014. URL: https://doi.org/10.1016/j.eswa.2013.07.107.
  25. Ran Liu, Biao Yuan, and Zhibin Jiang. A branch-and-price algorithm for the home-caregiver scheduling and routing problem with stochastic travel and service times. Flexible Services and Manufacturing Journal, 31(4):989-1011, 2019. URL: https://doi.org/10.1007/s10696-018-9328-8.
  26. P.A Maya Duque, M Castro, Kenneth Sörensen, and P Goos. Home care service planning. the case of landelijke thuiszorg. European journal of operational research, 243(1):292-301, 2015. URL: https://doi.org/10.1016/j.ejor.2014.11.008.
  27. Jorge Oyola, Halvard Arntzen, and David L Woodruff. The stochastic vehicle routing problem, a literature review, part i: models. EURO Journal on Transportation and Logistics, 7(3):193-221, 2018. URL: https://doi.org/10.1007/s13676-016-0100-5.
  28. César Rego, Dorabela Gamboa, Fred Glover, and Colin Osterman. Traveling salesman problem heuristics: Leading methods, implementations and latest advances. European journal of operational research, 211(3):427-441, 2011. URL: https://doi.org/10.1016/j.ejor.2010.09.010.
  29. María I Restrepo, Louis-Martin Rousseau, and Jonathan Vallée. Home healthcare integrated staffing and scheduling. Omega (Oxford), 95:102057-, 2020. URL: https://doi.org/10.1016/j.omega.2019.03.015.
  30. Carlos Rodriguez, Thierry Garaix, Xiaolan Xie, and Vincent Augusto. Staff dimensioning in homecare services with uncertain demands. International Journal of Production Research, 53(24):7396-7410, 2015. URL: https://doi.org/10.1080/00207543.2015.1081427.
  31. Stefan Ropke and David Pisinger. An adaptive large neighborhood search heuristic for the pickup and delivery problem with time windows. Transportation science, 40(4):455-472, 2006. URL: https://doi.org/10.1287/trsc.1050.0135.
  32. Nikolaos V Sahinidis. Optimization under uncertainty: state-of-the-art and opportunities. Computers & Chemical Engineering, 28(6-7):971-983, 2004. URL: https://doi.org/10.1016/j.compchemeng.2003.09.017.
  33. Paul Shaw. Using constraint programming and local search methods to solve vehicle routing problems. In Principles and Practice of Constraint Programming - CP98, volume 1520 of Lecture Notes in Computer Science, pages 417-431, Berlin, Heidelberg, 1999. Springer Berlin Heidelberg. URL: https://doi.org/10.1007/3-540-49481-2_30.
  34. Karmel S. Shehadeh and Mohan Chiriki. 13th aimms-mopta optimization modeling competition. In Modeling and Optimization: Theory and Applications (MOPTA), 2021. URL: https://coral.ise.lehigh.edu/~mopta/competition.
  35. Yong Shi, Toufik Boudouh, Olivier Grunder, and Deyun Wang. Modeling and solving simultaneous delivery and pick-up problem with stochastic travel and service times in home health care. Expert systems with applications, 102:218-233, 2018. URL: https://doi.org/10.1016/j.eswa.2018.02.025.
  36. Kenneth Sörensen and Marc Sevaux. A practical approach for robust and flexible vehicle routing using metaheuristics and monte carlo sampling. Journal of mathematical modelling and algorithms, 8(4):387, 2009. URL: https://doi.org/10.1007/s10852-009-9113-5.
  37. Biao Yuan, Ran Liu, and Zhibin Jiang. A branch-and-price algorithm for the home health care scheduling and routing problem with stochastic service times and skill requirements. International Journal of Production Research, 53:7450-7464, 2015. URL: https://doi.org/10.1080/00207543.2015.1082041.
  38. Yang Zhan and Guohua Wan. Vehicle routing and appointment scheduling with team assignment for home services. Computers & Operations Research, 100:1-11, 2018. URL: https://doi.org/10.1016/j.cor.2018.07.006.
  39. Yang Zhan, Zizhuo Wang, and Guohua Wan. Home service routing and appointment scheduling with stochastic service times. European Journal of Operational Research, 288(1):98-110, 2021. URL: https://doi.org/10.1016/j.ejor.2020.05.037.
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact