Strategic Route Planning for Disaster Relief in Palu, Indonesia: A MILP Model Incorporating GIS Data

When natural disasters strike, the impacts are often not only physical, but also affect the social and economic aspects of the affected communities [1]. Indonesia has a history of quite a lot of natural disasters, especially earthquakes [2]. Based on data from the last 30 years, the number of economic losses reached 930 m USD and more than 200,000 disaster losses. Like the earthquake and tsunami that occurred in Palu, Indonesia, in 2018 with a magnitude scale of 7.7 and damage between the IV-VI MMI [3] at coordinates 0.18 South Latitude and 119.85 East Longitude with a depth of 10 km shown in Figure 1. As a result of this incident, the death toll in Palu City was 1,703 people, Donggala 171 people, Sigi 366 people and Parigi Moutong 15 people [4] leaving important lessons about the importance of effective disaster management [5]. This incident shows how important it is to have a disaster management system that is not only fast and responsive but also strategic and well organized [6]. In dealing with emergency situations like this, the distribution of aid quickly and on target [7] is one of the critical factors that can determine the level of success of recovery efforts [8]. However, this distribution process is often faced with various challenges, ranging from limited access to affected locations, infrastructure damage, to other logistical obstacles [9]. Therefore, a route planning strategy is needed that is not only efficient but also able to overcome these obstacles [10].

Strategic planning in disaster management plays an important role in minimizing the impacts. This includes aspects of efficiency and speed in distributing aid to areas that need it most [11]. In this context, the use of Mixed-Integer Linear Programming (MILP) models offers a mathematical solution that can optimize resource allocation and aid distribution routes [12, 13]. This model allows more precise and measurable decision making [14], which is very much needed in post-disaster emergency situations. In addition, the integration of Geographic Information System (GIS) data into MILP models enriches the analysis by incorporating geospatial variables into planning [15]. Accurate and up-to-date GIS data can provide in-depth information about geographic conditions, including road accessibility, severely affected areas, and the distribution of affected populations [16]. This combination of MILP and GIS data opens up new opportunities in developing aid distribution strategies that are not only efficient but also responsive to dynamic field conditions [17].

21.png

Figure 1. Earthquake epicenter map

Source: BMKG Indonesia

However, the use of advanced technologies and models such as MILP and GIS in the context of disaster management still faces challenges, including the availability of accurate data and a deep understanding of disaster dynamics. The natural disaster in Palu provides a rich case study for analyzing and testing these models. The data generated from the Palu disaster event is very valuable for validating the effectiveness of the proposed strategic planning model, as well as correcting existing weaknesses. Developing a strategic route planning model for distributing disaster aid that utilizes MILP and GIS is therefore important. This research not only contributes to academic literature but also to real disaster management practices. By identifying the most effective aid distribution routes, this research has the potential to save more lives and speed up the recovery process for communities affected by disasters. Furthermore, it is hoped that this research can become a foundation for the development of a more resilient and adaptive disaster management system. By understanding the strengths and limitations of MILP models integrated with GIS data, policymakers and disaster management practitioners can design better strategies for dealing with future disasters. This research offers guidance on how technology and mathematical approaches can be used to improve disaster preparedness and response.

This chapter explains the methodology used in this research to develop and implement MILP model integrated with GIS data in the context of optimizing post-disaster logistics distribution in Palu, Indonesia. The methodology described includes the data collection process, data preprocessing, MILP model formulation, and model implementation using the PuLP library in Python. This chapter aims to provide a detailed overview of the approaches taken to overcome logistical challenges in emergency situations, ensuring that aid can be distributed effectively and efficiently to locations where it is needed most. This methodological process is important for understanding how data is collected and analyzed, how models are developed and optimized, and how the results are implemented in real disaster management practices showed on Figure 2.

22.png

Figure 2. Research methodology

3.1 Data collection

Data collection is the first and crucial step in research on strategic route planning for disaster relief using the MILP model that combines GIS data. The data collected includes geospatial information about the location of aid posts, disaster-affected areas, road networks, and warehouse locations, all of which are vital for effectively mapping and planning logistics distribution. This data is accessed and managed via Google Drive, facilitating integration and processing within the Colaboratory platform. In addition to geospatial data, data on logistics needs at each post is also collected, including the number of refugees and their daily logistics consumption, which is essential for determining the volume and type of resources required. Information about warehouse locations and transportation capacity is also needed to plan efficient logistics and distribution routes, ensuring that all resources are available and can be transported as needed. This systematic and organized data collection allowed researchers to build a strong foundation for the MILP model. With accurate and comprehensive data, models can more accurately forecast needs and plan distribution, reducing response times in disaster situations. This process also ensures that the analysis carried out is based on current field conditions, allowing adjustments to rapidly changing disaster dynamics. Through effective data collection, this research seeks to close the gap between planning theory and practical application in disaster response, ensuring that aid can be distributed efficiently to areas that need it most.

