Joint Optimization of a Bilevel Logistics Network and an Arc Interdiction Location-routing Problem

Document Type: Original Article

Authors

Department of Industrial Engineering, South Tehran Branch, Islamic Azad University, Tehran, Iran

Abstract

There is a high interest in optimization of transportation and logistics networks due to its high impact on the economic performance of supply chain networks. This paper presents a bilevel mixed-integer programming model as well as a solution method to manage distribution process in a logistic network, where two decision makers, called distributor and interdictor, make efforts to achieve their contradictory targets. This problem, known as arc interdiction location-routing problem (AI-LRP), is in fact a new, extended version of the classical LRP. The distributor strives to deliver goods to customers with minimal risk and cost, while the interdictor, by contrast, endeavors to disrupt products flow through a few critical arcs. AI-LRP has wide applications in reality, including distribution of particular goods like money, precious metals, hazardous materials, and prisoners that may need security measures. The interplay between two decision makers is formulated as a bilevel model. To solve the model, a novel genetic algorithm (NGA) is devised in which the density ordered heuristic of the knapsack problem is applied to generate an initial population of solutions. Computational results illustrate that NGA outperforms a commercial solver in terms of computational time and quality of solutions.

Keywords


  1. Aliakbarian, N., Dehghanian, F. and Salari, M., "A bi-level programming model for protection of hierarchical facilities under imminent attacks", Computers & Operations Research,  Vol. 64, (2015), 210-224. DOI: 10.1016/j.cor.2015.05.016
  2. Yaghlane, A.B., Azaiez, M.N. and Mrad, M., "System survivability in the context of interdiction networks", Reliability Engineering & System Safety,  Vol. 185, (2019), 362-371. DOI: 10.1016/j.ress.2019.01.005
  3. Noh, J., Kim, J.S. and Sarkar, B., "Two-echelon supply chain coordination with advertising-driven demand under stackelberg game policy", European Journal of Industrial Engineering,  Vol. 13, No. 2, (2019), 213-244. DOI: 10.1504/EJIE.2019.098516
  4. Fulkerson, D.R. and Harding, G.C., "Maximizing the minimum source-sink path subject to a budget constraint", Mathematical Programming,  Vol. 13, No. 1, (1977), 116-118. DOI: 10.1007/BF01584329
  5. Altner, D.S., Ergun, Ö. and Uhan, N.A., "The maximum flow network interdiction problem: Valid inequalities, integrality gaps, and approximability", Operations Research Letters,  Vol. 38, No. 1, (2010), 33-38. DOI: 10.1016/j.orl.2009.09.013
  6. Wollmer, R., "Removing arcs from a network", Operations Research,  Vol. 12, No. 6, (1964), 934-940. DOI: 10.1287/opre.12.6.934
  7. Bidgoli, M.M. and Kheirkhah, A., "An arc interdiction vehicle routing problem with information asymmetry", Computers & Industrial Engineering,  Vol. 115, (2018), 520-531. DOI: 10.1016/j.cie.2017.11.019
  8. Sadeghi, S., Seifi, A. and Azizi, E., "Trilevel shortest path network interdiction with partial fortification", Computers & Industrial Engineering,  Vol. 106, (2017), 400-411. DOI: 10.1016/j.cie.2017.02.006
  9. Ghasemi, P., Khalili-Damghani, K., Hafezalkotob, A. and Raissi, S., "Stochastic optimization model for distribution and evacuation planning (a case study of tehran earthquake)", Socio-Economic Planning Sciences,  Vol. 71, (2020), 100745. DOI: 10.1016/j.seps.2019.100745
  10. Farham, M.S., Süral, H. and Iyigun, C., "A column generation approach for the location-routing problem with time windows", Computers & Operations Research,  Vol. 90, (2018), 249-263. DOI: 10.1016/j.cor.2017.09.010
  11. Ghasemi, P., Khalili-Damghani, K., Hafezolkotob, A. and Raissi, S., "A decentralized supply chain planning model: A case study of hardboard industry", The International Journal of Advanced Manufacturing Technology,  Vol. 93, No. 9-12, (2017), 3813-3836. DOI: 10.1007/s00170-017-0802-3
  12. Rezaei, N., Ebrahimnejad, S., Moosavi, A. and Nikfarjam, A., "A green vehicle routing problem with time windows considering the heterogeneous fleet of vehicles: Two metaheuristic algorithms", European Journal of Industrial Engineering,  Vol. 13, No. 4, (2019), 507-535. DOI: 10.1504/EJIE.2019.100919
  13. Salhi, S. and Rand, G.K., "The effect of ignoring routes when locating depots", European Journal of Operational Research,  Vol. 39, No. 2, (1989), 150-156. DOI: 10.1016/0377-2217(89)90188-4
  14. Khalili-Damghani, K. and Ghasemi, P., "Uncertain centralized/decentralized production-distribution planning problem in multi-product supply chains: Fuzzy mathematical optimization approaches", Industrial Engineering & Management Systems,  Vol. 15, No. 2, (2016), 156-172. DOI: 10.7232/iems.2016.15.2.156
  15. Safaeian, M., Fathollahi-Fard, A.M., Tian, G., Li, Z. and Ke, H., "A multi-objective supplier selection and order allocation through incremental discount in a fuzzy environment", Journal of Intelligent & Fuzzy Systems,  Vol. 37, No. 1, (2019), 1435-1455. DOI: 10.3233/JIFS-182843
  16. Fathollahi-Fard, A.M., Hajiaghaei-Keshteli, M., Tian, G. and Li, Z., "An adaptive lagrangian relaxation-based algorithm for a coordinated water supply and wastewater collection network design problem", Information Sciences,  Vol. 512, (2020), 1335-1359. DOI: 10.1504/IJKL.2018.092055
  17. Lan, H., Li, R., Liu, Z. and Wang, R., "Study on the inventory control of deteriorating items under vmi model based on bi-level programming", Expert Systems with Applications,  Vol. 38, No. 8, (2011), 9287-9295. DOI: 10.1016/j.eswa.2011.01.034
  18. Sun, H., Gao, Z. and Wu, J., "A bi-level programming model and solution algorithm for the location of logistics distribution centers", Applied Mathematical Modelling,  Vol. 32, No. 4, (2008), 610-616. DOI: 10.1016/j.apm.2007.02.007
  19. Bayrak, H. and Bailey, M.D., "Shortest path network interdiction with asymmetric information", Networks: An International Journal,  Vol. 52, No. 3, (2008), 133-140. DOI: 10.1002/net.20236
  20. Babaeinesami, A. and Ghasemi, P., "Ranking of hospitals: A new approach comparing organizational learning criteria", International Journal of Healthcare Management,  (2020), 1-9. DOI: 10.1080/20479700.2020.1728923
  21. Church, R.L., Scaparra, M.P. and Middleton, R.S., "Identifying critical infrastructure: The median and covering facility interdiction problems", Annals of the Association of American Geographers,  Vol. 94, No. 3, (2004), 491-502. DOI: 10.1111/j.1467-8306.2004.00410.x
  22. McMasters, A.W. and Mustin, T.M., "Optimal interdiction of a supply network", Naval Research Logistics Quarterly,  Vol. 17, No. 3, (1970), 261-268. DOI: 10.1002/nav.3800170302
  23. Ghare, P., Montgomery, D.C. and Turner, W., "Optimal interdiction policy for a flow network", Naval Research Logistics Quarterly,  Vol. 18, No. 1, (1971), 37-45. DOI: 10.1002/nav.3800180103
  24. Akgün, İ., Tansel, B.Ç. and Wood, R.K., "The multi-terminal maximum-flow network-interdiction problem", European Journal of Operational Research,  Vol. 211, No. 2, (2011), 241-251. DOI: 10.1016/j.ejor.2010.12.011
  25. Wood, R.K., "Network interdiction problem", Mathematical and Computer Modeling,  Vol. 17, No. 2, (1993), 1-18. DOI: 10.1016/0895-7177(93)90236-R
  26. Ramirez-Marquez, J.E., "Bi and tri-objective optimization in the deterministic network interdiction problem", Reliability Engineering & System Safety,  Vol. 95, No. 8, (2010), 887-896. DOI: 10.1016/j.ress.2010.03.008
  27. .Zhang, J., Zhuang, J. and Behlendorf, B., "Stochastic shortest path. network interdiction with a case study of arizona–mexico border", Reliability Engineering & System Safety,  Vol. 179, (2018), 62-73DOI: 10.1016/j.ress.2017.10.026
  28. Rad, M.A. and Kakhki, H.T., "Maximum dynamic network flow interdiction problem: New formulation and solution procedures", Computers & Industrial Engineering,  Vol. 65, No. 4, (2013), 531-536. DOI: 10.1016/j.cie.2013.04.014
  29. Zenklusen, R., "Network flow interdiction on planar graphs", Discrete Applied Mathematics,  Vol. 158, No. 13, (2010), 1441-1455. DOI: 10.1016/j.dam.2010.04.008
  30.  Altner, D.S., Ergun, Ö. and Uhan, N.A., "The maximum flow network interdiction problem: Valid inequalities, integrality gaps, and approximability", Operations Research Letters,  Vol. 38, No. 1, (2010), 33-38. DOI: 10.1016/j.orl.2009.09.013
  31. Washburn, A. and Wood, K., "Two-person zero-sum games for network interdiction", Operations Research,  Vol. 43, No. 2, (1995), 243-251. DOI: 10.1287/opre.43.2.243
  32. Banusiewicz, J., “DoD policy official explains terror war strategy: American Forces Press Service, Washington, DC”, 2004.
  33. Garcia, M., “Drugs and security in a post-9/11world: coordinating the counter narcotics mission at DHS”, Washington, DC: US Immigration and Customs Enforcement Department of Homeland Security, 2004
  34. Brown, G., Carlyle, M., Salmerón, J. and Wood, K., "Defending critical infrastructure", Interfaces,  Vol. 36, No. 6, (2006), 530-544. DOI: 10.1287/inte.1060.0252
  35. Apostolakis, G.E. and Lemon, D.M., "A screening methodology for the identification and ranking of infrastructure vulnerabilities due to terrorism", Risk Analysis: An International Journal,  Vol. 25, No. 2, (2005), 361-376. DOI: 10.1111/j.1539-6924.2005.00595.x
  36. Aksen, D. and Aras, N., "A bilevel fixed charge location model for facilities under imminent attack", Computers & Operations Research,  Vol. 39, No. 7, (2012), 1364-1381. DOI: 10.1016/j.cor.2011.08.006
  37. Morton, D.P., Pan, F. and Saeger, K.J., "Models for nuclear smuggling interdiction", IIE Transactions,  Vol. 39, No. 1, (2007), 3-14. DOI: 10.1080/07408170500488956
  38. Pan, F., Charlton, W.S., and Morton, D.P., “A stochastic program for interdicting smuggled nuclear material”, Operations Research/ Computer Science Interfaces Series, Vol. 22, (2003), 1-19. DOI: 10.1007/0-306-48109-X_1 
  39. Witt, K.M., "Development of a probabilistic network model to simulate the smuggling of nuclear materials", University of Texas at Austin,  2003.
  40. Pan, F., “Stochastic network interdiction: Models and methods. Doctoral dissertation, The University of Texas at Austin”, 2005. URL: http://hdl.handle.net/2152/1692
  41. Assimakopoulos, N., "A network interdiction model for hospital infection control", Computers in Biology and Medicine,  Vol. 17, No. 6, (1987), 413-422. DOI: 10.1016/0010-4825(87)90060-6
  42. Lim, C. and Smith, J.C., "Algorithms for discrete and continuous multicommodity flow network interdiction problems", IIE Transactions,  Vol. 39, No. 1, (2007), 15-26. DOI: 10.1080/07408170600729192
  43. Garg, M. and Smith, J.C., "Models and algorithms for the design of survivable multicommodity flow networks with general failure scenarios", Omega,  Vol. 36, No. 6, (2008), 1057-1071. DOI: 10.1016/j.omega.2006.05.006
  44. Luss, H. and Wong, R.T., "Survivable telecommunications network design under different types of failures", IEEE Transactions on Systems, Man, and Cybernetics-Part A: Systems and Humans,  Vol. 34, No. 4, (2004), 521-530. DOI: 10.1109/TSMCA.2004.826825
  45. Clarke, L.W. and Anandalingam, G., "An integrated system for designing minimum cost survivable telecommunications networks", IEEE Transactions on Systems, Man, and Cybernetics-Part A: Systems and Humans,  Vol. 26, No. 6, (1996), 856-862. DOI: 10.1109/3468.541346
  46. Salmeron, J., Wood, K. and Baldick, R., "Analysis of electric grid security under terrorist threat", IEEE Transactions on Power Systems,  Vol. 19, No. 2, (2004), 905-912. DOI: 10.1109/TPWRS.2004.825888
  47. Anandalingam, G. and Apprey, V., "Multi-level programming and conflict resolution", European Journal of Operational Research,  Vol. 51, No. 2, (1991), 233-247. DOI: 10.1016/0377-2217(91)90253-R
  48. Jiang, J. and Liu, X., "Multi-objective stackelberg game model for water supply networks against interdictions with incomplete information", European Journal of Operational Research,  Vol. 266, No. 3, (2018), 920-933. DOI: 10.1016/j.ejor.2017.10.034
  49. Granata, D., Steeger, G. and Rebennack, S., "Network interdiction via a critical disruption path: Branch-and-price algorithms", Computers & Operations Research,  Vol. 40, No. 11, (2013), 2689-2702. DOI: 10.1016/j.cor.2013.04.016
  50. Ramirez-Marquez, J.E., "A bi-objective approach for shortest-path network interdiction", Computers & Industrial Engineering,  Vol. 59, No. 2, (2010), 232-240. DOI: 10.1016/j.cie.2010.04.004
  51. Fathollahi-Fard, A.M., Hajiaghaei-Keshteli, M. and Mirjalili, S., "Hybrid optimizers to solve a tri-level programming model for a tire closed-loop supply chain network design problem", Applied Soft Computing,  Vol. 70, (2018), 701-722. DOI: 10.1016/j.asoc.2018.06.021
  52. Hajiaghaei-Keshteli, M. and Fathollahi-Fard, A.M., "A set of efficient heuristics and metaheuristics to solve a two-stage stochastic bi-level decision-making model for the distribution network problem", Computers & Industrial Engineering,  Vol. 123, (2018), 378-395. DOI: 10.1016/j.cie.2018.07.009
  53. Jabarzare, Z., Zolfagharinia, H. and Najafi, M., "Dynamic interdiction networks with applications in illicit supply chains", Omega,  Vol. 96, (2020), 102069. DOI: 10.1016/j.omega.2019.05.005
  54. Mehranfar, N., Hajiaghaei-Keshteli, M. and Fathollahi-Fard, A.M., "A novel hybrid whale optimization algorithm to solve a production-distribution network problem considering carbon emissions", International Journal of Engineering, Transactions C: Aspects, Vol. 32, No. 12, (2019), 1781-1789. DOI: 10.5829/IJE.2019.32.12C.11
  55. Fathollahi-Fard, A., Hajiaghaei-Keshteli, M. and Tavakkoli-Moghaddam, R., "A lagrangian relaxation-based algorithm to solve a home health care routing problem", International Journal of Engineering, Transactions A: Basics,  Vol. 31, No. 10, (2018), 1734-1740. DOI: 10.5829/ije.2018.31.10a.16
  56. Ben-Ayed, O., Boyce, D.E. and Blair III, C.E., "A general bilevel linear programming formulation of the network design problem", Transportation Research Part B: Methodological,  Vol. 22, No. 4, (1988), 311-318. DOI: 10.1016/0191-2615(88)90006-9
  57. Sun, H., Gao, Z. and Wu, J., "A bi-level programming model and solution algorithm for the location of logistics distribution centers", Applied Mathematical Modelling,  Vol. 32, No. 4, (2008), 610-616. DOI: 10.1016/j.apm.2007.02.007
  58. Aksen, D., Akca, S.Ş. and Aras, N., "A bilevel partial interdiction problem with capacitated facilities and demand outsourcing", Computers & Operations Research, Vol. 41, No., (2014), 346-358. DOI: 10.1016/j.cor.2012.08.013
  59. Bard, J.F. and Falk, J.E., "An explicit solution to the multi-level programming problem", Computers & Operations Research,  Vol. 9, No. 1, (1982), 77-100. DOI: 10.1016/0305-0548(82)90007-7
  60. Bialas, W.F. and Karwan, M.H., "Two-level linear programming", Management Science,  Vol. 30, No. 8, (1984), 1004-1020. DOI: 10.1287/mnsc.30.8.1004
  61. Bard, J.F., "Convex two-level optimization", Mathematical Programming,  Vol. 40, No. 1-3, (1988), 15-27. DOI: 10.1007/BF01580720
  62. White, D.J. and Anandalingam, G., "A penalty function approach for solving bi-level linear programs", Journal of Global Optimization,  Vol. 3, No. 4, (1993), 397-419. DOI: 10.1007/BF01096412
  63. Vicente, L., Savard, G. and Júdice, J., "Descent approaches for quadratic bilevel programming", Journal of Optimization Theory and Applications,  Vol. 81, No. 2, (1994), 379-399. DOI: 10.1007/BF02191670
  64. Israeli, E. and Wood, R.K., "Shortest‐path network interdiction", Networks: An International Journal,  Vol. 40, No. 2, (2002), 97-111. DOI: 10.1002/net.10039
  65. Van Quy, N., "A global optimization method for solving convex quadratic bilevel programming problems", Journal of Global Optimization,  Vol. 26, No. 2, (2003), 199-219. DOI: 10.1023/A:1023047900333
  66. Arroyo, J.M. and Galiana, F.D., "On the solution of the bilevel programming formulation of the terrorist threat problem", IEEE Transactions on Power Systems,  Vol. 20, No. 2, (2005), 789-797. DOI: 10.1109/TPWRS.2005.846198
  67. Kuo, R. and Han, Y., "A hybrid of genetic algorithm and particle swarm optimization for solving bi-level linear programming problem–a case study on supply chain model", Applied Mathematical Modelling,  Vol. 35, No. 8, (2011), 3905-3917. DOI: 10.1016/j.apm.2011.02.008
  68. Ming, W., Bo, S. and Wenzhou, J., "A bi-level programming model for uncertain regional bus scheduling problems", Journal of Transportation Systems Engineering and Information Technology,  Vol. 13, No. 4, (2013), 106-112.
  69. Angulo, E., Castillo, E., García-Ródenas, R. and Sánchez-Vizcaíno, J., "A continuous bi-level model for the expansion of highway networks", Computers & Operations Research,  Vol. 41, (2014), 262-276. DOI: 10.1016/j.cor.2013.02.022
  70. Szeto, W.Y. and Jiang, Y., "Transit route and frequency design: Bi-level modeling and hybrid artificial bee colony algorithm approach", Transportation Research Part B: Methodological,  Vol. 67, (2014), 235-263. DOI: 10.1016/j.trb.2014.05.008 
  71. Camacho-Vallejo, J.-F., González-Rodríguez, E., Almaguer, F.-J. and González-Ramírez, R.G., "A bi-level optimization model for aid distribution after the occurrence of a disaster", Journal of Cleaner Production,  Vol. 105, (2015), 134-145. DOI: 10.1016/j.jclepro.2014.09.069
  72. Nandi, A.K., Medal, H.R. and Vadlamani, S., "Interdicting attack graphs to protect organizations from cyber attacks: A bi-level defender–attacker model", Computers & Operations Research,  Vol. 75, (2016), 118-131. DOI: 10.1016/j.cor.2016.05.005
  73. Saranwong, S. and Likasiri, C., "Bi-level programming model for solving distribution center problem: A case study in northern thailand’s sugarcane management", Computers & Industrial Engineering,  Vol. 103, (2017), 26-39. DOI: 10.1016/j.cie.2016.10.031
  74. Zhu, Y., Mao, B., Bai, Y. and Chen, S., "A bi-level model for single-line rail timetable design with consideration of demand and capacity", Transportation Research Part C: Emerging Technologies,  Vol. 85, (2017), 211-233. DOI: 10.1016/j.trc.2017.09.002
  75. Chalmardi, M.K. and Camacho-Vallejo, J.-F., "A bi-level programming model for sustainable supply chain network design that considers incentives for using cleaner technologies", Journal of Cleaner Production,  Vol. 213, (2019), 1035-1050. DOI: 10.1016/j.jclepro.2018.12.197
  76. Fazayeli, S., Eydi, A. and Kamalabadi, I.N., "Location-routing problem in multimodal transportation network with time windows and fuzzy demands: Presenting a two-part genetic algorithm", Computers & Industrial Engineering,  Vol. 119, (2018), 233-246. DOI: 10.1016/j.cie.2018.03.041
  77. Hiassat, A., Diabat, A. and Rahwan, I., "A genetic algorithm approach for location-inventory-routing problem with perishable products", Journal of Manufacturing Systems, Vol. 42, (2017), 93-103. DOI: 10.1016/j.jmsy.2016.10.004
  78. Holland, J., "Adaptation in natural and artificial systems: An introductory analysis with application to biology", Control and Artificial Intelligence, 1975.
  79. Ghasemi, P., Khalili-Damghani, K., Hafezalkotob, A. and Raissi, S., "Uncertain multi-objective multi-commodity multi-period multi-vehicle location-allocation model for earthquake evacuation planning", Applied Mathematics and Computation,  Vol. 350, (2019), 105-132. DOI: 10.1016/j.amc.2018.12.061
  80. Fathollahi-Fard, A.M., Hajiaghaei-Keshteli, M. and Tavakkoli-Moghaddam, R., "Red deer algorithm (RDA): A new nature-inspired meta-heuristic", Soft Computing, (2020), DOI: 10.1007/s00500-020-04812-z
  81. Fathollahi-Fard, A.M., Hajiaghaei-Keshteli, M. and Tavakkoli-Moghaddam, R., "The social engineering optimizer (SEO)", Engineering Applications of Artificial Intelligence,  Vol. 72, (2018), 267-293. DOI: 10.1016/j.engappai.2018.04.009