Solving a multi-depot vehicle routing problem with time windows and fuzzy demands using metaheuristic algorithms in home health care services

Rabbani, Masoud; Tohidi Fard, Maryam; Partovi, Mohammad; Farrokhi-Asl, Hamed

doi:10.22105/dmor.2018.65276

Document Type : Original Article

Authors

¹ School of Industrial Engineering, College of Engineering, University of Tehran, Tehran, Iran.

² School of Industrial Engineering, Iran University of Science & Technology, Tehran, Iran.

https://doi.org/10.22105/dmor.2018.65276

Abstract

Todays, meeting the healthcare needs of patients at home has many benefits. By providing regular and timely healthcare servicing, in addition to reducing costs, the patient's recovery process also speeds up. In this paper, a multi-depot vehicle routing problem is considered with regard to time windows and fuzzy demands. This paper attempts to optimize provided mathematical formulation in such a way that the distance traveled, total travel time, the number of transportation vehicles and transportation cost be minimized; also by taking the hard time window to meet patients , patient satisfaction rate will increase. This is a complex and difficult problem, and it takes a long time to solve it through linear programming and existing software. Therefore, in this paper, two general approaches including genetic algorithm and particle swarm optimization are used to tackle the problem. The response surface methodology (RSM) has been used to set parameters for meta-algorithms. To illustrate the efficiency of proposed algorithms, a number of test problems are solved and computational results are compared with the solutions obtained with the GAMS software.

Keywords

Main Subjects

supply chain management analyzing/modelling

References

Allaoua, H., Borne, S., Létocart, L., & Calvo, R. W. (2013). A matheuristic approach for solving a home health care problem. Electronic notes in discrete mathematics, 41,471-478.

Amirsadi, A., & Soleimani, H. (2005). Evaluating the phenomenon of aging and its consequences in Iran. Journal of health and wellbeing, 1(2), 19-35.

Bell, W. J., Dalberto, L. M., Fisher, M. L., Greenfield, A. J., Jaikumar, R., Kedia, P., ... & Prutzman, P. J. (1983). Improving the distribution of industrial gases with an on-line computerized routing and scheduling optimizer. Interfaces, 13(6), 4-23.

Bertels, S., & Fahle, T. (2006). A hybrid setup for a hybrid scenario: combining heuristics for the home health care problem. Computers & operations research, 33(10), 2866-2890.

Braekers, K., Hartl, R. F., Parragh, S. N., & Tricoire, F. (2016). A bi-objective home care scheduling problem: Analyzing the trade-off between costs and client inconvenience. European journal of operational research, 248(2), 428-443.

Bredström, D., & Rönnqvist, M. (2008). Combined vehicle routing and scheduling with temporal precedence and synchronization constraints. European journal of operational research, 191(1), 19-31.

Cappanera, P., Scutellà, M. G., & Visintin, F. (2014). Home Care Services delivery: equity versus efficiency in optimization models. Proceedings of the international conference on health care systems engineering. Springer.

Cheng, E., & Rich, J. L. (1998). A home health care routing and scheduling problem. Retrieved from CAAM Technical Reports.

Dantzig, G. B., & Ramser, J. H. (1959). The truck dispatching problem. Management science, 6(1), 80-91.

Decerle, J., Grunder, O., El Hassani, A. H., & Barakat, O. (2016). A two-phases matheuristic for the home care routing and scheduling problem. IFAC-PapersOnLine, 49(12), 1484-1489.

En-nahli, L., Afifi, S., Allaoui, H., & Nouaouri, I. (2016). Local search analysis for a vehicle routing problem with synchronization and time windows constraints in home health care services. IFAC-PapersOnLine, 49(12), 1210-1215.

Engelbrecht, A. P. (2006). Fundamentals of computational swarm intelligence. John Wiley & Sons.

En-nahli, L., Allaoui, H., & Nouaouri, I. (2015). A multi-objective modelling to human resource assignment and routing problem for home health care services. IFAC-PapersOnLine, 48(3), 698-703.

