A Vehicle Routing Problem for Modeling Home Healthcare: a Case Study

Document Type: Research Paper


1 MSc Student, School of Industrial Engineering, Iran University of Science and Technology, Tehran, Iran

2 Assistant Professor, School of Industrial Engineering, Iran University of Science and Technology, Tehran, Iran

3 Instructor, School of Industrial Engineering, Iran University of Science and Technology, Tehran, Iran


Compared to center-based hemodialysis (HD), peritoneal dialysis (PD) has many advantages among which cost effectiveness and comfort of patients are the most important ones. On the other hand the number of PD patients is so small and even decreasing worldwide due to difficulties of this mode of dialysis. Therefore to encourage dialysis patients to choose PD, health system must provide a proper set of care services proportional to special needs of these patients.Applying operations research (OR) as an efficient mathematical tool and considering the realistic assumptions such as travel time uncertainty, first a Vehicle Routing Problem model is presented to serve PD patients at home with special logistic services. Thereafter, based on the criticality of timeliness in providing healthcare service, a conservative method called robust optimization, is applied to handle time uncertainty. The corresponding results show that the proposed method at the maximum uncertainty level has less than 30% variations in results and in comparison with the deterministic model increases the costs only by 1.2%.With small variations in results,this model can handle the travel time uncertainty properly and is highly appropriate and practical to be used in a sensitive application like healthcare where timeliness is crucial.


-Barnhart, C., Johnson, E. L., Nemhauser, G. L., Savelsbergh, M. W. and Vance, P. H. (1998) "Branch-and-price: Column generation for solving huge integer programs", Operations Research, Vol. 46, pp. 316-329.

-Begur, S. V., Miller, D. M. and Weaver, J. R. (1997) "An integrated spatial DSS for scheduling and routing home-health-care nurses", Interfaces, Vol. 27, pp. 35-48.

-Ben-Tal, A., El Ghaoui, L. and Nemirovski, A. (2009). "Robust optimization", Princeton University Press.

-Ben-Tal, A. and Nemirovski, A. (1998) "Robust convex optimization", Mathematics of Operations Research, Vol. 23, pp. 769-805.

-Bertels, S. and Fahle, T. (2006) "A hybrid setup for a hybrid scenario: combining heuristics for the home health care problem", Computers and Operations Research, Vol. 33, pp. 2866-2890.

-Bertsimas, D. and Sim, M. (2004) "The price of robustness", Operations Research, Vol. 52, PP. 35-53.

-Braekers, K., Hartl, R. F., Parragh, S. N. and Tricoire, F. (2016) "A bi-objective home care scheduling problem: Analyzing the trade-off between costs and client inconvenience", European Journal of Operational Research, Vol. 248, pp. 428-443.

-Bredstrom, D. and Rönnqvist, M. (2007) "A branch and price algorithm for the combined vehicle routing and scheduling problem with synchronization constraints" NHH Dept. of Finance and Management Science Discussion Paper.

-Cappanera, P. and Scutellà, M. G. (2013) " Home care optimization: Impact of pattern generation policies on scheduling and routing decisions", International Network Optimization Conference.

-Cappanera, P., Scutellà, M. G. and Visintin, F. (2014) "Home Care Services delivery: equity versus efficiency in optimization models", Proceedings of the International Conference on Health Care Systems Engineering, Springer, pp. 1-13.

-Castillo-Salazar, J. A., Landa-Silva, D. and Qu, R. (2014) "Workforce scheduling and routing problems: literature survey and computational study", Annals of Operations Research, pp. 1-29.

-Cheng, E. and Rich, J. L. (1998) "A home health care routing and scheduling problem", URL http://citeseerx. ist. psu. edu/viewdoc/summary.

-Cheraghi, S., & Hosseini-Motlagh, S. M. (2017). "Optimal blood transportation in disaster relief considering facility disruption and route reliability under uncertainty". International Journal of Transportation Engineering,Vol.4, pp. 225-254.

-Cheraghi, S., Hosseini-Motlagh, S. M., & Ghatreh Samani, M. (2017). "Integrated planning for blood platelet production: a robust optimization approach". Journal of Industrial and Systems Engineering, vol.10,pp. 55-80.

-Dohn, A., Rasmussen, M. S., Justesen, T. and Larsen, J. (2008) " The home care crew scheduling problem", Proceedings of the 1st international conference on applied operational research (ICAOR’08), Yerevan, Armenia. Lecture Notes in Management Science, pp. 1-8.

