Indexability and Index Heuristics for a Simple Class of Inventory Routing Problems
Indexability and Index Heuristics for a Simple Class of Inventory Routing Problems
复制标题
DOI：
10.1287/opre.1070.0505
复制
发表时间：
2009-03
期刊：
影响因子：
--
通讯作者：
T. Archibald;Dan Black;K. Glazebrook
中科院分区：
文献类型：
--
作者：
T. Archibald;Dan Black;K. Glazebrook
我们利用和发展了惠特尔的不安分的强盗公式来分析一类简单的直接送货的库存路线问题。这些路径问题产生于供应商管理的库存补充的实践，并且涉及由能够监控整个网络的库存水平的决策者集中控制的库存保持位置集合的最优补充。我们从问题的拉格朗日松弛发展了位置可指标性的概念，并证明了(在温和的条件下)位置确实是可指标性的。因此，我们有一个封闭形式的地点指数集合，即库存水平的实值函数(每个地点一个)，它以一种自然的方式(即作为补给的公平费用)衡量每个地点每天送货的优先次序。我们讨论了如何使用这种位置指数来构造补货启发式算法，并在一个数值研究中对贪婪指数启发式算法进行了评估。对于每个地点的需求为泊松的情况，可以使用更简单的近似指数分析。这种分析允许更明确地描述保证(近似)位置可分度的持有成本率的范围。
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.