A Benders-Decomposition and Meta-Heuristic Algorithm for a Bi- Objective Stochastic Reliable Capacitated Facility Location Problem Not Dealing with Benders Feasibility-Cut Stage

Subject Areas : Executive Management

AmirHossien  ZahediAnaraki ¹ (Department of engineering,University of Applied Science andTechnology,Tehran, Iran)
Gholamreza  Esmaeilian ² (Department of Industrial Engineering, University of PayameNoor,Tehran,Iran)

Received: 2018-11-05 Accepted : 2021-01-12 Published : 2021-06-01

Keywords: reliability, Benders decomposition, Stochastic programming, Capacitated facility location,

Abstract :

This paper addresses a bi-objective two-stage stochastic mixed-integer linear programming model for a stochastic reliable capacitated facility location in which the optimum numbers, locations and as well as shipment quantity of the product between the network nodes for all scenarios should be determined. Unlike most of previous relevant works, multiple levels of capacities available to the manufacturers in different scenarios are permitted in this study. The proposed objectives of the model include: the minimization of expected sum of installation, production, transportation under uncertainty of parameters, such as transportation and production and disruption of facilities, as well as minimizing expected standard deviation of network costs for whole scenarios. Since one of the most important reasons for researchers' reluctance to apply Benders-decomposition algorithm in facility-location concept is the time-consuming nature of its feasibility-cut stage, one of the most outstanding innovation in this paper is to add a strengthening redundant constraint to the proposed model in order to eliminate the mechanism related to feasibility cuts in master problem. to the best of our knowledge, it is the first time that this technique, not being involved in keeping master-problem feasibility, is used to solve a reliable capacitated facility location problem. In this approach, in terms of time-consuming the Benders algorithm is able to powerfully compete with metaheuristic algorithms, but with an exact solution. To prove advantage of this algorithm satisfying both ultimate solution optimality and appropriate running time compared to metaheuristic algorithms at the same time, one metaheuristic algorithm, namely Imperialist Competitive Algorithm (ICA), is presented. Usefulness and practicality of the proposed model and solution method demonstrated through a case example in different class with variable size.

References:

Atashpaz-Gargari, E. and Lucas, C. (2007) ‘Imperialist competitive algorithm: an algorithm for optimization inspired by imperialistic competition’, in Evolutionary computation, 2007. CEC 2007. IEEE Congress on. IEEE, pp. 4661–4667.

Azaron, A. et al. (2008) ‘A multi-objective stochastic programming approach for supply chain design considering risk’, International Journal of Production Economics, 116(1), pp. 129–138.

Balas, E. (1965) ‘An additive algorithm for solving linear programs with zero-one variables’, Operations Research, 13(4), pp. 517–546.

Ball, M. O. and Lin, F. L. (1993) ‘A reliability model applied to emergency service vehicle location’, Operations research, 41(1), pp. 18–36.

Benders, J. F. (1962) ‘Partitioning procedures for solving mixed-variables programming problems’, Numerische mathematik, 4(1), pp. 238–252.

Beresnev, V. and Melnikov, A. (2018) ‘Exact method for the capacitated competitive facility location problem’, Computers & Operations Research, 95, pp. 73–82.

Cardona-Valdés, Y., Álvarez, A. and Ozdemir, D. (2011) ‘A bi-objective supply chain design problem with uncertainty’, Transportation Research Part C: Emerging Technologies, 19(5), pp. 821–832.

Chen, C.-H. and Ting, C.-J. (2008) ‘Combining lagrangian heuristic and ant colony system to solve the single source capacitated facility location problem’, Transportation research part E: logistics and transportation review, 44(6), pp. 1099–1122.

Correia, I. and Melo, T. (2016) ‘Multi-period capacitated facility location under delayed demand satisfaction’, European Journal of Operational Research, 255(3), pp. 729–746.

Costa, A. M. (2005) ‘A survey on benders decomposition applied to fixed-charge network design problems’, Computers & operations research, 32(6), pp. 1429–1450.

Gade, D. and Pohl, E. A. (2009) ‘Sample average approximation applied to the capacitated-facilities location problem with unreliable facilities’, Proceedings of the Institution of Mechanical Engineers, Part O: Journal of Risk and Reliability, 223(4), pp. 259–269.

Geoffrion, A. and Bride, R. M. (1978) ‘Lagrangean relaxation applied to capacitated facility location problems’, AIIE transactions, 10(1), pp. 40–47.

Harks, T. and von Falkenhausen, P. (2014) ‘Optimal cost sharing for capacitated facility location games’, European Journal of Operational Research, 239(1), pp. 187–198.

Laporte, G., Louveaux, F. V. and van Hamme, L. (1994) ‘Exact solution to a location problem with stochastic demands’, Transportation Science, 28(2), pp. 95–103.

Li, X. and Ouyang, Y. (2010) ‘A continuum approximation approach to reliable facility location design under correlated probabilistic disruptions’, Transportation research part B: methodological, 44(4), pp. 535–548.

Lim, M. et al. (2010) ‘A facility reliability problem: Formulation, properties, and algorithm’, Naval Research Logistics (NRL), 57(1), pp. 58–70.

Magnanti, T. L. and Wong, R. T. (1981) ‘Accelerating Benders decomposition: Algorithmic enhancement and model selection criteria’, Operations research, 29(3), pp. 464–484.

Melo, M. T., Nickel, S. and Saldanha-Da-Gama, F. (2009) ‘Facility location and supply chain management–A review’, European journal of operational research, 196(2), pp. 401–412.

Razmi, J., Zahedi-Anaraki, A. and Zakerinia, M. (2013) ‘A bi-objective stochastic optimization model for reliable warehouse network redesign’, Mathematical and Computer Modelling, 58(11–12), pp. 1804–1813.

Revelle, C. S., Eiselt, H. A. and Daskin, M. S. (2008) ‘A bibliography for some fundamental problem categories in discrete location science’, European Journal of Operational Research, 184(3), pp. 817–848.

Rodrigues, F. C. and Xavier, E. C. (2017) ‘Non-cooperative capacitated facility location games’, Information Processing Letters, 117, pp. 45–53.

Snyder, L. V. (2006) ‘Facility location under uncertainty: a review’, IIE transactions, 38(7), pp. 547–564.

Snyder, L. V. and Daskin, M. S. (2005) ‘Reliability models for facility location: the expected failure cost case’, Transportation Science, 39(3), pp. 400–416.

Snyder, L. V. and Daskin, M. S. (2007) ‘Models for reliable supply chain network design’, in Critical Infrastructure. Springer, pp. 257–289.

Sodagari, N. and Sadeghi, A. (2015) ‘A Benders Decomposition Method to Solve an Integrated Logistics Network Designing Problem with Multiple Capacities’, Journal of Optimization in Industrial Engineering, 8(18), pp. 79–93.

Üster, H. and Agrahari, H. (2011) ‘A Benders decomposition approach for a distribution network design problem with consolidation and capacity considerations’, Operations Research Letters, 39(2), pp. 138–143.

Wentges, P. (1996) ‘Accelerating Benders’ decomposition for the capacitated facility location problem’, Mathematical Methods of Operations Research, 44(2), pp. 267–290.