Allocation of discrete demand with changing costs

This paper investigates the allocation of discrete demand among facilities by stipulating that the unit mill price charged to users by a facility is a function of the total number of users patronizing that facility. This method of allocating customers to facilities can be used, in conjunction with global search strategies, to find the best location for a new facility.     

Efficient approximate solution methods for the multi-commodity capacitated multi-facility Weber problem

The capacitated multi-facility Weber problem is concerned with locating I capacitated facilities in the plane to satisfy the demand of J customers with the minimum total transportation cost of a single commodity. This is a nonconvex optimization problem and difficult to solve. In this work, we focus on a multi-commodity extension and consider the situation where K distinct commodities are shipped subject to capacity constraints between each customer and facility pair. Customer locations, demands and capacities for each commodity, and bundle restrictions are known a priori. The transportation costs, which are proportional to the distance between customers and facilities, depend on the commodity type. We address several location-allocation and discrete approximation heuristics using different strategies. Based on the obtained computational results we can say that the alternate solution of location and allocation problems is a very efficient strategy; but the discrete approximation has excellent accuracy.     

Supply facility and input/output point locations in the presence of barriers

This paper studies a facility location model in which two-dimensional Euclidean space represents the layout of a shop floor. The demand is generated by fixed rectangular-shaped user sites and served by a single supply facility. It is assumed that (i) communication between the supply point and a demand facility occurs at an input/output (I/O) point on the demand facility itself, (ii) the facilities themselves pose barriers to travel and (iii) distance measurement is as per the L₁-metric. The objective is to determine optimal locations of the supply facility as well as I/O points on the demand facilities, in order to minimize total transportation costs. Several, increasingly more complex, versions of the model are formulated and polynomial time algorithms are developed to find the optimal locations in each case.Scope and purposeIn a facility layout setting, often a new central supply facility such as a parts supply center or tool crib needs to be located to serve the existing demand facilities (e.g., workstations or maintenance areas). The demand facilities are physical entities that occupy space, that cannot be traveled through, and that receive material from the central facility, through a perimeter I/O (input/output or drop-off/pick-up) point. This paper addresses the joint problem of locating the central facility and determining the I/O point on each demand facility to minimize the total material transportation cost. Different versions of this problem are considered. The solution methods draw from and extend results of location theory for a class of restricted location problems. For practitioners, simple results and polynomial time algorithms are developed for solving these facility (re) design problems.     

Competitive Delivered Pricing by Mail-Order and Internet Retailers

Mail-order and internet sellers must decide how customers pay shipping charges. Typically, these sellers choose between two pricing policies: either “uniform pricing,” where the firm delivers to any customer at a fixed delivery charge (that may be volume dependent), or “mill pricing,” where the firm bills the customer a distance-related shipping charge. This paper studies price competition between a mail-order (or internet) seller and local retailers, and the mail-order firm’s choice of pricing policy. The price policy choice is studied when retailers do not change price in reaction to the mail-order firm’s policy choice, and when they do. In the second case, a two-stage non-cooperative game is used and it is found that for low customer willingness to pay, mill pricing is favored but as willingness to pay rises, uniform pricing becomes more attractive. These results are generalized showing that larger markets, higher transportation rates, higher unit production cost, and greater competition between retailers all increase profit under mill pricing relative to uniform pricing (and vice versa). On the other hand, cost asymmetries that favor the mail-order firm will tend to induce uniform rather than mill pricing. Some empirical data on retail and mail-order sales that confirm these results are presented.     

The Weber problem in congested regions with entry and exit points

The Weber problem is about finding a facility location on a plane such that the total weighted distance to a set of given demand points is minimized. The facility location and access routes to the facility can be restricted if the Weber problem contains congested regions, some arbitrary shaped polygonal areas on the plane, where location of a facility is forbidden and traveling is allowed at an additional fixed cost. Traveling through congested regions may also be limited to certain entry and exit points (or gates). It is shown that the restricted Weber problem is non-convex and nonlinear under Euclidean distance metric which justifies using heuristic approaches. We develop an evolutionary algorithm modified with variable neighborhood search to solve the problem. The algorithm is applied on test instances derived from the literature and the computational results are presented.     

Heuristics for the single source capacitated multi-facility Weber problem

