# American Institute of Mathematical Sciences

October  2018, 14(4): 1367-1380. doi: 10.3934/jimo.2018011

## Disaster relief routing in limited capacity road networks with heterogeneous flows

 Department of Industrial and Systems Engineering, Yeditepe University, 26 Agustos Yerlesimi, Kayisdagi Cad., 34755 Atasehir, Istanbul, Turkey

* Corresponding author: Dilek Tuzun Aksu

Received  September 2016 Revised  October 2017 Published  January 2018

In the aftermath of a major earthquake, delivery of essential services to survivors is of utmost importance and in urban areas it is conducted using road networks that are already stressed by road damages, other urban traffic and evacuation. Relief distribution efforts should be planned carefully in order to create minimal additional traffic congestion. We propose a dynamic relief distribution model where relief trucks share limited capacity road networks with counterflows resulting from car traffic. We develop a MIP model for this problem and solve it by decomposing the road network geographically and solving each subnetwork iteratively using the Relax and Fix method.

Citation: Linet Ozdamar, Dilek Tuzun Aksu, Elifcan Yasa, Biket Ergunes. Disaster relief routing in limited capacity road networks with heterogeneous flows. Journal of Industrial & Management Optimization, 2018, 14 (4) : 1367-1380. doi: 10.3934/jimo.2018011
##### References:

show all references

##### References:
Road network of Fatih County in Istanbul
 Algorithm 1 1: Initialize $k=0$ 2:While $(k < \frac{T}{\Delta t})$ do 3:     $k++$ 4:     Define $y_{ijcq}$ and $v_{ijcq}$ for $q=(k-1)\Delta t+1, ..., k\Delta t$ as integers, let $y_{ijcq}$ and $v_{ijcq}$ be positive float variables for $q= k\Delta t+1, ..., T$ 5:     Solve Model R 6:     Fix $y_{ijcq}$ and $v_{ijcq}$ for $q=(k-1)\Delta t+1, ..., k\Delta t$ at their optimal integer values 7: end while 8: Report final solution 9: End (Algorithm1)
 Algorithm 1 1: Initialize $k=0$ 2:While $(k < \frac{T}{\Delta t})$ do 3:     $k++$ 4:     Define $y_{ijcq}$ and $v_{ijcq}$ for $q=(k-1)\Delta t+1, ..., k\Delta t$ as integers, let $y_{ijcq}$ and $v_{ijcq}$ be positive float variables for $q= k\Delta t+1, ..., T$ 5:     Solve Model R 6:     Fix $y_{ijcq}$ and $v_{ijcq}$ for $q=(k-1)\Delta t+1, ..., k\Delta t$ at their optimal integer values 7: end while 8: Report final solution 9: End (Algorithm1)
