Cost-Effective Operational Research,Sessions 1 and 2

A procedure for locating depots and their distribution areas is described and illustrated for the area of South-east England. The solution was obtained by an iterative search procedure. The program was written in a flexible fashion so as to be able to deal with multi-factory deliveries and a variable number of depots. Existing depots were allowed for in the procedure. Arrangements were made to avoid impermissible depot locations and to allow increased driving time for natural hazards.     

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.     

Scheduling trucks in local depots for door-to-door delivery services

A scheduling method is suggested for trucks delivering and picking up freight between branch offices and a regional depot in door-to-door delivery services. As the objective functions, different levels of customer service resulting from different timing of deliveries and pickups to/from branch offices are considered as well as the travel cost of trucks. Useful properties of the optimal timing of deliveries and pickups are derived to reduce the size of the search space significantly. Numerical experiments were conducted to evaluate various algorithms to solve the problem.     

开放式多中心需求可拆分VRP及混沌遗传模拟退火算法

综合考虑客户需求量允许被拆分、配送系统拥有多个配送中心且车辆可就近返回配送中心的运输模式,建立以配送中心日均建设成本、车辆派遣成本、理货成本和油耗成本之和最小为目标的数学模型,并根据问题特征设计了混沌遗传模拟退火算法对问题进行求解。通过对不同规模以及不同类型的算例进行实验,验证了混沌遗传模拟退火算法求解本文问题的有效性。     

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.     

Expected Distances in Distribution Problems

In many problems in distribution management it is necessary to take account of the expected distances that result from dispatching vehicles to meet customer demand. For example, in mathematical models for determining the optimal location of depots, the sum of radial distances (between customers and the depot), or the sum of the weighted distances, is used as a measure of the delivery "costs". Since actual delivery operations from the depot usually consist of truck-routes with each truck delivering to more than one customer at a time, it is important to know to what extent the above simplification is valid, namely to find a relationship between the actual route-distances and the sum of the radial distances.This paper makes use of an algorithm which plans optimal or near optimal routes to estimate this relationship by solving a large number of randomly generated problems. The discrepancies between the two methods are shown to be significant under certain circumstances.     

Tabu search variants for the mix fleet vehicle routing problem

The Mix Fleet Vehicle Routing Problem (MFVRP) involves the design of a set of minimum cost routes, originating and terminating at a central depot, for a fleet of heterogeneous vehicles with various capacities, fixed costs and variable costs to service a set of customers with known demands. This paper develops new variants of a tabu search meta-heuristic for the MFVRP. These variants use a mix of different components, including reactive tabu search concepts; variable neighbourhoods, special data memory structures and hashing functions. The reactive concept is used in a new way to trigger the switch between simple moves for intensification and more complex ones for diversification of the search strategies. The special data structures are newly introduced to efficiently search the various neighbourhood spaces. The combination of data structures and strategic balance between intensification and diversification generates an efficient and robust implementation, which is very competitive with other algorithms in the literature on a set of benchmark instances for which some new best-known solutions are provided.     

An exact algorithm for solving a capacitated location-routing problem

In location-routing problems, the objective is to locate one or many depots within a set of sites (representing customer locations or cities) and to construct delivery routes from the selected depot or depots to the remaining sites at least system cost. The objective function is the sum of depot operating costs, vehicle acquisition costs and routing costs. This paper considers one such problem in which a weight is assigned to each site and where sites are to be visited by vehicles having a given capacity. The solution must be such that the sum of the weights of sites visited on any given route does not exceed the capacity of the visiting vehicle. The formulation of an integer linear program for this problem involves degree constraints, generalized subtour elimination constraints, and chain barring constraints. An exact algorithm, using initial relaxation of most of the problem constraints, is presented which is capable of solving problems with up to twenty sites within a reasonable number of iterations.     

Heuristics for the multi-depot petrol station replenishment problem with time windows

In the multi-depot petrol station replenishment problem with time windows (MPSRPTW), the delivery of petroleum products stored in a number of different petroleum depots to a set of petrol distribution stations has to be optimized. Each depot has its own fleet of heterogeneous and compartmented tank trucks. Stations specify their demand by indicating the minimum and maximum quantities to be delivered for each ordered product and require the delivery within a predetermined time window. Several inter-related decisions must be made simultaneously in order to solve the problem. For this problem, the set of feasible routes to deliver all the demands, the departure depot for each route, the quantities of each product to be delivered, the assignment of these routes to trucks, the time schedule for each trip, and the loading of the ordered products to different tanks of the trucks used need to be determined. In this paper, we propose a mathematical model that selects, among a set of feasible trips, the subset that allows the delivery of all the demands while maximizing the overall daily net revenue. If this model is provided with all possible feasible trips, it determines the optimal solution for the corresponding MPSRPTW. However, since the number of such trips is often huge, we developed a procedure to generate a restricted set of promising feasible trips. Using this restricted set, the model produces a good but not necessarily optimal solution. Thus the proposed solution process can be seen as a heuristic. We report the results of the extensive numerical tests carried out to assess the performance of the proposed heuristic. In addition, we show that, for the special case of only one depot, the proposed heuristic outperforms a previously published solution method.     

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.     