It is important to note that this research utilizes a combination of real geospatial data and simulated operational parameters. While the geographical locations and infrastructure data are based on actual conditions during the 2018 Palu disaster, several operational parameters were estimated or assumed due to data availability constraints in post-disaster situations. The data used in this research includes:

Geospatial data: GIS data that includes the location of aid posts, disaster-affected areas, and road networks. This data is obtained from Google Drive which has been synchronized with the Colaboratory platform for easy access and processing. According to crowdsourced developed by Task Force PDS (Pusat Data Sains) Universitas Gadjah Mada, geospatial data compiled through Google Maps platform [23] there are 22 posts provided and 19 hospitals for health care provided on Table 1. However, it turns out that this number is still far from commensurate with the population evacuation points which reached 429 in number. You can imagine that logistical assistance which was only concentrated in a few posts was distributed to a large number of evacuation points.

Table 1. Evacuation post

The logistics needs calculations represent simulated requirements as displayed on Figure 3 based on standard consumption patterns per refugee category (men, women, and children). These values were estimated using established humanitarian aid guidelines and average daily consumption rates, as actual consumption data during the disaster was not comprehensively available.

23.png

Figure 3. Logistics needs

Warehouse location data: Location of warehouses that store logistics, including Bulog Palu and BPBD Palu, along with storage capacity and types of logistics availabilty showed on Figure 4.

24.png

Figure 4. Warehouse data

Transportation capacity data: Assumed transportation parameters based on standard logistics vehicle specifications, including the maximum weight capacity of 20,000 kilograms (20 tons) and an average speed of 50 km/h. These parameters were standardized assumptions derived from typical disaster relief vehicle capabilities.

3.2 Preprocessing data

After the data is collected, the next step is data preprocessing, which is a vital process for preparing the data to suit the needs of the model and analysis. This preprocessing involves data format conversion, such as changing postal coordinates from DMS format to decimal, which facilitates further processing and analysis. The creation of a GeoDataFrame enables the integration of geospatial data with geopandas operations, facilitating more effective visualization and manipulation of spatial data. A data filtering process is also carried out to ensure that only relevant and accurate data is used in the model, such as filtering out posts located in affected areas and identifying passable road networks.

In addition, preprocessing involves data mapping to identify warehouse locations and their capacity, as well as determining logistics needs at each post based on the number of refugees and their average consumption. This step ensures that the model has all the information necessary to plan effective logistics distribution, including resource types and quantities, delivery locations, and capacity constraints. Data preprocessing helps reduce complexity and increase model accuracy, ensuring that the resulting analysis and distribution plans are based on the latest and most relevant information. With the data processed and ready for analysis, this research can move to the development and implementation stage of the MILP model, with the aim of increasing the efficiency and effectiveness of disaster aid distribution.

Coordinate data conversion: Converting postal coordinates from DMS format (Degrees Minutes Seconds) to decimal format the result showed on Figure 5.

25.png

Figure 5. Geospatial data conversion

GeoDataFrame creation: Create a GeoDataFrame to facilitate visualization and analysis of geospatial data. This raw data has been processed to display on Figure 6.

26.png

Figure 6. Data filtered

Data filtering and mapping: Filtering posts in affected areas and mapping the locations of posts, warehouses and disaster areas. Figure 7 is showed to proof data from some resources and kind were ready to be analysized.

27.png

Figure 7. GeoDataFrame

3.3 Mixed Integer Linear Programming (MILP) model

The Mixed Integer Linear Programming (MILP) model developed in this research aims to optimize the distribution of disaster aid logistics by minimizing the total distance or delivery time from the warehouse to aid posts. This model is specifically designed to address the complexities and challenges faced in disaster response, where delivery time and efficiency are key to saving lives and meeting the basic needs of victims. Decision variables in the model include the choice of delivery route and the amount of logistics sent, which must be decided in such a way that all postal needs are met without exceeding the available transportation capacity. This model takes into account the various types of logistics required, such as food, water, and clothing, as well as the weight per unit of each item to ensure that the total load does not exceed the vehicle's carrying capacity. The use of the MILP model in the context of disaster relief allows researchers and practitioners to make data-based and analytical decisions regarding the distribution of limited resources in highly dynamic and often critical situations. By utilizing geospatial data, this model is able to identify the most efficient delivery routes, considering road conditions that may be affected by disasters. In addition, the model offers flexibility in accommodating changing needs at the command post or logistics availability at the warehouse, enabling quick adjustments to changing field conditions. The MILP model has become an important tool in disaster logistics planning, ensuring that aid can arrive where it is needed most in the most effective and efficient manner. Through route optimization and resource allocation, this model contributes to more coordinated and structured disaster response efforts. This model involves:

