Fractional location problems

In this paper we analyze some variants of the classical uncapacitated facility location problem with a ratio as an objective function. Using basic concepts and results of fractional programming, we identify a class of one-level fractional location problems which can be solved in polynomial time in terms of the size of the problem. We also consider the fractional two-echelon location problem, which is a special case of the general two-level fractional location problem. For this two-level fractional location problem we identify cases for which its solution involves decomposing the problem into several one-level fractional location problems.     

The generalized maximal covering location problem

We consider a generalization of the maximal cover location problem which allows for partial coverage of customers, with the degree of coverage being a non-increasing step function of the distance to the nearest facility. Potential application areas for this generalized model to locating retail facilities are discussed.We show that, in general, our problem is equivalent to the uncapacitated facility location problem. We develop several integer programming formulations that capitalize on the special structure of our problem. Extensive computational analysis of the solvability of our model under a variety of conditions is presented.     

Solution approaches for facility location of medical supplies for large-scale emergencies

In this paper, we propose models and solution approaches for determining the facility locations of medical supplies in response to large-scale emergencies. We address the demand uncertainty and medical supply insufficiency by providing each demand point with services from a multiple quantity of facilities that are located at different quality levels (distances). The problem is formulated as a maximal covering problem with multiple facility quantity-of-coverage and quality-of-coverage requirements. Three heuristics are developed to solve the location problem: a genetic algorithm heuristic, a locate–allocate heuristic, and a Lagrangean relaxation heuristic. We evaluate the performance of the model and the heuristics by using illustrative emergency examples. We show that the model provides an effective method to address uncertainties with little added cost in demand point coverage. We also show that the heuristics are able to generate good facility location solutions in an efficient manner. Moreover, we give suggestions on how to select the most appropriate heuristic to solve different location problem instances.     

基于设施选址问题的费用分配问题的近似算法

许多有着重要理论和应用价值的最优化问题在算法复杂性上都是NP-hard的,其解决方法之一是近似算法。论文研究了与设施选址问题密切相关的费用分配问题,并利用原始与对偶线性规划的思想和无容量设施选址问题的一个1.52-近似算法[1]给出了该问题的一个更好的近似算法。     

Variable neighborhood search for location routing

In this paper we propose various neighborhood search heuristics (VNS) for solving the location routing problem with multiple capacitated depots and one uncapacitated vehicle per depot. The objective is to find depot locations and to design least cost routes for vehicles. We integrate a variable neighborhood descent as the local search in the general variable neighborhood heuristic framework to solve this problem. We propose five neighborhood structures which are either of routing or location type and use them in both shaking and local search steps. The proposed three VNS methods are tested on benchmark instances and successfully compared with other two state-of-the-art heuristics.     

Approximation algorithms for hierarchical location problems

We formulate and (approximately) solve hierarchical versions of two prototypical problems in discrete location theory, namely, the metric uncapacitated k-median and facility location problems. Our work yields new insights into hierarchical clustering, a widely used technique in data analysis. For example, we show that every metric space admits a hierarchical clustering that is within a constant factor of optimal at every level of granularity with respect to the average (squared) distance objective. A key building block of our hierarchical facility location algorithm is a constant-factor approximation algorithm for an “incremental” variant of the facility location problem; the latter algorithm may be of independent interest.     

A Branch and Bound Algorithm for An Uncapacitated Facility Location Problem with a Side Constraint

In this paper, a branch and bound algorithm for solving an uncapacitated facility location problem (UFLP) with an aggregate capacity constraint is presented. The problem arises as a subproblem when Lagrangean relaxation of the capacity constraints is used to solve capacitated facility location problems. The algorithm is an extension of a procedure used by Christofides and Beasley (A tree search algorithm for the p-median problem. European Journal of Operational Research , Vol. 10, 1982, pp. 196–204) to solve p -median problems and is based on Lagrangean relaxation in combination with subgradient optimization for lower bounding, simple Lagrangean heuristics to produce feasible solutions, and penalties to reduce the problem size. For node selection, a jump-backtracking rule is proposed, and alternative rules for choosing the branching variable are discussed. Computational experience is reported.     

Genetic algorithm with iterated local search for solving a location-routing problem

This paper deals with a location routing problem with multiple capacitated depots and one uncapacitated vehicle per depot. We seek for new methods to make location and routing decisions simultaneously and efficiently. For that purpose, we describe a genetic algorithm (GA) combined with an iterative local search (ILS). The main idea behind our hybridization is to improve the solutions generated by the GA using a ILS to intensify the search space. Numerical experiments show that our hybrid algorithm improves, for all instances, the best known solutions previously obtained by the tabu search heuristic.     

Dynamic location problem under uncertainty with a regret‐based measure of robustness

