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

optimization into public health logistics, offering insights for planners, administrators, and policymakers.

access

Blood availability represents one of the most critical determinants of a functional healthcare system globally.

As a unique medical resource, blood cannot be artificially synthesized, has a limited shelf life, and is

indispensable across numerous clinical procedures. It plays a life-saving role in trauma care, maternal

emergencies, surgical operations, treatment of hematological disorders, and management of cancers requiring

transfusion support. The World Health Organization (WHO) underscores that consistent and safe blood supply

is a cornerstone of modern health services, yet significant disparities persist between high- and low-income

regions. Globally, nearly 120 million units of blood are donated annually, but this remains insufficient to meet

56 of 171 reporting countries producing plasma-derived medicinal products domestically (Pop, 2024).

The Philippines, and specifically the Eastern Visayas region, provides a compelling case study for examining

blood supply logistics in resource-constrained environments. The Department of Health (2020) reported that

Eastern Visayas requires approximately 30,000 units of blood annually, but actual collections consistently fall

short of this target. This gap between supply and demand intensifies during periods of increased medical need,

such as the dengue outbreak of 2024, which led to a 314% surge in cases compared to the previous year. This

resulted in an overwhelming demand for blood and platelet concentrates, particularly at tertiary hospitals like

the Eastern Visayas Medical Center (EVMC). Despite intensified donation campaigns, hospitals reported

critical shortages (Leyte Samar Daily News, 2024), forcing families of patients to take on the burden of

searching for blood supplies themselves, often traveling across multiple facilities without guarantee of

resort to physically visiting different blood banks across Tacloban City, a process that is time-consuming,

(Raykar et al., 2021).

Consider a typical scenario: a relative of a patient requiring an urgent transfusion starts at EVMC, the primary

referral hospital in the region. After being informed that the blood type is unavailable, the relative must visit

other facilities such as the Philippine Red Cross, Divine Word Hospital, or Mother of Mercy Hospital. Each

trip entails transportation costs, waiting times, and uncertainty. If the relative travels inefficiently—

backtracking across distant hospitals or missing nearby facilities—they may spend hours and significant

financial resources without securing the needed blood. In critical cases, this inefficiency can be life-

threatening. Thus, the problem is not solely one of supply shortage but also of access optimization and

resource allocation.

This study proposes that mathematical optimization, specifically through the Traveling Salesman Problem

(TSP), offers a systematic approach to reducing wasted resources in this context. The TSP is one of the most

instance, studies have shown that heuristic algorithms can optimize routes for healthcare workers serving

patients in dispersed locations, reducing travel time and costs while improving service delivery (Pop, 2024).

families. Each hospital with a blood bank can be represented as a "node," and the travel distance, time, or fare

between hospitals serves as the "weight" of the connecting edge. Solving the TSP allows for the identification

of routes that minimize the total burden of visiting all potential facilities. While families may not need to visit

all hospitals in practice, the principle of route minimization ensures that any truncated journey follows an

efficient sequence, making the model highly applicable to real-time decision-making.

Various methods exist for solving the TSP. Exact algorithms like Branch-and-Bound (Little et al., 1963) and

Cutting Plane approaches (Dantzig et al., 1954) guarantee optimality but are computationally demanding for

solutions for small networks and aligns with human decision-making under stress (Pop., 2024).

One critical advantage of the Greedy Algorithm in this context is its flexibility for route truncation. Since each

step selects the nearest unvisited hospital, families can stop the route at any point once blood is secured,

confident that the sequence was efficient up to that point. This property distinguishes it from other heuristics

that may require complete route execution for efficiency. Moreover, the algorithm’s simplicity allows for easy

integration into mobile applications or printed guides, providing practical solutions for families in crisis.

From a policy perspective, this approach offers actionable insights. Healthcare administrators could provide

pre-computed efficient routes from each hospital, tailored to distance, time, or fare metrics. Local government

units could integrate such models into digital platforms, reducing the informational burden on patients.

fare—decision-makers can offer multiple route options based on family priorities (e.g., cost minimization

versus time urgency).

to ongoing discussions in operations research, healthcare access, and local health policy, while highlighting the

