Robust optimization for the hazardous materials transportation network design problem

详细信息    查看全文

• 作者：Chunlin Xin ; Letu Qingge ; Jiamin Wang ; Binhai Zhu
• 关键词：Hazmat transportation network design ; Uncertain edge risk ; Computational complexity ; Robust optimization ; Heuristic algorithms
• 刊名：Journal of Combinatorial Optimization
• 出版年：2015
• 出版时间：August 2015
• 年：2015
• 卷：30
• 期：2
• 页码：320-334
• 全文大小：643 KB
• 参考文献：1.China Chemical Safety Association. http://鈥媤ww.鈥媍hemicalsafety.鈥媜rg.鈥媍n
  2.Kara BY, Verter V (2004) Designing a road network for hazardous materials transportation. Transp Sci 38(2):188鈥?96View Article
  3.Erkut E, Alp O (2007) Designing a road network for hazardous materials shipments. Comput Oper Res 34(5):1389鈥?405MATH View Article
  4.Erkut E, Gzara F (2008) Solving the hazmat transport network design problem. Comput Oper Res 35(7):2234鈥?247MATH View Article
  5.Verter V, Kara BY (2008) A path-based approach for hazmat transport network design. Manag Sci 54(1):29鈥?0View Article
  6.Amaldi E, Bruglieri M, Fortz B (2011) On the hazmat transport network design problem. Lect Notes Comput Sci 6701:327鈥?38View Article
  7.Bianco L, Caramia M, Giordani S (2009) A bilevel flow model for hazmat transportation netwokrk design. Transp Res Part C Emerg Technol 17(2):175鈥?96View Article
  8.Erkut E, Verter V (1998) Modeling of transport risk for hazardous materials. Oper Res 46(5):625鈥?42MATH View Article
  9.Erkut E, Tjandra SA, Verter V (2007) Hazardous materials transportation. Elsevier, Amsterdam
  10.Zhu BH (2009) Approximability and fixed-parameter tractability for the exemplar genomic distance problems. Lect Notes Comput Sci 5532:71鈥?0View Article
  11.Soyster A (1973) Convex programming with set-inclusive constraints and applications to inexact linear programming. Oper Res 21:1154鈥?157MATH MathSciNet View Article
  12.Ben-Tal A, El Ghaoui L, Nemirovski AS (2009) Robust optimization. Princeton University Press, PrincetonMATH View Article
  13.Bertsimas D, Sim M (2003) Robust discrete optimization and network flows. Math Program Ser B 98(1鈥?):49鈥?1MATH MathSciNet View Article
  14.Bertsimas D, Sim M (2004) The price of robustness. Oper Res 52(1):35鈥?3MATH MathSciNet View Article
  15.Karasan OE, Pinar MC, Yaman H (2001) The robust shortest path problem with interval data[R]. Technical report, Bilkent University
  16.Kouvelis P, Yu G (1997) Robust discrete optimization and its applications. Kluwer Academic Publishers, BostonMATH View Article
  17.Gabrel V, Murat C (2007) Robust shortest path problems. Ann du LAMSADE 7:71鈥?3
  18.Zielinski P (2004) The computational complexity of the relative robust shortest path problem with interval data. Eur J Oper Res 158:570鈥?76MATH MathSciNet View Article
  19.Averbakh I, Lebedev V (2004) Interval data minmax regret network optimizationproblems. Discret Appl Math 138:289鈥?01MATH MathSciNet View Article
  20.Wen U, Hsu S (1991) Linear bi-Level programming problems - a review. J Oper Res Soc 42(2):125鈥?33MATH
  21.Colson B, Marcotte P, Savard G (2007) An overview of bilevel optimization. Ann Oper Res 153(1):235鈥?56MATH MathSciNet View Article
  22.Montemanni R, Gambardella LM (2004) An exact algorithm for the robust shortest path problem with interval data. Comput Oper Res 31:1667鈥?680MATH MathSciNet View Article
  23.Montemanni R, Gambardella LM (2005) The robust path problem with interval data via benders decomposition. Q J Oper Res 3(4):315鈥?28MATH MathSciNet View Article
  24.Montemanni R, Gambardella LM, Donati AV (2004) A branch and bound algorithm for the robust shortest path problem with interval data. Oper Res Lett 32:225鈥?32MATH MathSciNet View Article
  
• 作者单位：Chunlin Xin (1)
  Letu Qingge (1)
  Jiamin Wang (2)
  Binhai Zhu (3)
  
  1. School of Economics and Management, Beijing University of Chemical Technology, Beijing, 100029, China
  2. College of Management, Long Island University, C. W. Post Campus, Brookville, NY, 11548, USA
  3. Department of Computer Science, Montana State University, Bozeman, MT, 59717, USA
  
• 刊物类别：Mathematics and Statistics
• 刊物主题：Mathematics
  Combinatorics
  Convex and Discrete Geometry
  Mathematical Modeling and IndustrialMathematics
  Theory of Computation
  Optimization
  Operation Research and Decision Theory
  
• 出版者：Springer Netherlands
• ISSN：1573-2886

文摘

In this paper, we reconsider the hazardous materials transportation network design problem with uncertain edge risk (HTNDPUR) which is proved as strong NP-hard. The natural ways to handle NP-hard problems are approximation solutions or FPT algorithms. We prove that the HTNDPUR does not admit any approximation, neither any FPT algorithm, unless P = NP. Furthermore, we utilize the minimax regret criterion to model the HTNDPUR as a bi-level integer programming formulation under edge risk uncertainty, where an interval of possible risk values is associated with each arc. We present a robust heuristic approach that always finds a robust and stable hazmat transportation network. At the end, we test our method on a network of Guangdong province in China to illustrate the efficiency of the algorithm. Our experimental results illustrate that the robust interval risk scenario network performs better than the deterministic scenario network.