The Single Source Capacitated Multi-facility Weber Problem (SSCMWP) is concerned with locating I capacitated facilities in the plane to satisfy the demand of J customers with the minimum total transportation cost of a single commodity such that each customer satisfies all its demand from exactly one facility. The SSCMWP is a non-convex optimization problem and difficult to solve. In the SSCMWP, customer locations, customer demands and facility capacities are known a priori. The transportation costs are proportional to the distance between customers and facilities. We consider both the Euclidean and rectilinear distance cases of the SSCMWP. We first present an Alternate Location and Allocation type heuristic and its extension by embedding a Very Large Scale Neighborhood search procedure. Then we apply a Discrete Approximation approach and propose both lower and upper bounding procedures for the SSCWMP using a Lagrangean Relaxation scheme. The proposed heuristics are compared with the solution approaches from the literature. According to extensive computational experiments on standard and randomly generated test sets, we can say that they yield promising performance.     

Semi-obnoxious single facility location in Euclidean space

This paper deals with the problem of determining within a bounded region the location for a new facility that serves certain demand points. For that purpose, the facility planners have two objectives. First, they attempt to minimize the undesirable effects introduced by the new facility by maximizing its minimum Euclidean distance with respect to all demand points (maximin). Secondly, they want to minimize the total transportation cost from the new facility to the demand points (minisum). Typical examples for such “semi-obnoxious” facilities are power plants that, as polluting agents, are undesirable and should be located far away from demand points, while cost considerations force planners to have the facility in close proximity to the customers. We describe the set of efficient solutions of this bi-criterion problem and propose an efficient algorithm for its solution.

Scope and purpose

It is becoming increasingly difficult to site necessary but potentially polluting (semi-obnoxious) facilities such as power plants, chemical plants, waste dumps, airports or train stations. More systematic decision-aid tools are needed to generate several options that balance the public's concerns with the interests of the developer or location planner. In this paper, a model is presented that generates the best possible sites (efficient solutions) with respect to two conflicting criteria: maximize distance from population centers and minimize total transportation costs. Having all efficient solutions at hand, the two sides can select one that best compromises their criteria. A very interesting property found is that most of these efficient solutions are on edges of a Voronoi diagram. An algorithm is developed that constructs the complete trajectory of efficient solutions.     

Locating a semi-obnoxious facility with expropriation

This paper considers the problem of locating semi-obnoxious facilities assuming that “too close” demand nodes can be expropriated by the developer at a given price. The objective is to maximize the minimum weighted distance from the facility to the non-expropriated demand nodes given a limited budget while taking into account the fact that customers do not want to be too far away from the facility. Two models of this problem on a network are presented. One is to minimize the difference between the maximum and the minimum weighted distances. The other one is to maximize the minimum weighted distance subject to an upper bound constraint on the maximum weighted distance. The dominating sets are determined and efficient algorithms are presented.     

Optimal manufacturer's pricing and lot-sizing policies under trade credit financing

In this paper, we extend Goyal's economic order quantity (EOQ) model to allow for the following four important facts: (1) the manufacturer's selling price per unit is necessarily higher than its unit cost, (2) the interest rate charged by a bank is not necessarily higher than the manufacturer's investment return rate, (3) the demand rate is a downward‐sloping function of the price, and (4) an economic production quantity (EPQ) model is a generalized EOQ model. We then establish an appropriate EPQ model accordingly, in which the manufacturer receives the supplier trade credit and provides the customer trade credit simultaneously. As a result, the proposed model is in a general framework that includes numerous previous models as special cases. Furthermore, we provide an easy‐to‐use closed‐form optimal solution to the problem for any given price. Finally, we develop an algorithm for the manufacturer to determine its optimal price and lot size simultaneously.     

The facility and transfer points location problem

In this paper, we investigate the location of a facility and several transfer points to serve as collector points for customers who need the services of the facility. For example, demand for emergency services is generated at a set of demand points that need the services of a central facility (such as a hospital). Patients are transferred to a helicopter pad (transfer point) at normal speed, and from there they are transferred to the facility at increased speed. The model involves the location of multiple transfer points and one facility. Locating one transfer point when the set of demand points and the location of the facility are known was investigated in Berman et al. (2004a). Location of several transfer points when the location of the facility is given is investigated in Berman et al. (2004b). In this paper, we propose heuristic approaches for the solution of this problem and report computational experiments on a test set of 40 problems.     

Optimal facility location with random throughput costs