need for innovative solutions in resource-limited settings.

The objectives of this paper are threefold: (1) to construct weighted graphs representing distances, times, and

fares among major blood banks in Tacloban City; (2) to apply the Greedy Algorithm in generating minimized

travel routes; and (3) to evaluate the relative efficiency of different starting points. By demonstrating the utility

of heuristic optimization in a pressing public health context, this research aims to bridge the gap between

abstract mathematical models and the lived experiences of patients and families in resource-limited settings.

This uneven distribution provides a natural case study for route optimization problems in healthcare access.

Eight major hospitals and blood banks were included in the study, with each facility assigned a letter code to

represent its corresponding node in the graph: (A) Eastern Visayas Medical Center (EVMC), (B) Divine Word

Hospital, (C) Philippine Red Cross – Leyte Chapter, (D) Mother of Mercy Hospital, (E) United Shalom

Hospital, (F) Remedios Trinidad Romualdez (RTR) Hospital, (G) ACE Medical Center Tacloban, and (H)

Tacloban City Hospital. These coded nodes form the network of primary blood supply sources for patients in

Tacloban and its neighboring municipalities.

Data on travel distance, travel time, and transportation fare between each hospital pair were collected using a

combination of direct observation and digital mapping. Distances were measured using Google Maps, ensuring

The collected data were used to construct weighted, undirected graphs where: the vertices (nodes) represent the

blood banks, the edges represent the connections between facilities, and the weights correspond to one of three

metrics: distance (kilometers), time (minutes), or fare (Philippine pesos). Separate graphs were generated for

each metric to allow for independent analysis of travel efficiency depending on the constraint considered.

The study employed the Greedy Algorithm as a heuristic solver for the Traveling Salesman Problem (TSP).

1. Initialization: Select a starting vertex (hospital).

2. Selection rule: From the current vertex, choose the nearest unvisited vertex based on the chosen weight

(distance, time, or fare).

and interpretability make it a suitable heuristic for small-to-medium problem instances, such as the eight-

vertex case in this study.

As this study involved only publicly accessible hospital locations and did not require human subjects or patient

data, formal ethics approval was not required. However, the research adhered to principles of responsible

research conduct by ensuring data accuracy, avoiding misrepresentation of hospital services, and

contextualizing results for potential use in public health planning.

Figure 1 shows the weighted graph representing travel distances among the eight major blood banks in

The graph shows that distances between blood banks range from 0.9 km (between ACE Medical Center and

Tacloban City Hospital) to 13.2 km (between EVMC and Tacloban City Hospital). The data highlight two key

features of Tacloban’s hospital network. The graph reveals clear spatial clustering: Divine Word Hospital,

where these blood banks are within 2.5 km from each other. On the other hand, the Eastern Visayas Medical

Center (EVMC) is more peripheral which suggests that routes starting within the central cluster may yield

Figure 2 illustrates the weighted graph representing travel time between the eight major blood banks in

typically under 10 minutes between them, while EVMC requires 20–37 minutes to reach any other facility.

Figure 3 shows the weighted graph representing the fare when travelling between the eight major blood banks

in Tacloban City. Each vertex corresponds to a hospital, while edges are weighted by the fare paid in

Philippine pesos (₱).

of fare zoning rules rather than pure distance.

fare of ₱180.

When MMH is employed as the starting point, the Greedy Algorithm showed that there is a uniform route for

optimal distance, travel time, and fare amount. The route to be taken is as follows: MMH to USH to DWH to

Philippine Red Cross to ACEMC-Tacloban to Tacloban City Hospital to RTR Hospital to EVMC and finally

This route will yield a total distance of 35 km, total travel time of 1 hour 47 minutes and 56 seconds, while the

total fare is ₱205.

The Greedy Algorithm showed that, with RTR Hospital as starting point, there is a uniform route for optimal

distance, travel time, and fare amount. This route is from RTR Hospital to ACEMC-Tacloban to Tacloban City

Hospital to USH to DWH to Philippine Red Cross to MMH to EVMC then back to RTR Hospital. Taking this

route will result to a total 36.4 km of travelled distance, 1 hour 53 minutes and 10 seconds of travel time, and