Team B
資訊所一 楊晴雯 P76114511
資訊所一 許智豪 P76114503
- Introduction
1.1 Background: Disaster Relief Logistics
1.2 Abbreviation
1.3 Motivation
1.4 Problem Definition - Methodology
2.1 Formulation
2.2 Multi-Objective Optimization - Case Study
3.1 Data Collection
3.2 Implementation Details
3.3 Result Analysis
3.4 Weight Analysis
3.5 Constraint on Number of CS/RDC Analysis - Issues
- Conclusion
- References
Our project is inspired by "A multi-objective robust stochastic programming model for disaster relief logistics under uncertainty" by Ali Bozorgi-Amiri et al, published on OR Spectrum in year 2011. Their model is a multi-objective model that aims to minimizes the total cost and its variance (as the first objective), and maximizes the satisfaction level of the least satisfied affected area (as the second objective). Since the disaster scale is stochastic, their model proposes to use discrete scenario analysis to include the stochastic factors.
RDC: Resource Distribution Center
CS: Contactless Station
AA: Affected Area
As Covid-19 threats gradually becomes a normality, it is a must to consider how to respond to a disaster under the pandemic. An imaginary scenario is that an earthquake damages a hospital that quarantines many Covid-19 confirmed cases, and now the resources need to be sent to this hospital without further human contacts. In this case, some contactless stations (CSs) need to be set up in place of the Bozorgi-Amiri's proposed RDCs. CSs send resources via self-driving cars, therefore avoid the risk brought by frequent human mobility in between. They also reduce the transportation costs because no drivers are needed. We imagine that CSs should have higher setup cost and better capacity than RDCs. Figure 1 and 2 compares the original paper setting versus our proposed setting.
Amiri's paper models disaster planning and response capturing the inherent uncertainty in demand, supply, and cost resulting from the disaster. The model consists of 3 stages and 2 kinds of pair-wise transportation (Supplier-RDC, RDC-AA). Given constraints on transportation and the capacity limits in the 3 sets of nodes, the goal is to select optimum number of commodities in delivery from node to node, locations to set up RDCs, and capacitiy levels if an RDC is to be set up, while minimizing the total cost and the least satisified area's shortage cost. Bozorgi-Amiri's paper goes further to wrap the objective functions with a robust optimization framework to guarantee small variance and model feasibility; we would like to skip the part as it makes the model too complicated. In brief, we would like to mainly follow Bozorgi-Amiri's paper formulation and multi-objective (bi-objective) setting, but with the following modifications:
- Separating RDCs into standard RDCs (denoted RDC) and CSs (denoted CS).
- Separating affected areas into high-risk and low-risk AAs, where high-risk AAs only receive resources from CSs, and low-risk AAs could receive from both.
- Simplifying the constraints by removing the procure costs of commodities, and fixing the setup cost and capacity size for RDC (Bozorgi-Amiri's paper has 3 setup costs with 3 sizes), and handcrafting a setup cost and a capacity size for CS.
- Simplifying the objectives by removing the robust optimization framework described in the paper section 3 formula (13), and keeping only the naive
$\xi$ for both objectives.
-
Sets and Indices
-
$I$ : Suppliers -
$J$ : Candidate points for RDCs and CCs -
$K$ : Affected Areas -
$I$ , For each$j \in J$ , it is could be an RDC, or a CS, or none of the above, just an empty point. -
$K'$ : High-risk Affected Areas; Affected Areas that only receive commodities transported by CSs. -
$K/K'$ : Low-risk Affected Areas; Affected Areas that only receive commodities transported by RDCs. -
$C$ : Commodity Types. -
$S$ : Possible scenarios (discrete).
-
-
Parameters
(Deterministic Parameters)
-
$F^R$ : fixed setup cost for RDCs. -
$F^C$ : fixed setup cost for CSs. -
$C_{ijc}$ : transportation cost from supplier$i$ to candidate point$j$ with commodity$c$ . -
$h_{kc}$ : inventory holding cost for commodity$c$ at AA$k$ . -
$\pi_{c}$ : inventory shortage cost for commdotiy$c$ . -
$v_{c}$ : required unit space for commodity$c$ . -
$S_ic$ : amount of commodity$c$ supplied by supplier$i$ . -
$M$ : a large number
(Stochastic Parameters)
-
$p_s$ : occurrence of probability of scenario$s \ in S$ . -
$C_{ijcs}$ : transportation cost from supplier$i$ to candidate point$j$ with commodity$c$ under scenario$s$ . -
$C_{jkcs}$ : transportation cost from candidate point$j$ to AA$k$ with commodity$c$ under scenario$s$ . -
$D_{kcs}$ : amount of demand of commodity$c$ under scenario$s$ . -
$\rho_{jcs}$ : fraction of stocked materials of commodity$c$ remains usable at candidate point$j$ under scenario$s$ ($0 \leq \rho_{jcs} \leq 1$ ). -
$\rho_{ics}$ : fraction of stokced materials of commodity$c$ remains usdables at supplier$i$ under scenario$s$ ($0 \leq \rho_{ics} \leq 1$ ).
-
-
Decision Variables
-
$Q_{ijc}$ : amount of commodity$c$ supplied by supplier$i$ , stored at candidate point$j$ . -
$X_{ijcs}$ : amount of commodity$c$ transferred from supplier$i$ to candidate point$j$ under scenario$s$ . If$X_{ijcs} > 0, j$ must be either an RDC or a CS. -
$Y_{jkcs}$ : amount of commodity$c$ transferred from candidate point$j$ to AA$k$ under scenario$s$ . If$Y_{jkcs} > 0, j$ must be either an RDC or a CS.
-
$I_{kcs}$ : amount of inventory of commodity$c$ held at AA$k$ under scenario$s$ . -
$b_{kcs}$ : amount of shortage of commodity$c$ at AA$k$ under scenario$s$ . -
$\alpha_i$ : if candidate point$j$ is an RDC,$\alpha_j = 1$ ; otherwise$=0$ . -
$\beta_j$ : if candidate point$j$ is a CS,$\beta_j = 1$ ; otherwise$=0$ .
-
-
Mathematical Formulations
These are defined for convenience and the simplicity in objective functions.
-
$\Sigma_{j \in J}(F^R\alpha_j + F^C\beta_j)$ : (SC) Setup Cost for RDCs and CSs -
$\Sigma_{i\in I}\Sigma_{j \in J}\Sigma_{c \in C}C_{ijc}Q_{ijc}$ : Transportation Cost from suppliers to RDCs and CSs (preparedness phase). -
$\Sigma_{i\in I}\Sigma_{j \in J}\Sigma_{c \in C}C_{ijcs}X_{ijcs}$ :(TC-pre) Transportation Cost from suppliers to RDCs and CSs under a scenario (response phase). -
$\Sigma_{i\in I}\Sigma_{k \in K}\Sigma_{c \in C}C_{jkcs}Y_{jkcs}$ :(TC-post)Transportation Cost from RDCs and CSs to AAs under a scenario (response phase). -
$\Sigma_{k \in k}\Sigma_{c \in C}h_{kc}I_{kcs}$ :(IC) Inventory holding costs at AAs under a scenario (response phase). -
$\Sigma_{k \in K}\Sigma_{c \in C}\pi_{c}b_{kcs}$ :(SHC) Shortage costs at AAs under a scenario (response phase).
-
-
Constraints The green parts are highlighted to indicate the revised parts from Bozorgi-Amiri's paper.
(1) Control Balance Equation: The amount of commodities sent from suppliers and other RDC/CS
$j'$ to$j$ $-$ the amount$j$ sending out to other AA roughly equals to the amount of commodities transferred to AAs from the RDC$j$ . If LHS is greater than the RHS, this inventory surplus is penalized by the first objective.$$\Sigma_{i \in I} X_{ijcs} + \rho\Sigma_{i \in I}Q_{ijc} + {\color{green}\Sigma_{j' \neq j}{Y_{jj'cs}}\alpha_{j'}\beta_{j'}} - \Sigma_{k \in K}Y_{jkcs}(\alpha_j + \beta_j) = \delta_{jcs} \ \forall j \in J, \forall c \in C, \forall s \in S$$ (2) Inventory Equality Constraint: The amount of commodites from RDC/CS
$j$ to AA$k -$ AA$k$ 's demand should equal to$k$ 's invnentory$- k$ 's shortage. The revised part is the special case when$k$ is a special AA that could only receive commodites sent by a CS.$$(\Sigma_{j \in J}Y_{jkcs} (\alpha_j + \beta_j)) - D_{kcs} = I_{kcs} - b_{kcs} \ \forall k \in K/K' \forall c \in C, \forall s \in S$$ $$\color{green} (\Sigma_{j \in J}Y_{jk'cs} (\alpha_j + \beta_j)) - D_{k'cs} = I_{k'cs} - b_{k'cs} \ \forall k' \in K' \forall c \in C, \forall s \in S$$ (3) RDC/CS Transferability: RDC/CS could transfer commodity to other nodes only if there exists another RDC/CS/AA.
$$Y_{jkcs} \leq M(\alpha_j + \beta_j)D_{kcs} \ \forall j \in J, \forall k \in K/K', \forall c \in C, \forall s \in S$$ $$\color{green} Y_{jk'cs} \leq M\beta_jD_{k'cs} \forall j \in J, \ \forall k' \in K', \forall c \in C, \forall s \in S$$ $$\Sigma_{i \in I} {X_{ijcs} \leq M(\alpha_j + \beta_j)} \ \forall j \in J, \forall c \in C, \forall s \in S$$ (5) RDC Capacity Constraint: the amount of commodities sent from supplier
$i$ to RDC$j$ should not exceed the capacity of the RDC. Similarly, the amount of commodities sent from supplier$i$ to CS$j$ should not exceed the capacity of the CS.$$\Sigma_{i \in I}\Sigma_{c \in C} v_cQ_{ijc} \leq CapSize^R \cdot \alpha_j \forall j \in J$$ $$\Sigma_{i \in I}\Sigma_{c \in C} v_cQ_{ijc} \leq CapSize^C \cdot \beta_j \forall j \in J$$ (6) Supplier Capacity Constraint (in preparedness phase): The amount of commodities a supplier sends out to other places should not exceed the supplier's own capacity (before the disaster).
$$\Sigma_{j \in J} Q_{ijc} \leq S_{ic} ;\forall i \in I, \forall c \in C$$ (7) Supplier Capacity Constraint (in response phase): The amount of commodities a supplier sends out to other places should not exceed the supplier's own capacity (after the disaster, under all scenarios).
$$\Sigma_{j \in J} X_{ijcs} \leq \rho_{ics} S_{ic} ;\forall i \in I, \forall c \in C, \forall s \in S$$ (8) RDC/CS Identity Constraint: A node in set
$J$ could only be (1) none (2) RDC (3) CS, but not RDC and CS simultaneously.$$\alpha_j + \beta_j \leq 1 ;\forall j \in J$$ (9) CS Number Constraint:
$\epsilon$ is the maximum number of CSs allowed in the network.$$\color{green} \Sigma_{j \in J} \beta_j \leq \epsilon$$ -
Objectives
- Objective 1: minimize the total costs
$SC + TC_{pre} + TC_{post}+ IC + SHC$ Sometimes the input parameters make the model infeasible, so we add a penalty term$\delta$ to penalize the solutions that fail to meet the demand in a scenario or violate certain constraints, while keeping the model feasible. The final objective 1 is:$SC + TC_{pre} + TC_{post}+ IC + SHC + \gamma\Sigma_{j \in J}\Sigma_{c \in C}\Sigma_{s \in S}\delta_{jcs}$ , where$\gamma$ is the penalty weight of the deviation term. - Objective 2: maximize the total satisfaction; i.e., minimize the shortage costs of the least satisfied AA under all scenarios.
$\Sigma_{s \in S}p_s(\Sigma_{c \in C}\max_{k \in K}{b_{kcs}})$
- Objective 1: minimize the total costs
There are several methods to solve a multi-objective problem, as can be found in past literatures (Mahjoob, M. and Abbasian, P., 2018; Kong, Z. Y., How, B. S., Mahmoud, A., & Sunarso, J., 2022; Yang, Z. et al., 2014). We employ the following 2 methods to combine our 2 objectives together, and solve the problem as a single-objective problem.
Both objectives are assigned a positive weight (
The Lp-metric method aims to reduce the digression btween objective functions and their ideal solution obtained by indiviually optimizing them. In order to obtain the
We use the data in case study from Bozorgi-Amiri's paper. The scene is set at a well-populated region of Iran located near sourthern Central Alborz, with several active faults surrounding (hence the disaster is imagined to be an earthquake).
-
$I$ contains 5 suppliers, including Sari, Qazvin, Tehran, Arak and Isfahan. -
$J$ contains 15 candidate nodes, including Gorgan, Semnan, Sari, Rasht, Qazvin, Karaj, Tehran, Varamin, Roibatkarim, Islamshahr, Shahriar, Gom, Arak, Isfahan and Kashan. Their pair-wise distance statistics are shown in figure 3. The setup costs of an RDC ($F^R$ ) and a CS ($F^C$ ) are shown in figure 3. -
$K$ contains 15 demand points (AAs). The first 8 nodes are low-risk AAs while the later 7 are high-risk ones (the former is denoted$K/K'$ while the latter is denoted$K'$ ). Their demands under all scenarios ($D_{kcs}$ ) are shown in figure 4. The capacity of AA is an arbitrary value set to 16 (same unit as the capacity of an RDC and CS). -
$C$ is the set of commodities, here we use water, food, and shelter. -
$S$ is the set of scenarios with occurrence probabilites$p_s = [0.45, 0.3, 0.1, 0.15]$ .
Note that
Table 3.
We decide to solve the problem using Gurobi Optimization solver with the academic license. The environment is Gurobi 10.0.0 with Python 3.7.12 under the Linux x86_64 system with 12th Gen Intel(R) Core(TM) i7-12700.
In Gurobi implementation, we use the setObjectiveN() that defaults to weighted-sum method according to the official documentation (gurobi doc 9.1: Working with Multiple Objective) for both weighted-sum and Lp-metric strategies.
We start simple with a deterministic model first. It assumes that in the response phase, we have perfect knowledge of which scenario would happen, so the demand, transportation cost, and the fraction of stocked materials that remain usable are pre-determined. In the following experiments, we choose to use the scenario
The final stochastic programming model has 4,422 continuous variables and 210 binary variables; 666 quadratic constraints and 12 general constraints. The optimization procedure takes 0.81 seconds for over 4,000 simplex iterations. The below shows the statistics for the configuration:
stochastic model
objective 1 weight = 0.1
number of CS (epsilon) = 8
optimization method: Lp-metric
As seen in table 6, there are 8 CSs and 7 RDCs opened, which means that each node in candidate node set
We find that RDC does not receive anything in both phases, so the table only shows columns of CSs. We could see that the supplier in Sari ships 117 units of food under all scenarios; 39 units of shelter under scneario 3 and 4; 0 water under scneario 1 and 117 units of water under the rest, to the CS in the same province. Averagely speaking, the 3 commdoites sent to the same CS are usually supplied by the same supplier.
Table 7 shows the amount of commodity
Table 9 and 10 represent the inventory and shortage amount held at AA
| Lp-metric | Weighted-sum | |
|---|---|---|
| Deterministic |  |
 |
| Stochastic |  |
 |
With single-objective optimization, we can minimize the total costs to
[In Response to Professor Li's Question]
We notice that there's a small peak between
Stochastic Model
| CS | RDC | RDC+CS | |
|---|---|---|---|
| w/o deviation ( |
 |
 |
 |
| w/ deviation ( |
 |
 |
 |
The deviation (
A node could be an RDC, a CS or a null node that does not open any centers, however, it seems our stochastic model in Gurobi only allows a node to be either a RDC or a CS. We have attempted to fix the problem by adding the deviation term
In this paper, we proposed a multi-objective stochastic programming model to simultaneously optimize the humanitarian relief logistics in both the preparedness and response phases, while taking into account how to respond to disasters under the pandemic. In our hypothesis, it is necessary to set up contactless stations (CS) and emerging technologies such as unmanned vehicles to replace the original RDC to satisfy contactless delivery for certain AAs that have this requirement. Our model consists of two stages: the first stage determines the locations of RDCs/CSs and the required inventory quantities for each type of relief items under storage, and the second stage determines the amount of transportation from RDCs/CSs to AAs. Our multi-objective model minimizes expected total costs and expected penalty for infeasible solution due to uncertain parameters while maximizing customer satisfaction. In our model, the cost parameters for the relief logistics as well as demand are subject to uncertainty. Furthermore, the model considers uncertainty in the locations where those demands might arise as well as the possibility that some pre-positioned supplies at RDC/CS or supplier might be partially destroyed by the disaster (supply uncertainty). Finally, we solved our model as a single-objective, mixed-integer programming problem by applying the Lp-metric method. To demonstrate the effectiveness of the proposed model, a case study based on real-world data is presented. Sensitivity analysis is also performed to validate the model.
- Bozorgi-Amiri, A., Jabalameli, M.S. & Mirzapour Al-e-Hashem, S.M.J. (2013). A multi-objective robust stochastic programming model for disaster relief logistics under uncertainty. OR Spectrum 35, 905–933. link
- Blank, J., & Deb, K. (2020). Pymoo: Multi-objective optimization in python. IEEE Access, 8, 89497-89509. link
- Kong, Z. Y., How, B. S., Mahmoud, A., & Sunarso, J. (2022). Multi-objective Optimisation Using Fuzzy and Weighted Sum Approach for Natural Gas Dehydration with Consideration of Regional Climate. Process Integration and Optimization for Sustainability, 1-18. link
- Mahjoob, M. (2018). Designing a cost-time-quality-efficient grinding process using MODM methods. arXiv preprint arXiv:1804.10710. link
- Yang, Z., Cai, X., & Fan, Z. (2014, July). Epsilon constrained method for constrained multiobjective optimization problems: some preliminary results. In Proceedings of the companion publication of the 2014 annual conference on genetic and evolutionary computation (pp. 1181-1186).
React
Typescript
Django
Laravel
Facebook
Microsoft
Google
Alibaba
D3
Tencent