Improving Service Bus Routes for Patient Ergonomics

Yıl 2021, Cilt: 13 Sayı: 3, 98 - 108, 31.12.2021

Beyza Gunesen Muzaffer Kapanoğlu

https://doi.org/10.29137/umagd.1014407

Öz

Patient ergonomics requires optimizing system performance and patient comfort concurrently. The patient-oriented design of all services offered in health institutions is crucial in terms of increasing service quality and patient satisfaction. In this research, the problem of optimization of the routes of the shuttle vehicles offered for the patients who are treated in the dialysis centers to the center is emphasized. With the improvement of the routes, it is aimed to reduce the waiting time of the patients and the travel times spent in the service as much as possible. Patient comfort will be increased by the effective rotation of service vehicles. The problem of routing vehicles has been considered as the Multiple Traveling Salesman Problem since the starting and ending points include the activities of the same more than one vehicle, picking all patients up from their locations and delivering them to the center. A solution method has been developed for the problem, which takes into account the minimization of the longest distance and the total distance of the service vehicles. The method consists of two main steps, clustering and routing. In the first step, the locations are clustered with the k-means method, and in the second step, they are routed by the sequential use of Nearest Neighbor Heuristics and 2-opt algorithms. The results obtained were compared with the results of the mathematical model of the problem, and the longest distance traveled by a vehicle, the sum of the distances and the solution time were determined as performance criteria. The proposed method approached the best solution in the first criterion and gave better results in other two criteria.

Anahtar Kelimeler

Patient ergonomics, dialysis center, multi objective optimization, multiple travelling salesman problem

Hasta Ergonomisi Açısından Servis Güzergâhlarının İyileştirilmesi

Öz

Hasta ergonomisi, sistem performansının ve hasta konforunun birlikte optimize edilmesini gerektirir. Sağlık kuruluşlarında sunulan tüm hizmetlerin hasta odaklı tasarımı, hizmet kalitesinin ve hasta memnuniyetinin artırılması bakımından oldukça önemlidir. Bu çalışmada diyaliz merkezlerinde tedavi gören hastaların merkeze geliş gidişleri için sunulan servis araçlarına ait rotaların optimizasyonu problemi üzerinde durulmuştur. Rotaların iyileştirilmesi ile hastaların servis içerisinde geçirilen yolculuk sürelerinin mümkün olduğunca azaltılması ve dengelenmesi hedeflenmektedir. Servis araçlarının rotasyonunun etkin biçimde gerçekleştirilmesi ile hasta konforu arttırılacaktır. Servis araçlarının rotalanması problemi, başlangıç ve bitiş noktaları aynı birden fazla servis aracının tüm hastaları konumlarından alıp merkeze getirilmesi faaliyetlerini içerdiğinden Çoklu Gezgin Satıcı Problemi olarak ele alınmıştır. Problem kapsamında, servis araçlarına ait en uzun mesafenin ve toplam mesafenin en küçüklenmesini gözeten bir çözüm yöntemi geliştirilmiştir. Yöntem kümeleme ve rotalama olmak üzere iki ana adımdan meydana gelmektedir. Birinci adımda konumlar k – ortalamalar yöntemi ile kümelenmekte ikinci adımda ise En Yakın Komşu Sezgiseli ve 2 – opt algoritmalarının ardışık kullanımı ile rotalanmaktadır. Varılan sonuçlar probleme ait matematiksel model sonuçları ile karşılaştırılmış, bir servis aracının kat ettiği en uzun mesafe, tüm araçların katettiği mesafeler toplamı ve çözüm süresi performans kriterleri olarak belirlenmiştir. Yöntem ilk en iyi çözüme yaklaşmış diğer kriterlerde ise daha iyi sonuçlar vermiştir.

Anahtar Kelimeler

Hasta ergonomisi, diyaliz merkezi, çok – amaçlı optimizasyon, çoklu gezgin satıcı problemi

Kaynakça