Decision variables

(1) Route Binary Variable X_ij

a. X_ij : Binary variable indicating route selection from location i ke location j. 1 if the route from location i to location j is selected; otherwise, ij = 0

b. This variable determines whether a route between locations should be used in the optimal solution.

(2) Shipping quantity variables Q_ijk

a. Shows the number of logistics of type k sent from location i to location j.This variable determines whether a route between locations should be used in the optimal solution.

b. This variable is continuous and non-negative, representing the volume of resources allocated on the selected route.

(3) Objective function

The objective function of this model as in Eq. (1) is to minimize the total distance or logistics delivery time between locations. The objective function is defined mathematically as follows:

$\operatorname{Minimize} \mathrm{Z}=\sum_{\mathrm{i} \in \mathrm{P}} \sum_{\mathrm{j} \in \mathrm{P}} \mathrm{d}_{\mathrm{ij}}\ \mathrm{x}_{\mathrm{ij}}$                       (1)

Z is the total travel distance or time to be minimized.

d_ij represents the distance or time from location i to location j.

x_ij is a binary variable that equals 1 if the route from i to j is used, and 0 otherwise.

P denotes the set of all locations, including both warehouses and relief posts.

where, d_ij is the distance or travel time from the location i to location j, and P is the set of all locations including warehouses and posts.

(4) Constraints

This model includes several types of constraints that ensure a feasible and effective solution as in Eq. (2).

a. Need constraints

Ensure that each post receives sufficient logistics to meet its needs.

$\Sigma_{i \in G}\ q_{i j k} \geq demand _{j k}\ \forall j \in P, \forall k \in K$                     (2)

q_ijk represents the quantity of logistics type k shipped from location i to location j.

demand_jk is the demand for logistics type k at location j.

G is the set of warehouse locations.

P is the set of all locations.

K is the set of all types of logistics.

where, G is the set of warehouse locations, P is the set of all locations, and K is the set of logistics types.

b. Vehicle capacity constraints

The total amount of logistics sent must not exceed the vehicle capacity.

$\begin{aligned} & \Sigma_{k \in K}\ q_{i j k} \cdot{ weight\_per\_unit }_k \leq { vehicle\_capacity } \cdot x_{i j} \ \forall i \in P, \forall j \in P\end{aligned}$                     (3)

q_ijk is as defined previously.

weight_per_unit_k is the weight per unit of logistics type k.

vehicle_capacity is the capacity of the transport vehicle in weight units.

x_ij, P, and K are as defined previously.

This constraint as in Eq. (3) also ensures that routes are only activated (i.e., x_ij = 1) if there is a delivery made via that route.

c. Delivery constraints

Ensure that there are no sub-tours in the solution, i.e. travel cycles that do not include all locations.

Make additional subtour elimination constraint formulations and other approaches such as adding variables for location sequencing.

3.4 MILP model iimplementation

Implementation of the MILP model using the PuLP library in Python was a crucial step in this research, allowing researchers to translate the model's mathematical formulation into executable and optimized code [24]. PuLP is a powerful and flexible library, designed to solve linear and integer programming problems [25], making it well suited to address logistics distribution challenges in disaster contexts [26]. Implementation of the model begins by defining the optimization problem as minimizing the objective function, namely the total distance or delivery time, which reflects the desired operational efficiency. Decision variables, including route selection and the amount of logistics sent, are initialized with appropriate constraints, ensuring that the resulting solution complies with transportation capacity and meets logistics needs at each post.

The implementation process involves adding constraints to the model, such as logistics requirements at each post and transportation capacity, which are realized through codes that determine upper and lower bounds for the decision variables. This ensures that the resulting solution is not only optimal in terms of cost or distance but also realistic and practical to implement in the field. Through iteration and model solving, PuLP searches for a solution that satisfies all constraints while minimizing the objective function, resulting in an optimal logistics distribution plan. The output of this process provides valuable insights for decision makers, enabling them to allocate resources in the most effective way, based on quantitative analysis. Implementation of the MILP model with PuLP not only increases operational efficiency in the distribution of disaster aid but also offers a systematic and measurable approach to dealing with fast-paced and uncertain disaster situations.

