Dynamic location problems

A class of dynamic location problems is introduced. The relationship between a static problem and its corresponding dynamic one is studied. We concentrate on two types of dynamic problems. The first is the global optimization problem, in which one looks for the all-times optimum. The second is the steady-state problem in which one seeks to determine the steady-state behavior of the system if one exists. General approaches to these problems are discussed.Supported in part by the National Science Foundation under grants MCS-8300984, ECS-8218181 and ECS-8121741.     

Hamiltonian location problems

Exact algorithms for a series of simultaneous location and routing problems are developed. Problems are formulated as integer programs which are solved by a constraint relaxation procedure. Numerical results are reported.     

Multiple voting location problems

The facility voting location problems arise from the application of criteria derived from the voting processes concerning the location of facilities. The multiple location problems are those location problems in which the alternative solutions are sets of points. This paper extends previous results and notions on single voting location problems to the location of a set of facility points. The application of linear programming techniques to solve multiple facility voting location problems is analyzed. We propose an algorithm to solve Simpson multiple location problems from which the solution procedures for other problems are derived.     

Hull properties in location problems

Some properties of the solution set for single and multifacility continuous location problems with l_p distances are given. A set reduction algorithm is developed for problems in k-dimensional space having rectangular distances.     

Deterministic Time-inconsistent Optimal Control Problems - an Essentially Cooperative Approach

A general deterministic time-inconsistent optimal control problem is formulated for ordinary differential equations. To find a time-consistent equilibrium value function and the corresponding time-consistent equilibrium control, a non-cooperative N-person differential game (but essentially cooperative in some sense) is introduced. Under certain conditions, it is proved that the open-loop Nash equilibrium value function of the N -person differential game converges to a time-consistent equilibrium value function of the original problem, which is the value function of a time-consistent optimal control problem. Moreover, it is proved that any optimal control of the time-consistent limit problem is a time-consistent equilibrium control of the original problem.     

Deterministic approximation algorithms for sphere constrained homogeneous polynomial optimization problems

Due to their fundamental nature and numerous applications, sphere constrained polynomial optimization problems have received a lot of attention lately. In this paper, we consider three such problems: (i) maximizing a homogeneous polynomial over the sphere; (ii) maximizing a multilinear form over a Cartesian product of spheres; and (iii) maximizing a multiquadratic form over a Cartesian product of spheres. Since these problems are generally intractable, our focus is on designing polynomial-time approximation algorithms for them. By reducing the above problems to that of determining the L ₂-diameters of certain convex bodies, we show that they can all be approximated to within a factor of Ω((log n/n) ^d/2–1) deterministically, where n is the number of variables and d is the degree of the polynomial. This improves upon the currently best known approximation bound of Ω((1/n) ^d/2–1) in the literature. We believe that our approach will find further applications in the design of approximation algorithms for polynomial optimization problems with provable guarantees.     

Deterministic global derivative-free optimization of black-box problems with bounded Hessian

Obtaining guaranteed lower bounds for problems with unknown algebraic form has been a major challenge in derivative-free optimization. In this work, we pre     

Equality measures properties for location problems

The objectives underlying location decisions can be various. Among them, equity objectives have received an increasing attention in recent years, especially in the applications related to the public sector, where fair distributions of accessibility to the services should be guaranteed among users. In the literature a huge number of equality measures have been proposed; then, the problem of selecting the most appropriate one to be adopted in the decision-making processes is crucial. For this reason, many authors focused on the analysis of properties that equality measures should satisfy in order to be considered suitable. Most of the proposed properties are too general and related solely to the mathematical formulation of the measure itself (i.e., simpleness, impartiality, invariance). Hence, they do not give any indications about the behaviour of such measures in the optimization contexts. In this work, we propose some new properties to be associated to equality measures in order to describe characteristics which may be useful to drive optimization procedures in the search of optimal (or near-optimal) solutions. To this aim some empirical analyses have been performed in order to understand the typical behavior of remarkable measures in presence of a uniform distribution of demand points in a regular location spaces.     

A historical perspective on location problems

Location problems represent a popular class of optimization problems in the field of logistics, and their applications play a key role in strategic planning activities related to both manufacturing and service industries. This paper presents a historical perspective of their evolution, from the historic challenge posed by Pierre de Fermat, through the contributions by Torricelli, Viviani, Simpson, Heinen, and other researchers, to Weber’s intuition about a practical use of the results of that challenge, and its subsequent developments. Modern developments of the discipline are also reviewed. There is particular emphasis on the work of pioneering researchers who provided seminal contributions to the field.     

Approximation of solutions for location problems

This paper is devoted to a class of location problems with polyhedral norms. The objective function is shown to be a piecewise convex function which has to be maximized. We prove that the optimal locations belong to a finite set of intersection points, and we present an efficient method operating upon this finite set and providing a strict local maximum with few computational effort.     

Probabilistic analysis of geometric location problems

We analyze the behaviour of thek center and median problems forn points randomly distributed in an arbitrary regionA ofR ^d . Under a mild assumption on the regionA, we show that fork≦k(n)=o(n/logn), the objective function values of the discrete and continuous versions of these problems are equal to each otheralmost surely. For the two-dimensional case, both these problems can be solved by placing the centers or medians in an especially simple regular hexagonal pattern (the ‘honeycomb heuristic’ of Papadimitriou). This yields the exact asymptotic values for thek center and median problem, namely, α(|A|/k)^1/2 and β(|A|/k)^1/2, where |A| denotes the volume ofA, α and β are known constants, and the objective of the median problem is given in terms of the average, rather than the usual total, distance. For the 3- and 4-dimensional case, similar results can be obtained for the center problem to within an accuracy of roughly one percent. As a by-product, we also get asymptotically optimal algorithms for the 2-dimensionalp-normk median problem and for the twin problems of minimizing the maximum number of vertices served by any center and similarly for maximizing the minimum.     

