Implementing Solution Algorithms for a Bi-level Optimization to the Emergency Warehouse Location-allocation Problem

Document Type : Research Paper

Authors

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

Abstract

The aim of this paper was to develop a binary bi-level optimization model for the emergency warehouse location-allocation problem in terms of national and regional levels. This type of modeling is suitable for countries where the design of the disaster emergency network is decentralized. The upper-level decision-maker makes a decision regarding the location and allocation of national warehouses through considering the location of regional warehouses and allocating them to the demand cities. Each regional warehouse can provide a service for the demand cities within a specified distance threshold, ultimately affecting the efficiency of the solution algorithms. The optimization model parameters were calculated in terms of the real data in Iran. To solve the small size problem, an exact method was proposed from the explicit complete enumeration. Due to the complexity of the model with the large size, two innovative hybrid genetic algorithms, namely HG-ES-1 and HG-ES-2, were suggested. The results obtained from solving the problems showed that the HG-ES-1 algorithm outperformed HG-ES-2. The findings further indicated the proper functioning of the solution approaches.

Keywords


Akbari Kaasgari, M., Imani, D. M., and Mahmoodjanloo, M. (2017). Optimizing a vendor managed inventory (VMI) supply chain for perishable products by considering discount: Two calibrated meta-heuristic algorithms. Computers & Industrial Engineering, Vol. 103, pp. 227-241.
Aksen, D., and Aras, N. (2013). A matheuristic for leader-follower games involving facility location-protection-interdiction decisions Metaheuristics for Bi-level Optimization (pp. 115-151): Springer.
Balcik, B., and Beamon, B. M. (2008). Facility location in humanitarian relief. International Journal of Logistics, Vol. 11(2), pp. 101-121.
Bard, J. (1998). Practical bilevel optimization: applications and algorithms Series: Nonconvex Optimization and Its Applications (Vol. 30, pp. 7-8): Springer.
Bard, J. F., and Moore, J. T. (1992). An algorithm for the discrete bilevel programming problem. Naval Research Logistics, Vol. 39(3), pp. 419-435.
Boonmee, C., Arimura, M., and Asada, T. (2017). Facility location optimization model for emergency humanitarian logistics. International Journal of Disaster Risk Reduction, Vol. 24, pp. 485-498.
Bozorgi-Amiri, A., Jabalameli, M., and Al-e-Hashem, S. M. (2013). A multi-objective robust stochastic programming model for disaster relief logistics under uncertainty. OR spectrum, Vol. 35(4), pp. 905-933.
Bozorgi-Amiri, A., and Khorsi, M. (2016). A dynamic multi-objective location–routing model for relief logistic planning under uncertainty on demand, travel time, and cost parameters. The International Journal of Advanced Manufacturing Technology, Vol. 85(5-8), pp. 1633-1648.
Bracken, J., and McGill, J. T. (1973). Mathematical programs with optimization problems in the constraints. Operations Research, Vol. 21(1), pp. 37-44.
Calvete, H. I., Galé, C., and Iranzo, J. A. (2013). An efficient evolutionary algorithm for the ring star problem. European Journal of Operational Research, Vol. 231(1), pp. 22-33.
Camacho-Vallejo, J.-F., Cordero-Franco, Á. E., and González-Ramírez, R. G. (2014). Solving the bilevel facility location problem under preferences by a Stackelberg-evolutionary algorithm. Mathematical Problems in Engineering, 2014.
Camacho-Vallejo, J.-F., González-Rodríguez, E., Almaguer, F.-J., and González-Ramírez, R. G. (2015). A bi-level optimization model for aid distribution after the occurrence of a disaster. Journal of Cleaner Production, Vol. 105, pp. 134-145.
Caramia, M., and Mari, R. (2016). A decomposition approach to solve a bilevel capacitated facility location problem with equity constraints. Optimization Letters, Vol. 10(5), pp. 997-1019.
Chen, Y.-x., Tadikamalla, P. R., Shang, J., and Song, Y. (2020). Supply allocation: bi-level programming and differential evolution algorithm for Natural Disaster Relief. Cluster Computing, Vol. 23(1), pp. 203-217.
CRED. (2018). Natural Disasters 2017. Retrieved from Brussels:
Dempe, S. (1996). Discrete bilevel optimization problems: Inst. für Wirtschaftsinformatik.
Dempe, S. (2002). Foundations of bilevel programming: Springer Science & Business Media.
Dempe, S., and Kue, F. M. (2017). Solving discrete linear bilevel optimization problems using the optimal value reformulation. Journal of Global Optimization, Vol. 68(2), pp. 255-277.
DeNegre, S. T., and Ralphs, T. K. (2009). A branch-and-cut algorithm for integer bilevel linear programs Operations research and cyber-infrastructure (pp. 65-78): Springer.
Fontaine, P., and Minner, S. (2014). Benders decomposition for discrete–continuous linear bilevel problems with application to traffic network design. Transportation Research Part B: Methodological, Vol. 70, pp. 163-172.
Gutjahr, W. J., and Dzubur, N. (2016). Bi-objective bilevel optimization of distribution center locations considering user equilibria. Transportation Research Part E: Logistics and Transportation Review, Vol. 85, pp. 1-22.
Haeri, A., Hosseini-Motlagh, S.-M., Samani, M. R. G., and Rezaei, M. (2020). A bi-level programming approach for improving relief logistics operations: A real case in Kermanshah earthquake. Computers & Industrial Engineering, Vol. 145, pp. 106532.
Hajiaghaei-Keshteli, M., and Aminnayeri, M. (2014). Solving the integrated scheduling of production and rail transportation problem by Keshtel algorithm. Applied Soft Computing, Vol. 25, pp. 184-203.
Hajiaghaei-Keshteli, M., Molla-Alizadeh-Zavardehi, S., and Tavakkoli-Moghaddam, R. (2010). Addressing a nonlinear fixed-charge transportation problem using a spanning tree-based genetic algorithm. Computers & Industrial Engineering, Vol. 59(2), pp. 259-271.
Hecheng, L., and Yuping, W. (2008). Exponential distribution-based genetic algorithm for solving mixed-integer bilevel programming problems. Journal of Systems Engineering Electronics, Vol. 19(6), pp. 1157-1164.
Huang, B., and Liu, N. (2004). Bilevel programming approach to optimizing a logistic distribution network with balancing requirements. Transportation Research Record, Vol. 1894(1), pp. 188-197.
Kheirkhah, A., Navidi, H., and Bidgoli, M. M. (2015). Dynamic facility layout problem: a new bilevel formulation and some metaheuristic solution methods. IEEE Transactions on Engineering Management, Vol. 62(3), pp. 396-410.
Kheirkhah, A., Navidi, H., and Bidgoli, M. M. (2016). An improved benders decomposition algorithm for an arc interdiction vehicle routing problem. IEEE Transactions on Engineering Management, Vol. 63(2), pp. 259-273.
Legillon, F., Liefooghe, A., and Talbi, E.-G. (2012). Cobra: A cooperative coevolutionary algorithm for bi-level optimization. Paper presented at the 2012 IEEE Congress on evolutionary computation.
Manopiniwes, W., Nagasawa, K., and Irohara, T. (2014). Humanitarian relief logistics with time restriction: thai flooding case study. Industrial Engineering & Management Systems, Vol. 13(4), pp. 398-407.
Miandoabchi, E., and Farahani, R. Z. (2011). Optimizing reserve capacity of urban road networks in a discrete network design problem. Advances in Engineering Software, Vol. 42(12), pp. 1041-1050.
Mokhtarinejad, M., Ahmadi, A., Karimi, B., and Rahmati, S. H. A. (2015). A novel learning based approach for a new integrated location-routing and scheduling problem within cross-docking considering direct shipment. Applied Soft Computing, Vol. 34, pp. 274-285.
Moore, J. T., and Bard, J. F. (1990). The mixed integer linear bilevel programming problem. Operations research, Vol. 38(5), pp. 911-921.
Paul, J. A., and Hariharan, G. (2012). Location-allocation planning of stockpiles for effective disaster mitigation. Annals of Operations Research, Vol. 196(1), pp. 469-490.
Paul, J. A., and MacDonald, L. (2016a). Location and capacity allocations decisions to mitigate the impacts of unexpected disasters. European Journal of Operational Research, Vol. 251(1), pp. 252-263.
Paul, J. A., and MacDonald, L. (2016b). Optimal location, capacity and timing of stockpiles for improved hurricane preparedness. International Journal of Production Economics, Vol. 174, pp. 11-28.
Safaei, A. S., Farsad, S., and Paydar, M. M. (2018). Robust bi-level optimization of relief logistics operations. Applied Mathematical Modelling, Vol. 56, pp. 359-380.
Saghehei, E., Memariani, A., and Bozorgi-Amiri, A. (2021). A Bi-level Programming Approach for Pre-positioning Emergency Warehouses. International Journal of Engineering, Vol. 34(1), pp. 128-139.
Saranwong, S., and Likasiri, C. (2016). Product distribution via a bi-level programming approach: Algorithms and a case study in municipal waste system. Expert Systems with Applications, Vol. 44, pp. 78-91.
Sinha, A., Malo, P., and Deb, K. (2017). A review on bilevel optimization: from classical to evolutionary approaches and applications. IEEE Transactions on Evolutionary Computation.
Sinha, A., Malo, P., Frantsev, A., and Deb, K. (2014). Finding optimal strategies in a multi-period multi-leader–follower Stackelberg game using an evolutionary algorithm. Computers Operations Research, Vol. 41, pp. 374-385.
Talbi, E.-G. (2013). A taxonomy of metaheuristics for bi-level optimization Metaheuristics for bi-level optimization (pp. 1-39): Springer.
Vicente, L., Savard, G., and Judice, J. (1996). Discrete linear bilevel programming problem. Journal of optimization theory applications, Vol. 89(3), pp. 597-614.
Xu, J., Wang, Z., Zhang, M., and Tu, Y. (2016). A new model for a 72-h post-earthquake emergency logistics location-routing problem under a random fuzzy environment. Transportation Letters, Vol. 8(5), pp. 270-285.
Yue, D., Gao, J., Zeng, B., and You, F. (2019). A projection-based reformulation and decomposition algorithm for global optimization of a class of mixed integer bilevel linear programs. Journal of Global Optimization Vol. 73(1), pp. 27-57.
Zandieh, M., Amiri, M., Vahdani, B., and Soltani, R. (2009). A robust parameter design for multi-response problems. Journal of computational and applied mathematics, Vol. 230(2), pp. 463-476.