Evaluating the Effectiveness of Integrated Benders Decomposition Algorithm and Epsilon Constraint Method for Multi-Objective Facility Location Problem under Demand Uncertainty

Document Type : Research Paper

Authors

1 Department of Mechanical and Manufacturing Engineering, Faculty of Engineering, University Putra Malaysia, Malaysia

2 Australian Energy Research Institute and the School of Electrical Engineering and Telecommunications, University of New South Wales, Sydney, NSW 2032, Australia

3 Department of Mathematics, Faculty of Science, 43400 UPM Serdang, Selangor Malaysia,

4 Department of Electrical and Computer Engineering, University of New Brunswick, P.O. Box 4400-UNB, Fredericton, NB, Canada E3B 5A3

Abstract

One of the most challenging issues in multi-objective problems is finding Pareto optimal points. This paper describes an algorithm based on Benders Decomposition Algorithm (BDA) which tries to find Pareto solutions. For this aim, a multi-objective facility location allocation model is proposed. In this case, an integrated BDA and epsilon constraint method are proposed and it is shown that how Pareto points in multi-objective facility location model can be found. Results are compared with the classic form of BDA and the weighted sum method for demand uncertainty and deterministic demands. To do this, Monte Carlo method with uniform function is used, then the stability of the proposed method towards demand uncertainty is shown. In order to evaluate the proposed algorithm, some performance metrics including the number of Pareto points, mean ideal points, and maximum spread are used, then the t-test analysis is done which points out that there is a significant difference between aforementioned algorithms.

Keywords

Main Subjects

References

Abdolmohammadi, H. R., & Kazemi, A. (2013). A benders decomposition approach for a combined heat and power economic dispatch. Energy Conversion and Management, 71, 21-31.
Aghaei, J., Amjady, N., & Shayanfar, H. A. (2011). Multi-objective electricity market clearing considering dynamic security by lexicographic optimization and augmented epsilon constraint method. Applied Soft Computing, 11(4), 3846-3858.
Aghezzaf, E. (2005). Capacity planning and warehouse location in supply chains with uncertain demands. Journal of the Operational Research Society, 56(4), 453-462.
Al-Agtash, S., & Yamin, H. (2004). Optimal supply curve bidding using Benders decomposition in competitive electricity markets. Electric Power Systems Research, 71(3), 245-255.
Arjmand, M., & Najafi, A. A. (2015). Solving a multi-mode bi-objective resource investment problem using meta-heuristic algorithms. Advanced Computational Techniques in Electromagnetics, 2015(1), 41-58.
Baghalian, A., Rezapour, S., & Farahani, R. Z. (2013). Robust supply chain network design with service level against disruptions and demand uncertainties: A real-life case. European Journal of Operational Research, 227(1), 199-215.
Behmanesh, R., & Rahimi, I. (2012). Using combination of optimized recurrent neural network with design of experiments and regression for control chart forecasting. Business Engineering and Industrial Applications Colloquium, 435-439.
Benders, J. F. (1962). Partitioning procedures for solving mixed-variables programming problems. Numerische Mathematik, 4(1), 238-252.
Boschetti, M., & Maniezzo, V. (2009). Benders decomposition, lagrangean relaxation and metaheuristic design. Journal of Heuristics, 15(3), 283-312.
Çakır, O. (2009). Benders decomposition applied to multi-commodity, multi-mode distribution planning. Expert Systems with Applications, 36(4), 8212-8217.
Chan, Y., Carter, W. B., & Burnes, M. D. (2001). A multiple-depot, multiple-vehicle, location-routing problem with stochastically processed demands. Computers & Operations Research, 28(8), 803-826.
Charnes, A., Cooper, W. W., & Rhodes, E. (1978). Measuring the efficiency of decision making units. European Journal of Operational Research, 2(6), 429-444.
Charwand, M., Ahmadi, A., Heidari, A. R., & Esmaeel Nezhad, A. (2014). Benders decomposition and normal boundary intersection method for multiobjective decision making framework for an electricity retailer in energy markets. IEEE Systems Journal, 9(4), 1475-1484.
Chu, Y., & You, F. (2013). Integration of production scheduling and dynamic optimization for multi-product CSTRs: Generalized Benders decomposition coupled with global mixed-integer fractional programming. Computers & Chemical Engineering, 58, 315-333.
Coello, C. A. C., Lamont, G. B., & Van Veldhuizen, D. A. (2007). Evolutionary algorithms for solving multi-objective problems. New York, NY: Springer.
Dabia, S., Talbi, E. G., Van Woensel, T., & De Kok, T. (2013). Approximating multi-objective scheduling problems. Computers & Operations Research, 40(5), 1165-1175.
Danesh Asgari, S., & Haeri, A. (2017). Selection of appropriate measures by integrating the balanced scorecard and three-stage data envelopment analysis approaches. Iranian Journal of Management Studies, 10(2), 527-550.
Das, I., & Dennis, J. E. (1998). Normal-boundary intersection: A new method for generating the Pareto surface in nonlinear multicriteria optimization problems. SIAM Journal on Optimization, 8(3), 631-657.
Daskin, M. S., Snyder, L. V., & Berger, R. T. (2005). Logistics systems: Design and optimization. In Facility location in Supply chain design (pp. 39-65). Heidelberg, Berlin: Springer.
de Camargo, R. S., Miranda, G. D., & Luna, H. (2008). Benders decomposition for the uncapacitated multiple allocation hub location problem. Computers & Operations Research, 35(4), 1047-1064.
de Sá, E. M., de Camargo, R. S., & de Miranda, G. (2013). An improved Benders decomposition algorithm for the tree of hubs location problem. European Journal of Operational Research, 226(2), 185-202.
Esmaili, M., Ebadi, F., Shayanfar, H. A., & Jadid, S. (2013). Congestion management in hybrid power markets using modified Benders decomposition. Applied Energy, 102, 1004-1012.
Fortz, B., & Poss, M. (2009). An improved benders decomposition applied to a multi-layer network design problem. Operations Research Letters, 37(5), 359-364.
Fowler, R. J., Paterson, M. S., & Tanimoto, S. L. (1981). Optimal packing and covering in the plane are NP-complete. Information Processing Letters, 12(3), 133-137.
Ghane-Kanafi, A., & Khorram, E. (2015). A new scalarization method for finding the efficient frontier in non-convex multi-objective problems. Applied Mathematical Modelling, 1-16. DOI: 10.1016/j.apm.2015.03.022.
Gonzalez, T. F. (1985). Clustering to minimize the maximum intercluster distance. Theoretical Computer Science, 38, 293-306.
Ismail-Yahaya, A., & Messac, A. (2002). Effective generation of the Pareto frontier using the normal constraint method. AIAA 40th Aerospace Sciences Meeting and Exhibit, 1-12.
Kagan, N., & Adams, R. (1993). A Benders' decomposition approach to the multi-objective distribution planning problem. International Journal of Electrical Power & Energy Systems, 15(5), 259-271.
Khalili-Damghani, K., & Amiri, M. (2012). Solving binary-state multi-objective reliability redundancy allocation series-parallel problem using efficient epsilon-constraint, multi-start partial bound enumeration algorithm, and DEA. Reliability Engineering & System Safety, 103, 35-44.
Klimberg, R. K., & Ratick, S. J. (2008). Modeling data envelopment analysis (DEA) efficient location/allocation decisions. Computers & Operations Research, 35(2), 457-474.
Laumanns, M., Thiele, L., & Zitzler, E. (2006). An efficient, adaptive parameter variation scheme for metaheuristics based on the epsilon-constraint method. European Journal of Operational Research, 169(3), 932-942.
Longinidis, P., & Georgiadis, M. C. (2011). Integration of financial statement analysis in the optimal design of supply chain networks under demand uncertainty. International Journal of Production Economics, 129(2), 262-276.
Megiddo, N., & Tamir, A. (1982). On the complexity of locating linear facilities in the plane. Operations Research Letters, 1(5), 194-197.
Melo, M. T., Nickel, S., & Saldanha-Da-Gama, F. (2009). Facility location and supply chain management–A review. European Journal of Operational Research, 196(2), 401-412.
Messac, A., Ismail-Yahaya, A., & Mattson, C. A. (2003). The normalized normal constraint method for generating the Pareto frontier. Structural and Multidisciplinary Optimization, 25(2), 86-98.
Mirghafoori, S. H., Ardakani, F. A., & Azizi, F. (2014). Developing a method for risk analysis in tile and ceramic industry using failure mode and effects analysis by data envelopment analysis. Iranian Journal of Management Studies, 7(2), 229.
 
