|
Article Excerpt
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.
Area of review: Stochastic Models.
History: Received March 2007; revision received July 2007; accepted September 2007. Published online in Articles in Advance January 5, 2009.
1. Introduction
The classical work of Gittins (1979, 1989) on multiarmed bandit problems gave formal mathematical expression to the natural idea that many complex dynamic stochastic optimization problems have good (sometimes optimal) solutions that use state-based calibrations (indices) of the options facing the decision maker to assist in choosing between them. A recent survey describing a range of developments of Gittins' work is due to Mahajan and Teneketzis (2008).
One particularly important extension of Gittins' model was described by Whittle (1988). Whittle's restless bandit problems concern the development of rules for the optimal activation of collections of stochastic projects or bandits. In Whittle's model, M projects from a collection of size N (>M) are chosen for activation at each of a sequence of decision epochs. Projects may change state whether active or passive, though according to different dynamics. The innovation in Whittle's model was precisely the state evolution of passive projects, a phenomenon he called restlessness. Each project earns a state-dependent reward at each epoch. The goal of analysis is the determination of a policy or rule for project activation to maximise the average reward rate earned from all projects over an infinite horizon. Whittle's model is almost certainly intractable, having been shown to be PSPACE-hard by Papadimitriou and Tsitsiklis (1999). Whittle used a Lagrangian relaxation of his restless bandit problem to develop an index heuristic for the subclass of problems in which each constituent project passes an indexability test. Whittle's heuristic attaches an index to each project, namely, a real-valued function on that project's state space, and chooses for activation at each decision epoch the M projects with the largest index values. Ties are broken arbitrarily. Weber and Weiss (1990, 1991) established a form of asymptotic optimality for Whittle's heuristic under given conditions, while Nino-Mora (2001, 2002) and Glazebrook et al. (2002) have explored the issue of indexability. Further, Whittle's approach has been shown to give rise to strongly performing policies in a range of application domains. These include the control of service systems, investment problems, and the dynamic routing of jobs for service and machine maintenance. See, for example, Ansell et al. (2003), Glazebrook et al. (2005, 2006), and Glazebrook and Kirkbride (2007).
This current paper is, to the authors' knowledge, the first to apply index theory to problems concerning inventory routing. In [section]2, we describe an inventory routing problem (IRP) which arises from the developing practice of vendor-managed inventory replenishment. The latter term describes situations in which a central controller monitors inventory levels at several locations and makes decisions regarding inventory replenishment at those locations in the interests of the network as a whole. Surveys of research contributions to such problems can be found in Federgruen and Simchi-Levi (1995) and Kleywegt et al. (2002). The latter paper explains why the inventory routing problem with direct deliveries (IRPDD) in which the delivery trucks under the decision maker's control visit just a single location on each trip from a central depot is important. In [section]2, we describe a version of IRPDD in which, whenever a decision is made to replenish a particular location, it is replenished in full. Such a model has previously been considered by Barnes-Schuster and Bassok (1997). IRPs are extremely challenging and the solution methods proposed have often been complex and computationally demanding. In sharp contrast, this paper offers something simple and natural (albeit within a restricted class of models), namely, inventory control policies which are constructed by attaching an index to each location, a function of its current inventory level, with large indices indicating that the location concerned is a high priority for replenishment.
In [section]2, we develop and adapt Whittle's general approach to our IRP. We describe what it means that a location be indexable and, if so, how its index is defined. Some proposals are advanced concerning how index values can be used to construct heuristic policies for inventory replenishment. In [section]3, we show that in our problem, locations are guaranteed indexable when holding costs are ignored. We are able to infer that they remain indexable when holding cost rates are set at realistic levels. Location indices are given in closed form. For the important case of Poisson demands, we develop a simpler, but approximating, index analysis in [section]4. This approach allows us to formally specify a range of holding cost rates for which (approximate) indexability is achieved. The paper concludes in [section]5 with a numerical study in which index-based heuristic policies perform strongly.
2. The Model and Methodology
In our IRPDD, each of L locations holds supplies of an item. The inventory level of the item at each location is recorded at regularly spaced time epochs. These epochs will be referred to as "the beginning of each day" throughout the paper, although nowhere do we require the day to be our basic time unit. Once all L inventories have been inspected, a decision is made concerning which locations (if any) should be resupplied that day. The goal of decision making is to minimise a combination of inventory and delivery costs for the network. Further details are as follows:
(i) The daily demand for the item at location l is described by the probability mass function {[p.sub.jl], j [greater than or equal to] 0}, with [p.sub.jl] the probability that j items will be requested at location l in a single day. We use
[[lambda].sub.l] = [[infinity].summation over (j = 0)][jp.sub.jl]
for the mean of this distribution and refer to it as the demand rate at location l. Daily demands are assumed independent across locations and over time.
(ii) We assume that holding costs and shortage costs are incurred at each location with [h.sub.l] the holding cost rate (per item per day) and [[sigma].sub.l] the cost incurred whenever a demand cannot be met through a shortage at location l. There is no backlogging of demand.
(iii) During each day, M identical trucks are available to make deliveries. Each truck makes a series of round trips between the central depot and individual locations. Resupplying location l incurs a fixed cost [K.sub.l] together with a cost of [C.sub.l] per item supplied, takes total delivery time [[tau].sub.l] (an integer multiple of the time taken for a single round trip to l) and results in [S.sub.l] (the replenishment level) items being available to meet demand at location l the following day. We are here making simplifying modelling assumptions which cannot be met exactly in practice because of uncertainty in both the inventory level at a location at each delivery time and in the demand arising at a location in that part of the day which follows completion of each delivery. This could be overcome by a modelling approach which incorporated information on inter alia the timing of deliveries. Such an approach would involve major additional complexities and would, in our judgement, add little to the analysis. We also assume that delivered items are not available to meet demand at a location l until the beginning of the next day. Put briefly, we treat delivered items as though they arrived at the end of their day of delivery.
(iv) A set of locations will be said to be feasible if there exists a schedule of round trips to those locations which can be made by the trucks during a single day and which would guarantee a completed delivery to each. To identify a feasible set, we need to know, for each l, the time taken for a single round trip between the depot and location l ([t.sub.1]) and hence the number of visits to l to complete a delivery ([[tau].sub.l]/[t.sub.l]). Expressed differently, a set of locations is feasible if there exists an M-fold partition of the visits required to complete a delivery to each such that the visits in each partition set can be completed in one day by a single truck. We assume that each individual location constitutes a feasible set.
Please note that, throughout our numerical investigations, we take the cost parameters [h.sub.l], [[sigma].sub.l], and [C.sub.l] to be l-independent. However, this is not required for the theory.
We write [pi] for a general delivery policy, namely, a rule for choosing a feasible set of locations to be supplied each day. Our goal is to choose [pi] to minimise an aggregate cost rate
[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (1)
where in (1), [C.sub.l]([pi]) is the average cost rate (including the cost of deliveries to l and inventory costs) incurred at l over an infinite horizon. By the theory of stochastic dynamic programming (DP) (see, for example, Puterman 1994) we may restrict attention to the class of stationary delivery policies which make decisions on the basis of current inventory levels only. That said, direct application of DP for problems of realistic size (in particular, reasonable values of L) is not computationally possible. Our search is, therefore, for effective heuristic approaches.
We proceed in three steps, each of which involves...
|