In this paper we consider the optimal location and size of facilities where the throughput costs for each facility are random. Given a set of origins and a set of destinations, we want to determine the optimal location and size of a set of intermediate facilities in order to minimize the expected total generalized transportation cost. The generalized transportation cost of a freight unit from an origin to a destination passing through a facility is the sum of two terms: the transportation cost from the origin to the destination through the facility and the throughput cost of the facility. While the first term is deterministic, the second one is stochastic with a Gumbel probability distribution. Looking for the expected value of the optimal solution, a mixed deterministic nonlinear problem for the optimal location of the facilities is derived. Two heuristics, which give very good approximations to the optimum, are proposed.     

A leader-follower game in competitive facility location

We address the problem of locating new facilities of a firm or franchise that enters a market where a competitor operates existing facilities. The goal of the new entrant firm is to decide the location and attractiveness of its new facilities that maximize its profit. The competitor can react by opening new facilities, closing existing ones, and adjusting the attractiveness levels of its existing facilities, with the aim of maximizing its own profit. The demand is assumed to be aggregated at certain points in the plane and the new facilities of both the firm and the competitor can be located at predetermined candidate sites. We employ the gravity-based rule in modeling the behavior of the customers where the probability that a customer visits a certain facility is proportional to the facility attractiveness and inversely proportional to the distance between the facility site and demand point. We formulate a bilevel mixed-integer nonlinear programming model where the firm entering the market is the leader and the competitor is the follower. We propose heuristics that combine tabu search with exact solution methods.     

Integrated use of fuzzy c-means and convex programming for capacitated multi-facility location problem

In this study a fuzzy c-means clustering algorithm based method is proposed for solving a capacitated multi-facility location problem of known demand points which are served from capacitated supply centres. It involves the integrated use of fuzzy c-means and convex programming. In fuzzy c-means, data points are allowed to belong to several clusters with different degrees of membership. This feature is used here to split demands between supply centers. The cluster number is determined by an incremental method that starts with two and designated when capacity of each cluster is sufficient for its demand. Finally, each group of cluster and each model are solved as a single facility location problem. Then each single facility location problem given by fuzzy c-means is solved by convex programming which optimizes transportation cost is used to fine-tune the facility location. Proposed method is applied to several facility location problems from OR library (Osman & Christofides, 1994) and compared with centre of gravity and particle swarm optimization based algorithms. Numerical results of an asphalt producer’s real-world data in Turkey are reported. Numerical results show that the proposed approach performs better than using original fuzzy c-means, integrated use of fuzzy c-means and center of gravity methods in terms of transportation costs.     

A bilevel fixed charge location model for facilities under imminent attack

We investigate a bilevel fixed charge facility location problem for a system planner (the defender) who has to provide public service to customers. The defender cannot dictate customer-facility assignments since the customers pick their facility of choice according to its proximity. Thus, each facility must have sufficient capacity installed to accommodate all customers for whom it is the closest one. Facilities can be opened either in the protected or unprotected mode. Protection immunizes against an attacker who is capable of destroying at most r unprotected facilities in the worst-case scenario. Partial protection or interdiction is not possible. The defender selects facility sites from m candidate locations which have different costs. The attacker is assumed to know the unprotected facilities with certainty. He makes his interdiction plan so as to maximize the total post-attack cost incurred by the defender. If a facility has been interdicted, its customers are reallocated to the closest available facilities making capacity expansion necessary. The problem is formulated as a static Stackelberg game between the defender (leader) and the attacker (follower). Two solution methods are proposed. The first is a tabu search heuristic where a hash function calculates and records the hash values of all visited solutions for the purpose of avoiding cycling. The second is a sequential method in which the location and protection decisions are separated. Both methods are tested on 60 randomly generated instances in which m ranges from 10 to 30, and r varies between 1 and 3. The solutions are further validated by means of an exhaustive search algorithm. Test results show that the defender's facility opening plan is sensitive to the protection and distance costs.     

Price and capacity competition of application services duopoly

In this paper, we study the price and capacity competition of two application service providers (ASPs). The customers realize an intrinsic time-independent value from transactions processed by the ASP. The cost to the customers includes both the price charged by the ASP and the delay cost due to turnaround time of the ASP service system. Customers will choose to join the ASP who delivers a higher net value of the service. This paper examines the competition between two ASPs and the impact of customers' delay cost on ASP's pricing and capacity decisions. We find that the ASP with higher capacity will charge a higher price and enjoy a larger market share and, surprisingly, that customers' delay cost has no direct impact on the arrival rates to the ASPs but affects the ASPs' pricing decisions. The ASPs will charge a higher price premium to capitalize customers' higher delay cost. For the long-run problem, we find that in the presence of higher customer's delay cost, both ASPs' optimal profits suffer, in contrast to the short-run problem where a higher customer's delay cost leads to a higher profitability for both ASPs.     