Performance of the RF Algorithm as a function of $\Delta t$
 Region Method Obj. CPU(secs.) Rel.Gap % Dev 1(56 links) No RF 1948.89 590.48 0.001 - RF ($\Delta t$=2) 1928.38 680.01 -1.052 RF ($\Delta t$=4) 1931.90 415.80 -0.872 RF ($\Delta t$=8) 1932.05 374.31 -0.864 2(54 links) No RF 2055.46 3609.47 0.017 - RF ($\Delta t$=2) 2037.86 734.53 -0.856 RF ($\Delta t$=4) 2052.20 489.48 -0.159 RF ($\Delta t$=8) 2053.23 744.67 -0.108 3(65 links) No RF 1659.32 3611.89 0.021 - RF ($\Delta t$=2) 1667.39 999.43 0.486 RF ($\Delta t$=4) 1655.30 636.56 -0.242 RF ($\Delta t$=8) 1656.58 645.14 -0.165 4(52 links) No RF 3967.29 3609.02 0.003 - RF ($\Delta t$=2) 3964.52 713.17 -0.070 RF ($\Delta t$=4) 3961.60 424.16 -0.143 RF ($\Delta t$=8) 3967.04 278.05 -0.006 5(46 links) No RF 2969.91 3610.08 0.009 - RF ($\Delta t$=2) 2969.68 304.56 -0.008 RF ($\Delta t$=4) 2973.97 164.88 0.137 RF ($\Delta t$=8) 2972.40 140.04 0.084 6(63 links) No RF 1347.78 3612.22 0.018 - RF ($\Delta t$=2) 1346.13 948.06 -0.122 RF ($\Delta t$=4) 1353.34 533.05 0.413 RF ($\Delta t$=8) 1353.42 472.09 0.418 7(64 links) No RF 1834.74 3608.97 0.011 - RF ($\Delta t$=2) 1822.31 999.92 -0.677 RF ($\Delta t$=4) 1824.13 539.54 -0.578 RF ($\Delta t$=8) 1830.28 475.05 -0.243
 Region Method Obj. CPU(secs.) Rel.Gap % Dev 1(56 links) No RF 1948.89 590.48 0.001 - RF ($\Delta t$=2) 1928.38 680.01 -1.052 RF ($\Delta t$=4) 1931.90 415.80 -0.872 RF ($\Delta t$=8) 1932.05 374.31 -0.864 2(54 links) No RF 2055.46 3609.47 0.017 - RF ($\Delta t$=2) 2037.86 734.53 -0.856 RF ($\Delta t$=4) 2052.20 489.48 -0.159 RF ($\Delta t$=8) 2053.23 744.67 -0.108 3(65 links) No RF 1659.32 3611.89 0.021 - RF ($\Delta t$=2) 1667.39 999.43 0.486 RF ($\Delta t$=4) 1655.30 636.56 -0.242 RF ($\Delta t$=8) 1656.58 645.14 -0.165 4(52 links) No RF 3967.29 3609.02 0.003 - RF ($\Delta t$=2) 3964.52 713.17 -0.070 RF ($\Delta t$=4) 3961.60 424.16 -0.143 RF ($\Delta t$=8) 3967.04 278.05 -0.006 5(46 links) No RF 2969.91 3610.08 0.009 - RF ($\Delta t$=2) 2969.68 304.56 -0.008 RF ($\Delta t$=4) 2973.97 164.88 0.137 RF ($\Delta t$=8) 2972.40 140.04 0.084 6(63 links) No RF 1347.78 3612.22 0.018 - RF ($\Delta t$=2) 1346.13 948.06 -0.122 RF ($\Delta t$=4) 1353.34 533.05 0.413 RF ($\Delta t$=8) 1353.42 472.09 0.418 7(64 links) No RF 1834.74 3608.97 0.011 - RF ($\Delta t$=2) 1822.31 999.92 -0.677 RF ($\Delta t$=4) 1824.13 539.54 -0.578 RF ($\Delta t$=8) 1830.28 475.05 -0.243
