Solving the uncapacitated multi-facility Weber problem by vector quantization and self-organizing maps

The uncapacitated multi-facility Weber problem is concerned with locating m facilities in the Euclidean plane and allocating the demands of n customers to these facilities with the minimum total transportation cost. This is a non-convex optimization problem and difficult to solve exactly. As a consequence, efficient and accurate heuristic solution procedures are needed. The problem has different types based on the distance function used to model the distance between the facilities and customers. We concentrate on the rectilinear and Euclidean problems and propose new vector quantization and self-organizing map algorithms. They incorporate the properties of the distance function to their update rules, which makes them different from the existing two neural network methods that use rather ad hoc squared Euclidean metric in their updates even though the problem is originally stated in terms of the rectilinear and Euclidean distances. Computational results on benchmark instances indicate that the new methods are better than the existing ones, both in terms of the solution quality and computation time.     

Probabilistic Formulation of the Emergency Service Location Problem

The problem of locating emergency service facilities is studied under the assumption that the locations of incidents (accidents, fires, or customers) are random variables. The probability distribution for rectilinear travel time between a new facility location and the random location of the incident P _i is developed for the case of P _i being uniformly distributed over a rectangular region. The location problem is considered in a discrete space. A deterministic formulation is obtained and recognized to be a set cover problem. Probabilistic variation of the central facility location problem is also presented.An example and some computational experience are provided to emphasize the impact of the probabilistic formulation on the location decision.     

Local search algorithm for universal facility location problem with linear penalties

The universal facility location problem generalizes several classical facility location problems, such as the uncapacitated facility location problem and the capacitated location problem (both hard and soft capacities). In the universal facility location problem, we are given a set of demand points and a set of facilities. We wish to assign the demands to facilities such that the total service as well as facility cost is minimized. The service cost is proportional to the distance that each unit of the demand has to travel to its assigned facility. The open cost of facility i depends on the amount z of demand assigned to i and is given by a cost function \(f_i(z)\). In this work, we extend the universal facility location problem to include linear penalties, where we pay certain penalty cost whenever we refuse serving some demand points. As our main contribution, we present a (\(7.88+\epsilon \))-approximation local search algorithm for this problem.     

The Existence of a Solution to the Multi-Index Problem

The multi-index problem can be described as minimizing the cost of moving a set of p different commodities (k = 1, 2,..., p) from n origins (i = 1, 2,..., n) to m destinations (j = 1, 2,..., m). The equations then give rise to the conditions on the amount of the various types of combination that is available and required. Alternatively, the same set of restrictions arise when a single commodity has to be moved by different methods, e.g. road, rail, sea, canal, air, etc. Similarly the use of intermediate depots may require the use of a multi-index formulation. A third special type of problem where the method can be used is the capacitated transportation problem (each variable has an upper bound).     

Solving the multi-commodity capacitated multi-facility Weber problem using Lagrangean relaxation and a subgradient-like algorithm

The Multi-commodity Capacitated Multi-facility Weber Problem (MCMWP) is concerned with locating I-capacitated facilities in the plane in order to satisfy the demands of J customers for K commodities so that the total transportation cost is minimized. We propose a Lagrangean relaxation scheme and a subgradient-like algorithm based on the relaxation of the capacity and commodity bundle constraints. The resulting subproblem is a variant of the well-known Multi-facility Weber Problem and it can be solved by using column generation and branch-and-price on an equivalent set covering formulation, which is accurate but extremely inefficient. Therefore, we devise different strategies to increase the efficiency. They mainly benefit from the effective usage of the lower and upper bounds on the optimal value of the Lagrangean subproblem. On the basis of extensive computational tests, we can say that they increase the efficiency considerably and result in accurate Lagrangean heuristics.     

The <Emphasis Type="Italic">p</Emphasis>-Centre Problem—Heuristic and Optimal Algorithms

The p-centre problem, or minimax location-allocation problem in location theory terminology, is the following: given n demand points on the plane and a weight associated with each demand point, find p new facilities on the plane that minimize the maximum weighted Euclidean distance between each demand point and its closest new facility. We present two heuristics and an optimal algorithm that solves the problem for a given p in time polynomial in n. Computational results are presented.     

Set covering location models with stochastic critical distances

This paper formulates a new version of set covering models by introducing a customer-determined stochastic critical distance. In this model, all services are provided at the sites of facilities, and customers have to go to the facility sites to obtain the services. Due to the randomness of their critical distance, customers patronize a far or near facility with a probability. The objective is to find a minimum cost set of facilities so that every customer is covered by at least one facility with an average probability greater than a given level α. We consider an instance of the problem by embedding the exponential effect of distance into the model. An algorithm based on two searching paths is proposed for solutions to the instance. Experiments show that the algorithm performs well for problems with greater α, and the experimental results for smaller α are reported and analysed.     

