Competitive facility location model with concave demand

We consider a spatial interaction model for locating a set of new facilities that compete for customer demand with each other, as well as with some pre-existing facilities to capture the “market expansion” and the “market cannibalization” effects. Customer demand is assumed to be a concave non-decreasing function of the total utility derived by each customer from the service offered by the facilities. The problem is formulated as a non-linear Knapsack problem, for which we develop a novel solution approach based on constructing an efficient piecewise linear approximation scheme for the objective function. This allows us to develop exact and α-optimal solution approaches capable of dealing with relatively large-scale instances of the model. We also develop a fast Heuristic Algorithm for which a tight worst-case error bound is established.     

The gravity p-median model

In this paper we propose a new model for the p-median problem. In the standard p-median problem it is assumed that each demand point is served by the closest facility. In many situations (for example, when demand points are communities of customers and each customer makes his own selection of the facility) demand is divided among the facilities. Each customer selects a facility which is not necessarily the closest one. In the gravity p-median problem it is assumed that customers divide their patronage among the facilities with the probability that a customer patronizes a facility being proportional to the attractiveness of that facility and to a decreasing utility function of the distance to the facility.     

Optimizing pricing and location decisions for competitive service facilities charging uniform price

In this paper, we present the problem of optimizing the location and pricing for a set of new service facilities entering a competitive marketplace. We assume that the new facilities must charge the same (uniform) price and the objective is to optimize the overall profit for the new facilities. Demand for service is assumed to be concentrated at discrete demand points (customer markets); customers in each market patronize the facility providing the highest utility. Customer demand function is assumed to be elastic; the demand is affected by the price, facility attractiveness, and the travel cost for the highest-utility facility. We provide both structural and algorithmic results, as well as some managerial insights for this problem. We show that the optimal price can be selected from a certain finite set of values that can be computed in advance; this fact is used to develop an efficient mathematical programming formulation for our model.     

Facility location for market capture when users rank facilities by shorter travel and waiting times

A firm wants to locate several multi-server facilities in a region where there is already a competitor operating. We propose a model for locating these facilities in such a way as to maximize market capture by the entering firm, when customers choose the facilities they patronize, by the travel time to the facility and the waiting time at the facility. Each customer can obtain the service or goods from several (rather than only one) facilities, according to a probabilistic distribution. We show that in these conditions, there is demand equilibrium, and we design an ad hoc heuristic to solve the problem, since finding the solution to the model involves finding the demand equilibrium given by a nonlinear equation. We show that by using our heuristic, the locations are better than those obtained by utilizing several other methods, including MAXCAP, p-median and location on the nodes with the largest demand.     

A note on the allocation of queuing facilities using a minisum criterion

This paper suggests a formulation and a solution procedure for resource allocation problems which consider a central planner, m static queuing facilities providing a homogeneous service at their locations, and a known set of demand points or customers. It is assumed that upon a request for service the customer is routed to a facility by a probabilistic assignment. The objective is to determine how to allocate a limited number of servers to the facilities, and to specify demand rates from customers to facilities in order to minimize a weighted sum of response times. This sum measures the total time lost in the system due to two sources: travel time from customer to facility locations and waiting time for service at the facilities. The setting does not allow for cooperation between the facilities.     

考虑顾客便利半径和质量阈值的竞争设施选址问题

在竞争设施选址问题中,顾客选择行为是决定设施占领市场份额的重要因素,其描述了需求在设施之间的分配方式。为了贴近顾客真实的光顾行为,本文提出了一种考虑顾客便利半径和质量阈值的顾客选择规则,并研究了在该规则下市场中新进入公司的竞争设施选址问题。提出了一种基于排名的遗传算法(RGA)求解该问题,并将该算法与经典遗传算法(GA)和基于排名的离散优化算法(RDOA)进行了比较,结果说明了算法的有效性以及模型中质量阈值的重要性。     

A facility location model with safety stock costs: analysis of the cost of single-sourcing requirements

We consider a supply chain setting where multiple uncapacitated facilities serve a set of customers with a single product. The majority of literature on such problems requires assigning all of any given customer??s demand to a single facility. While this single-sourcing strategy is optimal under linear (or concave) cost structures, it will often be suboptimal under the nonlinear costs that arise in the presence of safety stock costs. Our primary goal is to characterize the incremental costs that result from a single-sourcing strategy. We propose a general model that uses a cardinality constraint on the number of supply facilities that may serve a customer. The result is a complex mixed-integer nonlinear programming problem. We provide a generalized Benders decomposition algorithm for the case in which a customer??s demand may be split among an arbitrary number of supply facilities. The Benders subproblem takes the form of an uncapacitated, nonlinear transportation problem, a relevant and interesting problem in its own right. We provide analysis and insight on this subproblem, which allows us to devise a hybrid algorithm based on an outer approximation of this subproblem to accelerate the generalized Benders decomposition algorithm. We also provide computational results for the general model that permit characterizing the costs that arise from a single-sourcing strategy.     

竞争环境下截流设施选址问题

