Single facility location on a network under mill and delivered pricing

^** E-mail: pelegrin{at}um.es Firms normally use either a mill price or a delivered pricepolicy, depending on market conditions (type of good, transportationway, customers location, costs, etc). In this paper, the problemof selecting the best location for an entering firm in competitionwith some pre-existing firms, under each price policy, is studiedon a network for the first time. With mill pricing, an equilibriumin price rarely exists and it is assumed that all competingfirms set a common mill price for all customers. With deliveredpricing, there exists a Nash equilibrium in price and it isassumed that the equilibrium price in each area is offered tothe customers in that area. In both cases, we consider thatcustomers buy from the cheapest facility and the same rulesare used for tie breaking in the lowest cost. While the profitmaximization problem for the entering firm always has optimalsolutions under mill pricing, this problem might not have anoptimal solution under delivered pricing. We show some discretizationresults and give procedures to find the full set of optimal,or -optimal, solutions to the problem under the two price policies.A comparison of results with the two price policies is givenby using an illustrative example.     

Finding location equilibria for competing firms under delivered pricing

We address the problem of finding location equilibria of a location-price game where firms first select their locations and then set delivered prices in order to maximize their profits. Assuming that firms set the equilibrium prices in the second stage, the game is reduced to a location game for which a global minimizer of the social cost is a location equilibrium if demand is completely inelastic and marginal production cost is constant. The problem of social cost minimization is studied for both a network and a discrete location space. A node optimality property when the location space is a network is shown and an Integer Linear Programming (ILP) formulation is obtained to minimize the social cost. It is also shown that multiple location equilibria can be found if marginal delivered costs are equal for all competitors. Two ILP formulations are given to select one of such equilibria that take into account the aggregated profit and an equity criterion, respectively. An illustrative example with real data is solved and some conclusions are presented.     

Spatial competition facility location models: Definition,formulation and solution approach

Models are presented for locating a firm's production facilities and determining production levels at these facilities so as to maximize the firm's profit. These models take into account the changes in price at each of the spatially separated markets that would result from the increase in supply provided by the new facilities and also from the response of competing firms. Two different models of spatial competition are presented to represent the competitive market situation in which the firm's production facilities are being located. These models are formulated as variational inequalities; recent sensitivity analysis results for variational inequalities are used to develop derivatives of the prices at each of the spatially separated markets with respect to the production levels at each of the new facilities. These derivatives are used to develop a linear approximation of the implicit function relating prices to productions. A heuristic solution procedure making use of this approximation is proposed.     

On a Profit Maximizing Location Model

In this paper we discuss a locational model with a profit-maximizing objective. The model can be illustrated by the following situation. There is a set of potential customers in a given region. A firm enters the market and wants to sell a certain product to this set of customers. The location and demand of each potential customer are assumed to be known. In order to maximize its total profit, the firm has to decide: (1) where to locate its distribution warehouse to serve the customers; (2) the price for its product. Due to existence of competition, each customer holds a reservation price for the product. This reservation price is a decreasing function in the distance to the warehouse. If the actual price is higher than the reservation price, then the customer will turn to some other supplier and hence is lost from the firm's market. The problem of the firm is to find the best location for its warehouse and the best price for its product at the same time in order to maximize the total profit. We show that under certain assumptions on the complexity counts, a special case of this problem can be solved in polynomial time.     

Solving the plant location problem on a line by linear programming

This paper investigates the simple uncapacitated plant location problem on a line. We show that under general conditions the special structure of the problem allows the optimal solution to be obtained directly from a linear programming relaxation. This result may be extended to the related p-median problem on a line. Thus, the practitioner is now able to use readily available LP codes in place of specialized algorithms to solve these one-dimensional models. The findings also shed some light on the “integer friendliness” of the general problem.     

LP-based approximation for uniform capacitated facility location problem

In this paper, we study uniform hard capacitated facility location problem. The standard LP for the problem is known to have an unbounded integrality gap. We present constant factor approximation by rounding a solution to the standard LP with a slight $(1+ϵ)$ violation in the capacities.Our result shows that the standard LP is not too bad.Our algorithm is simple and more efficient as compared to the strengthened LP-based true approximation that uses the inefficient ellipsoid method with a separation oracle. True approximations are also known for the problem using local search techniques that suffer from the problem of convergence. Moreover, solutions based on standard LP are easier to integrate with other LP-based algorithms.The result is also extended to give the first approximation for uniform hard capacitated $k$-facility location problem violating the capacities by a factor of $(1+ϵ)$ and breaking the barrier of 2 in capacity violation. The result violates the cardinality by a factor of $\frac{2}{1+ϵ}$.     

Fault-tolerant concave facility location problem with uniform requirements

In this paper, we consider the fault-tolerant concave facility location problem (FTCFL) with uni- form requirements. By investigating the structure of the FTCFL, we obtain a modified dual-fitting bifactor approximation algorithm. Combining the scaling and greedy argumentation technique, the approximation fac- tor is proved to be 1.52.     

A discrete long-term location–price problem under the assumption of discriminatory pricing: Formulations and parametric analysis

We consider a competitive location problem in which a new firm has to make decisions on the locations of several new facilities as well as on its price setting in order to maximise profit. Under the assumption of discriminatory prices, competing firms set a specific price for each market area. The customers buy one unit of a single homogeneous price-inelastic product from the facility that offers the lowest price in the area the consumers belong to. Three customer choice rules are considered in order to break ties in the offered prices. We prove that, considering long-term competition on price, this problem can be reduced to a problem with decisions on location only. For each one of the choice rules the location problem is formulated as an integer programming model and a parametric analysis of these models is given. To conclude, an application with real data is presented.     