Frifita, S., Masmoudi, M., & Euchi, J. (2017). General variable neighborhood search for home healthcare routing and scheduling problem with time windows and synchronized visits. Electronic notes in discrete mathematics, 58, 63-70.

Majidi, S., Hosseini-Motlagh, S. M., Yaghoubi, S., & Jokar, A. (2017). Fuzzy green vehicle routing problem with simultaneous pickup–delivery and time windows. RAIRO-operations research, 51(4), 1151-1176.

Ho, W., Ho, G. T., Ji, P., & Lau, H. C. (2008). A hybrid genetic algorithm for the multi-depot vehicle routing problem. Engineering applications of artificial intelligence, 21(4), 548-557.

Hu, X., Shi, Y., & Eberhart, R. (2004, June). Recent advances in particle swarm. Proceedings of the 2004 congress on evolutionary computation (IEEE Cat. No.04TH8753). Portland, OR, USA: IEEE.

Jiao, B., Lian, Z., & Gu, X. (2008). A dynamic inertia weight particle swarm optimization algorithm. Chaos, solitons & fractals, 37(3), 698-705.

Kergosien, Y., Lenté, C., & Billaut, J.-C. (2009). Home health care problem: An extended multiple traveling salesman problem. Proceedings of the 4th multidisciplinary international conference on scheduling: Theory and applications (MISTA'09). Dublin (Irlande).

Kergosien, Y., Ruiz, A., & Soriano, P. (2014). A routing problem for medical test sample collection in home health care services. Proceedings of the international conference on health care systems engineering (pp. 29-46). Springer.

Liu, R., Xie, X., Augusto, V., & 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, 230(3), 475-486.

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

Mankowska, D. S., Meisel, F., & Bierwirth,C. (2014). The home health care routing and scheduling problem with interdependent services. Health care management science, 17(1), 15-30.

Nickel, S., Schröder, M., & Steeg, J. (2012). Mid-term and short-term planning support for home health care services. European journal of operational research, 219(3), 574-587.

Ombuki-Berman, B., & Hanshar, F. T. (2009). Using genetic algorithms for multi-depot vehicle routing. Bio-inspired algorithms for the vehicle routing problem (pp.77-99). Berlin, Heidelberg: Springer.

Potvin, J. Y., & Rousseau, J. M. (1995). An exchange heuristic for routeing problems with time windows. Journal of the operational research society, 46(12), 1433-1446.

Rasmussen, M. S., Justesen, T., Dohn, A., & Larsen, J. (2012). The home care crew scheduling problem: Preference-based visit clustering and temporal dependencies. European journal of operational research, 219(3), 598-610.

Talbi, E. G. (2009). Metaheuristics: from design to implementation. John Wiley & Sons.

Torres-Ramos, A., Alfonso-Lizarazo, E., Reyes-Rubiano, L., & Quintero-Araújo, C. (2014). Mathematical model for the home health care routing and scheduling problem with multiple treatments and timewindows. Proceedings of the 1st international conference on mathematical methods & computational techniques in science & engineering (MMCTSE 2014).

Trautsamwieser, A., & Hirsch, P. (2011). Optimization of daily scheduling for home health care services. Journal of applied operational research, 3(3), 124-136.

Yalçındağ, S., Matta, A., Şahin, E., & Shanthikumar, J. G. (2014). 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.

Yuan, B., Liu, R., & Jiang, Z. (2015). 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(24), 7450-7464.

Journal of Decisions and Operations Research

Solving a multi-depot vehicle routing problem with time windows and fuzzy demands using metaheuristic algorithms in home health care services

References

References

Volume 3, Issue 2
September 2018
Pages 114-127

Solving a multi-depot vehicle routing problem with time windows and fuzzy demands using metaheuristic algorithms in home health care services

References

References

Volume 3, Issue 2September 2018Pages 114-127

Volume 3, Issue 2
September 2018
Pages 114-127