-El Ghaoui, L., Oustry, F. and Lebret, H. (1998) "Robust solutions to uncertain semidefinite programs", SIAM Journal on Optimization, Vol. 9, pp. 33-52.

-Fischetti, M. and Monaci, M. (2009) "Light robustness", Robust and online large-scale optimization. Springer, pp. 61-84.

-Ghatreh Samani, M., & Hosseini-Motlagh, S. M. (2017)."A Hybrid algorithm for a two-echelon location-routing problem with simultaneous pickup and delivery under fuzzy demand", International Journal of Transportation Engineering, Vol 5,pp. 59-85.

-Griva, K., Yu, Z., Chan, S., Krisnasamy, T., Yamin, R. B. A., Zakaria, F. B., Wu, S. Y., Oei, E. and Foo, M. (2014) "Age is not a contraindication to home‐based dialysis–Quality‐of‐Life outcomes favour older patients on peritoneal dialysis regimes relative to younger patients", Journal of Advanced Nursing, Vol. 70, pp. 1902-1914.

-Holte, M. and Mannino, C. (2013) "The implementor/adversary algorithm for the cyclic and robust scheduling problem in health-care", European Journal of Operational Research, Vol. 226, pp. 551-559.

-Jain, A. K., Blake, P., Cordy, P. and Garg, A. X. (2012) "Global trends in rates of peritoneal dialysis",  Journal of the American Society of Nephrology, Vol. 23, pp. 533-544.

-Jokar, A., & Hosseini-Motlagh, S. M. (2015). "Impact of capacity of mobile units on blood supply chain performance: Results from a robust analysis",International Journal of Hospital Research,Vol 4,pp. 101-105.