A cross decomposition procedure for the facility location problem with a choice of facility type

Consider a capacitated facility location problem in which each customer is assumed to have a unit demand, and each facility capacity has to be chosen from the given set of admissible levels. Under the restriction that each customer's unit demand be met by exactly one facility, the objective is to select a set of facilities to open, along with their capacities, and to assign customer's demand to them so as to minimize the total cost which includes fixed costs of opening facilities as well as variable assignment costs. The problem is modelled as a pure 0–1 program which extends the scope of applicability significantly over that by conventional location models. Based on Cross Decomposition recently developed by Van Roy, a solution procedure is proposed, when exploits the special structure of the problem. Computational results with a set of test problems shows the superiority of our solution procedure to other related ones.     

Group technology inventories with optimal production costs

A model of group technology (GT) production systems including the cost of raw material processing is developed. It is assumed that the throughput time in a given GT cell depends linearly on the lot size. The optimal GT lot–size formula is derived and its properties discussed. The variability with respect to changes in the annual demand rate, the average carrying cost rate, and the rate charged per unit of cell production time are examined and evaluated. A typical case study is worked out to illustrate the analytical results.     

New heuristic algorithms for discrete competitive location problems with binary and partially binary customer behavior

We consider discrete location problems for an entering firm which competes with other established firms in a market where customers are spatially separated. In these problems, a given number of facility locations must be selected among a finite set of potential locations. The formulation and resolution of this type of problem depend on customers' behavior. The attraction for a facility depends on its characteristics and the distance between the facility and the customer. In this paper we study the location problem for the so-called Binary and Partially Binary Rules, in which the full demand of a customer is served by the most attractive facility, or by all the competing firms but patronizing only one facility of each firm, the one with the maximum attraction in the firm. Two new heuristic algorithms based on ranking of potential locations are proposed to deal with this sort of location problems. The proposed algorithms are compared with a classical genetic algorithm for a set of real geographical coordinates and population data of municipalities in Spain.     

Stochastic facility and transfer point covering problem with a soft capacity constraint

Existing models for transfer point location problems (TPLPs) do not guarantee the desired service time to customers. In this paper, a facility and TPLP is formulated based on a given service time that is targeted by a decision maker. Similar to real‐world situations, transportation times and costs are assumed to be random. In general, facilities are capacitated. However, in emergency services, they are not allowed to reject the customers for out of capacity reasons. Therefore, a soft capacity constraint for the facilities and a second objective to minimize the overtime in the facility with highest assigned demand are proposed. To solve the biobjective model with random variables, a variance minimization technique and chance‐constraint programming are applied. Thereafter, using fuzzy multiple objective linear programming, the proposed biobjective model is converted to a single objective. Computational results on 30 randomly designed experimental problems confirm satisfactory performance of the proposed model in reducing the variance of solutions as well as the overtime in the busiest facility.     

Constrained location of competitive facilities in the plane

This paper examines a competitive facility location problem occurring in the plane. A new gravity-based utility model is developed, in which the capacity of a facility serves as its measure of attractiveness. A new problem formulation is given, having elastic gravity-based demand, along with capacity, forbidden region, and budget constraints. Two solution algorithms are presented, one based on the big square small square method, and the second based on a penalty function formulation using fixed-point iteration. Computational testing is presented, comparing these two algorithms along with a general-purpose nonlinear solver.Scope and purposeIn a competitive business environment where products are not distinguishable, facility location plays an important role in an organization's success. This paper examines a firm's problem of selecting the locations in the plane for a set of new facilities such that market capture is maximized across all of the firm's facilities (both new and pre-existing). Customers are assumed to divide their demand among all competing facilities according to a utility function that considers facility attractiveness (measured by facility capacity for satisfying demand) and customer-facility distance. The level of customer demand is assumed to be a function of the facility configuration. Three types of constraints are introduced, involving facility capacity, forbidden regions for new facility location, and a budget function. Two solution algorithms are devised, one based on branch-and-bound methods and the other based on penalty functions. Computational testing is presented, comparing these two algorithms along with a general-purpose nonlinear solver.