Moheb-Alizadeh, H., Rasouli, S., & Tavakkoli-Moghaddam, R. (2011). The use of multi-criteria data envelopment analysis (MCDEA) for location–allocation problems in a fuzzy environment. Expert Systems with Applications, 38(5), 5687-5695.
Montemanni, R. (2006). A Benders decomposition approach for the robust spanning tree problem with interval data. European Journal of Operational Research, 174(3), 1479-1490.
Oliveira, F., Grossmann, I. E., & Hamacher, S. (2014). Accelerating Benders stochastic decomposition for the optimization under uncertainty of the petroleum product supply chain. Computers & Operations Research, 49, 47-58.
Osman, H., & Demirli, K. (2010). A bilinear goal programming model and a modified Benders decomposition algorithm for supply chain reconfiguration and supplier selection. International Journal of Production Economics, 124(1), 97-105.
Pishvaee, M., Razmi, J., & Torabi, S. (2014). An accelerated Benders decomposition algorithm for sustainable supply chain network design under uncertainty: A case study of medical needle and syringe supply chain. Transportation Research Part E: Logistics and Transportation Review, 67, 14-38.
Rahimi, I., Askari, M., Tang, S., Lee, L., Azfanizam Binti Ahmad, S., & Sharaf, A. M. (2016). Development model for supply chain network design by demand uncertainty and mode selection. International Journal of Applied Operational Research-An Open Access Journal, 6(1), 51-64.
Taguchi, G. (1986). Introduction to quality engineering: Designing quality into products and processes. Quality and Reliability Engineering International, 4, 198-199.
Tang, S. H., Rahimi, I., & Karimi, H. (2016). Objectives, products and demand requirements in integrated supply chain network design: A review. International Journal of Industrial and Systems Engineering, 23(2), 181-203.
Torabi, M., & Mahlooji, H. (2017). An integrated simulation-DEA approach to multi-criteria ranking of scenarios for execution of operations in a construction project. Iranian Journal of Management Studies, 9(4), 801-827.
Üster, H., & Agrahari, H. (2011). A Benders decomposition approach for a 
distribution network design problem with consolidation and capacity considerations. Operations Research Letters, 39(2), 138-143.
Wang, F., Lai, X., & Shi, N. (2011). A multi-objective optimization for green supply chain network design. Decision Support Systems, 51(2), 262-269.
Yang, Y., & Lee, J. M. (2012). A tighter cut generation strategy for acceleration of Benders decomposition. Computers & Chemical Engineering, 44, 84-93.
Zitzler, E. (1999). Evolutionary algorithms for multiobjective optimization: Methods and applications (Doctoral dissertaion). ETH Zurich, Switzerland.
Interdisciplinary Journal of Management Studies (Formerly known as Iranian Journal of Management Studies)
Volume 10, Issue 3
July 2017
Pages 551-576

Files

Share

How to cite

Statistics