مدلسازی عدم تقارن اطلاعات در مساله حمله به شبکه حمل و نقل مواد خطرناک

نوع مقاله : علمی - پژوهشی

نویسندگان

1 دانشیار، دانشکده مهندسی، دانشگاه بوعلی سینا، همدان، ایران

2 دانشیار، دانشکده علوم پایه، دانشگاه شاهد، تهران، ایران

3 دانشجوی دکتری، دانشکده مهندسی، دانشگاه بوعلی سینا، همدان، همدان

چکیده

در این مقاله، مساله توزیع مواد خطرناک در شرایطی مورد بررسی قرار می‏گیرد که در آن از یک سو، توزیع‏کننده درصدد انتخاب مسیرهای اقتصادی با کمترین هزینه بر روی شبکه است و از سوی دیگر به منظور افزایش ایمنی حمل مواد خطرناک، آژانسی نظارتی به عنوان مهاجم، در صدد است که تصمیم توزیع‏کننده برای عبور از کمان‏های شبکه را تحت کنترل قراردهد و در صورتی‏که توزیع‏کننده از این کمان‏ها عبور نماید، از وی جریمه دریافت نماید. در این تحقیق، تعارض موجود بین دو تصمیم‏گیرنده در حالتی‏که آن‏ها درک یکسانی از اطلاعات شبکه ندارند، در قالب مدلی دوسطحی مدلسازی می‏شود. از آنجا که چنین مساله‏ای از نوع مسایل محاسباتی دشوار محسوب می‏شود و روش‏های دقیق برای حل این مسایل زمانبر است، دو الگوریتم فراابتکاری دوسطحی برای حل مساله توسعه داده می‏شود. همچنین به کمک نتایج حاصل از حل مسایل تصادفی در ابعاد مختلف، کارآیی الگوریتم‏های پیشنهادی در مقایسه با یکدیگر تحلیل می‌شوند.

کلیدواژه‌ها

عنوان مقاله [English]

Modeling and Solving the Hazmat Routing Problem under Network Interdiction with Information Asymmetry

نویسندگان [English]

  • Amir Saman Kheirkhah 1
  • Hami Reza Navidi 2
  • Masoume Messi Bidgoli 3
1 Department of Industrial Engineering, Bu-Ali Sina University, Hamadan, Iran
2 Department of Applied Mathematical, Shahed University, Tehran, Iran
3 Department of Industrial Engineering, Bu-Ali Sina University, Hamadan, Iran
چکیده [English]

In this paper, we consider the problem of hazardous material distribution where the distributer chooses the routes on the network, and a regulatory agency controls the behavior of the distributer to traverse the specified routes. In these circumstances, the distributer wants to select some routes to minimize the total distributing costs. Most of the time, this occurs due to selecting risky arcs in which more individuals are exposed to risk. To prevent this and increase the capability to deal with the risk of hazardous material transportation through roads, the regulatory agency obliges carriers to traverse through the most secure arcs, though imposing more distribution costs.
In reality, two decision makers may have different perceptions or asymmetric information about the network. To apply network interdiction models for real situations, we introduce the information asymmetry for these types of vehicle routing network interdiction problems and investigate its benefits and risks. For this purpose, a bi-level programming model is proposed and two bi-level meta-heuristics are suggested to solve this Stachelberg interdictor-evader game. The computational results showed that the developed co-evolutionary meta-heuristic algorithm could be more effective and more rational than the developed Bi-GA for these problems.

کلیدواژه‌ها [English]

  • Network Interdiction
  • hazardous transportation
  • vehicle routing problem
  • Information Asymmetry
  • Bi-level programming

مراجع

