A Bi-level Programming Approach for Pre-positioning Emergency Warehouses

Document Type : Original Article


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

2 Department of Electrical and Computer Engineering, Kharazmi University, Tehran, Iran

3 School of Industrial Engineering, College of Engineering, University of Tehran, Tehran, Iran


In some countries, regional authorities may attempt to rebalance the allocation of national facilities in benefit of their own region which, in turn, may cause disturbances in the central government’s decision-making proces. Regarding the hierarchical nature of these types of decisions, classical optimization models are not effective in decision-making and the use of multi-level programming can increase the efficiency of planning. Our paper aims to address the issue of a bi-level programming model to conduct the location analysis of emergency warehouses. A three-echelon relief supply chain is considered in which the relief network involves national and regional warehouses and demand cities. The upper-level model decides on the location of national warehouses, allocating them to regional warehouses. The lower-level model determines the location of regional warehouses and allocates them to demand points. The structure of both levels is based on the median location-allocation problem. Three solution approaches are presented based on the full enumeration and two types of nested evolutionarymethods (genetic and heuristic local search algorithms). For the model to be used in Iran, the efficiency of algorithms is analyzed for two sizes of problems. The obtained results show the proper functioning of the solution approaches.  


2.     Gharib, Z., Bozorgi-Amiri, A., Tavakkoli-Moghaddam, R. and Najafi, E., "A cluster-based emergency vehicle routing problem in disaster with reliability", Scientia Iranica,Transaction E, Industrial Engineering,  Vol. 25, No. 4, (2018), 2312-2330, DOI: 10.24200/SCI.2017.4450.
3.     Akkihal, A.R., "Inventory pre-positioning for humanitarian operations", Massachusetts Institute of Technology, Doctoral dissertation,  (2006),
4.     Verma, A. and Gaukler, G.M., "Pre-positioning disaster response facilities at safe locations: An evaluation of deterministic and stochastic modeling approaches", Computers & Operations Research,  Vol. 62, (2015), 197-209, DOI: 10.1016/j.cor.2014.10.006.
5.     Rawls, C.G. and Turnquist, M.A., "Pre-positioning and dynamic delivery planning for short-term response following a natural disaster", Socio-Economic Planning Sciences,  Vol. 46, No. 1, (2012), 46-54, DOI: 10.1016/j.seps.2011.10.002.
6.     Caunhye, A.M., Nie, X. and Pokharel, S., "Optimization models in emergency logistics: A literature review", Socio-Economic Planning Sciences,  Vol. 46, No. 1, (2012), 4-13, DOI: 10.1016/j.seps.2011.04.004.
7.     Anaya-Arenas, A.M., Renaud, J. and Ruiz, A., "Relief distribution networks: A systematic review", Annals of Operations Research,  Vol. 223, No. 1, (2014), 53-79, DOI: 10.1007/s10479-014-1581-y.
8.     Hoyos, M.C., Morales, R.S. and Akhavan-Tabatabaei, R., "Or models with stochastic components in disaster operations management: A literature survey", Computers & Industrial Engineering,  Vol. 82, (2015), 183-197, DOI: 10.1016/j.cie.2014.11.025.
9.     Balcik, B., Bozkir, C.D.C. and Kundakcioglu, O.E., "A literature review on inventory management in humanitarian supply chains", Surveys in Operations Research management Science,  Vol. 21, No. 2, (2016), 101-116, DOI: 10.1016/j.sorms.2016.10.002.
10.   Rawls, C.G. and Turnquist, M.A., "Pre-positioning of emergency supplies for disaster response", Transportation research part B: Methodological,  Vol. 44, No. 4, (2010), 521-534, DOI: 10.1016/j.trb.2009.08.003.
11.   Rawls, C.G. and Turnquist, M.A., "Pre-positioning planning for emergency response with service quality constraints", OR Spectrum,  Vol. 33, No. 3, (2011), 481-498, DOI: 10.1007/s00291-011-0248-1.
12.   Bozorgi-Amiri, A., Jabalameli, M.S., Alinaghian, M. and Heydari, M., "A modified particle swarm optimization for disaster relief logistics under uncertain environment", The International Journal of Advanced Manufacturing Technology,  Vol. 60, No. 1-4, (2012), 357-371, DOI: 10.1007/s00170-011-3596-8.
13.   Rezaei-Malek, M., Tavakkoli-Moghaddam, R., Zahiri, B. and Bozorgi-Amiri, A., "An interactive approach for designing a robust disaster relief logistics network with perishable commodities", Computers & Industrial Engineering,  Vol. 94, (2016), 201-215, DOI: 10.1016/j.cie.2016.01.014.
14.   Mohammadi, R., Ghomi, S.F. and Jolai, F., "Prepositioning emergency earthquake response supplies: A new multi-objective particle swarm optimization algorithm", Applied Mathematical Modelling,  Vol. 40, No. 9, (2016), 5183-5199, DOI: 10.1016/j.apm.2015.10.022.
15.   Javadian, N., Modares, S. and Bozorgi-Amiri, A., "A bi-objective stochastic optimization model for humanitarian relief chain by using evolutionary algorithms", International Journal of Engineering, Transaction A: Basics,  Vol. 30, No. 10, (2017), 1526-1537.
16.   Aslan, E. and Çelik, M., "Pre-positioning of relief items under road/facility vulnerability with concurrent restoration and relief transportation", IISE Transactions,  Vol. 51, No. 8, (2019), 847-868, DOI: 10.1080/24725854.2018.1540900.
17.   Simaan, M. and Cruz Jr, J.B., "On the stackelberg strategy in nonzero-sum games", Journal of Optimization Theory and Applications,  Vol. 11, No. 5, (1973), 533-555.
18.   Sakawa, M. and Nishizaki, I., "Cooperative and noncooperative multi-level programming, Springer Science & Business Media,  Vol. 48,  (2009).
19.   Bracken, J. and McGill, J.T., "Mathematical programs with optimization problems in the constraints", Operations Research,  Vol. 21, No. 1, (1973), 37-44.
20.   Kongsomsaksakul, S., Yang, C. and Chen, A., "Shelter location-allocation model for flood evacuation planning", Journal of the Eastern Asia Society for Transportation Studies,  Vol. 6, (2005), 4237-4252, DOI: 10.11175/easts.6.4237.
21.   Hua-li, S., Xun-qing, W. and Yao-feng, X., A bi-level programming model for a multi-facility location-routing problem in urban emergency system, in Engineering education and management. 2012, Springer.75-80.
22.   Li, A.C., Nozick, L., Xu, N. and Davidson, R., "Shelter location and transportation planning under hurricane conditions", Transportation Research Part E: Logistics and Transportation Review,  Vol. 48, No. 4, (2012), 715-729, DOI: 10.1016/j.tre.2011.12.004.
23.   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.
24.   Gutjahr, W.J. and Dzubur, N., "Bi-objective bilevel optimization of distribution center locations considering user equilibria", Transportation Research Part E: Logistics and Transportation Review,  Vol. 85, (2016), 1-22, DOI: 10.1016/j.tre.2015.11.001.
25.   Xu, J., Wang, Z., Zhang, M. and Tu, Y., "A new model for a 72-h post-earthquake emergency logistics location-routing problem under a random fuzzy environment", Transportation Letters,  Vol. 8, No. 5, (2016), 270-285, DOI: 10.1080/19427867.2015.1126064.
26.   Safaei, A.S., Farsad, S. and Paydar, M.M., "Robust bi-level optimization of relief logistics operations", Applied Mathematical Modelling,  Vol. 56, (2018), 359-380, DOI: 10.1016/j.apm.2017.12.003.
27.   Ng, M., Park, J. and Waller, S.T., "A hybrid bilevel model for the optimal shelter assignment in emergency evacuations", Computer‐Aided Civil and Infrastructure Engineering,  Vol. 25, No. 8, (2010), 547-556, DOI: 10.1111/j.1467-8667.2010.00669.x.
28.   Apivatanagul, P., Davidson, R.A. and Nozick, L.K., "Bi-level optimization for risk-based regional hurricane evacuation planning", Natural hazards,  Vol. 60, No. 2, (2012), 567-588, DOI: 10.1007/s11069-011-0029-9.
29.   Chen, Y.-x., Tadikamalla, P.R., Shang, J. and Song, Y., "Supply allocation: Bi-level programming and differential evolution algorithm for natural disaster relief", Cluster Computing,  Vol., (2017), 1-15, DOI: 10.1007/s10586-017-1366-6.
30.   Haeri, A., Motlagh, S.-M.H., Samani, M.R.G. and Rezaei, M.S., "A bi-level programming approach for improving relief logistics operations: A real case in kermanshah earthquake", Computers & Industrial Engineering,  (2020), 106532, DOI: 10.1016/j.cie.2020.106532.
31.   Sinha, A., Malo, P. and Deb, K., "A review on bilevel optimization: From classical to evolutionary approaches and applications", IEEE Transactions on Evolutionary Computation,  Vol. 22, No. 2, (2017), 276-295, DOI: 10.1109/TEVC.2017.2712906.
32.   Hansen, P., Jaumard, B., Savard, G. and Computing, S., "New branch-and-bound rules for linear bilevel programming", SIAM Journal on Scientific,  Vol. 13, No. 5, (1992), 1194-1217.
33.   Talbi, E.-G., A taxonomy of metaheuristics for bi-level optimization, in Metaheuristics for bi-level optimization. 2013, Springer.1-39.
34.   Shepherd, S. and Sumalee, A., "A genetic algorithm based approach to optimal toll level and location problems", Networks and Spatial Economics,  Vol. 4, No. 2, (2004), 161-179, DOI: 10.1023/B:NETS.0000027771.13826.3a.
35.   Wang, G.-m., Wang, X.-j., Wan, Z.-p. and Jia, S.-h., "An adaptive genetic algorithm for solving bilevel linear programming problem", Applied Mathematics and Mechanics,  Vol. 28, No. 12, (2007), 1605-1612, DOI: 10.1007/s10483-007-1207-1.
36.   Zuo, Z., Kanamori, R., Miwa, T. and Morikawa, T., "A study of both optimal locations and toll levels road pricing using genetic algorithm", Journal of the Eastern Asia Society for Transportation Studies,  Vol. 8, (2010), 145-156, DOI: 10.11175/easts.8.145.
37.   Parvasi, S.P., Mahmoodjanloo, M. and Setak, M., "A bi-level school bus routing problem with bus stops selection and possibility of demand outsourcing", Applied Soft Computing
 Vol. 61, No., (2017), 222-238, DOI: 10.1016/j.asoc.2017.08.018.
38.   Huang, B. and Liu, N., "Bilevel programming approach to optimizing a logistic distribution network with balancing requirements", Transportation Research Record,  Vol. 1894, No. 1, (2004), 188-197, DOI: 10.3141/1894-20.
39.          Saranwong, S. and Likasiri, C., "Product distribution via a bi-level programming approach: Algorithms and a case study in municipal waste system", Expert Systems with Applications,  Vol. 44, (2016), 78-91, DOI: 10.1016/j.eswa.2015.08.053.