Algorithms for dynamic and stochastic logistics problems
Vijay S. Nori, Anton J. Kleywegt, Martin W. P. Savelsbergh · SMARTech Repository (Georgia Institute of Technology) · 1999
In this thesis we study approaches for dynamic decision making under uncertainty in the context of two important problems in logistics. Electric utilities in the United States charge industrial users for the electricity that they use, based on the total amount of electricity consumed, as well as the peak usage rate. Consider a manufacturing company where work with different deadlines arrives over time, and has to be processed using purchased electricity, which is the major cost component. The goal is to minimize the cost of completing all the work before its deadline, by dynamically scheduling the work so that the maximum amount of electricity purchased at any time during the planning period is minimized. The online resource minimization problem (ORMP) addresses this problem and is studied in the first part of this thesis. We develop policies for the ORMP, known as online policies, which decide on the amount of electricity to be purchased at any time based on the amount of work remaining to be processed at that time. Vendor managed inventory (VMI) replenishment is a business practice in which vendors monitor their customers' inventories, and decide when and how much inventory should be replenished. The stochastic inventory routing problem (SIRP), studied in the second part of this research, addresses the coordination of inventory management and transportation, and needs to be solved for implementing a VMI strategy. The goal is to maximize profit (revenue minus cost) for the vendor by determining at any time the customers who should be visited, the amount of product to be delivered and the sequence in which they should be visited. We formulate the SIRP as a Markov decision process, which is hard to solve optimally if a large number of customers are involved. Approximation methods are proposed which involve (i) developing an approximate value function based on a decomposition of the problem, (ii) developing an efficient randomized approach to estimate an expected value, and (iii) developing efficient ways to determine the action in a state. Computational results are presented to show that the proposed methods help in finding good solutions with reasonable computational effort.