Single facility location and relocation problem with time dependent weights and discrete planning horizon

In this paper a single facility location problem with multiple relocation opportunities is investigated. The weight associated with each demand point is a known function of time. We consider either rectilinear, or squared Euclidean, or Euclidean distances. Relocations can take place at pre-determined times. The objective function is to minimize the total location and relocation costs. An algorithm which finds the optimal locations, relocation times and the total cost, for all three types of distance measurements and various weight functions, is developed. Locations are found using constant weights, and relocations times are the solution to a Dynamic Programming or Binary Integer Programming (BIP) model. The time horizon can be finite or infinite.     

Decision/forecast horizon for a single facility dynamic location/relocation problem

Procedures to solve finite horizon dynamic location/relocation problems have been reported in the literature by many authors. This paper provides several decision/forecast horizon results for a single facility dynamic location/relocation problem; these results are helpful in finding optimal initial decisions for the infinite horizon problem by using information only for a finite horizon.     

The single facility location problem with average-distances

This paper considers a location problem in ℝ ⁿ , where the demand is not necessarily concentrated at points but it is distributed in hypercubes following a Uniform probability distribution. The goal is to locate a service facility minimizing the weighted sum of average distances (measured with ℓ _p norms) to these demand hypercubes. In order to do that, we present an iterative scheme that provides a sequence converging to an optimal solution of the problem for p∈[1,2]. For the planar case, analytical expressions of this iterative procedure are obtained for p=2 and p=1, where two different approaches are proposed. The paper ends with a computational analysis of the proposed methodology, comparing its efficiency with a standard minimizer.      

The incorporation of fixed cost and multilevel capacities into the discrete and continuous single source capacitated facility location problem

In this study we investigate the single source location problem with the presence of several possible capacities and the opening (fixed) cost of a facility that is depended on the capacity used and the area where the facility is located. Mathematical models of the problem for both the discrete and the continuous cases using the Rectilinear and Euclidean distances are produced. Our aim is to find the optimal number of open facilities, their corresponding locations, and their respective capacities alongside the assignment of the customers to the open facilities in order to minimise the total fixed and transportation costs. For relatively large problems, two solution methods are proposed namely an iterative matheuristic approach and VNS-based matheuristic technique. Dataset from the literature is adapted to assess our proposed methods. To assess the performance of the proposed solution methods, the exact method is first applied to small size instances where optimal solutions can be identified or lower and upper bounds can be recorded. Results obtained by the proposed solution methods are also reported for the larger instances.

     

On solving a large-scale problem on facility location and customer assignment with interaction costs along a time horizon

A 0-1 quadratic programming model is presented for solving the strategic problem of timing the location of facilities and the assignment of customers to facilities in a multi-period setting. It is assumed that all parameters are known and, on the other hand, the quadratic character of the objective function is due to considering the interaction cost incurred by the joint assignment of customers belonging to different categories to a facility at a period. The plain use of a state-of-the-art MILP engine with capabilities for dealing with quadratic terms does not give any advantage over the matheuristic algorithm proposed in this work. In fact, the MILP engine was frequently running out of memory before reaching optimality for the equivalent mixed 0-1 linear formulation, being its best lower bound at that time instant too far from the incumbent solution for the large-sized instances which we have worked with. As an alternative, a fix-and-relax algorithm is presented. A deep computational comparison between MILP alternatives is performed, such that fix-and-relax provides a solution value very close to (and, frequently, a better than) the one provided by the MILP engine. The time required by fix-and-relax is very affordable, being frequently two times smaller than the time required by the MILP engine.     

A single facility stochastic location problem undera-distance

In this paper we consider a stochastic facility location model in which the weights of demand points are not deterministic but independent random variables, and the distance between the facility and each demand point isA-distance. Our objective is to find a solution which minimizes the total cost criterion subject to a chance constraint on cost restriction. We show a solution method which solves the problem in polynomial order computational time. Finally the case of rectilinear distance, which is used in many facility location models, is discussed.     

Ambulance location and relocation problems with time-dependent travel times

EMERGENCY SERVICE PROVIDERS ARE FACING THE FOLLOWING PROBLEM: how and where to locate vehicles in order to cover potential future demand effectively. Ambulances are supposed to be located at designated locations such that in case of an emergency the patients can be reached in a time-efficient manner. A patient is said to be covered by a vehicle if (s)he can be reached by an ambulance within a predefined time limit. Due to variations in speed and the resulting travel times it is not sufficient to solve the static ambulance location problem once using fixed average travel times, as the coverage areas themselves change throughout the day. Hence we developed a multi-period version, taking into account time-varying coverage areas, where we allow vehicles to be repositioned in order to maintain a certain coverage standard throughout the planning horizon. We have formulated a mixed integer program for the problem at hand, which tries to optimize coverage at various points in time simultaneously. The problem is solved metaheuristically using variable neighborhood search. We show that it is essential to consider time-dependent variations in travel times and coverage respectively. When ignoring them the resulting objective will be overestimated by more than 24%. By taking into account these variations explicitly the solution on average can be improved by more than 10%.     

A decomposition approach for facility location and relocation problem with uncertain number of future facilities

In this paper, we discuss two challenges of long term facility location problem that occur simultaneously; future demand change and uncertain number of future facilities. We introduce a mathematical model that minimizes the initial and expected future weighted travel distance of customers. Our model allows relocation for the future instances by closing some of the facilities that were located initially and opening new ones, without exceeding a given budget. We present an integer programming formulation of the problem and develop a decomposition algorithm that can produce near optimal solutions in a fast manner. We compare the performance of our mathematical model against another method adapted from the literature and perform sensitivity analysis. We present numerical results that compare the performance of the proposed decomposition algorithm against the exact algorithm for the problem.     