Variable neighbourhood search heuristics for the probabilistic multi-source Weber problem

The Multi-source Weber Problem (MWP) is concerned with locating m facilities in the Euclidean plane, and allocating these facilities to n customers at minimum total cost. The deterministic version of the problem, which assumes that customer locations and demands are known with certainty, is a non-convex optimization problem and difficult to solve. In this work, we focus on a probabilistic extension and consider the situation where customer locations are randomly distributed according to a bivariate distribution. We first present a mathematical programming formulation for the probabilistic MWP called the PMWP. For its solution, we propose two heuristics based on variable neighbourhood search (VNS). Computational results obtained on a number of test instances show that the VNS heuristics improve the performance of a probabilistic alternate location-allocation heuristic referred to as PALA. In its original form, the applicability of the new heuristics depends on the existence of a closed-form expression for the expected distances between facilities and customers. Unfortunately, such an expression exists only for a few distance function and probability distribution combinations. We therefore use two approximation methods for the expected distances, which make the VNS heuristics applicable for any distance function and bivariate distribution of customer locations.     

An algorithm for generalized constrained multi-source Weber problem with demand substations

In this paper, we consider a multi-source Weber problem of m new facilities with respect to n demand regions in order to minimize the sum of the transportation costs between these facilities and the demand regions. We find a point on the border of each demand region from which the facilities serve the demand regions at these points. We present an algorithm including a location phase and an allocation phase in each iteration for solving this problem. An algorithm is also proposed for carrying out the location phase. Moreover, global convergence of the new algorithm is proved under mild assumptions, and some numerical results are presented.     

An iterated local search heuristic for the capacitated prize-collecting travelling salesman problem

This paper considers a variant of the travelling salesman problem named the capacitated prize-collecting travelling salesman problem (CPCTSP), which is derived from the colour-coating production scheduling in a cold rolling mill. The objective of the CPCTSP is to minimize the travel cost and the penalties paid for unvisited customers in such a way that a sufficiently large prize is collected and the demand of the visited customers does not exceed the salesman's capacity. For this problem, we propose an iterated local search (ILS) heuristic adopting guided kick and enhanced dynasearch. The experimental results on randomly generated instances show that the proposed heuristic outperforms the improved tabu search algorithm using frequency-based memory, and the further experimental results on instances collected from real colour-coating production also show that the proposed ILS algorithm is more effective and efficient than the currently adopted manual scheduling method.     

Heuristic algorithms for general <Emphasis Type="Italic">k</Emphasis>-level facility location problems

In a general k-level uncapacitated facility location problem (k-GLUFLP), we are given a set of demand points, denoted by D, where clients are located. Facilities have to be located at a given set of potential sites, which is denoted by F in order to serve the clients. Each client needs to be served by a chain of k different facilities. The problem is to determine some sites of F to be set up and to find an assignment of each client to a chain of k facilities so that the sum of the setup costs and the shipping costs is minimized. In this paper, for a fixed k, an approximation algorithm within a factor of 3 of the optimum cost is presented for k-GLUFLP under the assumption that the shipping costs satisfy the properties of metric space. In addition, when no fixed cost is charged for setting up the facilities and k=2, we show that the problem is strong NP-complete and the constant approximation factor is further sharpen to be 3/2 by a simple algorithm. Furthermore, it is shown that this ratio analysis is tight.     

Heuristics for Multistage Production Planning Problems

Several heuristics for the capacitated multistage production planning problem with concave production costs, based on traditional production planning techniques and linear programming, are stated and empirically evaluated using a new capacity relaxation of the problem to furnish lower bounds on cost.     

An efficient algorithm for the single facility location problem with polyhedral norms and disk-shaped demand regions

The single facility location problem with demand regions seeks for a facility location minimizing the sum of the distances from n demand regions to the facility. The demand regions represent sales markets where the transportation costs are negligible. In this paper, we assume that all demand regions are disks of the same radius, and the distances are measured by a rectilinear norm, e.g. \(\ell _1\) or \(\ell _\infty \). We develop an exact combinatorial algorithm running in time \(O(n\log ^c n)\) for some c dependent only on the space dimension. The algorithm is generalizable to the other polyhedral norms.     

A New Method for the Multifacility Minimax Location Problem

This paper presents a new method of locating n new facilities among m destinations in accordance with the minimax criterion; that is, the facilities are located to minimize the maximum weighted distance in the system. Distances may be rectangular, Euclidean, or general (l _p ). The method involves the numerical integration of ordinary differential equations and is computationally superior to methods using nonlinear programming.     

A branch-and-cut algorithm for the plant-cycle location problem

