Location of depots in a sugar-beet distribution system

In the following case study the problem of the location of depots in a sugar-beet distribution system for a certain sugar enterprise in Poland is considered. The sugar-beet is delivered from farms to sugar-mills either directly or through some depots. Lower and upper limits on the depot throughputs are imposed. The depot investment and operating costs are estimated by a piecewiselinear function. Given a set of possible depot locations, costs associated with the depots and the unit transportation costs, we seek a minimum cost location-transportation plan determining the number, location and sizes of the depots to be opened and the amounts of the sugar-beet flows. Two solution procedures are developed: (1) The application of MPSX and MIP systems for the problem of the reduced size; (2) The heuristic method. Based upon the computational results both approaches can be treated as alternative solution techniques to the presented problem.     

An inventory-transportation system with stochastic demand

We study a logistic system in which a supplier has to deliver a set of products to a set of retailers to face a stochastic demand over a given time horizon. The transportation from the supplier to each retailer can be performed either directly, by expensive and fast vehicles, or through an intermediate depot, by less expensive but slower vehicles. At most one time period is required in the former case, while two time periods are needed in the latter case. A variable transportation cost is charged in the former case, while a fixed transportation cost per journey is charged in the latter case. An inventory cost is charged at the intermediate depot. The problem is to determine, for each time period and for each product, the quantity to send from the supplier to the depot, from the depot to each retailer and from the supplier to each retailer, in order to minimize the total expected cost. We first show that the classical benchmark policy, in which the demand of each product at each retailer is set equal to the average demand, can give a solution which is infinitely worse with respect to the optimal solution. Then, we propose two classes of policies to solve this problem. The first class, referred to as Horizon Policies, is composed of policies which require the solution of the overall problem over the time horizon. The second class, referred to as Reoptimization Policies, is composed of a myopic policy and several rolling-horizon policies in which the problem is reoptimized at each time period, once the demand of the time period is revealed. We evaluate the performance of each policy dynamically, by using Monte Carlo Simulation.     

Depot location: A technique for the avoidance of local optima

This paper is concerned with facility location as exemplified by the depot-siting problem. In particular it considers the problem of achieving only locally-optimal locations and describes a readily-available technique which greatly increases the chance of attaining the global solution. The technique is exemplified on two data sets using a depot cost function which is linear in throughput and also one displaying economies of scale.     

The Depot Siting Problem with Discontinuous Delivery Cost<Superscript>†</Superscript>

Discontinuities may occur in the distribution cost function for a variety of reasons. Some of these, notably discontinuous trunking costs and depot costs dependent on location, have been examined in the literature. In this paper the problem which arises when discontinuities occur in the local delivery cost function is examined and a method of solution incorporating heuristics is described. An illustrative example is given.     

A neural network approach to facility layout problems

A near-optimum parallel algorithm for solving facility layout problems is presented in this paper where the problem is NP-complete. The facility layout problem is one of the most fundamental quadratic assignment problems in Operations Research. The goal of the problem is to locate N facilities on an N-square (location) array so as to minimize the total cost. The proposed system is composed of N × N neurons based on an artificial two-dimensional maximum neural network for an N-facility layout problem. Our algorithm has given improved solutions for several benchmark problems over the best existing algorithms.     

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.     

A tabu search heuristic for a routing problem arising in servicing of offshore oil and gas platforms

This paper introduces a pickup and delivery problem encountered in servicing of offshore oil and gas platforms in the Norwegian Sea. A single vessel must perform pickups and deliveries at several offshore platforms. All delivery demands originate at a supply base and all pickup demands are also destined to the base. The vessel capacity may never be exceeded along its route. In addition, the amount of space available for loading and unloading operations is limited at each platform. The problem, called the Single Vehicle Pickup and Delivery Problem with Capacitated Customers consists of designing a least cost vehicle (vessel) route starting and ending at the depot (base), visiting each customer (platform), and such that there is always sufficient capacity in the vehicle and at the customer location to perform the pickup and delivery operations. This paper describes several construction heuristics as well as a tabu search algorithm. Computational results are presented.     

A heuristic algorithm for the symmetric and asymmetric vehicle routing problems with backhauls

We consider an extension of the capacitated Vehicle Routing Problem (VRP), known as the Vehicle Routing Problem with Backhauls (VRPB), in which the set of customers is partitioned into two subsets: Linehaul and Backhaul customers. Each Linehaul customer requires the delivery of a given quantity of product from the depot, whereas a given quantity of product must be picked up from each Backhaul customer and transported to the depot. VRPB is known to be NP-hard in the strong sense, and many heuristic algorithms were proposed for the approximate solution of the problem with symmetric or Euclidean cost matrices. We present a cluster-first-route-second heuristic which uses a new clustering method and may also be used to solve problems with asymmetric cost matrix. The approach exploits the information of the normally infeasible VRPB solutions associated with a lower bound. The bound used is a Lagrangian relaxation previously proposed by the authors. The final set of feasible routes is built through a modified Traveling Salesman Problem (TSP) heuristic, and inter-route and intra-route arc exchanges. Extensive computational tests on symmetric and asymmetric instances from the literature show the effectiveness of the proposed approach.     