Multiple depot ring star problem: a polyhedral study and an exact algorithm

The multiple depot ring-star problem (MDRSP) is an important combinatorial optimization problem that arises in optical fiber network design and in applications that collect data using stationary sensing devices and autonomous vehicles. Given the locations of a set of customers and a set of depots, the goal is to (i) find a set of simple cycles such that each cycle (ring) passes through a subset of customers and exactly one depot, (ii) assign each non-visited customer to a visited customer or a depot, and (iii) minimize the sum of the routing costs, i.e., the cost of the cycles and the assignment costs. We present a mixed integer linear programming formulation for the MDRSP and propose valid inequalities to strengthen the linear programming relaxation. Furthermore, we present a polyhedral analysis and derive facet-inducing results for the MDRSP. All these results are then used to develop a branch-and-cut algorithm to obtain optimal solutions to the MDRSP. The performance of the branch-and-cut algorithm is evaluated through extensive computational experiments on several classes of test instances.     

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.     

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.     

Determining the optimal number of depots in a physical distribution system according to market characteristics

This paper is an extension of an earlier paper to investigate the interactive effects of location, price and demand using mathematical models of distribution systems.The paper considers the additive nature of solutions to depot location problems and shows how this property can be used to advantage in determining the optimal number of depots in a distribution system. The importance of using marginal profit and marginal return on investment in this context is demonstrated.The sensitivity of the results to changes in cost parameters is also discussed.     

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.     

An integrated producer–buyer supply chain with delivery cost under stochastic transportation time

An integrated producer–buyer supply chain is used to simultaneously determine the optimum levels of the safety stock, delivery quantity, and number of shipments in this paper. The scenario is created by scheduling a single-setup at the producer with multiple deliveries to the buyer, and all shipments to the buyer are equal-sized batches. This study attempts to study the effects of delivery cost and transportation time, assumes that there is a stochastic transportation time between both producer and buyer, and that shortages are allowed. The transportation time is assumed to be Weibull distributed. The objective functions of the integrated model include the setup cost, inventory carrying cost, and delivery cost. We analyze the scenario where the delivery cost is explicitly considered in the model rather than considered as part of the fixed ordering cost or insignificant. A numerical example is also presented to demonstrate the proposed model using actual shipping rate data. In particular, the results show that when the producer's and buyer's carrying costs are low, and/or the mean time of transportation and delivery costs are high, then this can benefit both parties with regard to sharing total profit.     

A multi-depot period vehicle routing problem arising in the utilities sector

This paper considers the resource planning problem of a utility company that provides preventive maintenance services to a set of customers using a fleet of depot-based mobile gangs. The problem is to determine the boundaries of the geographic areas served by each depot, the list of customers visited each day and the routes followed by the gangs. The objective is to provide improved customer service at minimum operating cost subject to constraints on frequency of visits, service time requirements, customer preferences for visiting on particular days and other routing constraints. The problem is solved as a Multi-Depot Period Vehicle Routing Problem (MDPVRP). The computational implementation of the complete planning model is described with reference to a pilot study and results are presented. The solution algorithm is used to construct cost-service trade-off curves for all depots so that management can evaluate the impact of different customer service levels on total routing costs.     

Single Supplier�CBuyer Integrated Inventory Model Under Multiple JIT Delivery and Stock-Dependent Demand

In this paper, an integrated inventory model for a supply chain comprising of single buyer and single supplier is studied when demand is stock-dependent and units in inventory deteriorate at a constant rate. The total cost of the integrated system consists of the transportation cost, inspection cost and the cost of less flexibility under the assumption of JIT deliveries. The total integrated cost of single-supplier and single-buyer is minimized with respect to number of inspections and deliveries, the cycle time of deliveries and the delivery size for the replenishment time. A numerical example is given to validate the model. The sensitivity analysis carried out suggests that the unit inspection cost, deterioration rate of units in inventory and stock-dependent parameter are the critical factors.     

An exact algorithm for minimizing routing and operating costs in depot location

The problem of locating a single depot among n points is considered. The objective is to minimize the sum of depot operating cost and routing cost. The best depot location is found by means of an exact algorithm that determines simultaneously both the best depot location and the associated optimal delivery routes. A global integer programming formulation of the problem is given; the model is solved by relaxing most of its constraints and by introducing them only when they are violated.     

Direct shipping and the dynamic single-depot/multi-retailer inventory system

In this paper we study a single-depot/multi-retailer system with independent stochastic stationary demands, linear inventory costs, and backlogging at the retailers over an infinite horizon. In addition, we also consider the transportation cost between the depot and the retailers. Orders are placed each period by the depot. The orders arrive at the depot and are allocated and delivered to the retailers. No inventory is held at the depot. We consider a specific policy of direct shipments. That is, a lower bound on the long run average cost per period for the system over all order/delivery strategies is developed. The simulated long term average cost per period of the delivery strategy of direct shipping with fully loaded trucks is examined via comparison to the derived lower bound. Simulation studies demonstrate that very good results can be achieved by a direct shipping policy.