The Plant-Cycle Location Problem (PCLP) is defined on a graph G=(I∪J, E), where I is the set of customers and J is the set of plants. Each customer must be served by one plant, and the plant must be opened to serve customers. The number of customers that a plant can serve is limited. There is a cost of opening a plant, and of serving a customer from an open plant. All customers served by a plant are in a cycle containing the plant, and there is a routing cost associated to each edge of the cycle. The PCLP consists in determining which plants to open, the assignment of customers to plants, and the cycles containing each open plant and its customers, minimizing the total cost. It is an NP-hard optimization problem arising in routing and telecommunications. In this article, the PCLP is formulated as an integer linear program, a branch-and-cut algorithm is developed, and computational results on real-world data and randomly generated instances are presented. The proposed approach is able to find optimal solutions of random instances with up to 100 customers and 100 potential plants, and of instances on real-world data with up to 120 customers and 16 potential plants.     

An Algorithm for Solving Capacitated Multicommodity <Emphasis Type="Italic">p</Emphasis>-median Transportation Problems

An algorithm for solving a special capacitated multicommodity p-median transportation problem (CMPMTP), which arises in container terminal management, is presented. There are some algorithms to solve similar kinds of problems. The formulation here is different from the existing modelling of the p-median or some related location problems. We extend the existing work by applying a Lagrangean relaxation to the CMPMTP. In order to obtain a satisfactory solution, a heuristic branch-and-bound algorithm is designed to search for a better solution, if one is possible. A comparison is also made with different algorithms.     

(<Emphasis Type="Italic">Q,r</Emphasis>) Inventory Model with a Mixture of Lost Sales and Time-Weighted Backorders

This paper presents a stochastic inventory model for situations in which, during a stockout period, a fraction β of the demand is backordered and the remaining fraction 1 – β is lost. The model is suggested by the customers' different reactions to a stockout condition: during the stockout period, some patient customers wait until their demand is satisfied, while other impatient or urgent customers cannot wait and have to fill their demand from another source. The cost of a backorder is assumed to be proportional to the length of time for which the backorder exists, and a fixed penalty cost is incurred per unit of lost demand. Based on a heuristic treatment of a lot-size reorder-point policy, a mathematical model representing the average annual cost of operating the inventory system is developed. The optimal operating policy variables minimizing the average annual cost can be calculated iteratively. At the extremes β = 1 and β = 0, the model presented reduces to the usual backorders and lost sales case, respectively.     

Approximation algorithms for the robust facility leasing problem

In this paper, we consider the robust facility leasing problem (RFLE), which is a variant of the well-known facility leasing problem. In this problem, we are given a facility location set, a client location set of cardinality n, time periods \(\{1, 2, \ldots , T\}\) and a nonnegative integer \(q < n\). At each time period t, a subset of clients \(D_{t}\) arrives. There are K lease types for all facilities. Leasing a facility i of a type k at any time period s incurs a leasing cost \(f_i^{k}\) such that facility i is opened at time period s with a lease length \(l_k\). Each client in \(D_t\) can only be assigned to a facility whose open interval contains t. Assigning a client j to a facility i incurs a serving cost \(c_{ij}\). We want to lease some facilities to serve at least \(n-q\) clients such that the total cost including leasing and serving cost is minimized. Using the standard primal–dual technique, we present a 6-approximation algorithm for the RFLE. We further offer a refined 3-approximation algorithm by modifying the phase of constructing an integer primal feasible solution with a careful recognition on the leasing facilities.     

Stochastic inventory system with lead time flexibility: offered by a manufacturer/transporter

This paper studies lead time flexibility in a two-stage continuous review supply chain in which the retailer uses the (R, Q) inventory system: when his inventory position reaches R, the retailer places orders with size Q to the manufacturer, who uses a transportation provider to deliver them with different lead time options. According to the contract, the manufacturer is able to expedite or postpone the delivery if the retailer makes such a request. Hence, the retailer has the flexibility to modify the lead time by using the most up-to-date demand information. The optimal lead time policy is found to be a threshold-type policy. The sensitivity analysis also shows that R is much more sensitive to the change of lead time than Q, and thus, the paper is primarily focused on finding optimal R. We also provide a cost approximation which yields unimodal cost in R. Furthermore, we analyze the order crossing problem and derive an upper bound for the probability of order crossing. Finally, we conduct an extensive sensitivity analysis to illustrate the effects of lead time flexibility on supply chain performance and discuss the managerial insights.     

Planar maximal covering location problem under block norm distance measure

This paper introduces a new model for the planar maximal covering location problem (PMCLP) under different block norms. The problem involves locating g facilities anywhere on the plane in order to cover the maximum number of n given demand points. The generalization, in this paper, is that the distance measures assigned to facilities are block norms of different types and different proximity measures. First, the PMCLP under different block norms is modelled as a maximum clique partition problem on an equivalent multi-interval graph. Then, the equivalent graph problem is modelled as an unconstrained binary quadratic problem (UQP). Both the maximum clique partition problem and the UQP are NP-hard problems; therefore, we solve the UQP format through a genetic algorithm heuristic. Computational examples are given.