Finite and infinite-horizon single vehicle routing problems with a predefined customer sequence and pickup and delivery

We consider the problem of finding the optimal routing of a single vehicle that starts its route from a depot and picks up from and delivers K different products to N customers that are served according to a predefined customer sequence. The vehicle is allowed during its route to return to the depot to unload returned products and restock with new products. The items of all products are of the same size. For each customer the demands for the products that are delivered by the vehicle and the quantity of the products that is returned to the vehicle are discrete random variables with known joint distribution. Under a suitable cost structure, it is shown that the optimal policy that serves all customers has a specific threshold-type structure. We also study a corresponding infinite-time horizon problem in which the service of the customers is not completed when the last customer has been serviced but it continues indefinitely with the same customer order. For each customer, the joint distribution of the quantities that are delivered and the quantity that is picked up is the same at each cycle. The discounted-cost optimal policy and the average-cost optimal policy have the same structure as the optimal policy in the finite-horizon problem. Numerical results are given that illustrate the structural results.     

A linear time algorithm for inverse obnoxious center location problems on networks

For an inverse obnoxious center location problem, the edge lengths of the underlying network have to be changed within given bounds at minimum total cost such that a predetermined point of the network becomes an obnoxious center location under the new edge lengths. The cost is proportional to the increase or decrease, resp., of the edge length. The total cost is defined as sum of all cost incurred by length changes. For solving this problem on a network with m edges an algorithm with running time ${\mathcal{O}(m)}$ is developed.     

A Tabu Search with Slope Scaling for the Multicommodity Capacitated Location Problem with Balancing Requirements

In this paper, a tabu search heuristic is combined with slope scaling to solve a discrete depot location problem, known as the multicommodity location problem with balancing requirements. Although the uncapacitated version of this problem has already been addressed in the literature, this is not the case for the more challenging capacitated version, where each depot has a fixed and finite capacity. The slope scaling approach is used during the initialization phase to provide the tabu search with good starting solutions. Numerical results are reported on various types of large-scale randomly generated instances. The quality of the heuristic is assessed by comparing the solutions obtained with those of a commercial mixed-integer programming code.     

Relative Performance of Some Sequential Methods of Planning Multiple Delivery Journeys

The relative performance of several sequential methods of planning multiple delivery journeys has been tested on batches of problems which varied in size, journey restrictions, delivery pattern and depot location.The saving criterion, of the methods tested, produced the best results for the conditions tested and required less than 0·1 min CDC 6600 central processor time for a 400 delivery problem; the time required varied as N^1·6 where N is the number of deliveries.The relative performance of different methods varied considerably both between problems conforming to the same specifications and between batches of problems with different specifications.To compare the performance of different methods for any but extremely limited purposes, samples of results for a variety of conditions are needed; even so, in the absence of an explanation for the performance variations, only tentative conclusions are possible.     

Weber problems with alternative transportation systems

In this paper we address a planar p-facility location problem where, together with a metric induced by a gauge, there exists a series of rapid transit lines, which can be used as alternative transportation system to reduce the total transportation cost. The location problem is reduced to solving a finite number of (multi)-Weber problems, from which localization results are obtained. In particular, it is shown that, if the gauge in use is polyhedral, then the problem is reduced to finding a p-median.     

A biased random-key genetic algorithm for the tree of hubs location problem

Hubs are facilities used to treat and dispatch resources in a transportation network. The objective of Hub Location Problems (HLP) is to locate a set of hubs in a network and route resources from origins to destinations such that the total cost of attending all demands is minimized. In this paper, we investigate a particular HLP, called the Tree of Hubs Location Problem in which hubs are connected by means of a tree and the overall network infrastructure relies on a spanning tree. This problem is particularly interesting when the total cost of building the hub backbone is high. We propose a biased random key genetic algorithm for solving the tree of hubs location problem. Computational results show that the proposed heuristic is robust and effective to this problem. The method was able to improve best known solutions of two benchmark instances used in the experiments.     

Cost Functions in the Location of Depots for Multiple-Delivery Journeys

Most wholesale distribution is performed during multiple-delivery journeys. Mathematical methods of locating depots utilize simple functions of delivery data, e.g. weight and distance from the depot, to measure the delivery "cost"; the total "cost" is minimized to find the depot location.It is pointed out that the cost of a delivery is influenced by the occurrence of other deliveries. It is shown that, in a few examples, simple functions of the delivery data are not always good measures of variable cost, as measured by the length of journeys planned to carry out the same deliveries, and that the minimum points of the simple functions rarely coincide with the point of minimum variable cost. It is concluded that, subject to reservations, which are discussed, about the experiments, the use of simple cost functions to locate wholesale distribution depots will probably give misleading results.     