研究企业新建设施时,市场上已有设施存在的情况下,使本企业总体利润最大的截流设施选址问题。在一般截留设施选址模型的基础上引入引力模型,消费者到某个设施接受服务的概率与偏离距离及设施的吸引力相关,同时设施的建设费用与设施吸引力正相关,建立非线性整数规划模型并使用贪婪算法进行求解。数值分析表明,该算法求解速度快,模型计算精度较高。     

Algorithms for a Facility Location Problem with Stochastic Customer Demand and Immobile Servers

This paper studies a facility location problem with stochastic customer demand and immobile servers. Motivated by applications to locating bank automated teller machines (ATMs) or Internet mirror sites, these models are developed for situations in which immobile service facilities are congested by stochastic demand originating from nearby customer locations. Customers are assumed to visit the closest open facility. The objective of this problem is to minimize customers' total traveling cost and waiting cost. In addition, there is a restriction on the number of facilities that may be opened and an upper bound on the allowable expected waiting time at a facility. Three heuristic algorithms are developed, including a greedy-dropping procedure, a tabu search approach and an -optimal branch-and-bound method. These methods are compared computationally on a bank location data set from Amherst, New York.     

A pricing problem under Monge property

We study a pricing problem where buyers with non-uniform demand purchase one of many items. Each buyer has a known benefit for each item and purchases the item that gives the largest utility, which is defined to be the difference between the benefit and the price of the item. The optimization problem is to decide on the prices that maximize total revenue of the seller. This problem is also called the optimal product line design problem in the absence of competition.

Even though the general problem is known to be NP-hard, it can be solved efficiently under some natural assumptions on customer benefits. In this paper we study properties of optimal solutions and present a dynamic programming algorithm when customer benefits satisfy the Monge property. The same algorithm can also be used to solve the problem under the additional requirement that all buyers should be served.     

p-Median theorems for competitive locations

In competitive location theory, one wishes to optimally choose the locations ofr facilities to compete againstp existing facilities for providing service (or goods) to the customers who are at given discrete points (or nodes). One normally assumes that: (a) the level of demand of each customer is fixed (i.e. this demand is not a function of how far a customer is from a facility), and (b) the customer always uses the closest available facility. In this paper we study competitive locations when one or both of the above assumptions have been relaxed. In particular, we show that for each case and under certain assumptions, there exists a set of optimal locations which consists entirely of nodes.This work was supported by a National Science Foundation Grant ECS-8121741.     

Inventory sharing in integrated network design and inventory optimization with low-demand parts

Service Parts Logistics (SPL) problems induce strong interaction between network design and inventory stocking due to high costs and low demands of parts and response time based service requirements. These pressures motivate the inventory sharing practice among stocking facilities. We incorporate inventory sharing effects within a simplified version of the integrated SPL problem, capturing the sharing fill rates in 2-facility inventory sharing pools. The problem decides which facilities in which pools should be stocked and how the demand should be allocated to stocked facilities, given full inventory sharing between the facilities within each pool so as to minimize the total facility, inventory and transportation costs subject to a time-based service level constraint. Our analysis for the single pool problem leads us to model this otherwise non-linear integer optimization problem as a modified version of the binary knapsack problem. Our numerical results show that a greedy heuristic for a network of 100 facilities is on average within 0.12% of the optimal solution. Furthermore, we observe that a greater degree of sharing occurs when a large amount of customer demands are located in the area overlapping the time windows of both facilities in 2-facility pools.     

Equilibrium analysis of disaggregate facility choice systems subject to congestion-elastic demand.

This paper considers the impact of congestion on the spatial distribution of customer utilization of service facilities in a stochastic-dynamic environment. Previous research has assumed that the rate of demand for service is independent of the attributes of the facilities. We consider the more general case in which facility utilization is determined both by individual facility choice (based on the stochastic disaggregate choice mechanism) and by the rate of demand for service. We develop generalized results for proving that equilibria exist and describe sufficient conditions for the uniqueness and global stability of these equilibria. These conditions depend upon the elasticity of demand with respect to the level of congestion at the facilities, and on whether customers are congestion-averse or are congestion-loving. Finally, we examine special cases when these conditions are satisfied.     

Rational Abandonment from Tele-Queues: Nonlinear Waiting Costs with Heterogeneous Preferences

We consider the modelling of abandonment from a queueing system by impatient customers. Within the proposed model, customers act rationally to maximise a utility function that weights service utility against expected waiting cost. Customers are heterogeneous, in the sense that their utility function parameters may vary across the customer population. The queue is assumed invisible to waiting customers, who do not obtain any information regarding their standing in the queue during their waiting period. Such circumstances apply, for example, in telephone centers or other remote service facilities, to which we refer as tele-queues. We analyse this decision model within a multi-server queue with impatient customers, and seek to characterise the Nash equilibria of this system. These equilibria may be viewed as stable operating points of the system, and determine the customer abandonment profile along with other system-wide performance measures. We provide conditions for the existence and uniqueness of the equilibrium, and suggest procedures for its computation. We also suggest a notion of an equilibrium based on sub-optimal decisions, the myopic equilibrium, which enjoys favourable analytical properties. Some concrete examples are provided to illustrate the modelling approach and analysis. The present paper supplements previous ones which were restricted to linear waiting costs or homogeneous customer population.     