In this paper, we present a dynamic uncapacitated facility location problem that considers uncertainty in fixed and assignment costs as well as in the sets of potential facility locations and possible customers. Uncertainty is represented via a set of scenarios. Our aim is to minimize the expected total cost, explicitly considering regret. Regret is understood as a measure, for each scenario, of the loss incurred for not choosing that scenario's optimal solution if that scenario indeed occurred. We guarantee that the regret for each scenario is always upper bounded. We present a mixed integer programming model for the problem and we propose a solution approach based on Lagrangean relaxation integrating a local neighborhood search and a subgradient algorithm to update Lagrangean multipliers. The problem and the solutions obtained are first analyzed through the use of illustrative examples. Computational results over sets of randomly generated test problems are also provided.     

Lagrangean relaxation and decomposition in an uncapacitated 2-hierarchal location-allocation problem

We consider an uncapacitated 2-hierarchal location-allocation problem where p₁ level 1 facilities and p₂ level 2 facilities are to be located among n(?p₁ + p₂) potential locations so as to minimize the total weighted travel distance to the facilities when θ, (0 ? θ ? 1) fraction of the demand from a level 1 facility is referred to a level 2 facility. At most one facility may be located at any location. In this model, a level 2 facility provides services in addition to services provided by a level 1 facility.The problem is formulated as a mathematical programming problem, relaxed and solved by a subgradient optimization procedure. The proposed procedure is illustrated with an example.     

Heuristics for a continuous multi-facility location problem with demand regions

We consider a continuous multi-facility location allocation problem where the demanding entities are regions in the plane instead of points. The problem can be stated as follows: given m (closed, convex) polygonal demand regions in the plane, find the locations of q facilities and allocate each region to exactly one facility so as to minimize a weighted sum of squares of the maximum Euclidean distances between the demand regions and the facilities they are assigned to.We propose mathematical programming formulations of the single and multiple facility versions of the problem considered. The single facility location problem is formulated as a second order cone programming (SOCP) problem, and hence is solvable in polynomial time. The multiple facility location problem is NP-hard in general and can be formulated as a mixed integer SOCP problem. This formulation is weak and does not even solve medium-size instances. To solve larger instances of the problem we propose three heuristics. When all the demand regions are rectangular regions with their sides parallel to the standard coordinate axes, a faster special heuristic is developed. We compare our heuristics in terms of both solution quality and computational time.     

The Weber problem in congested regions with entry and exit points

The Weber problem is about finding a facility location on a plane such that the total weighted distance to a set of given demand points is minimized. The facility location and access routes to the facility can be restricted if the Weber problem contains congested regions, some arbitrary shaped polygonal areas on the plane, where location of a facility is forbidden and traveling is allowed at an additional fixed cost. Traveling through congested regions may also be limited to certain entry and exit points (or gates). It is shown that the restricted Weber problem is non-convex and nonlinear under Euclidean distance metric which justifies using heuristic approaches. We develop an evolutionary algorithm modified with variable neighborhood search to solve the problem. The algorithm is applied on test instances derived from the literature and the computational results are presented.     

Efficient primal-dual heuristic for a dynamic location problem

In this paper the dynamic location problem with opening, closure and reopening of facilities is formulated and an efficient primal-dual heuristic that computes both upper and lower limits to its optimal solution is described. The problem here studied considers the possibility of reconfiguring any location more than once over the planning horizon. This problem is NP-hard (the simple plant location problem is a special case of the problem studied). A primal-dual heuristic based on the work of Erlenkotter [A dual-based procedure for uncapacitated facility location. Operations Research 1978;26:992–1009] and Van Roy and Erlenkotter [A dual-based procedure for dynamic facility location. Management Science 1982;28:1091–105] was developed and tested over a set of randomly generated test problems. The results obtained are quite good, both in terms of the quality of lower and upper bounds calculated as in terms of the computational time spent by the heuristic. A branch-and-bound procedure that enables to optimize the problem is also described and tested over the same set of randomly generated problems.     

Evaluating the impact of AND/OR search on 0-1 integer linear programming

AND/OR search spaces accommodate advanced algorithmic schemes for graphical models which can exploit the structure of the model. We extend and evaluate the depth-first and best-first AND/OR search algorithms to solving 0-1 Integer Linear Programs (0-1 ILP) within this framework. We also include a class of dynamic variable ordering heuristics while exploring an AND/OR search tree for 0-1 ILPs. We demonstrate the effectiveness of these search algorithms on a variety of benchmarks, including real-world combinatorial auctions, random uncapacitated warehouse location problems and MAX-SAT instances.     

Solving a Location Problem of a Stackelberg Firm Competing with Cournot-Nash Firms

We study a discrete facility location problem on a network, where the locating firm acts as the leader and other competitors as the followers in a Stackelberg-Cournot-Nash game. To maximize expected profits the locating firm must solve a mixed-integer problem with equilibrium constraints. Finding an optimal solution is hard for large problems, and full-enumeration approaches have been proposed in the literature for similar problem instances. We present a heuristic solution procedure based on simulated annealing. Computational results are reported.     

Risk management in uncapacitated facility location models with random demands

