Exact Solution Of The Multi-allocation Facility Location Problem With Multiple Capacity Levels And Multiple Uncertainties

A two-stage facility location problem with multiple capacities and multiple uncer-tainties is studied in this paper.The decision-making of this problem is divided into two stages.In the first stage,the location and capacity of facilities are determined.In the second stage,the allocation decisions between demand points and facility points are made according to the actual situation,i.e.the various realization of model input parameters.Generally speaking,the location and capacity of facilities are closely related to each other as important strategic decisions.However,most literatures only consider the location of facilities but not the capacity.The model with multiple capacity levels proposed in this paper considers the location and capacity of facilities at the same time,which is closer to the actual situation.In addition,compared with some related modeling methods in the literature,the new model in this paper is more general in describing the uncertainties.As our study proves,it can deal with the following three kinds of uncertainties: supply-side uncertainty,demand-side uncertainty and in-between uncertainty.The facility location problem can be divided into stochastic facility location problem(probability known)and robust facility location problem(probability unknown)according to the decision rules adopted or whether the probability of each scenario is known or not,and it also can be divided into single assignment location problem and multiple assign-ment location problem according to whether the demand point can be satisfied by multiple facilities or not.For stochastic facility location problem with multi assignment and robust facility location problem with multi assignment,we design algorithms based on Benders Decomposition assisted with some enhancement strategies respectively in this paper.For each problem,we gives two ways to realize the algorithm: Classical Benders Decompo-sition method and Branch and Benders Cut method.Since the assignment subproblem of the problem we studied can be regarded as a transportation problem,we propose a method to effectively recover the original dual optimal solution from the transformed dual optimal solution by exploiting the effective solution of the transportation problem.To strengthen the initial Benders' s reformulation,we also propose a heuristic to generate the initial solutions and cuts.In the Classical Benders Decomposition method,we propose an ac-celeration strategy,i.e.elimination test,to reduce the size of variables.In the Branch and Benders Cut method,we use the mixed integer rounding(MIR)process to enhance the cut generated before.For the robust facility location problem with multiple assignment,in addition to the above strategies,we propose scenario ranking strategy to accelerate the solving process since it is enough to generate the cut with the worst-case scenario.Finally,a detailed numerical experiment based on the randomly generated data is carried out to analyze the efficiency of the proposed algorithms and those enhancement strategies.The results show that the two algorithms based on Benders Decomposition can greatly reduce the solution time on both the problems.In particular,for the stochastic location problem,the |K|-cut MIR enhanced Benders Branch and Cut method is very ef-fective and it only takes less than 1 % of the solution time in many instances compared with the CPLEX solver? for the robust location problem,the classical Benders Decompo-sition algorithm is very effective and it takes less than 1 ‰ solution time in many instances compared with the CPLEX solver.