Continuous location of an assembly station

Demand existing at client points in the plane for several products should be met. Products have to be assembled from different components obtainable at given prices at various sources with known production capacities. The optimal design of the resulting supply chain must be determined, including the location of a central assembly station in the plane, so as to minimize the total operational cost comprising buying and transport of components as well as transport of final products. This problem leads to a difficult nonlinear and non-convex optimization problem for which a locally convergent algorithm is proposed. Some computational results are presented.     

Solving a Huff-like competitive location and design model for profit maximization in the plane

A chain wants to set up a single new facility in a planar market where similar facilities of competitors, and possibly of its own chain, are already present. Fixed demand points split their demand probabilistically over all facilities in the market proportionally with their attraction to each facility, determined by the different perceived qualities of the facilities and the distances to them, through a gravitational or logit type model. Both the location and the quality (design) of the new facility are to be found so as to maximise the profit obtained for the chain. Several types of constraints and costs are considered.     

Four-point Fermat location problems revisited. New proofs and extensions of old results

^** Email: frank.plastria{at}vub.ac.be What is the point at which the sum of (Euclidean) distancesto four fixed points in the plane is minimised? This extensionof the celebrated location question of Fermat about three pointswas partially solved by Fagnano around 1750, giving the followingsimple geometric answer: when the fixed points form a convexquadrangle it is the intersection point of both diagonals; itis not known who first derived the other case: otherwise itis the fixed point in the triangle formed by the three otherfixed points. We show that the first case extends and generalisesto general metric spaces, while the second case extends to anyplanar norm, any ellipsoidal norm in higher dimensional spacesand to the sphere. Received January 2005. accepted on 16 December 2005.     

Alternating local search based VNS for linear classification

We consider the linear classification method consisting of separating two sets of points in d-space by a hyperplane. We wish to determine the hyperplane which minimises the sum of distances from all misclassified points to the hyperplane. To this end two local descent methods are developed, one grid-based and one optimisation-theory based, and are embedded into a VNS metaheuristic scheme. Computational results show these approaches to be complementary, leading to a single hybrid VNS strategy which combines both approaches to exploit the strong points of each. Extensive computational tests show that the resulting method can always be expected to approach the global optimum close enough that any deviations from the global optimum are irrelevant with respect to the classification power.     

Minmax-distance approximation and separation problems: geometrical properties

A center hyperplane in the d-dimensional space minimizes the maximum of its distances from a finite set of points A with respect to possibly different gauges. In this note it is shown that a center hyperplane exists which is at (equal) maximum distance from at least d?+?1 points of A. Moreover the projections of the points among these which lie above the center hyperplane cannot be separated by another hyperplane from the projections of those that are below it. When all gauges involved are smooth, all center hyperplanes satisfy these properties. This geometric property allows us to improve and generalize previously existing results, which were only known for the case in which all distances are measured using a common norm. The results also extend to the constrained case where for some points it is prespecified on which side of the hyperplane (above, below or on) they must lie. In this case the number of points lying on the hyperplane plus those at maximum distance is at least d?+?1. It follows that solving such global optimization problems reduces to inspecting a finite set of candidate solutions. Extensions of these results to a separation problem are outlined.     

Polynomial algorithms for parametric minquantile and maxcovering planar location problems with locational constraints

A location is sought within some convex region of the plane for the central site of some public service to a finite number of demand points. The parametric maxcovering problem consists in finding for eachR>0 the point from which the total weight of the demand points within distanceR is maximal. The parametric minimal quantile problem asks for each percentage α the point minimising the distance necessary for covering demand points of total weight at least α. We investigate the properties of these two closely related problems and derive polynomial algorithms to solve them both in case of either (possibly inflated) Euclidean or polyhedral distances. The research of the first author is partially supported by Grant PB96-1416-C02-02 of Ministerio de Educación y Cultura, Spain.     

On minquantile and maxcovering optimisation

In this paper we introduce the parametric minquantile problem, a weighted generalisation ofkth maximum minimisation. It is shown that, under suitable quasiconvexity assumptions, its resolution can be reduced to solving a polynomial number of minmax problems.It is also shown how this simultaneously solves (parametric) maximal covering problems. It follows that bicriteria problems, where the aim is to both maximize the covering and minimize the cover-level, are reducible to a discrete problem, on which any multiple criteria method may be applied.Corresponding author.Visiting researcher at the Center for Industrial Location of the Vrije Universiteit Brussel during this research.     

Improved fixed point optimality conditions for mixed norms minisum location

We improve and extend sufficient conditions for an optimal solution to happen at a fixed point in a single facility minisum location model with mixed transportation modes recently proposed and studied by Brimberg, Love and Mladenovi?. In particular, conditions are derived that are valid for general mixed metrics, while for mixed ? _p -norms, possibly with rotated axes, much stronger conditions are obtained. An example demonstrates the superiority of the new conditions.