In this paper we consider a location-optimization problem where the classical uncapacitated facility location model is recast in a stochastic environment with several risk factors that make demand at each customer site probabilistic and correlated with demands at the other customer sites. Our primary contribution is to introduce a new solution methodology that adopts the mean–variance approach, borrowed from the finance literature, to optimize the “Value-at-Risk” (VaR) measure in a location problem. Specifically, the objective of locating the facilities is to maximize the lower limit of future earnings based on a stated confidence level. We derive a nonlinear integer program whose solution gives the optimal locations for the p facilities under the new objective. We design a branch-and-bound algorithm that utilizes a second-order cone program (SOCP) solver as a subroutine. We also provide computational results that show excellent solution times on small to medium sized problems.     

New simple and efficient heuristics for the uncapacitated single allocation hub location problem

Hub-and-spoke networks are widely studied in the area of location theory. They arise in several contexts, including passenger airlines, postal and parcel delivery, and computer and telecommunication networks. Hub location problems usually involve three simultaneous decisions to be made: the optimal number of hub nodes, their locations and the allocation of the non-hub nodes to the hubs. In the uncapacitated single allocation hub location problem (USAHLP) hub nodes have no capacity constraints and non-hub nodes must be assigned to only one hub. In this paper, we propose three variants of a simple and efficient multi-start tabu search heuristic as well as a two-stage integrated tabu search heuristic to solve this problem. With multi-start heuristics, several different initial solutions are constructed and then improved by tabu search, while in the two-stage integrated heuristic tabu search is applied to improve both the locational and allocational part of the problem. Computational experiments using typical benchmark problems (Civil Aeronautics Board (CAB) and Australian Post (AP) data sets) as well as new and modified instances show that our approaches consistently return the optimal or best-known results in very short CPU times, thus allowing the possibility of efficiently solving larger instances of the USAHLP than those found in the literature. We also report the integer optimal solutions for all 80 CAB data set instances and the 12 AP instances up to 100 nodes, as well as for the corresponding new generated AP instances with reduced fixed costs.     

An LP rounding algorithm for approximating uncapacitated facility location problem with penalties

In this paper, we consider an interesting variant of the facility location problem called uncapacitated facility location problem with penalties (UFLWP, for short) in which each client can be either assigned to some opened facility or rejected by paying a penalty. Existing approaches [M. Charikar, S. Khuller, D. Mount, G. Narasimhan, Algorithms for facility location problems with outliers, in: Proc. Symposium on Discrete Algorithms, 2001, p. 642] and [K. Jain, M. Mahdian, E. Markakis, A. Saberi, V. Vazirani, Greedy facility location algorithms analyzed using dual fitting with factor-revealing LP, J. ACM 50 (2003) 795] for this variant of facility location problem are all based on primal-dual method. In this paper, we present an efficient linear programming (LP) rounding based approach to show that LP rounding techniques are equally capable of solving this variant of facility location problem. Our algorithm uses a two-phase filtering technique (generalized from Lin and Vitter's [?-approximation with minimum packing constraint violation, in: Proc. 24th Annual ACM Symp. on Theory of Computing, 1992, p. 771]) to identify those to-be-rejected clients and open facilities for the remaining ones. Our approach achieves an approximation ratio of 2+2/e (≈2.736) which is worse than the best approximation ratio of 2 achieved by the much more sophisticated dual fitting technique [K. Jain, M. Mahdian, E. Markakis, A. Saberi, V. Vazirani, Greedy facility location algorithms analyzed using dual fitting with factor-revealing LP, J. ACM 50 (2003) 795], but better than the approximation ratio of 3 achieved by the primal-dual method [M. Charikar, S. Khuller, D. Mount, G. Narasimhan, Algorithms for facility location problems with outliers, in: Proc. Symposium on Discrete Algorithms, 2001, p. 642]. Our algorithm is simple, natural, and can be easily integrated into existing LP rounding based algorithms for facility location problem to deal with outliers.     

Parallel island based Memetic Algorithm with Lin–Kernighan local search for a real-life Two-Echelon Heterogeneous Vehicle Routing Problem based on Brazilian wholesale companies

This paper deals with a Two-Echelon Fixed Fleet Heterogeneous Vehicle Routing Problem (2E-HVRP) faced by Brazilian wholesale companies. Vehicle routing problems with more than one phase are known as Multi-Echelon VRP and consider situations in which freight is moved through some intermediate facilities (e.g., cross-docks or distribution centers) before reaching its destination. The first phase of the problem dealt here is to choose a first-level vehicle, from an heterogeneous set, that will leave a depot and reach an intermediate uncapacitated facility (satellite) to serve a set of second-level vehicles. After that, it is necessary to define routes for smaller vehicles, also from an heterogeneous set, that will visit a set of customers departing from and returning to a satellite. The solution proposed here is an efficient island based memetic algorithm with a local search procedure based on Lin–Kernighan heuristic (IBMA-LK). In order to attest the algorithm’s efficiency, first it was tested in single echelon HVRP benchmark instances. After that the instances were adapted for two-echelon context and used for 2E-HVRP validation and, finally, it was tested on 2E-HVRP instances created using real world normalized data. Localsolver tool was also executed for comparison purposes. Promising results (which corroborate results obtained on the real problem) and future works are presented and discussed.