I.A. Karimi and Rajagopalan Srinivasan (Editors), Proceedings of the 11th International Symposium on Process Systems Engineering, 15-19 July 2012, Singapore. © 2012 Elsevier B.V. All rights reserved.
Hybrid Approach for Multi-stage Logistics Network Optimization under Disruption Risk Yoshiaki Shimizua and Muhammad Rusmana a
Department of Mechanical Engineering, Toyohashi University of Technology, 1-1 Hibarigaoka, Ten-paku-cho, Toyohashi 441-8580, Japan
Abstract Modern supply chains are subject to a wide range of risks, such as demand uncertainty, natural disasters, and terrorist attacks. Based on some prospects for risk management, this study investigates a logistics network design problem with facility disruption that will be caused by various risks. To find a solution for this design issue, we have formulated a probabilistic programming problem, and propose an effective hybrid method composed of meta-heuristic method and graph algorithm to offset potential losses from the network disruptions. Through numerical experiments, effectiveness of the proposed method is validated. Keywords: Multistage logistics network design, Hybrid method, Disruption risk, Probabilistic programming problem.
1. Introduction Under today’s global and agile manufacturing, modern supply chains are subject to a wide range risk such as the demand uncertainty, natural disasters, terrorist attacks and so on. Recent disruptions by earthquake and tsunami in Japan (2011) and the massive flooding in Thailand (2011) had dramatic impacts on the supply chains and logistic distribution of many companies. The resulting slowdowns and cessation of operations affected seriously some companies. Against this, we can anticipate the disruption by considering preventive action viewed as mitigation planning. Toward such mitigation plan, supply chain must build a resilient system that can minimize the impact of the disruption in future by having appropriate backup facilities. In this study, therefore, we focus on the issue related to facility disruption risk for multistage logistic networks and present a hybrid approach that will provide a resilient design in practice. Finally, effectiveness of such approach will be examined through numerical experiments.
2. Problem Formulation Among some previous studies, Tomlin (2006), Snyder and Daskin (2005) and Chopra and Sodhi (2004) investigate the impact and/or risk management perspective for two echelon logistic problems. Considering the risk associated with demand fluctuation, Shimizu et al. (2011) give a solution procedure by recourse model for a three echelon logistic problem. This study takes three echelon networks for which Shimizu and Rusman (2011) carried out a morphological analysis. The network is consisted of distribution centre (DC), relay station (RS) and customer (RE). For RS, we consider two kinds of RS, i.e.,
Y. Shimizu et al.
reliable RS (RRS) and unreliable RS (URS). URS is no longer available for serving customers when the disruption would occur. In contrast, RRS is the hardened one and can continue the business even after the incident. Figure 1 illustrates the case where RS is potentially being disrupted. Thereat, two DCs distribute products to three relay stations (RSs), which are consisted of two RRSs and one URS. If the demand of the customer is satisfied by RRSs, then only single assignment is sufficient. On the other hand, if the customer is assigned to URS, backup assignment is required besides the primary assignment. This means when the disruption occurs at URS, the demand of customer will be distributed from the backup RRS. Here, we assume that each facility has the same probability of disruption q (0
T2Bjk : Transport cost from RRS j to customer k as backup assignment Uj : Upper bounded capacity of RS j PUi : Maximum supply ability of DC i PLi : Minimum supply ability of DC i dk : Demand of customer k q : Probability of disruption (0
After all, we can formulate the model as a probabilistic mixed-integer programming problem as follows.
Hybrid Approach for Multi-stage Logistics Network Optimization under Disruption Risk 1037
Minimize ܨ ݔ ܨோ ݔோ ሺͳ െ ݍሻ ቌ ൫ܥ ܶͳ ൯݂ ൫ܪ ܶʹ ൯݃ ቍ א
൯݃ ቍ ݍቌ ൫ܥ ܶͳ ൯݂ ൫ܪ ܶʹ אூ א
subject to ݔ ݔோ ͳǡܬ א ݆ሺͳሻ ݔோ ͳሺʹሻ א
݂ ܷ ൫ݔ ݔோ ൯ǡ ܬ א ݆ሺ͵ሻ אூ
ܷ ݔோ ǡ ݆
݂ ܷܲ ǡ ܫ א ݅ሺͷሻ א
݂ ܷܲ ǡ ܫ א ݅ሺሻ א
݂ ܲܮ ǡ ܫ א ݅ሺሻ א
݂ ܲܮ ǡ ܫ א ݅ሺͺሻ
݂ െ ݃ ൌ Ͳǡ ܬ א ݆ሺͻሻ אூ
݂ െ ݃ ൌ Ͳǡ ܬ א ݆ሺͳͲሻ אூ ݃ א
ൌ ݀ ǡ ܭ א ݇ሺͳͳሻ
ൌ ݀ ǡ ܭ א ݇ሺͳʹሻ ݃ א
ݔோ אሼͲǡͳሽǡ ܬ א ݆ሺͳ͵ሻ ݔ אሼͲǡͳሽǡ ܬ א ݆ሺͳͶሻ ݂ Ͳǡ ܫ א ݅ǡ ܬ א ݆ሺͳͷሻ ݂ Ͳǡ ܫ א ݅ǡ ܬ א ݆ሺͳሻ ݃ Ͳǡ ܬ א ݆ǡ ܭ א ݇ሺͳሻ ݃ Ͳǡ ܬ א ݆ǡ ܭ א ݇ሺͳͺሻ
The objective function is expected costs that consist of fixed cost for opening RS, shipping cost at DC, transportation costs between facilities and handling cost at RS. Equation (1) requires that either of RRS or URS can be open, but not both; Eq.(2) at least one RRS must be opened; Equations (3) and (4) are capacity constraints for RS as primary and backup assignment, respectively; Eqs.(5) and (6) upper bounds for available supply as primary and backup assignment, respectively; Eqs.(7) and (8) lower bounds for available supply as primary and backup assignment, respectively; Eqs.(9) and (10) balances of product flow as primary and backup assignment, respectively: Equations (11) and (12) mean demand of every customer must be satisfied as primary and backup assignment, respectively. Due to some undisrupted reasons, it makes sense to assume such a relation for each cost parameter that FjR > FjU, T1jkB > T1jkP, T2jkB > T2jkP, CiB > CiP and HkB > HkP. Since thus formulated problem belongs to a NP-hard class, its solution becomes extremely difficult according to the increase in problem size.
3. Hybrid Approach for Solution Taking a similar hierarchical logistic network mentioned above, we proposed a method termed hybrid tabu search (Shimizu et al., 2004) and applied its variants both to the
Y. Shimizu et al.
certain and uncertain cases. It is a two-level method whose upper level problem decides the locations of distribution centre and the lower derives the routes among the facilities. At the upper level, evolutionary search is carried out so that the neighbor location is updated by the sophisticated tabu search, in turn. On the other hand, the location pegged problem at the lower level refers to a linear program (LP) that is possible to transform into the minimum cost flow problem (MCF). Finally, we can apply the graph algorithm such as CS2 or Relax 4 to solve the resulting problem extremely fast compared with solving Start stage=1 directly the original LP. These procedures will be Evolutionary search Set stage data repeated until a certain (RS location) convergence criterion has stage:=stage+1 been satisfied. This basic No Stage=2 Graph algorithm idea is possible to ? (product delivery) straightforwardly extend to Yes the present solution just by Compute expected value solving the lower level No Converged problem both for normal ? Yes Conventional and abnormal cases, Two-step method Stop respectively and combining stage 1=normal, 2=abnormal them together to compute the expected cost (See right Fig.2 Flowchart of the proposed procedure hand side of Fig.2).
4. Numerical Experiment To verify the effectiveness of the proposed approach, we provide a few benchmark problems whose system parameters are given randomly within the respective upper and lower bounded values. Result of the hybrid approach for a small model (number of DC/ RS/ Customer = 2/ 5/ 50) is given in Table 1. This coincides with the one derived from commercial software known as CPLEX 12. From this, we know DCs will distribute products from three open RSs (RS#2, RS#4 and RS#5) for every disruption probability except for q=0.4. It is interesting to see that RS#4 is used as the unreliable RS when q is low while it appears as the reliable one at the higher q after it disappears during the middle range of probability. This is because the opening cost of RS#4 is quite cheap among RSs. Hence, opening this RS as URS can save the transportation cost greatly when q is low. In contrast, when q becomes higher, it makes sense to open this RS as RRS to cope with the disruption as well as transportation cost saving. The situation when q=0.4 appears as the transient status of these two cases. These facts can confirm the adequateness of the proposed model. Relying on this preliminary experiment, we solved several problems with such larger sizes that makes extremely difficult to solve by the commercial software from our previous experiences. For example, Table 2 summarizes the results for different numbers of customer up to 5000 when q=0.1. We also know that the rising rate with the increase in q is almost constant for the primal cost while most remarkable for the backup cost. From Fig.3, as expected a priori, we can observe a rapid increase in CPU time with the problem size.
Hybrid Approach for Multi-stage Logistics Network Optimization under Disruption Risk 1039
Table 1 Result for a small problem: DC/ RS/ Customer = 2/ 5/ 50 Probability (q) Relay station (RS) Number of RS Facilities (RS #) Expected cost unit [-]
0.01 URS RRS 1 2 (#4) (#2,5) 4,454,105
URS: unreliable relay station
0.1 URS RRS 1 2 (#4) (#2,5) 4,644,056
RRS 2 (#2,5) 5,276,776
RRS 3 (#2,4,5) 5,484,457
RRS: reliable relay station
Table 2 Results for larger problem size when q=0.1 Problem size (DC/ RS/ Customer)
10/ 30/ 500 10/ 30/ 1000 10/ 30/ 2000 10/ 30/ 3000 10/ 30/ 5000
Expected cost unit 2.75E7 5.70E7 1.43E8 1.94E8 3.24E8
Primal cost unit 2.61E7 5.44E7 1.37E8 1.83E8 3.08E8
Backup cost unit 3.95E7 8.11E7 2.00E8 2.95E8 4.68E8
9 15 14 16 17
5 2 1 8 7
CPU time [sec]
1.00E+03 Concerning with supply chain, this study investigates the multistage logistics network design that 5.00E+02 are exposed to various risks. The problem under disruption risk is 0.00E+00 formulated as a probabilistic 500 1000 2000 3000 5000 programming model. Then to find RE number [-] the optimal solution of this problem in practice, a hybrid Fig.3 CPU time vs. problem size method is employed which combines a meta-heuristic method and a graph algorithm in a hierarchical manner. Through the numerical experiment, we have shown the proposed approach is promising to design the resilient logistic networks available for the real world mitigation planning. Future studies should be devoted to enhance the solution ability and consider the more realistic conditions suitable for business continuity plan/management that will provide .
References S. Chopra and M.S. Sodhi, 2004, Managing risk to avoid supply-chain breakdown, MIT Sloan Management Review, Vol.46, 53-61 Y. Shimizu, H. Fushimi and T. Wada, 2011, Robust Logistics Network Modeling and Design against Uncertainties, Journal of Advanced Mechanical Design, Systems, and Manufacturing, Vol.5, No.2, 103-114 Y. Shimizu and M. Rusman, 2012, Morphological Analysis for Multistage Logistic Network Optimization under Disruption Risk, Proc. International Symposium on Semiconductor Manufacturing Intelligence, Hsinchu, Taiwan L.V. Snyder and M.S Daskin, 2005, Reliability models for facility location: the expected failure cost case, Transportation Science, Vol.39, No.5, 400-416 B. Tomlin, 2006, The value of mitigation and contingency strategies for managing supply chain disruption risks, Management Science, Vol.50, No.5, 639-657