Comparison of solution quality for various decomposition strategies
 Subnetworks Obj. CPU Rel.Gap No. of Links 67 3527.10 7251.00 0.03 127 6+7 3182.52 7221.19 6+7 (RF) 3183.70 947.14 12 3998.60 7241.77 0.02 110 1+2 4004.35 4199.95 1+2 (RF) 3985.28 1118.97 45 8499.28 7232.73 0.01 98 4+5 6937.20 7219.10 4+5 (RF) 6939.44 418.10 37 3744.10 7243.97 0.10 129 3+7 3494.06 7220.86 3+7 (RF) 3486.86 1120.19 34 5621.70 7246.52 0.01 117 3+4 5626.61 7220.91 3+4 (RF) 5623.62 923.19 345 9050.53 10897.60 0.12 163 34+5 8591.61 10856.60 3+4+5 8596.52 10830.99 3+4+5 (RF) 8596.02 1063.23 456 9713.23 10905.90 0.08 161 45+6 9847.06 10844.95 4+5+6 8284.98 10831.32 4+5+6 (RF) 8292.86 890.18 567 5520.59 10914.90 0.24 173 5+67 6497.01 10861.08 5+6+7 6152.43 10831.27 5+6+7 (RF) 6156.10 1087.18 123 650.07 10939.80 1.00 175 12+3 5657.92 10853.66 1+2+3 5663.67 7811.84 1+2+3 (RF) 5641.86 1764.11 12345 1145.08 18450.00 1.00 273 12+345 13049.13 18139.37 123+45 9149.35 18172.53 1+2+3+4+5 12600.87 15030.94 1+2+3+4+5 (RF) 12581.30 2182.21 34567 1170.16 18560.90 1.00 290 34+567 11142.29 18161.42 37+456 13457.33 18149.87 3+4+5+6+7 11779.04 18052.18 3+4+5+6+7 (RF) 11779.72 2010.37
 Subnetworks Obj. CPU Rel.Gap No. of Links 67 3527.10 7251.00 0.03 127 6+7 3182.52 7221.19 6+7 (RF) 3183.70 947.14 12 3998.60 7241.77 0.02 110 1+2 4004.35 4199.95 1+2 (RF) 3985.28 1118.97 45 8499.28 7232.73 0.01 98 4+5 6937.20 7219.10 4+5 (RF) 6939.44 418.10 37 3744.10 7243.97 0.10 129 3+7 3494.06 7220.86 3+7 (RF) 3486.86 1120.19 34 5621.70 7246.52 0.01 117 3+4 5626.61 7220.91 3+4 (RF) 5623.62 923.19 345 9050.53 10897.60 0.12 163 34+5 8591.61 10856.60 3+4+5 8596.52 10830.99 3+4+5 (RF) 8596.02 1063.23 456 9713.23 10905.90 0.08 161 45+6 9847.06 10844.95 4+5+6 8284.98 10831.32 4+5+6 (RF) 8292.86 890.18 567 5520.59 10914.90 0.24 173 5+67 6497.01 10861.08 5+6+7 6152.43 10831.27 5+6+7 (RF) 6156.10 1087.18 123 650.07 10939.80 1.00 175 12+3 5657.92 10853.66 1+2+3 5663.67 7811.84 1+2+3 (RF) 5641.86 1764.11 12345 1145.08 18450.00 1.00 273 12+345 13049.13 18139.37 123+45 9149.35 18172.53 1+2+3+4+5 12600.87 15030.94 1+2+3+4+5 (RF) 12581.30 2182.21 34567 1170.16 18560.90 1.00 290 34+567 11142.29 18161.42 37+456 13457.33 18149.87 3+4+5+6+7 11779.04 18052.18 3+4+5+6+7 (RF) 11779.72 2010.37
 [1] Louis Caccetta, Syarifah Z. Nordin. Mixed integer programming model for scheduling in unrelated parallel processor system with priority consideration. Numerical Algebra, Control & Optimization, 2014, 4 (2) : 115-132. doi: 10.3934/naco.2014.4.115 [2] Elham Mardaneh, Ryan Loxton, Qun Lin, Phil Schmidli. A mixed-integer linear programming model for optimal vessel scheduling in offshore oil and gas operations. Journal of Industrial & Management Optimization, 2017, 13 (4) : 1601-1623. doi: 10.3934/jimo.2017009 [3] Wan Nor Ashikin Wan Ahmad Fatthi, Adibah Shuib, Rosma Mohd Dom. A mixed integer programming model for solving real-time truck-to-door assignment and scheduling problem at cross docking warehouse. Journal of Industrial & Management Optimization, 2016, 12 (2) : 431-447. doi: 10.3934/jimo.2016.12.431 [4] Ye Tian, Cheng Lu. Nonconvex quadratic reformulations and solvable conditions for mixed integer quadratic programming problems. Journal of Industrial & Management Optimization, 2011, 7 (4) : 1027-1039. doi: 10.3934/jimo.2011.7.1027 [5] Alessia Marigo, Benedetto Piccoli. A model for biological dynamic networks. Networks & Heterogeneous Media, 2011, 6 (4) : 647-663. doi: 10.3934/nhm.2011.6.647 [6] Haiying Liu, Wenjie Bi, Kok Lay Teo, Naxing Liu. Dynamic optimal decision making for manufacturers with limited attention based on sparse dynamic programming. Journal of Industrial & Management Optimization, 2019, 15 (2) : 445-464. doi: 10.3934/jimo.2018050 [7] René Henrion, Christian Küchler, Werner Römisch. Discrepancy distances and scenario reduction in two-stage stochastic mixed-integer programming. Journal of Industrial & Management Optimization, 2008, 4 (2) : 363-384. doi: 10.3934/jimo.2008.4.363 [8] Edward S. Canepa, Alexandre M. Bayen, Christian G. Claudel. Spoofing cyber attack detection in probe-based traffic monitoring systems using mixed integer linear programming. Networks & Heterogeneous Media, 2013, 8 (3) : 783-802. doi: 10.3934/nhm.2013.8.783 [9] Zhiguo Feng, Ka-Fai Cedric Yiu. Manifold relaxations for integer programming. Journal of Industrial & Management Optimization, 2014, 10 (2) : 557-566. doi: 10.3934/jimo.2014.10.557 [10] Meihong Qiao, Anping Liu, Qing Tang. The dynamics of an HBV epidemic model on complex heterogeneous networks. Discrete & Continuous Dynamical Systems - B, 2015, 20 (5) : 1393-1404. doi: 10.3934/dcdsb.2015.20.1393 [11] Huai-Che Hong, Bertrand M. T. Lin. A note on network repair crew scheduling and routing for emergency relief distribution problem. Journal of Industrial & Management Optimization, 2019, 15 (4) : 1729-1731. doi: 10.3934/jimo.2018119 [12] Fanwen Meng, Kiok Liang Teow, Kelvin Wee Sheng Teo, Chee Kheong Ooi, Seow Yian Tay. Predicting 72-hour reattendance in emergency departments using discriminant analysis via mixed integer programming with electronic medical records. Journal of Industrial & Management Optimization, 2019, 15 (2) : 947-962. doi: 10.3934/jimo.2018079 [13] Mahmoud Ameri, Armin Jarrahi. An executive model for network-level pavement maintenance and rehabilitation planning based on linear integer programming. Journal of Industrial & Management Optimization, 2017, 13 (5) : 1-17. doi: 10.3934/jimo.2018179 [14] Yongjian Yang, Zhiyou Wu, Fusheng Bai. A filled function method for constrained nonlinear integer programming. Journal of Industrial & Management Optimization, 2008, 4 (2) : 353-362. doi: 10.3934/jimo.2008.4.353 [15] A. Cascone, Alessia Marigo, B. Piccoli, L. Rarità. Decentralized optimal routing for packets flow on data networks. Discrete & Continuous Dynamical Systems - B, 2010, 13 (1) : 59-78. doi: 10.3934/dcdsb.2010.13.59 [16] Xuefeng Wang. The heterogeneous fleet location routing problem with simultaneous pickup and delivery and overloads. Discrete & Continuous Dynamical Systems - S, 2019, 12 (4&5) : 1147-1166. doi: 10.3934/dcdss.2019079 [17] Raul Borsche, Axel Klar, T. N. Ha Pham. Nonlinear flux-limited models for chemotaxis on networks. Networks & Heterogeneous Media, 2017, 12 (3) : 381-401. doi: 10.3934/nhm.2017017 [18] Dandan Hu, Zhi-Wei Liu. Location and capacity design of congested intermediate facilities in networks. Journal of Industrial & Management Optimization, 2016, 12 (2) : 449-470. doi: 10.3934/jimo.2016.12.449 [19] Zhenbo Wang, Shu-Cherng Fang, David Y. Gao, Wenxun Xing. Global extremal conditions for multi-integer quadratic programming. Journal of Industrial & Management Optimization, 2008, 4 (2) : 213-225. doi: 10.3934/jimo.2008.4.213 [20] Jing Quan, Zhiyou Wu, Guoquan Li. Global optimality conditions for some classes of polynomial integer programming problems. Journal of Industrial & Management Optimization, 2011, 7 (1) : 67-78. doi: 10.3934/jimo.2011.7.67

2018 Impact Factor: 1.025