• Abbasi, M. A., Chertow, G. M., & Hall, Y. N. (2010). End-stage renal disease. BMJ clinical evidence, 2010.
• Al Saran, K., & Sabry, A. (2012). The cost of hemodialysis in a large hemodialysis center. Saudi Journal of Kidney Diseases and Transplantation, 23(1), 78.
• Angel, R. D., Caudle, W. L., Noonan, R., & Whinston, A. N. D. A. (1972). Computer-assisted school bus scheduling. Management Science, 18(6), B-279.
• Bektas, T. (2006). The multiple traveling salesman problem: an overview of formulations and solution procedures. Omega, 34(3), 209-219.
• Bikbov, B., Purcell, C. A., Levey, A. S., Smith, M., Abdoli, A., Abebe, M., ... & Owolabi, M. O. (2020). Global, regional, and national burden of chronic kidney disease, 1990–2017: a systematic analysis for the Global Burden of Disease Study 2017. The Lancet, 395(10225), 709-733.
• Bolaños, R., Echeverry, M., & Escobar, J. (2015). A multiobjective non-dominated sorting genetic algorithm (NSGA-II) for the Multiple Traveling Salesman Problem. Decision Science Letters, 4(4), 559-568.
• Brumitt, B. L., & Stentz, A. (1996, April). Dynamic mission planning for multiple mobile robots. In Proceedings of IEEE International Conference on Robotics and Automation (Vol. 3, pp. 2396-2401). IEEE.
• Campbell, S. M., Braspenning, J. A., Hutchinson, A., & Marshall, M. (2002). Research methods used in developing and applying quality indicators in primary care. Quality and Safety in Health Care, 11(4), 358-364.
• Carter, A. E. (2003). Design and application of genetic algorithms for the multiple traveling salesperson assignment problem (Doctoral dissertation, Virginia Tech).
• Carter, A. E., & Ragsdale, C. T. (2002). Scheduling pre-printed newspaper advertising inserts using genetic algorithms. Omega, 30(6), 415-421.
• Croes, G. A. (1958). A method for solving traveling-salesman problems. Operations research, 6(6), 791-812.
• Dantzig, G. B., & Ramser, J. H. (1959). The truck dispatching problem. Management science, 6(1), 80-91.
• Gavish, B. (1976). Note—a note on “the formulation of the m-salesman traveling salesman problem”. Management Science, 22(6), 704-705.
• Gilbert, K.C. & Hofstra, R.B. (1992). A new multiperiod multiple traveling salesman problem with heuristic and application to a scheduling problem. Decision Sciences, Vol. 23, pp.250–9.
• Gulcu, S. D., & Ornek, H. K. (2019). Solution of multiple travelling salesman problem using particle swarm optimization based algorithms. International Journal of Intelligent Systems and Applications in Engineering, 7(2), 72-82.
• Gunesen, Beyza (2021), “Data For: Euclidean Matrix”, Mendeley Data, V1, doi: 10.17632/rvv4ymck92.1
• Gurses, A. P., Ozok, A. A., & Pronovost, P. J. (2012). Time to accelerate integration of human factors and ergonomics in patient safety. BMJ quality & safety, 21(4), 347-351.
• Holland, J. (1994). Scheduling patients in hemodialysis centers. Production and inventory management journal, 35(2), 76. http://comopt.ifi.uni-heidelberg.de/software/TSPLIB95/ https://nefroloji.org.tr/tr/
• Huang, Z. (1998). Extensions to the k-means algorithm for clustering large data sets with categorical values. Data mining and knowledge discovery, 2(3), 283-304.
• Joss, R., & Kogan, M. (1995). Advancing quality: Total quality management in the National Health Service. Open university press.
• Journal of Operational Research, Vol. 124, pp. 267–82
• Junjie, P., & Dingwei, W. (2006, August). An ant colony optimization algorithm for multiple travelling salesman problem. In First International Conference on Innovative Computing, Information and Control-Volume I (ICICIC'06) (Vol. 1, pp. 210-213). IEEE.
• K. Helsgaun. An Effective Implementation of the Lin-Kernighan Traveling Salesman Heuristic,Department of Computer Science, Roskilde University.
• Kara, I., & Bektas, T. (2006). Integer linear programming formulations of multiple salesman problems and its variations. European Journal of Operational Research, 174(3), 1449-1458.
• Kitjacharoenchai, P., Ventresca, M., Moshref-Javadi, M., Lee, S., Tanchoco, J. M., & Brunese, P. A. (2019). Multiple traveling salesman problem with drones: Mathematical model and heuristic approach. Computers & Industrial Engineering, 129, 14-30.
• Kodinariya, T. M., & Makwana, P. R. (2013). Review on determining number of Cluster in K-Means Clustering. International Journal, 1(6), 90-95.
• Laporte, G. & Nobert, Y. (1980). A cutting planes algorithm for the m-salesmen problem. Journal of the Operational Research Society, Vol. 31, pp.1017–23.
• Latah, M. (2016). Solving multiple TSP problem by K-means and crossover based modified ACO algorithm. International Journal of Engineering Research and Technology, 5(02).
• Lin, S. & Kernighan, B. (1973). An effective heuristic algorithm for the traveling salesman problem. Operations Research, Vol. 21, pp. 498–516.
• Liu, W., Li, S., Zhao, F., & Zheng, A. (2009, May). An ant colony optimization algorithm for the multiple traveling salesmen problem. In 2009 4th IEEE conference on industrial electronics and applications (pp. 1533-1537). IEEE.
• Lu, J., & Hu, R. (2013, March). A new hybrid clustering algorithm based on K-means and ant colony algorithm. In Proceedings of the 2nd International Conference on Computer Science and Electronics Engineering (pp. 1718-1721). Atlantis Press.
• Matai, R., Singh, S. P., & Mittal, M. L. (2010). Traveling salesman problem: an overview of applications, formulations, and solution approaches. Traveling salesman problem, theory and applications, 1.
• Matsuura, T., & Numata, K. (2014, September). Solving min-max multiple traveling salesman problems by chaotic neural network. In International Symposium on Nonlinear Theory and its Applications.
• Miller, C.E.; Tucker, A.W. & Zemlin, R.A.(1960). Integer programming formulation of traveling salesman problems. Journal of Association for Computing Machinery, Vol. 7, pp. 326–9.
• Na, S., Xumin, L., & Yong, G. (2010, April). Research on k-means clustering algorithm: An improved k-means clustering algorithm. In 2010 Third International Symposium on intelligent information technology and security informatics (pp. 63-67). IEEE.
• Nallusamy, R., Duraiswamy, K., Dhanalaksmi, R., & Parthiban, P. (2010). Optimization of non-linear multiple traveling salesman problem using k-means clustering, shrink wrap algorithm and meta-heuristics. International Journal of Nonlinear Science, 9(2), 171-177.
• Napoleon, D., & Lakshmi, P. G. (2010, December). An efficient K-Means clustering algorithm for reducing time complexity using uniform distribution data points. In Trendz in information sciences & computing (TISC2010) (pp. 42-45). IEEE.
• Necula, R., Breaban, M., & Raschip, M. (2015, November). Tackling the bi-criteria facet of multiple traveling salesman problem with ant colony systems. In 2015 IEEE 27th International Conference on Tools with Artificial Intelligence (ICTAI) (pp. 873-880). IEEE.
• Necula, R., Raschip, M., & Breaban, M. (2018). Balancing the subtours for multiple TSP approached with ACS: Clustering-based approaches vs. MinMax formulation. In EVOLVE-A Bridge between Probability, Set Oriented Numerics, and Evolutionary Computation VI (pp. 210-223). Springer, Cham.
• Nuriyeva, F., & Kizilates, G. (2017). A new heuristic algorithm for multiple traveling salesman problem. TWMS Journal of Applied and Engineering Mathematics, 7(1), 101-109.
• Rosenkrantz, D. J., Stearns, R. E., & Lewis, II, P. M. (1977). An analysis of several heuristics for the traveling salesman problem. SIAM journal on computing, 6(3), 563-581.
• Shabanpour, M., Yadollahi, M., & Hasani, M. M. (2017). A New Method to Solve the Multi Traveling Salesman Problem with the Combination of Genetic Algorithm and Clustering. IJCSNS, 17(5), 221.
• Shuai, Y., Yunfeng, S., & Kai, Z. (2019). An effective method for solving multiple travelling salesman problem based on NSGA-II. Systems Science & Control Engineering, 7(2), 108-116.
• Singh, A. (2016). A review on algorithms used to solve multiple travelling salesman problem. International Research Journal of Engineering and Technology (IRJET), 3(4), 598-603.
• Singh, S., & Lodhi, E. A. (2013). Study of variation in TSP using genetic algorithm and its operator comparison. International Journal of Soft Computing and Engineering, 3(2), 264-267.
• Somhom, S., Modares, A., & Enkawa, T. (1999). Competition-based neural network for the multiple travelling salesmen problem with minmax objective. Computers & Operations Research, 26(4), 395-407.
• Soylu, B. (2015). A general variable neighborhood search heuristic for multiple traveling salesmen problem. Computers & Industrial Engineering, 90, 390-401.
• Springer, T. (2007). Ergonomics for healthcare environments. Geneva, IL: Knoll, HERO.
• Svestka, J.A. & Huckfeldt, V.E. (1973). Computational experience with an m-salesman traveling salesman algorithm. Management Science, Vol. 19, No. 7, pp. 790–9.
• Sze, S., & Tiong, W. (2007). A comparison between heuristic and meta-heuristic methods for solving the multiple traveling salesman problem. World Academy of Science, Engineering and Technology, 1.
• Taiwo, O. S., Josiah, O., Taiwo, A., Dkhrullahi, S., & Sade, O. K. (2013). Implementation of heuristics for solving travelling salesman problem using nearest neighbor and nearest insertion approaches. International Journal of Advance Research, 1(3), 139-155.
• Tang, L., Liu, J., Rong, A., & Yang, Z. (2000). A multiple traveling salesman problem model for hot rolling scheduling in Shanghai Baoshan Iron & Steel Complex. European Journal of Operational Research, 124(2), 267-282.
• Tiong, W. K. (2007). A Comparison between Heuristic and Meta-Heuristic Methods for Solving the Multiple Traveling Salesman Problem. International Journal of Mathematical and Computational Sciences, 1(1), 13-16.
• Xu, X., Yuan, H., Liptrott, M., & Trovati, M. (2018). Two phase heuristic algorithm for the multiple-travelling salesman problem. Soft Computing, 22(19), 6567-6581.
• Yu, Q., Wang, D., Lin, D., Li, Y., & Wu, C. (2012, June). A novel two-level hybrid algorithm for multiple traveling salesman problems. In International Conference in Swarm Intelligence (pp. 497-503). Springer, Berlin, Heidelberg.
• Yuan, S., Skinner, B., Huang, S., & Liu, D. (2013). A new crossover approach for solving the multiple travelling salesmen problem using genetic algorithms. European Journal of Operational Research, 228(1), 72-82.
• Zhang, T.; Gruver, W.A. & Smith, M.H. (1999). Team scheduling by genetic search. Proceedings of the second international conference on intelligent processing and manufacturing of materials, Vol. 2,. pp. 839–44.