This Article Full Text (PDF) References Alert me when this article is cited Alert me if a correction is posted Services Email this article to a friend Similar articles in this journal Alert me to new issues of the journal Download to citation manager Citing Articles Citing Articles via Google Scholar Google Scholar Articles by Archibald, T. W. Articles by Glazebrook, K. D. Search for Related Content

Indexability and Index Heuristics for a Simple Class of Inventory Routing Problems

Management School, University of Edinburgh, Edinburgh, EH8 9JY, United Kingdom
Management School, Lancaster University, Lancaster, LA1 4YX, United Kingdom
Management School, Lancaster University, Lancaster, LA1 4YX, United Kingdom
t.archibald{at}ed.ac.uk
dan.black{at}lancaster.ac.uk
k.glazebrook{at}lancaster.ac.uk

We utilise and develop Whittle's restless bandit formulation to analyse a simple class of inventory routing problems with direct deliveries. These routing problems arise from the practice of vendor-managed inventory replenishment and concern the optimal replenishment of a collection of inventory holding locations controlled centrally by a decision maker who is able to monitor inventory levels throughout the network. We develop a notion of location indexability from a Lagrangian relaxation of the problem and show that (subject to mild conditions) the locations are indeed indexable. We thus have a collection of location indices in closed form, namely, real-valued functions of the inventory level (one for each location), which measure in a natural way (namely, as a fair charge for replenishment) each location's priority for inclusion in each day's deliveries. We discuss how to use such location indices to construct heuristics for replenishment and assess a greedy index heuristic in a numerical study where it performs strongly. A simpler approximate index analysis is available for the case in which the demand at each location is Poisson. This analysis permits a more explicit characterisation of the range of holding cost rates for which (approximate) location indexability is guaranteed.

Subject classifications: dynamic programming/optimal control; applications; models; inventory/production; policies; probability; stochastic model applications.
History: Received March 2007; revision received July 2007; accepted September 2007.