A competitive hub location and pricing problem

We formulate and solve a new hub location and pricing problem, describing a situation in which an existing transportation company operates a hub and spoke network, and a new company wants to enter into the same market, using an incomplete hub and spoke network. The entrant maximizes its profit by choosing the best hub locations and network topology and applying optimal pricing, considering that the existing company applies mill pricing. Customers’ behavior is modeled using a logit discrete choice model. We solve instances derived from the CAB dataset using a genetic algorithm and a closed expression for the optimal pricing. Our model confirms that, in competitive settings, seeking the largest market share is dominated by profit maximization. We also describe some conditions under which it is not convenient for the entrant to enter the market.     

Retail facility location under changing market conditions

In this paper we investigate the location of retail facilitiesunder changing market conditions when market conditions areexpected to change during the planning horizon. Three modelsare presented: (1) the minimax regret model where the objectivefunction is to minimize the maximum possible loss under differentmarket scenarios, (2) the Stackelberg equilibrium model wherebya future competitor enters the market and one wishes to maximizethe market share captured throughout the planning horizon incorporatingthe market share loss to the competitor, and (3) the thresholdmodel in which we consider a minimum threshold level such thatif the market share captured by the new facility fails to reachthat threshold, the facility will not survive. Our objectiveis to minimize the probability of failure.     

Plant location with minimum inventory

We present an integer programming model for plant location with inventory costs. The linear programming relaxation has been solved by Dantzig-Wolfe decomposition. In this case the subproblems reduce to the minimum cut problem. We have used subgradient optimization to accelerate the convergence of the D-W algorithm. We present our experience with problems arising in the design of a distribution network for computer spare parts. In most cases, from a fractional solution we were able to derive integer solutions within 4% of optimality.     

Solving Large-scale Profit Maximization Capacitated Lot-size Problems by Heuristic Methods

This paper introduces a simple heuristic for a quadratic programming sub-problem within a Lagrangean relaxation heuristic for a dynamic pricing and lot-size problem. This simple heuristic is demonstrated to work well on both ‘standard problem instances’ from the CLSP-literature, as well as on very large-scale cases. Additionally, we introduce price constraints within the framework of dynamic pricing, discuss their relevance in a real world market modelling, and demonstrate their applicability within this algorithmic framework.      

ADD-heuristics' starting procedures for capacitated plant location models

This paper is concerned with heuristics for capacitated plant location models where locations have different capacities. In this case ADD-heuristics normally lead to bad solutions. We present some starting procedures (priority rules) in order to overcome this difficulty. Finally, we report numerical results, including comparisons between ADD-heuristics with starting procedures and DROP-heuristics.     

Some facets of the simple plant location polytope

We relate the simple plant location problem to the vertex packing problem and derive several classes of facets of their associated integer polytopes.This work was supported by NSF Grant ENG 79-02506.     

Simple dynamic location problem with uncertainty: a primal-dual heuristic approach

Abstract

In this paper, the simple dynamic facility location problem is extended to uncertain realizations of the potential locations for facilities and the existence of customers as well as fixed and variable costs. With limited knowledge about the future, a finite and discrete set of scenarios is considered. The decisions to be made are where and when to locate the facilities, and how to assign the existing customers over the whole planning horizon and under each scenario, in order to minimize the expected total costs. Whilst assignment decisions can be scenario dependent, location decisions have to take into account all possible scenarios and cannot be changed according to each scenario in particular. We first propose a mixed linear programming formulation for this problem and then we present a primal-dual heuristic approach to solve it. The heuristic was tested over a set of randomly generated test problems. The computational results are provided.     

An aggressive reduction scheme for the simple plant location problem

Pisinger et al. introduced the concept of ‘aggressive reduction’ for large-scale combinatorial optimization problems. The idea is to spend much time and effort in reducing the size of the instance, in the hope that the reduced instance will then be small enough to be solved by an exact algorithm.     

Relaxed voting and competitive location under monotonous gain functions on trees

We examine competitive location problems where two competitors serve a good to users located in a network. Users decide for one of the competitors based on the distance induced by an underlying tree graph. The competitors place their server sequentially into the network. The goal of each competitor is to maximize his benefit which depends on the total user demand served. Typical competitive location problems include the (1,X₁)-medianoid, the (1,1)-centroid, and the Stackelberg location problem.An additional relaxation parameter introduces a robustness of the model against small changes in distance. We introduce monotonous gain functions as a general framework to describe the above competitive location problems as well as several problems from the area of voting location such as Simpson, Condorcet, security, and plurality.In this paper we provide a linear running time algorithm for determining an absolute solution in a tree where competitors are allowed to place on nodes or on inner points. Furthermore we discuss the application of our approach to the discrete case.     

A strengthened formulation for the simple plant location problem with order

The simple plant location problem with order, a generalization of the well-known simple plant location problem where preferences for the customers are considered, is studied here. Some valid inequalities are introduced as well as a basic preprocessing analysis. A computational study shows the efficiency of this approach.     

Production and location on a network under demand uncertainty

The Hakimi theorem is fundamental in location theory. It says that the set of nodes and market-places necessarily contains a profit-maximizing location when the transportation costs are concave in distance. The purpose of this letter is to discuss the validity of this theorem in the context of a two-stage stochastic model of the location of a firm on a network. In the first stage, the firm chooses its location and production level before knowing the exact demands. In the second stage, it observes the realization of the random variables representing the demands and decides upon the distribution of its production. It is shown that the Hakimi theorem still holds in this model when the firm is risk-neutral. On the other hand, in the case of a risk-averse firm, it ceases to be true in that all the points of the network must be considered to obtain an optimal location.