\`x^2+y_1+z_12^34\`
Advanced Search
Article Contents
Article Contents

Disaster relief routing in limited capacity road networks with heterogeneous flows

  • * Corresponding author: Dilek Tuzun Aksu

    * Corresponding author: Dilek Tuzun Aksu 
Abstract Full Text(HTML) Figure(1) / Table(3) Related Papers Cited by
  • 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.

    Mathematics Subject Classification: Primary: 90C35, 90C11, 90C06, 90B06, 90B20.

    Citation:

    \begin{equation} \\ \end{equation}
  • 加载中
  • Figure 1.  Road network of Fatih County in Istanbul

    Table .   

    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)
     | Show Table
    DownLoad: CSV

    Table 1.  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
     | Show Table
    DownLoad: CSV

    Table 2.  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
     | Show Table
    DownLoad: CSV
  •   A. Afshar  and  A. Haghani , Modeling integrated supply chain logistics in real-time large-scale disaster relief operations, Socio-Economic Planning Sciences, 46 (2012) , 327-338.  doi: 10.1016/j.seps.2011.12.003.
      V. Akbari  and  F. S. Salman , Multi-vehicle synchronized arc routing problem to restore post-disaster network connectivity, European Journal of Operational Research, 257 (2017) , 625-640.  doi: 10.1016/j.ejor.2016.07.043.
      M. Albareda-Sambola , A. Alonso-Ayuso , L. F. Escudero , E. Fernandez  and  C. Pizarro , Fix-and-relax-coordination for a multi-period location-allocation problem under uncertainty, Computers & Operations Research, 40 (2013) , 2878-2892.  doi: 10.1016/j.cor.2013.07.004.
      A. M. Anaya-Arenas , J. Renaud  and  A. Ruiz , Relief distribution networks: A systematic review, Annals of Operations Research, 223 (2014) , 53-79.  doi: 10.1007/s10479-014-1581-y.
      J. Araoz , E. Fernandez  and  C. Zoltan , Privatized rural postman problems, Computers & Operations Research, 33 (2006) , 3432-3449.  doi: 10.1016/j.cor.2005.02.013.
      J. Araoz , E. Fernandez  and  O. Meza , Solving the prize-collecting rural postman problem, European Journal of Operational Research, 196 (2009) , 886-896.  doi: 10.1016/j.ejor.2008.04.037.
      C. Archetti , D. Feillet , A. Hertz  and  M. G. Speranza , The undirected capacitated arc routing problem with profits, Computers & Operations Research, 37 (2010) , 1860-1869.  doi: 10.1016/j.cor.2009.05.005.
      B. Balcik , B. M. Beamon  and  K. Smilowitz , Last mile distribution in humanitarian relief, Journal of Intelligent Transportation Systems, 12 (2008) , 51-63.  doi: 10.1080/15472450802023329.
      T. A. Baldo , M. O. Santos , B. Almada-Lobo  and  R. Morabito , An optimization approach for the lot sizing and scheduling problem in the brewery industry, Computers & Industrial Engineering, 72 (2014) , 58-71.  doi: 10.1016/j.cie.2014.02.008.
      P. Beraldi , G. Ghiani , E. Guerriero  and  A. Grieco , Scenario-based planning for lot-sizing and scheduling with uncertain processing times, International Journal of Production Economics, 101 (2006) , 140-149.  doi: 10.1016/j.ijpe.2005.05.018.
      D. Berkoune , J. Renaud , M. Rekik  and  A. Ruiz , Transportation in disaster response operations, Socio-Economic Planning Sciences, 46 (2012) , 23-32.  doi: 10.1016/j.seps.2011.05.002.
      V. Campos , R. Bandeira  and  A. Bandeira , A method for evacuation route planning in disaster situations, Procedia-Social and Behavioral Sciences, 54 (2012) , 503-512.  doi: 10.1016/j.sbspro.2012.09.768.
      A. M. Caunhye , X. Nie  and  S. Pokharel , Optimization models in emergency logistics: A literature review, Socio-Economic Planning Sciences, 46 (2012) , 4-13.  doi: 10.1016/j.seps.2011.04.004.
      A. Y. Chen , F. Pena-Mora  and  Y. Ouyang , A collaborative GIS framework to support equipment distribution for civil engineering disaster response operations, Automation in Construction, 20 (2011) , 637-648.  doi: 10.1016/j.autcon.2010.12.007.
      T. Cova  and  J. Johnson , A network flow model for lane-based evacuation routing, Transportation Research Part A: Policy and Practice, 37 (2003) , 579-604.  doi: 10.1016/S0965-8564(03)00007-7.
      J. Cui, S. An and M. Zhao, A generalized minimum cost flow model for multiple emergency flow routing Mathematical Problems in Engineering 2014 (2014), Article ID 832053, 12 pages. doi: 10.1155/2014/832053.
      C. F. Daganzo , The cell transmission model: A dynamic representation of highway traffic consistent with the hydrodynamic theory, Transportation Research Part B: Methodological, 28 (1994) , 269-287.  doi: 10.1016/0191-2615(94)90002-7.
      L. E. de la Torre , I. S. Dolinskaya  and  K. R. Smilowitz , Disaster relief routing: Integrating research and practice, Socio-Economic Planning Sciences, 46 (2012) , 88-97. 
      L. Escudero , A. Garin , M. Merino  and  G. Perez , BFC-MSMIP: An exact branch-and-fix coordination approach for solving multistage stochastic mixed 0--1 problems, TOP, 17 (2009) , 96-122.  doi: 10.1007/s11750-009-0083-6.
      D. Feillet , P. Dejax  and  M. Gendreau , The profitable arc tour problem: Solution with a branch-and-price algorithm, Transportation Science, 39 (2005) , 539-552.  doi: 10.1287/trsc.1040.0106.
      C. M. Feng  and  C. C. Wen , A fuzzy bi-level and multi-objective model to control traffic flow into disaster area post earthquake, Journal of the Eastern Asia Society for Transportation Studies, 6 (2005) , 4253-4268. 
      D. Ferreira , R. Morabito  and  S. Rangel , Relax and fix heuristics to solve one-stage one machine lot-scheduling models for small-scale soft drink plants, Computers & Operations Research, 37 (2010) , 684-691.  doi: 10.1016/j.cor.2009.06.007.
      S. Gupta , M. Starr , R. Zanjirani Farahani  and  N. Matinrad , Disaster management from a POM perspective: Mapping a new domain, Production and Operations Management, 25 (2016) , 1611-1637.  doi: 10.1111/poms.12591.
      A. Haghani  and  S. C. Oh , Formulation and solution of a multi-commodity, multi-modal network flow model for disaster relief operations, Transportation Research Part A: Policy and Practice, 30 (1996) , 231-250.  doi: 10.1016/0965-8564(95)00020-8.
      F. Liberatore , M. T. Ortuno , G. Tirado , B. Vitoriano  and  M. P. Scaparra , A hierarchical compromise model for the joint optimization of recovery operations and distribution of emergency goods in Humanitarian Logistics, Computers & Operations Research, 42 (2014) , 3-13.  doi: 10.1016/j.cor.2012.03.019.
      G. J. Lim , S. Zangeneh , M. R. Baharnemati  and  T. Assavapokee , A capacitated network flow optimization approach for short notice evacuation planning, European Journal of Operational Research, 223 (2012) , 234-245.  doi: 10.1016/j.ejor.2012.06.004.
      Y. H. Lin , R. Batta , P. A. Rogerson , A. Blatt  and  M. Flanigan , A logistics model for emergency supply of critical items in the aftermath of a disaster, Socio-Economic Planning Sciences, 45 (2011) , 132-145.  doi: 10.1016/j.seps.2011.04.003.
      Y. Liu , X. R. Lai  and  G. L. Chang , Two-level integrated optimization system for planning emergency evacuation, J. Of Transportation Engineering, 132 (2006) , 800-807.  doi: 10.1061/(ASCE)0733-947X(2006)132:10(800).
      E. Miller-Hooks  and  S. S. Patterson , On solving quickest time problems in time-dependent, dynamic networks, Journal of Mathematical Modelling and Algorithms, 3 (2004) , 39-71.  doi: 10.1023/B:JMMA.0000026708.57419.6d.
      M. Najafi , K. Eshghi  and  W. Dullaert , A multi-objective robust optimization model for logistics planning in the earthquake response phase, Transportation Research Part E: Logistics and Transportation Review, 49 (2013) , 217-249.  doi: 10.1016/j.tre.2012.09.001.
      L. Ozdamar  and  O. Demir , A hierarchical clustering and routing procedure for large scale disaster relief logistics planning, Transportation Research Part E: Logistics and Transportation Review, 48 (2012) , 591-602.  doi: 10.1016/j.tre.2011.11.003.
      L. Ozdamar , E. Ekinci  and  B. Kucukyazici , Emergency logistics planning in natural disasters, Annals of Operations Research, 129 (2004) , 217-245.  doi: 10.1023/B:ANOR.0000030690.27939.39.
      L. Ozdamar  and  M. A. Ertem , Models, solutions and enabling technologies in humanitarian logistics, European Journal of Operational Research, 244 (2015) , 55-65.  doi: 10.1016/j.ejor.2014.11.030.
      B. Vitoriano , M. T. Ortuno , G. Tirado  and  J. Montero , A multi-criteria optimization model for humanitarian aid distribution, Journal of Global Optimization, 51 (2011) , 189-208.  doi: 10.1007/s10898-010-9603-z.
      B. Vitoriano , T. Ortuno  and  G. Tirado , HADS, a goal programming-based humanitarian aid distribution system, Journal of Multi-Criteria Decision Analysis, 16 (2009) , 55-64.  doi: 10.1002/mcda.439.
      S. Yan  and  Y. L. Shih , Optimal scheduling of emergency roadway repair and subsequent relief distribution, Computers & Operations Research, 36 (2009) , 2049-2065.  doi: 10.1016/j.cor.2008.07.002.
  • 加载中

Figures(1)

Tables(3)

SHARE

Article Metrics

HTML views(1811) PDF downloads(689) Cited by(0)

Access History

Catalog

    /

    DownLoad:  Full-Size Img  PowerPoint
    Return
    Return