A Tabu Search Algorithm for Optimization of Blood Distribution Routes


  • Agus Mulyadi Universitas Muhammadiyah Riau
  • St. Nova Meirizha Universitas Muhammadiyah Riau
  • Muhammad Qurthuby Universitas Muhammadiyah Riau
  • Ari Andriyas Universitas Muhammadiyah Riau
  • Dedi Dermawan Universitas Muhammadiyah Riau
  • Denny Astrie Anggraini Universitas Muhammadiyah Riau
  • Faradila Ananda Yul Universitas Muhammadiyah Riau
  • Rozar Rayendra Universitas Muhammadiyah Riau
  • Satriardi Universitas Muhammadiyah Riau
  • Irsan Pratama Universitas Muhammadiyah Riau


PMI Blood Transfusion Unit is an agency that provides or a health service agency that organizes blood donation and blood supply. The observations and interviews showed that some existing cases were not carried out immediately and accurately, and there was no distance to align the duration with blood cells. The formation of blood distribution routes only stems from the highest number of requests and the delay in the distribution in several hospitals. Therefore, it is necessary to determine vehicle routes to meet demand due to the limited number of vehicles. The distribution time limit is another obstacle in the distribution process due to delays in delivering blood products from UTD to hospitals or hospital blood banks. In this study, the CCVRPTW solution was determined using a metaheuristic algorithm, namely the Tabu Search algorithm, to minimize blood distribution routes and distances at UTD PMI Pekanbaru. The solution for blood distribution is solved using a programming language through MATLAB software based on the Tabu Search algorithm. Based on the study results, the route 0-1-14-8-18-6-2-17-11-10-4-3-15-9-5-7-16-19-12-13-0 with a distance of 55, 9 KM in 67.1 Minutes. The initial distribution route is 0-1-2-6-5-4-3-7-17-8-13-11-12-14-16-15-18-9-10-19-0 with a distance of 130.7 KM in 156.8 minutes. UTD PMI uses one coolbox with 100 bags of blood capacity, but there is a delay because it only uses one vehicle. The optimized route is divided into two routes: car 1 has a route of 0-1-14-8-18-6-0 with a total distance of 9.2 KM, and car 2 has a route of 0-2-17-11-10-4 -3-15-9-5-7-16-19-12-13-0 with a total distance of 50.6 KM.


W. Liu, G. Y. Ke, J. Chen, and L. Zhang, “Scheduling the distribution of blood products: A vendor-managed inventory routing approach,” Transp. Res. Part E Logist. Transp. Rev., vol. 140, p. 101964, Aug. 2020.

K. Katsaliaki, “Cost-effective practices in the blood service sector,” Health Policy (New. York)., vol. 86, no. 2–3, pp. 276–287, May 2008.

R. Rayendra, “Analysis of Blood Products Inventory Control on Unit Blood Bank Service Hospital X Yogyakarta,” in Seminar Nasional Sains Dan Teknologi, 2019, pp. 35–39.

A. A. Puji, F. A. Yul, and M. Rafian, “Desain Manajemen Risiko Rantai Pasok Darah Menggunakan House of Risk Model ( Studi Kasus : PMI Kota Pekanbaru ),” in Seminar Nasional Teknologi Informasi Komunikasi dan Industri, 2020, pp. 427–434.

E. Reynolds, C. Wickenden, and A. Oliver, “The impact of improved safety on maintaining a sufficient blood supply,” Transfus. Clin. Biol., vol. 8, no. 3, pp. 235–239, Jun. 2001.

D. Paolo, “The Vehicle Routing Problem,” Soc. Ind. Appl. Math. Philadelphia, vol. 1999, 2006.

M. Gmira, M. Gendreau, A. Lodi, and J.-Y. Potvin, “Tabu search for the time-dependent vehicle routing problem with time windows on a road network,” Eur. J. Oper. Res., vol. 288, no. 1, pp. 129–140, Jan. 2021.

J. Cordeau, M. Gendreau, and G. Laporte, “A tabu search heuristic for periodic and multi‐depot vehicle routing problems,” Networks, vol. 30, no. 2, pp. 105–119, Sep. 1997.

H. Prasetyo, M. A. Alfatsani, and G. Fauza, “Solving Capacitated Closed Vehicle Routing Problem with Time Windows (CCVRPTW) using BRKGA with local search,” IOP Conf. Ser. Mater. Sci. Eng., vol. 352, no. 1, 2018.

J. Beliën and H. Forcé, “Supply chain management of blood products: A literature review,” Eur. J. Oper. Res., vol. 217, no. 1, pp. 1–16, 2012.