Abstract
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.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
A. Assad, B. Golden, R. Dahl and M. Dror, Design of an inventory routing system for a large propane-distribution firm,Proc. Southeastern TIMS Conf., Myrtle Beach (1982) p. 315.
A. Assad, B. Golden, R. Dahl and M. Dror, Evaluation of the effectiveness of an integrated system for fuel delivery,Proc. 1983 Southeastern TIMS Conf., ed. J. Eastman, Myrtle Beach (1983) p. 153.
W. Bell, L. Dalberto, M. Fisher, A. Greenfield, R. Jaikumar, P. Kedia, R. Mack and P. Prutzman, Improving the distribution of industrial gases with an on-line computerized routing and scheduling optimizer, Interfaces 13, 6(1983)4.
L. Bodin, B. Golden, A. Assad and M. Ball, Routing and scheduling of vehicles and crews: The state of the art, Computers & Operations Research 10, 2(1983)62.
N. Christofides and J. Beasley, The period routing problem, Networks 14, 2(1984)237.
G. Clarke and J. Wright, Scheduling of vehicles from a general depot to a number of delivery points, Oper. Res. 12(1964)568.
G. Dantzig and J. Ramser, The truck dispatching problem, Management Science 6(1959)81.
M. Dror, The inventory routing problem, Ph.D. Diss., College of Business and Management, University of Maryland (1983).
M. Dror and M. Ball, Inventory routing: Reduction from an annual to short period problem, Working Paper No. 167, Dept. of Management Sciences, University of Waterloo, Ontario, Canada (1985).
M. Dror and L. Levy, A vehicle routing improvement algorithm-comparison of a ‘greedy’ and a ‘matching’ implementation for inventory routing, Centre Recherche sur les Transports, Pub. No. 353 (1984).
A. Federgruen and P. Zipkin, A combined vehicle routing and inventory allocation problem, Oper. Res. 32(1984)1019.
M. Fisher and R. Jaikumar, A generalized assignment heuristic for vehicle routing, Networks 11, 2(1981)109.
B. Golden, T. Magnanti and H. Nguyen, Implementing vehicle routing algorithms, Networks 7, 2(1977)113.
B. Golden, A. Assad, M. Dror and R. Dahl, Planning a distribution system in the presence of routing and inventory subproblems, presented at ORSA/TIMS National Meeting, San Diego (1982).
L. Lasdon,Optimizing Theory for Large Systems (McMillan, 1970).
R. Russell and W. Igo, An assignment routing problem, Networks 9, 1(1979)1.
W.R. Stewart, New algorithms for deterministic and stochastic vehicle routing problems, Ph.D. Diss., College of Business and Management, University of Maryland (1981).
W.R. Stewart and B. Golden, Stochastic vehicle routing: A comprehensive approach, Eur. J. Oper. Res. 14(1983)371.
Author information
Authors and Affiliations
Additional information
Part of this work was performed while this author was visiting the University of Waterloo.
Rights and permissions
About this article
Cite this article
Dror, M., Ball, M. & Golden, B. A computational comparison of algorithms for the inventory routing problem. Ann Oper Res 4, 1–23 (1985). https://doi.org/10.1007/BF02022035
Issue Date:
DOI: https://doi.org/10.1007/BF02022035