The maximum capture problem with random utilities: Problem formulation and algorithms

A model for the optimal location of new facilities in a competitive market is introduced under the hypothesis that customers' behavior can be modeled by random utility functions. It means that the company, that wished to locate, uses a random utility model to forecast the market share of a location. Therefore the company cannot forecast the behavior of every customer in a deterministic fashion, but is able to embed him by a probability distribution. Three formulations are proposed to compute upper bounds of the objective function and compared in a numerical simulation. A branch and bound method is developed and tested on examples with up to 50 potential locations, and a Variable Neighborhood Search heuristic is proposed to solve larger instances.     

Evaluation of (R,Q)-policies for two-level inventory systems with generally distributed customer inter-arrival times

In this paper we consider a two-level inventory system with a central warehouse and a number of retailers. All facilities apply continuous review (R,Q)-policies. We first extend Forsberg's exact Poisson model to the case with unit demand and customer inter-arrival times that are Erlang distributed. In the case with generally distributed customer inter-arrival times we approximate by Erlang distributions. We use two different methods to choose the approximate Erlang distribution. The first method means that we, for each retailer, choose the Erlang distribution that has the exact mean and minimum difference in standard deviation. Our second method means that we, for each retailer, choose the Erlang distribution of customer inter-arrival times that gives the exact mean and minimum difference in the standard deviation of the demand per unit of time instead of the inter-arrival time. Both methods are tested on 38 simulated cases. In all cases both methods give the same approximation.     

Incorporating the threat of terrorist attacks in the design of public service facility networks

In this paper, we consider the design problem of a public service facility network with existing facilities when there is a threat of possible terrorist attacks. The aim of the system planner, who is responsible for the operation of the network, is to open new facilities, relocate existing ones if necessary, and protect some of the facilities to ensure a maximum coverage of the demand that is assumed to be aggregated at customer zones. By doing so, the system planner anticipates that a number of unprotected facilities will be rendered out-of-service by terrorist attacks. It is assumed that the sum of the fixed cost of opening new facilities, the relocation costs, and the protection costs cannot exceed a predetermined budget level. Adopting the approach of gradual (or partial) coverage, we formulate a bilevel programming model where the system planner is the leader and the attacker is the follower. The objective of the former is the maximization of the total service coverage, whereas the latter wants to minimize it. We propose a heuristic solution procedure based on tabu search where the search space consists of the decisions of the system planner, and the corresponding objective value is computed by optimally solving the attacker??s problem using CPLEX. To assess the quality of the solutions produced by the tabu search (TS) heuristic, we also develop an exhaustive enumeration method, which explores all the possible combinations of opening new facilities, relocating existing ones, and protecting them. Since its time complexity is exponential, it can only be used for relatively small instances. Therefore, to be used as a benchmark method, we also implement a hill climbing procedure employed with the same type of moves as the TS heuristic. Besides, we carry out a sensitivity analysis on some of the problem parameters to investigate their effect on the solution characteristics.     

Heuristics to Schedule Service Engineers within Time Windows

This paper describes the development of a set of heuristics for tackling vehicle routeing problems with time windows (VRPTW) subject to uncertain demand where schedules are prepared interactively. Many public utility companies, e.g. gas, water, electricity, are now having to quote very specific times for visits to customers, both for regular service and emergency call-outs. The heuristics developed produce good tours by sequencing visits on the basis of closeness to existing visits. Tours are developed as and when demand occurs so that the customer is given an immediate appointment time, rather than waiting for a number of requests for service to be received. Simple methods to construct time windows will also be discussed.     

Integrated supply chain planning under uncertainty using an improved stochastic approach

This paper proposes an integrated model and a modified solution method for solving supply chain network design problems under uncertainty. The stochastic supply chain network design model is provided as a two-stage stochastic program where the two stages in the decision-making process correspond to the strategic and tactical decisions. The uncertainties are mostly found in the tactical stage because most tactical parameters are not fully known when the strategic decisions have to be made. The main uncertain parameters are the operational costs, the customer demand and capacity of the facilities. In the improved solution method, the sample average approximation technique is integrated with the accelerated Benders’ decomposition approach to improvement of the mixed integer linear programming solution phase. The surrogate constraints method will be utilized to acceleration of the decomposition algorithm. A computational study on randomly generated data sets is presented to highlight the efficiency of the proposed solution method. The computational results show that the modified sample average approximation method effectively expedites the computational procedure in comparison with the original approach.     

Build-1: A disaggregate model of the U.S. electric utility industry

We present a linear programming model of the U.S. electric utility industry which explicitly represents each of the nation's 300 electric utilities and the options each has for meeting demand for electric energy. The model has been designed to estimate how the utility industry would respond to changes in policy or energy markets, especially in the present period of slow growth in demand and limited opportunities for expansion. By estimating the use, upgrading, retrofitting, and retirement of individual generating facilities with known geographical coordinates, the model provides the geographically detailed results needed by models of pollutant transport and other regional environmental impacts.