Route Optimization for Blood Bank Visits in Tacloban City Using the Traveling Salesman Problem

Efficient access to blood banks is critical for patient care in regions experiencing persistent shortages of blood supply. This study applies the Traveling Salesman Problem (TSP) framework to optimize travel routes among eight major blood banks in Tacloban City, Philippines. Using data on distance, time, and fare collected through field observations, Google Maps, and local fare matrices, weighted graphs were constructed to represent inter-hospital connectivity. The Greedy Algorithm was employed to generate heuristic solutions for minimizing total travel burdens from multiple starting points. Results showed that optimal paths varied depending on the choice of starting facility, with centrally located hospitals such as Mother of Mercy Hospital and Divine Word Hospital producing shorter routes in terms of both time and cost. By contrast, the Eastern Visayas Medical Center, being geographically isolated, consistently resulted in higher travel distances. Findings demonstrate that heuristic approaches can effectively support healthcare logistics by reducing cost and time for patients’ families during emergencies. This research contributes to the growing body of work integrating combinatorial optimization into public health logistics, offering insights for planners, administrators, and policymakers.

Traveling Salesman Problem, healthcare logistics

1. Department of Health, Philippines. (2020). Philippine National Blood Services Program Annual Report. [Google Scholar] [Crossref]

2. Dorigo, M., & Gambardella, L. M. (1997). Ant colony system: A cooperative learning approach to the traveling salesman problem. IEEE Transactions on Evolutionary Computation, 1(1), 53–66. https://doi.org/10.1109/4235.585892 [Google Scholar] [Crossref]

3. Dantzig, G., Fulkerson, R., & Johnson, S. (1954). Solution of a large-scale traveling-salesman problem. Journal of the Operations Research Society of America, 2(4), 393–410. [Google Scholar] [Crossref]

4. Holland, J. H. (1992). Adaptation in natural and artificial systems. MIT Press. [Google Scholar] [Crossref]

5. Cormen, T. H., Leiserson, C. E., Rivest, R. L., & Stein, C. (2009). Introduction to algorithms (3rd ed.). MIT Press. [Google Scholar] [Crossref]

6. Little, J. D. C., Murty, K. G., Sweeney, D. W., & Karel, C. (1963). An algorithm for the traveling salesman problem. Operations Research, 11(6), 972–989. [Google Scholar] [Crossref]

7. Liu, G., Xu, X., Wang, F., & Tang, Y. (2022). Solving traveling salesman problems based on artificial cooperative search algorithm. Computational Intelligence and Neuroscience, 2022, Article 1008617. https://doi.org/10.1155/2022/1008617 [Google Scholar] [Crossref]

8. Pop, P.C., Cosma, O., Sabo, C., Pop Sitar, C. (2024), A comprehensive survey on the generalized traveling salesman problem, European Journal of Operational Research, 314 (3), 819-835. https://doi.org/10.1016/j.ejor.2023.07.022. [Google Scholar] [Crossref]

9. Raykar N.P., Makin J., Khajanchi M., Olayo B., Munoz Valencia A., Roy N., Ottolino P., Zinco A., MacLeod J., Yazer M., Rajgopal J., Zeng B., Lee H.K., Bidanda B., Kumar P., Puyana J.C., Rudd K. (2021). Assessing the global burden of hemorrhage: The global blood supply, deficits, and potential solutions. SAGE Open Med. 9. doi: 10.1177/20503121211054995. [Google Scholar] [Crossref]

10. Teng, F., Wu, X., Zhang, L., Zhang, Y., & Chen, L. (2022). Research on improved ant colony optimization for traveling salesman problem. Mathematical Biosciences and Engineering, 19(8), 8152–8186. https://doi.org/10.3934/mbe.2022381 [Google Scholar] [Crossref]

11. World Health Organization. (n.d.). Blood transfusion safety. https://www.who.int/health-topics/blood-transfusion-safety#tab=tab_1 [Google Scholar] [Crossref]

12. Leyte Samar Daily News. (2024). [Details on dengue outbreak and blood shortages]. (Unpublished manuscript) [Google Scholar] [Crossref]

• Tribal Child Nutrition and Health in District of Sundargarh: A Public Health Review of ICDS Intervention
• Knowledge, Attitudes and Practices Towards Prostate Cancer Screening Amongst Men Aged 40-60 Years in The Buea Health District: A Cross-Sectional Study
• Compliance with JCI Protocols: A Focus on Employee Safety
• Influence and Involvement of Teachers in Menstrual Hygiene Management of Female Secondary School Students in Kogi State, Nigeria
• A Critical Evaluation of Ayushman Bharat Pradhan Mantri Jan Arogya Yojana in Bihar