Akgün, İ., Tansel, B. Ç. and Wood, R. K. (2011) “The multi-terminal maximum-flow network-interdiction problem”, European Journal of Operational Research, Vol. 211, No.2, pp. 241-251.
-Aksen, D. and Aras, N. (2012) “Abilevel fixed charge location model for facilities under imminent attack”, Computer and operation research, Vol.39, No.7, pp.1364-1381.
-Apostolakis G. and Lemon, D. (2005) “A screening methodology for the identification and ranking of infrastructures vulnerability due to terrorism”, Risk Analysis, Vol. 25, No.1, pp.361–76.
-Bard, J. (1998) “Practical Bilevel Optimization: Algorithms and Applications”, Kluwer Academic Publishers, Norwell, MA.
-Bayrak, H. and Bailey, M. D. (2008) “Shortest path network interdiction with asymmetric information”, Networks, Vol.52, No.3, pp. 133-140.
-Bianco, L., Caramia, M., and Giordani, S. (2009) “A bilevel flow model for hazmat transportation network design”, Transportation Research Part C: Emerging Technologies, Vol.17, No.2, pp. 175-196.‏
-Brown, G., Carlyle, M., Salmeron, J. and Wood, K. (2007) “Defending critical infrastructure”, Interfaces, Vol. 36, No.6, pp.530–44.
-Claudio, M., Rocco, S., Ramirez-Marquez J. E., Daniel E. and Salazar, A. (2010) “Bi and tri-objective optimization in the deterministic network interdiction problem”, Reliability Engineering and System Safety, 95, pp. 887–896.
-Colson, P. M. B. and Savard, G. (2005) “Bilevel programming: a survey”, 4OR, vol.3, 87–107.
-Cormican, K. J., Morton, D. P. and Wood, R. K. (1998) “Stochastic network interdiction”, Operations Research, Vol.46, No.2, pp. 184-197.
-Dai, Y. and Poh, K. (2002, December) “Solving the network interdiction problem with genetic algorithms”, In Proceedings of the fourth Asia-Pacific conference on industrial engineering and management system, Taipei, pp. 18-20.
-Dempe, Stephan (2002) “Foundations of bi-level programming”, Kluwer Academic Publisher.
- Dimitrov, N. B., Gonzalez, M. A., Michalopoulos, D. P., Morton, D. P., Nehme, M. V., Popova, E. and Thoreson, G. G. (2008, November). Interdiction modeling for smuggled nuclear material”, In Proceedings of the 49th annual meeting of the Institute of Nuclear Materials Management.
-EKsioglu.B., Vural, A. V. and Reisman, A. (2009) “The vehicle routing problem: A taxonomic review”, Computers and Industrial Engineering, Vol.57, No.4, pp. 1472-1483.
-Erkut, E. and Gzara, F. (2008) “Solving the hazmat transport network design problem”, Computers and Operations Research, Vol.35, No.7, pp. 2234-2247.
-Garg, M. and Smith, C. (2008) “Models and algorithms for the design of survivable multi-commodity flow networks with general failure scenarios”, Omega; Vol.36, pp.1057–71.
-Granata, D., Steeger, G. and Rebennack. S. (2013) “Network interdiction via a Critical Disruption Path: Branch-and-Price algorithms”, Computers and Operations Research, Vol.40, No.11, pp. 2689-2702.
-Hodgson, M. J., Rosing, K. E. and Zhang, J. (1996) “Locating Vehicle Inspection Stations to Protect a Transportation Network”, Geographical Analysis, Vol.28, pp. 299–314.
-Israeli, E. and Wood, R. K. (2002) “Shortest path network interdiction”, Networks, Vol.40, No.2, pp. 97-111.
-Jiang, Y., Zhang, X., Rong, Y. and Zhang, Z. (2014) “A Multimodal Location and Routing Model for Hazardous Materials Transportation based on Multi-commodity Flow Model”, Procedia-Social and Behavioral Sciences, 138, pp. 791-799.‏
-Kara, B. Y. and Verter, V. (2004) '“Designing a road network for hazardous materials transportation”,  Transportation Science, Vol. 38, No.2, pp. 188–196.
-Kennedy, K. T., Deckro, R. F., Moore, J. T. and  Hopkinson, K. M. (2011) “Nodal interdiction”, Mathematical and Computer Modeling, Vol. 54, No.11, pp. 3116-3125.
-Kevin T. Kennedy, Richard F. Deckro, James T. Moore, Kenneth M. Hopkinson, (2011) “Nodal interdiction”, Mathematical and Computer Modeling, Vol. 54, pp. 3116–3125.
-Kheirkhah, A., Navidi, H. and Messi Bidgoli, M. (2015) “A bi-level network interdiction model for solving the hazmat routing problem”, International Journal of Production Research, (ahead-of-print), pp. 1-13, DOI:10.1080/00207543.2015.1084061.
-Laporte, G. (1992) “The vehicle routing problem: An overview of exact and approximate algorithms”, European journal of operational research, Vol. 59, pp. 345–358.
-Legillon, F., Liefooghe, A. and Talbi, E. (2012, June) “Cobra: A cooperative co-evolutionary algorithm for bi-level optimization”, In Evolutionary Computation (CEC), 2012 IEEE Congress  , pp. 1-8.
-Lim C. and Smith J. (2007) “Algorithms for discrete and continuous multi-commodity flow network interdiction problems”, IIE Transactions; 39, pp. 15–26. [Special issue on Homeland Security].
-McMasters, A. and Mustin, T. (1970) “Optimal interdiction of a supply network”, Naval Research Logistics Quarterly, Vol. 17, pp. 261–268.
-Morton, D., Pan, F. and Saeger, K. (2007) “Models for nuclear smuggling interdiction”, IIE Transactions on Operations Engineering, Vol. 38, pp.3–14.
-Oduguwa, V. and Roy, R. (2002) “Bi-level optimization using genetic algorithm”, IEEE International Conference on Artificial Intelligence Systems (ICAIS 2002), pp. 322–327.
-Önal, H. (1993) “A modified simplex approach for solving bi-level linear programming problems”, European Journal of Operational Research, Vol. 67, No. 1, pp. 126-135.
-Pan, F. (2005) “Stochastic network interdiction: models and methods”, Doctoral dissertation, The University of Texas at Austin.
-Prince, M., Geunes, J. and   Smith, C. (2013) “Procurement allocation planning with multiple suppliers under competition”, DOI: 10.1080/00207543.2013.807956.
-Ramirez-Marquez, J. E. and Rocco, C. (2009) “Stochastic network interdiction optimization via capacitated network reliability modeling and probabilistic solution discovery”, Reliability Engineering and System Safety, Vol. 94, pp. 913–921. 
-Rocco, C. and Ramirez-Marquez, JE. (2009) “Deterministic network interdiction optimization via an evolutionary approach”, Reliability Engineering and System Safety, Vol. 94, No. 2, pp. 568–76.
-Royset, J. O. and  Wood, R. K. (2007) “Solving the bi-objective maximum-flow network-interdiction problem”, INFORMS Journal on Computing, Vol. 19, No. 2, pp. 175-184.
-Salmeron, J.,  Wood, K. and Baldick, R. (2004), Analysis of electric grid security under terrorist thread”, IEEE Transaction on Power Systems, Vol. 19, No. 2, pp. 905-912.
-Smith, J. C., Lim, C. and Sudargho, F. (2007), “Survivable network design under optimal and heuristic interdiction scenarios”, J. Glob Optim, Vol.38, pp. 181–199.
-Steinrauf, R. L. (1991) “A Network Interdiction Model”,  M.S. Thesis, Naval Postgraduate School, Monterey, CA.
-Toth, P. and Vigo, D. (2001) An overview of vehicle routing problems”, In The vehicle routing problem, pp. 1-26. Society for Industrial and Applied Mathematics.
-Wang, H., Xiao, G. and Wei, Z. (2013) “Optimizing route for hazardous materials logistics based on hybrid ant colony algorithm”, Discrete dynamics in nature and society.‏
-Washburn, A. and Wood, R. K. (1995) “Two-person zero-sum games for network inter diction”, Operations Research, Vol. 43, No. 2, pp. 243-251.
-Washburn, A. and  Wood, K. (1995) “Two-person zero-sum games for network interdiction”, Operations Research, Vol. 43, No. 2, pp. 243-251.
-Wen, U. P. and Yang.Y. H. (1990) “Algorithms for solving the mixed integer two-level linear programming problem”, Computers and Operation Researches, Vol. 17, pp. 133–142.
-Wood, R. K. (1993) “Deterministic network interdiction”, Mathematical and Computer Modeling, Vol. 17, No. 2, pp. 1-18.
-Xie, Y., Lu, W., Wang, W. and Quadrifoglio, L. (2012) “A multimodal location and routing model for hazardous materials transportation”, Journal of hazardous materials, Vol. 227, pp. 135-141.
-Zenklusen, R. (2010) “Network flow interdiction on planar graphs”, Discrete Applied Mathematics, Vol. 158, No. 13, pp. 1441-1455.
 

فایل ها

سابقه مقاله

  • تاریخ دریافت: 24 مرداد 1394
  • تاریخ بازنگری: 14 آذر 1394
  • تاریخ پذیرش: 15 تیر 1395

هم رسانی

ارجاع به این مقاله

آمار