Incorporating market characteristics into physical distribution models

This paper is concerned with incorporating the interactive effects of location, price and demand into mathematical models of distribution systems. Equations for distribution costs, capital investment, demand and gross profit margin are introduced and from these, profit and return on investment equations are derived. For a given number of depots, a search procedure is derived to determine the locations of the depots which maximise the derived profit equation. A similar search procedure is derived to maximise return on investment. The maximum profit and maximum return on investment solutions are compared and it is deduced that for a fixed gross profit margin, these solutions will be almost identical. Finally, the search procedures are applied to real data and observations are made on how the type of location determined by the search procedures varies as the market characteristics vary.     

Discontinuous Local Delivery Costs Re-Examined

The problem of locating depots when discontinuities occur in the local delivery cost function has been examined before and a heuristic procedure proposed. Here, an alternative search procedure, which can be used in conjunction with the previous heuristic, is described leading to the development of a family of heuristics. Some of these are tested and the results given. Conclusions are then drawn as to the best procedure to use under different circumstances.     

A tabu search procedure for multicommodity location/allocation with balancing requirements

We propose a tabu search heuristic for the location/allocation problem with balancing requirements. This problem typically arises in the context of the medium term management of a fleet of containers of multiple types, where container depots have to be selected, the assignment of customers to depots has to be established for each type of container, and the interdepot container traffic has to be planned to account for differences in supplies and demands in various zones of the geographical territory served by a container shipping company. It is modeled as a mixed integer program, which combines zero-one location variables and a multicommodity network flow structure. Extensive computational results on a set of benchmark problems and comparisons with an efficient dual ascent procedure are reported. These show that tabu search is a competitive approach for this class of problems.     

An Efficient Method for the Multi-Depot Location—Allocation Problem

This paper describes a procedure based on large-scale nonlinear programming for solving the multidepot location-allocation problem. Both the location of depots and the allocation of customers are allowed to vary simultaneously. Numerical experience on a 5 x 50 and a 10 x 50 example is described, and possible extensions to the basic model are discussed.     

Computer Scheduling of Vehicles from One or More Depots to a Number of Delivery Points

The problem of scheduling delivery vehicles from a number of depots to customers, subject to constraints on load and distance or time, is considered. A new algorithm is presented; this allows routes from several depots to be constructed simultaneously, subject to restrictions on numbers of vehicles at individual depots. Where too many customers require service, a flexible priority rule will select those to be served. Results for the single depot case are compared with other known algorithms; further results are given and discussed for cases of several depots.     

Lower and upper bounds for a two-stage capacitated facility location problem with handling costs

We study in this paper multi-product facility location problem in a two-stage supply chain in which plants have production limitation, potential depots have limited storage capacity and customer demands must be satisfied by plants via depots. In the paper, handling cost for batch process in depots is considered in a realistic way by a set of capacitated handling modules. Each module can be regards as alliance of equipment and manpower. The problem is to locate depots, choose appropriate handling modules and to determine the product flows from the plants, opened depots to customers with the objective to minimize total location, handling and transportation costs. For the problem, we developed a hybrid method. The initial lower and upper bounds are provided by applying a Lagrangean based on local search heuristic. Then a weighted Dantzig–Wolfe decomposition and path-relinking combined method are proposed to improve obtained bounds. Numerical experiments on 350 randomly generated instances demonstrate our method can provide high quality solution with gaps below 2%.     

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.     

Solving the capacitated location-routing problem by a GRASP complemented by a learning process and a path relinking

As shown in recent researches, the costs in distribution systems may be excessive if routes are ignored when locating depots. The location routing problem (LRP) overcomes this drawback by simultaneously tackling location and routing decisions. This paper presents a new metaheuristic to solve the LRP with capacitated routes and depots. A first phase executes a GRASP, based on an extended and randomized version of Clarke and Wright algorithm. This phase is implemented with a learning process on the choice of depots. In a second phase, new solutions are generated by a post-optimization using a path relinking. The method is evaluated on sets of randomly generated instances, and compared to other heuristics and a lower bound. Solutions are obtained in a reasonable amount of time for such a strategic problem. Furthermore, the algorithm is competitive with a metaheuristic published for the case of uncapacitated depots.     

