A computational comparison of algorithms for the inventory routing problem

The inventory routing problem is a distribution problem in which each customer maintains a local inventory of a product such as heating oil and consumes a certain amount of that product each day. Each day a fleet of trucks is dispatched over a set of routes to resupply a subset of the customers. In this paper, we describe and compare algorithms for this problem defined over a short planning period, e.g. one week. These algorithms define the set of customers to be serviced each day and produce routes for a fleet of vehicles to service those customers. Two algorithms are compared in detail, one which first allocates deliveries to days and then solves a vehicle routing problem and a second which treats the multi-day problem as a modified vehicle routing problem. The comparison is based on a set of real data obtained from a propane distribution firm in Pennsylvania. The solutions obtained by both procedures compare quite favorably with those in use by the firm.Part of this work was performed while this author was visiting the University of Waterloo.     

A multi-stop routing problem

The problem of determining the sequence of stops and the amount of load to carry in each segment route, named the Multi-Stop Routing Problem (MSRP) is addressed. A 0/1 mixed integer linear program and formulation refinements which facilitate the solution process are presented. Since the constraint set of the MSRP includes 0/1 mixed rows, valid inequalities for this type of regions are presented. Then these results are applied to the constraint set of the routing problem, presenting additional valid inequalities. In addition, polynomial separation algorithms associated with the valid inequalities are given, computational results are also included.     

A solution approach to the inventory routing problem in a three-level distribution system

We consider the infinite horizon inventory routing problem in a three-level distribution system with a vendor, a warehouse and multiple geographically dispersed retailers. In this problem, each retailer faces a demand at a deterministic, retailer-specific rate for a single product. The demand of each retailer is replenished either from the vendor through the warehouse or directly from the vendor. Inventories are kept at both the retailers and the warehouse. The objective is to determine a combined transportation (routing) and inventory strategy minimizing a long-run average system-wide cost while meeting the demand of each retailer without shortage. We present a decomposition solution approach based on a fixed partition policy where the retailers are partitioned into disjoint and collectively exhaustive sets and each set of retailers is served on a separate route. Given a fixed partition, the original problem is decomposed into three sub-problems. Efficient algorithms are developed for the sub-problems by exploring important properties of their optimal solutions. A genetic algorithm is proposed to find a near-optimal fixed partition for the problem. Computational results show the performance of the solution approach.     

New models and algorithms for the cyclic inventory routing problem

This is a summary of the author’s PhD thesis supervised by El-Houssaine Aghezzaf and defended on 4 December 2006 at the Universiteit Gent. The thesis is written in English and is electronically available from http://ir18.ugent.be/birger.raa/. This work studies the problem of finding optimal three-way cost trade-offs between vehicle fleet costs, distribution costs and holding costs in the cyclic replenishment of a set of customers with constant demand rates from a single depot.      

Maritime inventory routing with multiple products: A case study from the cement industry

This paper considers a maritime inventory routing problem faced by a major cement producer. A heterogeneous fleet of bulk ships transport multiple non-mixable cement products from producing factories to regional silo stations along the coast of Norway. Inventory constraints are present both at the factories and the silos, and there are upper and lower limits for all inventories. The ship fleet capacity is limited, and in peak periods the demand for cement products at the silos exceeds the fleet capacity. In addition, constraints regarding the capacity of the ships’ cargo holds, the depth of the ports and the fact that different cement products cannot be mixed must be taken into consideration. A construction heuristic embedded in a genetic algorithmic framework is developed. The approach adopted is used to solve real instances of the problem within reasonable solution time and with good quality solutions.     

Performance evaluation of distribution strategies for the inventory routing problem

Direct shipping strategy is an easy-to-implement distribution strategy frequently used in industrial distribution systems. In this paper, an analytic method is developed for performance evaluation of the strategy for the infinite horizon inventory routing problem with delivery frequency constraint. With the method, the effectiveness of direct shipping strategy can be represented as a function of some system parameters. We demonstrate that the effectiveness of direct shipping is at least the square root of the smallest utilization ratio of vehicle capacity. This implies that the effectiveness of the strategy can reach 100% (respectively, 94.86%) whenever the demand rate of each retailer is 100% (respectively, 90%) of the vehicle capacity multiplied by the upper bound of the delivery frequency. This insight can help a firm answer questions such as: under what conditions direct shipping strategy is effective and why, and how effective the strategy is under a specific condition? In case direct shipping strategy is proven ineffective, a more general Fixed Partition Policy (FPP) that combines direct shipping strategy and multiple-stop shipping strategy must be used. An analytic method is also developed for performance evaluation of general FPPs. We demonstrate that the effectiveness of an FPP depends on the total demand rate of the retailers in each partition (each retailer set) and their closeness level. This insight provides a useful guideline to the design of effective FPPs. The analytic methods make the performance improvement of a distribution system possible through adjusting its system parameters.     