A capacitated facility location and inventory management problem with single sourcing

The current paper addresses the integrated location and inventory problem with capacity constraints. Adopting more realistic assumptions comes at the cost of increased complexity and inability to solve the model with existing methods, mainly due to the non-linear terms that arise. We attempt to render the extended formulation solvable by linearizing its non-linear terms. Certain terms are replaced by exact reformulations while for the rest a piecewise linearization is implemented. The contribution of this work is not only the development of a formulation that is more practical, but also the reformulation that enables its solving with commercial software. We test our proposed approach on a benchmark dataset from the literature, including both small and large instances of the problem. Results clearly demonstrate the superiority of this approach in terms of both solution quality and computational time.     

The obnoxious p facility network location problem with facility interaction

Three heuristics are proposed to solve the maximin formulation for siting p facilities on a network considering a pollution dispersion equation and facility interaction. Initially, the single facility problem is approached by building up polygons which model pollution spread about the nodes of the network. This is extended in the first heuristic to the p facility problem. The second combines both the p-maximin and p-maxisum objectives in a lexicographic manner. The third is based on recent developments of Simulated Annealing. The proposed heuristics are evaluated for up to six facilities on a set of randomly generated networks having 20 to 40 nodes and low or medium arc density.     

Solving general continuous single facility location problems by cutting planes

A unified cutting plane method is proposed to solve a large class of continuous single facility location problems. These include both minisum and minimax problems with mixed norms and convex transportation costs. The method provides an easy stopping rule and permits the post optimal determination of an outer approximation to near optimality regions. Two examples are given which show the power of the method. Extensive computational results in dimension two and higher are reported.     

The ordered capacitated facility location problem

In this paper, we analyze flexible models for capacitated discrete location problems with setup costs. We introduce a major extension with regards to standard models which consists of distinguishing three different points of view of a location problem in a logistics system. We develop mathematical programming formulations for these models using discrete ordered objective functions with some new features. We report on the computational behavior of these formulations tested on a randomly generated battery of instances.     

Scatter search for the single source capacitated facility location problem

This paper considers the Single Source Capacitated Facility Location Problem (SSCFLP). We propose a Scatter Search approach to provide upper bounds for the optimal solution of the problem. The proposed approach uses GRASP to initialize the Reference Set. Solutions of the Reference Set are combined using a procedure that consists of two phases: (1) the initialization phase and (2) the improvement phase. During the initialization phase each client is assigned to an open facility to obtain a solution that is then improved with the improvement phase. Also, a tabu search algorithm is applied. In order to evaluate the proposed approach we use different sets of test problems. According to the results obtained we observe that the method provides good quality solutions with reasonable computational effort.     

A general model for the undesirable single facility location problem

In this paper, a finite set in which an optimal solution for a general Euclidean problem of locating an undesirable facility in a polygonal region, is determined and can be found in polynomial time. The general problem we propose leads us, among others, to several well-known problems such as the maxisum, maximin, anticentdian or r-anticentrum problem.     

The general facility location problem with connectivity on trees

In this note we study the general facility location problem with connectivity. We present an O(np ²)-time algorithm for the general facility location problem with connectivity on trees. Furthermore, we present an O(np)-time algorithm for the general facility location problem with connectivity on equivalent binary trees.     

On a facility location problem with applications to tele-diagnostic

Consider an undirected graph G modelling a network. Each vertex in the graph contains some physical devices, which can be monitored and possibly repaired from a remote site in case they become faulty. We assume that there can be two kinds of faults in the system: soft faults, which can be repaired remotely from another site (i.e., a monitor), and severe faults which cannot be repaired remotely and require further (possibly human) interventions. We assume that soft faults happen with some fixed probability λ, 0 < λ ≤ 1. We investigate the problem of locating monitors in the network so as to minimize the total expected communication cost per fault. We formalize such a problem as a location problem with a cost function depending on λ and study some properties of the optimal solutions. The latter are exploited for investigating the complexity of the problem and providing efficient approximation algorithms.     

The multifacility maximin planar location problem with facility interaction

^** Email: s.salhi{at}kent.ac.uk Two branch-and-bound algorithms are proposed to optimally solvethe maximin formulation for locating p facilities in the plane.Tight upper and lower bounds are constructed and suitable methodsof guiding the search developed. To enhance the method, efficientmeasures for identifying specific squares for subdivision aresuggested. The proposed algorithms are evaluated on a set ofrandomly generated problems of up to five facilities and 120nodes.     

带有异常点的平方度量设施选址问题

传统的设施选址问题一般假设所有顾客都被服务,考虑到异常点的存在不仅会增加总费用(设施的开设费用与连接费用之和),也会影响到对其他顾客的服务质量.研究异常点在最终方案中允许不被服务的情况,称之为带有异常点的平方度量设施选址问题.该问题是无容量设施选址问题的推广.问题可描述如下:给定设施集合、顾客集,以及设施开设费用和顾客...     

Competitive facility location and design problem

We develop a spatial interaction model that seeks to simultaneously optimize location and design decisions for a set of new facilities. The facilities compete for customer demand with pre-existing competitive facilities and with each other. The customer demand is assumed to be elastic, expanding as the utility of the service offered by the facilities increases. Increases in the utility can be achieved by increasing the number of facilities, design improvements, or locating facilities closer to the customer.     

Resource-saving tracking problem with infinite time horizon

We consider the problem on the infinite-duration tracking of a prescribed trajectory of an inaccurately observed control system subjected to an unobservable dynamic disturbance. We construct a solution algorithm that is resource-saving in the sense that the control resources used for solving the problem for small noise values in the state observation channel are little different from the corresponding resources in the “ideal case” where the current values of the dynamic disturbance are available to direct observation.