Easy and hard bottleneck location problems

We consider a bottleneck location problem on a graph and present an efficient (polynomial time) algorithm for solving it. The problem involve the location of K noxious facilities that are to be placed as far as possilbe from the other facilities, and the objective is to maximize the minimum distance from the noxious facilities to the others. We then show that two other bottleneck (min-max) location problems, finding K-centers and absolute K-centers of a graph appear to be very difficult to solve even for reasonably good approximate solutions.     

A heuristic for large-sizep-median location problems with application to school location

This paper initially proposes a heuristic algorithm for thep-median problem designed for large weighted graphs. The problem is approached through the construction ofp trees whose shapes are progressively modified according to successive tests over the stability of their roots and vertices. The algorithm seems promising because: (i) on a regular PC it can handle problems of the order of 500 vertices, while the mainframe version goes indefinitely further, (ii) contrary to what normally would be expected, execution times seem to be inversely proportional top, and even for large problems, they may be reasonable, especially ifp is large relative to the number of vertices, and (iii) it produces solutions of good quality and in most of the cases studied, it outperforms the traditional heuristic of Teitz and Bart. A real application of the algorithm embedded in a methodology to evaluate the location of 85 public schools, among 389 possible vertices, in the metropolitan area of Rio de Janeiro is reported. Results confirmed the conjecture of poor location and the procedure was able to identify several micro-regions simply void of schools. The methodology is being well received by the education authorities and its extension to the whole metropolitan area is being considered.     

Metric location problems with nonshortest service routes

We study the generalizations of the classical metric location problems in which the route of a service team passes through a remote depository containing some components needed for replacement. Generally speaking, in this case the path to the client is not shortest and the problem ceases to be metric. We show that the available approximation algorithms for the classical metric problems translate to our generalizations with preservation of approximation ratios.     

Variable neighbourhood structures for cycle location problems

Variable neighbourhood search is a metaheuristic used mainly to tackle combinatorial optimization problems. Its performance depends on having a good variable neighbourhood structure: that is, a sequence of neighbourhoods that are ideally pairwise disjoint and contain feasible solutions further and further from a given feasible solution. This article defines a variable neighbourhood structure with these properties that is new for cycle location problems. It find bounds for the neighbourhood sizes and shows how to iterate over then when the cycle is a circuit. It tests the structure and iteration method using variable neighbourhood search on a range of median cycle problems and finds a neighbourhood size beyond which there is, on average, no benefit in applying local search. This neighbourhood size is found not to depend on problem size or bound on circuit length.     

Planar weber location problems with line barriers

The Weber problem for a given finite set of existing facilities in the plane is to find the location of a new facility such that the weithted sum of distances to the existing facilities is minimized.

A variation of this problem is obtained if the existing facilities are situated on two sides of a linear barrier. Such barriers like rivers, highways, borders or mountain ranges are frequently encountered in practice.

Structural results as well as algorithms for this non-convex optimization problem depending on the distance function and on the number and location of passages through the barrier are presented.     

A note on two source location problems

We consider Source Location ($\mathsf{SL}$) problems: given a capacitated network $G=(V,E)$, cost $c(v)$ and a demand $d(v)$ for every $v\in V$, choose a min-cost $S\subseteq V$ so that $\lambda (v,S)⩾d(v)$ holds for every $v\in V$, where $\lambda (v,S)$ is the maximum flow value from v to S. In the directed variant, we have demands $d^{\mathit{in}}(v)$ and $d^{\mathit{out}}(v)$ and we require $\lambda (S,v)⩾d^{\mathit{in}}(v)$ and $\lambda (v,S)⩾d^{\mathit{out}}(v)$. Undirected $\mathsf{SL}$ is (weakly) NP-hard on stars with $r(v)=0$ for all v except the center. But, it is known to be polynomially solvable for uniform costs and uniform demands. For general instances, both directed an undirected $\mathsf{SL}$ admit a $(\ln D+1)$-approximation algorithms, where D is the sum of the demands; up to constant this is tight, unless P = NP. We give a pseudopolynomial algorithm for undirected $\mathsf{SL}$ on trees with running time $O(|V|{\Delta }^3)$, where $\Delta ={\max }_{v\in V}d(v)$. This algorithm is used to derive a linear time algorithm for undirected $\mathsf{SL}$ with $\Delta ⩽3$. We also consider the Single Assignment Source Location ($\mathsf{SASL}$) where every $v\in V$ should be assigned to a single node $s(v)\in S$. While the undirected $\mathsf{SASL}$ is in P, we give a $(\ln |V|+1)$-approximation algorithm for the directed case, and show that this is tight, unless P = NP.     

E-approximations for multidimensional weighted location problems.

This paper considers the multidimensional weighted minimax location problem, namely, finding a facility location that minimizes the maximal weighted distance to n points. General distance norms are used. An epsilon-approximate solution is obtained by applying a variant of the Russian method for the solution of Linear Programming. The algorithm has a time complexity of O(n log epsilon) for fixed dimensionality k. Computational results are presented.