Locating service facilities with concave variable cost

We consider a nonlinear version of the Uncapacitated Facility Location Problem (UFLP). The totalcost in consideration consists of a fixed cost to open facilities, a travel cost in proportion to thedistance between demand and the assigned facility, and an operational cost at each open facility,which is assumed to be a concave nondecreasing function of the demand served. Thus we call theproblem Uncapacitated Facility Location Problem with Concave Operating Cost (UFLPCOC).Specifically, we assume that service facilities are to be located and customers seek service fromthe closest open facility. As a consequence, an explicit constraint is needed in the model to imposeclosest assignment. An exact solution approach, which is called the Search and Cut algorithm, ispresented. This approach is mainly based on sequentially improving the lower and upper boundsfor UFLPCOC. Lower bounds are obtained by solving a UFLP model with extra linear constraints.To find an upper bound, we present a heuristic that is based on a neighborhood search procedurestarting from the solution to a mixed integer programming model. An approximation solutionapproach is also suggested that explores linear approximation to transform the model into a mixedinteger linear programming problem. Computational results are presented. It is found that the coststructure has a significant effect on intractability of the problem and that the Search and Cutalgorithm dominates the approximation solution approach in general.

Locating service facilities with concave variable cost Articles