Methods for solving combined two level location-routing problems of realistic dimensions

Very few distribution studies have dealt with combined location-routing problems, the problems of locating depots from which customers are served by tours rather than individual trips.This paper gives a survey of methods solving combined location-routing problems. Some methods are analyzed and three new heuristic methods are developed, implemented and compared.A newspaper delivery system consisting of 4500 customers is solved. The results seem to indicate that an alternate location-allocation-savings procedure and a saving-drop procedure are promising.     

Shipment planning at oil refineries using column generation and valid inequalities

In this paper we suggest an optimization model and a solution method for a shipment planning problem. This problem concerns the simultaneous planning of how to route a fleet of ships and the planning of which products to transport in these ships. The ships are used for moving products from oil refineries to storage depots. There are inventory levels to consider both at the refineries and at the depots. The inventory levels are affected by the process scheduling at the refineries and demand at the depots. The problem is formulated using an optimization model including an aggregated representation of the process scheduling at the refineries. Hence, we integrate the shipment planning and the process scheduling at the refineries. We suggest a solution method based on column generation, valid inequalities, and constraint branching. The solution method is tested on data provided by the Nynas oil refinery company and solutions are obtained within 4 hours, for problem instances of up to 3 refineries, 15 depots, and 4 products when considering a time horizon of 42 days.     

An optimization based approach for deployment of roadway incident response vehicles with reliability constraints

In recent years transportation agencies have introduced patrol based response programs to remove roadway incidents rapidly. With the evolution of technology incident detection and notification from remote traffic operation centers is possible and patrols to detect incidents are not necessary. Instead, the response units can be placed at various depots in urban areas and dispatched to incident sites upon notification. In this paper, we propose a reliability based mixed integer programming model to find best locations of incidence response depots and assign response vehicles to these depots so that incidents can be cleared efficiently at a minimum cost. The approach is unique as it considers fixed and variable costs of vehicles and depots, occurrences of major and minor incidents, and reliability of response service in the same model. Numerical results are generated for an example problem and sensitivity analysis is conducted to explore the relationships between parameters of the problem.     

Operational scheduling of refined product pipeline with dual purpose depots

Pipelines are one of the most economic and safe ways to transport oil derivatives to depots near the local markets. This is so, especially when there is a need for carrying a huge amount of petroleum products to long distance points. A pipeline may connect several refineries and depots where the connected points are able to inject products or receive them, or both (dual purpose depots). The main point of pipeline scheduling is to identify an optimal sequence of batches that satisfy demand with minimum costs. This paper presents an MILP continuous formulation for pipeline scheduling. The proposed model results in the reduction of problem size with respect to available models, and increases the accuracy. Computational results and data are reported.     

An LP-based heuristic for two-stage capacitated facility location problems

In this paper, a linear programming based heuristic is considered for a two-stage capacitated facility location problem with single source constraints. The problem is to find the optimal locations of depots from a set of possible depot sites in order to serve customers with a given demand, the optimal assignments of customers to depots and the optimal product flow from plants to depots. Good lower and upper bounds can be obtained for this problem in short computation times by adopting a linear programming approach. To this end, the LP formulation is iteratively refined using valid inequalities and facets which have been described in the literature for various relaxations of the problem. After each reoptimisation step, that is the recalculation of the LP solution after the addition of valid inequalities, feasible solutions are obtained from the current LP solution by applying simple heuristics. The results of extensive computational experiments are given.     

Delimitation of service areas in reverse logistics networks with multiple depots