The time constrained maximal covering salesman problem

We introduce the time constrained maximal covering salesman problem (TCMCSP) which is the generalization of the covering salesman and orienting problems. In this problem, we are given a set of vertices including a central depot, customer and facility vertices where each facility can supply the demand of some customers within its pre-determined coverage distance. Starting from the depot, the goal is to maximize the total number of covered customers by constructing a length constrained Hamiltonian cycle over a subset of facilities. We propose several mathematical programming models for the studied problem followed by a heuristic algorithm. The developed algorithm takes advantage of different procedures including swap, deletion, extraction-insertion and perturbation. Finally, an integer linear programming based improvement technique is designed to try to improve the quality of the solutions. Extensive computational experiments on a set of randomly generated instances indicate the effectiveness of the algorithm.     

Modeling fuzzy capacitated p-hub center problem and a genetic algorithm solution

Hub and spoke networks are used to switch and transfer commodities between terminal nodes in distribution systems at minimum cost and/or time. The p-hub center allocation problem is to minimize maximum travel time in networks by locating p hubs from a set of candidate hub locations and allocating demand and supply nodes to hubs. The capacities of the hubs are given. In previous studies, authors usually considered only quantitative parameters such as cost and time to find the optimum location. But it seems not to be sufficient and often the critical role of qualitative parameters like quality of service, zone traffic, environmental issues, capability for development in the future and etc. that are critical for decision makers (DMs), have not been incorporated into models. In many real world situations qualitative parameters are as much important as quantitative ones. We present a hybrid approach to the p-hub center problem in which the location of hub facilities is determined by both parameters simultaneously. Dealing with qualitative and uncertain data, Fuzzy systems are used to cope with these conditions and they are used as the basis of this work. We use fuzzy VIKOR to model a hybrid solution to the hub location problem. Results are used by a genetic algorithm solution to successfully solve a number of problem instances. Furthermore, this method can be used to take into account more desired quantitative variables other than cost and time, like future market and potential customers easily.     

The p/q-active uncapacitated facility location problem: Investigation of the solution space and an LP-fitting heuristic

The p/q-active uncapacitated facility location problem is the problem of locating p facilities on n possible sites each serving at least q of the m clients at the minimum cost. The problem is an extension of the uncapacitated facility location problem (UFL) where constraints on the number of facilities and their minimum activity have been added. A use of this formulation could be the opening of p new schools where each must have at least q pupils. p/q-active is NP-hard like the UFL.     

Uniform-cost inverse absolute and vertex center location problems with edge length variations on trees

This article considers the inverse absolute and the inverse vertex 1-center location problems with uniform cost coefficients on a tree network T with n+1 vertices. The aim is to change (increase or reduce) the edge lengths at minimum total cost with respect to given modification bounds such that a prespecified vertex s becomes an absolute (or a vertex) 1-center under the new edge lengths. First an O(nlogn) time method for solving the height balancing problem with uniform costs is described. In this problem the height of two given rooted trees is equalized by decreasing the height of one tree and increasing the height of the second rooted tree at minimum cost. Using this result a combinatorial O(nlogn) time algorithm is designed for the uniform-cost inverse absolute 1-center location problem on tree T. Finally, the uniform-cost inverse vertex 1-center location problem on T is investigated. It is shown that the problem can be solved in O(nlogn) time if all modified edge lengths remain positive. Dropping this condition, the general model can be solved in O(r_vnlogn) time where the parameter r_v is bounded by ⌈n/2⌉. This corrects an earlier result of Yang and Zhang.     

Capacitated facility location: Separation algorithms and computational experience

We consider the polyhedral approach to solving the capacitated facility location problem. The valid inequalities considered are the knapsack cover, flow cover, effective capacity, single depot, and combinatorial inequalities. The flow cover, effective capacity and single depot inequalities form subfamilies of the general family of submodular inequalities. The separation problem based on the family of submodular inequalities is NP-hard in general. For the well known subclass of flow cover inequalities, however, we show that if the client set is fixed, and if all capacities are equal, then the separation problem can be solved in polynomial time. For the flow cover inequalities based on an arbitrary client set and general capacities, and for the effective capacity and single depot inequalities we develop separation heuristics. An important part of these heuristics is based on the result that two specific conditions are necessary for the effective cover inequalities to be facet defining. The way these results are stated indicates precisely how structures that violate the two conditions can be modified to produce stronger inequalities. The family of combinatorial inequalities was originally developed for the uncapacitated facility location problem, but is also valid for the capacitated problem. No computational experience using the combinatorial inequalities has been reported so far. Here we suggest how partial output from the heuristic identifying violated submodular inequalities can be used as input to a heuristic identifying violated combinatorial inequalities. We report on computational results from solving 60 medium size problems. © 1998 The Mathematical Programming Society, Inc. Published by Elsevier Science B.V.