Lower and upper bounds for location-arc routing problems with vehicle capacity constraints

This paper addresses multi-depot location arc routing problems with vehicle capacity constraints. Two mixed integer programming models are presented for single and multi-depot problems. Relaxing these formulations leads to other integer programming models whose solutions provide good lower bounds for the total cost. A powerful insertion heuristic has been developed for solving the underlying capacitated arc routing problem. This heuristic is used together with a novel location–allocation heuristic to solve the problem within a simulated annealing framework. Extensive computational results demonstrate that the proposed algorithm can find high quality solutions. We also show that the potential cost saving resulting from adding location decisions to the capacitated arc routing problem is significant.     

An iterated local search algorithm for the single-vehicle cyclic inventory routing problem

The Single-Vehicle Cyclic Inventory Routing Problem (SV-CIRP) belongs to the class of Inventory Routing Problems (IRP) in which the supplier optimises both the distribution costs and the inventory costs at the customers. The goal of the SV-CIRP is to minimise both kinds of costs and to maximise the collected rewards, by selecting a subset of customers from a given set and determining the quantity to be delivered to each customer and the vehicle routes, while avoiding stockouts. A cyclic distribution plan should be developed for a single vehicle.     

A partition approach to the inventory/routing problem

In this study we focus on the integration of inventory control and vehicle routing schedules for a distribution system in which the warehouse is responsible for the replenishment of a single item to the retailers with demands occurring at a specific constant (but retailer-dependent) rate, combining deliveries into efficient routes. This research proposes a fixed partition policy for this type of problem, in which the replenishment interval of each of the retailers’ partition region as well as the warehouse is accorded the power of two (POT) principle. A lower bound of the long-run average cost of any feasible strategy for the considered distribution system is drawn. And a tabu search algorithm is designed to find the retailers’ optimal partition regions under the fixed partition policy proposed. Computational results reveal the effectiveness of the policy as well as of the algorithm.     

A tree search algorithm for the multi-commodity location problem

The multi-commodity location problem is an extension of the simple plant location problem. The problem is to decide on locations of facilities to meet customer demands for several commodities in such a way that total fixed plus variable costs are minimized. Only one commodity may be supplied from any location.In this paper a primal and a dual heuristic for producing good bounds are presented. A method of improving these bounds by using a new Lagrangean relaxation for the problem is also presented. Computational results with problems taken from the literature are provided.     

A new model and hybrid approach for large scale inventory routing problems

This paper studies an inventory routing problem (IRP) with split delivery and vehicle fleet size constraint. Due to the complexity of the IRP, it is very difficult to develop an exact algorithm that can solve large scale problems in a reasonable computation time. As an alternative, an approximate approach that can quickly and near-optimally solve the problem is developed based on an approximate model of the problem and Lagrangian relaxation. In the approach, the model is solved by using a Lagrangian relaxation method in which the relaxed problem is decomposed into an inventory problem and a routing problem that are solved by a linear programming algorithm and a minimum cost flow algorithm, respectively, and the dual problem is solved by using the surrogate subgradient method. The solution of the model obtained by the Lagrangian relaxation method is used to construct a near-optimal solution of the IRP by solving a series of assignment problems. Numerical experiments show that the proposed hybrid approach can find a high quality near-optimal solution for the IRP with up to 200 customers in a reasonable computation time.     

Improved approximation for the capacitated inventory access point problem

The Inventory Access Point (IAP) is the single-item lot-sizing problem where a single customer faces demands in a discrete planning horizon, and the goal is to find a replenishment policy that minimizes the total inventory and ordering costs. While the uncapacitated version is polynomial, only a 3-approximation is known for the capacitated case. We improve this factor to 2.619 and, as a byproduct, we also improve the best factor for SIRPFL, which is a variant with multiple depots and customers.     

A comparison of average and discounted cost models for the dynamic lot size inventory problem

It is a common practice in the inventory literature to use average cost models as approximations to the theoretically correct discounted cost models. An average cost model minimizes the average undiscounted cost per period, while a discounted cost model minimizes the total discounted cost over the problem horizon. This paper attempts to answer an important question: How good are the results (the total discounted costs) for the average cost models compared to those for the discounted cost models? This question has been conclusively answered for the simplest inventory model where the demand rate and other parameters are assumed to remain constant in time. This paper addresses this issue for the first time for the case where demand rates are allowed to be nonstationary in time.A discounted cost model has been developed in the paper to carry out this comparison. It is shown that a simple dynamic programming algorithm can be used to find optimal order policies for the discounted cost model.The effect of the varying interest rates and other parameters on the relative performance of the average cost model has been studied by developing an insightful analysis and also by doing a computational study. The results show that, while the average cost model can cost as much as about 26% more than the discounted cost model in extreme cases, this increase is not significant for the parameter values in the range of the common interest.     

The maximum covering/shortest path problem: A multiobjective network design and routing formulation