-Kergosien, Y., Lenté, C. and Billaut, J.-C. (2009) "Home health care problem: An extended multiple traveling salesman problem", 4th Multidisciplinary International Conference on Scheduling: Theory and Applications (MISTA'09), Dublin (Irlande), pp. 10-12.

-Kergosien, Y., Ruiz, A. and Soriano, P. (2014) "Published. A routing problem for medical test sample collection in home health care services", Proceedings of the International Conference on Health Care Systems Engineering, Springer, pp. 29-46.

-Klarenbach, S. and Manns, B. (2009) "Economic evaluation of dialysis therapies",  Seminars in Nephrology, Elsevier, pp. 524-532.

-Lanzarone, E. and Carello, G. (2014) "Applying the Cardinality–Constrained Approach in Health Care Systems: The Home Care Example".  Proceedings of the International Conference on Health Care Systems Engineering, Springer, pp. 61-72.

-Li, Z., Ding, R. and Floudas, C. A. (2011) "A comparative theoretical and computational study on robust counterpart optimization: I. Robust linear optimization and robust mixed integer linear optimization", Industrial and Engineering Chemistry Research, Vol. 50, pp. 10567-10603.

-Liem, Y. S., Wong, J., Hunink, M., de Charro, F. T. and Winkelmayer, W. (2007) "Comparison of hemodialysis and peritoneal dialysis survival in The Netherlands", Kidney International, Vol. 71, pp. 153-158.

-Liu, R., Xie, X., Augusto, V. and Rodriguez, C. (2013) "Heuristic algorithms for a vehicle routing problem with simultaneous delivery and pickup and time windows in home health care", European Journal of Operational Research, Vol. 230, pp. 475-486.

-Liu, R., Xie, X. and Garaix, T. (2014) "Hybridization of tabu search with feasible and infeasible local searches for periodic home health care logistics", Omega, Vol. 47, pp. 17-32.

-Majidi, S., Hosseini-Motlagh, S. M., & Ignatius, J. (2017). "Adaptive large neighborhood search heuristic for pollution-routing problem with simultaneous pickup and delivery". Soft Computing,pp. 1-15.

-Hosseini-Motlagh, S. M., Majidi, S., Yaghoubi, S., & Jokar, A. (2017). "Fuzzy green vehicle routing problem with simultaneous pickup-delivery and time windows". RAIRO-Operations Research.

-McDonald, S. P., Marshall, M. R., Johnson, D. W. and Polkinghorne, K. R. (2009) "Relationship between dialysis modality and mortality",  Journal of the American Society of Nephrology, Vol. 20, pp.155-163.

-Min, H. (1989) "The multiple vehicle routing problem with simultaneous delivery and pick-up points", Transportation Research Part A: General, Vol. 23, pp. 377-386.

-Nickel, S., Schröder, M. and Steeg, J. (2012) "Mid-term and short-term planning support for home health care services", European Journal of Operational Research, Vol. 219, pp. 574-587.

-Nikkhah Qamsari, A., Hosseini Motlagh, S. M., & Jokar, A. (2017). "A two-phase hybrid heuristic method for a multi-depot inventory-routing problem". International Journal of Transportation Engineering,Vol 4,pp. 287-304.

-Perl, J., Davies, S. J., Lambie, M., Pisoni, R. L., McCullough, K., Johnson, D. W., Sloand, J. A., Prichard, S., Kawanishi, H. and Tentori, F. (2015) "The Peritoneal Dialysis Outcomes and Practice Patterns Study (PDOPPS): unifying efforts to inform practice and improve global outcomes in peritoneal dialysis", Peritoneal Dialysis International, pdi. 2014.00288.

-Pishvaee, M. S., Rabbani, M. and Torabi, S. A. (2011) "A robust optimization approach to closed-loop supply chain network design under uncertainty", Applied Mathematical Modelling, Vol. 35, pp. 637-649.

-Pishvaee, M. S., Razmi, J. and Torabi, S. A. (2012) "Robust possibilistic programming for socially responsible supply chain network design: A new approach", Fuzzy Sets and Systems, Vol. 206, pp. 1-20.

-Riahi, N., Hosseini-Motlagh, S. M., & Teimourpour, B. (2013). "A Three-phase Hybrid Times Series Modeling Framework for Improved Hospital Inventory Demand Forecast". International Journal of Hospital Research, Vol 2,pp. 133-142.

-Rubin, H. R., Fink, N. E., Plantinga, L. C., Sadler, J. H., Kliger, A. S. and Powe, N. R. (2004) "Patient ratings of dialysis care with peritoneal dialysis vs hemodialysis", Jama, Vol. 291, pp. 697-703.

-Soyster, A. L. (1973) "Technical note—convex programming with set-inclusive constraints and applications to inexact linear programming", Operations Research, Vol. 21, pp. 1154-1157.

-Stevens, L. A., Viswanathan, G. and Weiner, D. E. (2010) "CKD and ESRD in the elderly: Current prevalence, future projections, and clinical significance", Advances in Chronic Kidney Disease, Vol. 17, pp. 293.

-Torres-Ramos, A. F., Alfonso-Lizarazo, E. H., Reyes-Rubiano, L. S. and Quintero-Araújo, C. L. (2014) "Published. Mathematical Model for the Home Health Care Routing and Scheduling Problem with Multiple Treatments and Time Windows", Proceedings of the 1st International Conference on Mathematical Methods and Computational Techniques in Science and Engineering (MMCTSE 2014), pp. 140-145.

-Trautsamwieser, A., Gronalt, M. and Hirsch, P. (2011) "Securing home health care in times of natural disasters", OR Spectrum, Vol. 33, pp. 787-813.

-Treharne, C., Liu, F. X., Arici, M., Crowe, L. and Farooqui, U. (2014) "Peritoneal dialysis and in-centre haemodialysis: a cost-utility analysis from a UK payer perspective", Applied Health Economics and Health Policy, Vol. 12, pp. 409-420.

-Triki, N., Garaix, T. and Xie, X. (2014) "Published. A two-phase approach for periodic home health care planning",  Automation Science and Engineering (CASE), 2014 IEEE International Conference, pp. 518-523.

-Workeneh, B., Guffey, D., Minard, C. G. and Mitch, W. E. (2015) "Causes for Withdrawal in an Urban Peritoneal Dialysis Program", International journal of nephrology.

-Yalçındağ, S., Matta, A., Şahin, E. and Shanthikumar, J. G. (2014) "Published. A two-stage approach for solving assignment and routing problems in home health care services", Proceedings of the International Conference on Health Care Systems Engineering, Springer, pp. 47-59.

-Yu, Z. L., Seow, Y.-Y., Seow, P. S. and Tan, B. L. K. (2016) "Effectiveness of a day care program in supporting patients on peritoneal dialysis and their caregivers", International Urology and Nephrology, pp. 1-7.

-Zare-Reisabadi, E. and Mirmohammadi, S. H. (2015) "Site dependent vehicle routing problem with soft time window: Modeling and solution approach", Computers and Industrial Engineering, Vol. 90, pp. 177-185.