حل مسئله مسیریابی وسایل نقلیه چند انباره با در نظر گرفتن پنجره زمانی و تقاضای فازی با استفاده از الگوریتم‌های فرا ابتکاری در خدمات بهداشت خانگی

نوع مقاله: مقاله پژوهشی

نویسندگان

1 دانشکده مهندسی صنایع و سیستم، پردیس دانشکده های فنی، دانشگاه تهران، تهران، ایران.

2 دانشکده مهندسی صنایع، دانشگاه علم و صنعت ایران، تهران، ایران.

چکیده

در دنیای امروز، برطرف کردن نیازهای بهداشتی و درمانی بیماران در منزل دارای فواید متعددی است. با ارائه خدمات درمانی به‌صورت منظم و به‌موقع، علاوه بر کاهش هزینه‌ها، روند بهبودی بیمار نیز سرعت می­یابد. در این مقاله، یک مسئله مسیریابی وسایل نقلیه چند انباره با در نظر گرفتن پنجره زمانی و تقاضای فازی در نظر گرفته‌شده است. این مسئله، درصدد است تا با مدل‌های ریاضی و بهینه‌سازی به‌گونه‌ای عمل کند که مسافت طی شده، زمان کل سفر، تعداد وسایل حمل‌ونقل و تابع هزینه حمل‌ونقل حداقل گردد و با در نظر گرفتن پنجره زمانی سخت، جهت ملاقات بیماران، رضایت بیماران افزایش یابد. این مسئله جزء مسائل پیچیده و متعلق به کلاس NP-hard است و حل آن از طریق برنامه­ریزی خطی و نرم‌افزارهای موجود مدت‌زمان بالایی را به خود اختصاص می­دهد. لذا در این مقاله برای حل آن از دو رویکرد فرا ابتکاری شامل الگوریتم ژنتیک و بهینه­سازی ازدحام ذرات استفاده‌شده است. با توجه به حساسیت الگوریتم‌های فرا ابتکاری به مقدار پارامترهایشان، برای تنظیم این پارامترها از متدولوژی سطح پاسخ استفاده‌شده است. تعدادی مسئله برای نشان دادن کارایی الگوریتم­های پیشنهادی حل‌شده است و نتایج محاسباتی با نرم‌افزار GAMS مقایسه شده است. 

کلیدواژه‌ها

موضوعات


عنوان مقاله [English]

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

نویسندگان [English]

  • Masoud Rabbani 1
  • Maryam Tohidi Fard 1
  • Mohammad Partovi 1
  • Hamed Farrokhi-Asl 2
1 School of Industrial Engineering, College of Engineering, University of Tehran, Tehran, Iran.
2 School of Industrial Engineering, Iran University of Science & Technology, Tehran, Iran.
چکیده [English]

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.

کلیدواژه‌ها [English]

  • vehicle routing problem
  • time windows
  • fuzzy demands
  • response surface method
  • Metaheuristic Algorithms

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.