In this paper the authors introduce the maximum covering/shortest path problem and the maximum population/shortest path problem, a special case of the former model. Both models are formulated as two objective integer programs. A summary of the results of a sample problem for the latter formulation is given. Possible modifications to, and extensions and applications of both models are also presented. With these formulations the authors extend the concept of ‘coverage’ from facility location analysis to network design and routing analysis.     

An efficient computational method for a stochastic dynamic lot-sizing problem under service-level constraints

We provide an efficient computational approach to solve the mixed integer programming (MIP) model developed by Tarim and Kingsman [8] for solving a stochastic lot-sizing problem with service level constraints under the static-dynamic uncertainty strategy. The effectiveness of the proposed method hinges on three novelties: (i) the proposed relaxation is computationally efficient and provides an optimal solution most of the time, (ii) if the relaxation produces an infeasible solution, then this solution yields a tight lower bound for the optimal cost, and (iii) it can be modified easily to obtain a feasible solution, which yields an upper bound. In case of infeasibility, the relaxation approach is implemented at each node of the search tree in a branch-and-bound procedure to efficiently search for an optimal solution. Extensive numerical tests show that our method dominates the MIP solution approach and can handle real-life size problems in trivial time.     

Hybrid flexible flowshop problems: Models and solution methods

This paper considers the problem of hybrid flowshop scheduling. First, we review the shortcoming of the available model in the literature. Then, four different mathematical models are developed in form of mixed integer linear programming models. A complete experiment is conducted to compare the models for performance based on the size and computational complexities. Besides the models, the paper proposes a novel hybrid particle swarm optimization algorithm equipped with an acceptance criterion and a local search heuristic. The features provide a fine balance of diversification and intensification capabilities for the algorithm. Using Taguchi method, the algorithm is fine tuned. Then, two numerical experiments are performed to evaluate the performance of the proposed algorithm with three particle swarm optimization algorithms available in the scheduling literature and one well-known iterated local search algorithm in the hybrid flowshop literature. All the results show the high performance of the proposed algorithm.     

A practical solution approach for the cyclic inventory routing problem

Vendor managed inventory (VMI) is an example of effective cooperation and partnering practices between up- and downstream stages in a supply chain. In VMI, the supplier takes the responsibility for replenishing his customers’ inventories based on their consumption data, with the aim of optimizing the over all distribution and inventory costs throughout the supply chain. This paper discusses the challenging optimization problem that arises in this context, known as the inventory routing problem (IRP). The objective of this IRP problem is to determine a distribution plan that minimizes average distribution and inventory costs without causing any stock-out at the customers. Deterministic constant customer demand rates are assumed and therefore, a long-term cyclical approach is adopted, integrating fleet sizing, vehicle routing, and inventory management. Further, realistic side-constraints such as limited storage capacities, driving time restrictions and constant replenishment intervals are taken into account. A heuristic solution approach is proposed, analyzed and evaluated against a comparable state-of-the-art heuristic.     

Measuring the impact of primal heuristics

In modern MIP solvers, primal heuristics play a key role in finding high-quality solutions. However, classical performance measures reflect the impact of primal heuristics on the overall solving process badly. In this article, we introduce a new performance measure, the “primal integral”, which depends on the quality of solutions and on the time when they are found. We compare five state-of-the-art MIP solvers w.r.t. the newly proposed measure, and show that heuristics improve their performance by up to 80%.     

Integrated design and operation of remnant inventory supply chains under uncertainty

We consider the simultaneous design and operation of remnant inventory supply chains. Remnant inventory is generated when demand for various lengths of a product may be satisfied by existing inventory, or by cutting a large piece into smaller pieces. We formulate our problem as a two-stage stochastic mixed-integer program. In solving our stochastic program, we enhance the standard L-shaped method in two ways. Our computational experiments demonstrate that these enhancements are effective, dramatically reducing the solution time for large instances.     

Inventory constrained maritime routing and scheduling for multi-commodity liquid bulk,Part I: Applications and model

This paper formulates a model for finding a minimum cost routing in a network for a heterogeneous fleet of ships engaged in pickup and delivery of several liquid bulk products. The problem is frequently encountered by maritime chemical transport companies, including oil companies serving an archipelago of islands. The products are assumed to require dedicated compartments in the ship. The problem is to decide how much of each product should be carried by each ship from supply ports to demand ports, subject to the inventory level of each product in each port being maintained between certain levels that are set by the production rates, the consumption rates, and the storage capacities of the various products in each port. This important and challenging inventory constrained multi-ship pickup–delivery problem is formulated as a mixed-integer nonlinear program. We show that the model can be reformulated as an equivalent mixed-integer linear program with special structure. Over 100 test problems are randomly generated and solved using CPLEX 7.5. The results of our numerical experiments illuminate where problem structure can be exploited in order to solve larger instances of the model. Part II of the sequel will deal with new algorithms that take advantage of model properties.