This paper describes a heuristic approach for the definition of service (or influence) areas of multiple depots in a reverse logistics network. This work is based on a case study: the recyclable waste collection system with 5 depots that covers seven municipalities in the Alentejo region, southern Portugal. The system optimization considers two objectives, related with economic and organizational issues: minimizing the variable costs (function of the travelled distances by the collection vehicles), and the pursuit of equity, aiming at minimizing the workload differences among depots. The goal of balancing workloads poses a problem not usually treated in the existing literature. This fact required the development of a new approach with innovative elements adjusted to the existing circumstances.     

Lower bounds for the two-stage uncapacitated facility location problem

In the two-stage uncapacitated facility location problem, a set of customers is served from a set of depots which receives the product from a set of plants. If a plant or depot serves a product, a fixed cost must be paid, and there are different transportation costs between plants and depots, and depots and customers. The objective is to locate plants and depots, given both sets of potential locations, such that each customer is served and the total cost is as minimal as possible. In this paper, we present a mixed integer formulation based on twice-indexed transportation variables, and perform an analysis of several Lagrangian relaxations which are obtained from it, trying to determine good lower bounds on its optimal value. Computational results are also presented which support the theoretical potential of one of the relaxations.     

Local improvement in planar facility location using vehicle routing

In physical distribution the location of depots and vehicle routes are interdependent problems, but they are usually treated independently. Location-routing is the study of solving locational problems such that routing considerations are taken into account. We present an iterative heuristic for the location-routing problem on the plane. For each depot the Weber problem is solved using the end-points of the routes found previously as input nodes to the Weiszfeld procedure. Although the improvements found are usually small they show that it pays not to ignore the routing aspects when solving continuous location problems. Possible research avenues in continuous location-routing will also be suggested.     

A location-allocation problem in a large Belgian brewery

This paper discusses the depot location problem of a large Belgian brewery. Emphasis is on practical problems encountered in the course of the study (e.g. data gathering, estimating distances, etc.). Both a discrete location model (Dualoc) and a continuous model developed in-house (GRAVLOC) were used to perform the analysis. Both models indicated substantial savings to be obtained by relocating some depots and by reallocating customers to depots.     

A multi-level composite heuristic for the multi-depot vehicle fleet mix problem

The problem of simultaneously allocating customers to depots, finding the delivery routes and determining the vehicle fleet composition is addressed. A multi-level composite heuristic is proposed and two reduction tests are designed to enhance its efficiency. The proposed heuristic is tested on benchmark problems involving up to 360 customers, 2 to 9 depots and 5 different vehicle capacities. When tested on the special case, the multi-depot vehicle routing, our heuristic yields solutions almost as good as those found by the best known heuristics but using only 5 to 10% of their computing time. Encouraging results were also obtained for the case where the vehicles have different capacities.     

New facets for the two-stage uncapacitated facility location polytope

The two-stage uncapacitated facility location problem is considered. This problem involves a system providing a choice of depots and plants, each with an associated location cost, and a set of demand points which must be supplied, in such a way that the total cost is minimized. The formulations used until now to approach the problem were symmetric in plants and depots. In this paper the asymmetry inherent to the problem is taken into account to enforce the formulation which can be seen like a set packing problem and new facet defining inequalities for the convex hull of the feasible solutions are obtained. A computational study is carried out which illustrates the interest of the new facets. A new family of facets recently developed, termed lifted fans, is tested with success.     

Strategic planning in LTL logistics – increasing the capacity utilization of trucks

A “less than truckload” (LTL) network organises the transport of small shipping volumes by truck between given depots. To be cost-efficient it is necessary to bundle and unbundle goods on their way, using depots as so-called hubs. Our aim is to develop a strategic plan which is cost-optimal for given average shipping volumes. We consider transshipment and transport costs; to give a realistic estimate of the economies of scale, we charge each truck on a specific route equally, whether it is full or (nearly) empty.Real-sized problems become too hard for standard solvers so that we develop a combination of heuristic strategies (which can, in the end, be combined with solvers like CPLEX). We consider the problem in two flavours: MAPIT requires to transport unsplit goods from one depot to another, using at most two intermediate depots as hubs. IO-MAPIT furthermore considers the circulation of trucks.