3.5 Analysis result

After the MILP model has been successfully run using PuLP, the next stage is to analyze the results obtained. This analysis aims to verify and assess the effectiveness of the logistics distribution routes proposed by the model. This evaluation includes understanding resource allocation, meeting needs at aid posts, and efficiency of delivery routes. The following is a systematic explanation of the steps in results analysis, accompanied by examples of results that can be substituted for real data when available.

First, we need to examine the route proposed by the model to ensure that it is logical and practical. This includes examining routes between warehouses and posts, as well as testing whether the model successfully avoids unnecessary deliveries or inefficient routes. In this study, logistics route analysis was implemented to evaluate the efficiency of sending aid to various posts located in the affected areas in Palu. The data collected includes routes from two main warehouses, namely the Palu Bulog Warehouse and the Palu BPBD Warehouse, to various destinations in the city and surrounding areas. In total, there were 366 routes observed, with distances varying from a few hundred meters to more than fifteen kilometers showed on Table 2. These routes were chosen based on the logistical needs of the posts visited and the availability of adequate road access after the disaster. Each route is assessed based on distance traveled and conditions of use, with the majority of routes used to ensure fast and efficient distribution of aid. This analysis revealed several critical routes with longer distances, indicating the need for more detailed logistics planning to optimize the use of resources and time.

Table 2. Generated routes

Table documents on Table 3 was simulated the logistics management and distribution efforts by the BPBD (Regional Disaster Management Agency) of Palu, detailing various shipments of relief supplies from their central location to multiple destinations across the region using MILP Model. Each row of the table records a distinct shipment, including details like the origin (always BPBD Palu), destination addresses, distance traveled in kilometers, status and specifics of the cargo. The cargo includes essential items such as rice, water, men's and women's clothing, diapers, canned food, instant noodles, and sanitary pads, with the total weight given in kilograms. The table also notes the loading time in hours, and the number of trips made for each shipment. The purpose of this data appears to be to monitor and optimize the distribution process of emergency supplies following a disaster, ensuring timely and efficient delivery of essential goods to affected populations. This could be part of a larger analysis to improve disaster response strategies or for reporting in a logistical or operational study within a disaster management context.

Table 3. Logistics distribution data

Image on Figure 8 depicts a complex visualization of shipping routes and logistics distribution in the Palu area, which was affected by natural disasters. This visualization is an important part of the logistics aid distribution analysis, showing post points (marked with blue icons) and delivery routes between these posts (marked with gray lines). The data used in this visualization comes from GIS that collects geospatial information from logistics posts in the area. The points on the map indicate the geographical location of the posts, while the lines connecting these points represent potential routes that can be used by logistics transport vehicles. These lines do not always represent actual road routes, but rather logical connections between posts based on need and urgency. From this visualization, it can be seen that there is a concentration of posts in the city center, with routes branching out to more remote areas. This suggests a centralized logistics distribution strategy, where aid is collected at main distribution centers and then distributed to areas of greater need. The conclusion that can be drawn from this visualization is the need to optimize delivery routes so that logistics can be distributed more efficiently to all posts. Additionally, visualization helps in the identification of posts that may have limited access or require further assistance, which can better guide resource allocation. The results of this visualization provide important insights to decision makers and aid organizations about how best to design logistics operations in disaster areas. By understanding current distribution patterns, strategies can be adjusted to increase efficiency and effectiveness in disaster management.

28.png

Figure 8. Distributions routes

3.6 Ethical considerations

This research adheres to strict ethical guidelines given the sensitive nature of disaster-related data and the potential impact on vulnerable populations. All location data and demographic information used in this study were anonymized to protect the privacy of individuals and communities affected by the disaster. Personal identifiers were removed from all datasets, and only aggregated demographic data (total number of refugees, general logistics needs) were utilized in the analysis. The geospatial data were obtained from publicly available sources, including government databases and Google Maps data accessed through Gadjah Mada University repository links, with no primary data collection involving direct interaction with disaster survivors.

The research was designed with the primary intention of improving disaster response capabilities for the benefit of affected communities. Care was taken to ensure that the research findings would not inadvertently compromise the security or privacy of evacuation sites or vulnerable populations. All methodological approaches, data sources, and analytical procedures are transparently reported to enable peer review and validation, while research limitations and potential biases are clearly acknowledged to prevent misinterpretation or misapplication of the findings. The optimization model was developed to enhance the efficiency of aid distribution while maintaining the dignity and rights of disaster survivors.