Strategies for Online Inventory Routing Problem under Real-Time Information

Abstract

The inventory routing problem (IRP) under real-time information studied in this paper involves repeated delivery of products from a depot to a set of retailers that face stochastic demands over a long period. This system is controlled by a central decision maker who operates with real-time information about the complete state of the system. To address this online IRP under real-time information, rolling horizon approaches are proposed: plans are updated and solve a mixed integer programming formulation for the off-line version of the problem. In this mixed integer programming formulation, an incremental inventory cost (IIC) function is introduced to combine inventory and transportation costs in the same objective function. This IIC function takes into account additional inventory costs associated with serving a customer at a different time and refilling an amount different from that prescribed by the best inventory policy with fixed transportation costs. Three rolling horizon strategies for the real-time version are compared. These policies are based on repeated reoptimization of different instances of the offline IRP and differ in the number of steps that are implemented for current solutions and the events that trigger plan updates. These policies are compared with a benchmark policy of operating the system in a decentralized manner. The comparison is conducted with a general simulation framework. New replanning policies are shown to outperform systematically the benchmark policy under all scenarios considered.

Get full access to this article

View all access options for this article.

References

Regan

A. C.

Mahmassani

H. S.

and Jaillet

Improving the Efficiency of Commercial Vehicle Operations Using Real-Time Information: Potential Uses and Assignment Strategies. In Transportation Research Record 1493, TRB, National Research Council, Washington, D.C., 1995, pp. 188–198.

Rabah

and Mahmassani

H. S.

Impact of Information and Communication Technologies on Logistics and Freight Transportation: Example of Vendor-Managed Inventories. In Transportation Research Record: Journal of the Transportation Research Board, No. 1790, Transportation Research Board of the National Academies, Washington, D.C., 2002, pp. 10–19.

Thomas

D. J.

and Griffin

P. M.

Coordinated Supply Chain Management. European Journal of Operational Research, Vol. 94, 1996, pp. 1–15.

Campbell

Clarke

Kleywegt

A. J.

and Savelsbergh

M. W. P.

The Inventory Routing Problem. In Fleet Management and Logistics ( Crainic

T. G.

and Laporte

, eds.), Kluwer Academic Publishers, Dordrecht, Netherlands, 1998, chapt. 4.

Bell

J. B.

Dalberto

L. M.

Fisher

M. L.

Greenfield

A. J.

Jaikumar

Kedia

Mack

R. G.

and Prutzman

P. J.

Improving the Distribution of Gases with an On-line Computerized Routing and Scheduling Optimizer. Interfaces, Vol. 13, 1983, pp. 4–23.

Golden

Assad

and Dahl

Analysis of a Large Scale Vehicle Routing Problem with an Inventory Component. Large Scale Systems, Vol. 7, 1984, pp. 181–190.

Kleywegt

A. J.

Nori

V. S.

and Savelsbergh

M. W. P.

The Stochastic Inventory Routing Problem with Direct Deliveries. Transportation Science, Vol. 36, 2002, pp. 94–118.

Baita

Ukovich

Penseti

and Favaretto

Dynamic Routing and Inventory Problems: A Review. Transportation Research Part A, Vol. 32, No. 8 1998, pp. 585–598.

Regan

A. C.

Mahmassani

H. S.

and Jaillet

Dynamic Decision Making for Commercial Fleet Operations Using Real-Time Information. In Transportation Research Record 1537, TRB, National Research Council, Washington, D.C., 1996, pp. 91–97.

10.

Psaraftis

H. N.

Dynamic Vehicle Routing Problems. In Vehicle Routing: Methods and Studies ( Golden

B. L.

and Assad

A. A.

, eds.), Elsevier, Amsterdam, 1988, pp. 223–248.

11.

Psaraftis

H. N.

Dynamic Vehicle Routing: Status and Prospects. Annals of Operations Research, Vol. 61, 1995, pp. 143–164.

12.

Powell

W. B.

Jaillet

and Odoni

Stochastic and Dynamic Networks and Routing. In Handbooks in Operations Research and Management Science, Vol. 8, Network Routing ( Ball

M. O.

Magnanti

T. L.

Monma

C. L.

and Nemhauser

G. L.

, eds.), Elsevier, Amsterdam, 1995, pp. 141–296.

13.

Bertsimas

D. J.

and Simchi-Levi

A New Generation of Vehicle Routing Research: Robust Algorithms, Addressing Uncertainty. Operations Research, Vol. 44, No. 2 1996, pp. 286–304.

14.

Powell

W. B.

Dynamic Models of Transportation Operations. In Handbooks in Operations Research and Management Science, Vol. 11, Supply Chain Management ( Ball

M. O.

Magnanti

T. L.

Monma

C. L.

and Nemhauser

G. L.

, eds.), Elsevier, Amsterdam, 2003, pp. 677–756.

15.

Ichoua

Gendreau

and Potvin

J.-Y.

Diversion Issues in Realtime Vehicle Dispatching. Transportation Science, Vol. 34, No. 4 2000, pp. 426–438.

16.

Gendreau

Guertin

Potvin

J.-Y.

and Taillard

Parallel Tabu Search for Real-time Vehicle Routing and Dispatching. Transportation Science, Vol. 33, No. 4 1999, pp. 381–390.

17.

Larsen

The Dynamic Vehicle Routing Problem. Ph.D. dissertation. Technical University of Denmark, Lyngby, 2000.

18.

Yang

Jaillet

and Mahmassani

H. S.

On-line Algorithms for Truck Fleet Assignment and Scheduling Under Real-Time Information. In Transportation Research Record: Journal of the Transportation Research Board, No. 1667, TRB, National Research Council, Washington, D.C., 1999, pp. 107–113.

19.

Yang

Jaillet

and Mahmassani

H. S.

Real-Time Multivehicle Truckload Pickup and Delivery Problems. Transportation Science, Vol. 38, No. 2 2004, pp. 135–148.

20.

Kim

Jaillet

and Mahmassani

H. S.

Two-Phase Optimization Approaches to Solve Dynamic Large Fleet Management Problems. Working Paper, University of Texas at Austin, 2002.

21.

Axsáter, S. Inventory Control, 1st ed. Kluwer Academic Publishers, Dordrecht, Netherlands, 2000.

22.

Zipkin

P. H.

Foundations of Inventory Management, 1st ed. McGraw-Hill, New York, 1999.

23.

Wolff

R. W.

Stochastic Modeling and the Theory of Queues, 1st ed. Prentice Hall, Upper Saddle River, N.J., 1989.

24.

Zheng

and Federgruen

Finding Optimal (s, S) Policies Is About As Simple As Evaluating a Single Policy. Operations Research, Vol. 39, No. 4 1991, pp. 654–665.

25.

ILOG CPLEX 8.1 Reference Manual. ILOG, Gentilly, France, 2002.