A Case Study of Joint Online Truck Scheduling and Inventory Management for Multiple Warehouses∗

C. Helmberg† S. R¨ohl‡

January 2005

IM18

Abstract

For a real world problem — transporting pallets between warehouses in order to guarantee sufficient supply for known and additional stochastic demand — we propose a solution approach via convex relaxation of an integer programming formulation, suitable for online optimization.

The essential new element linking routing and inventory management is a convex piecewise linear cost function that is based on minimizing the expected number of pallets that still need transportation.

For speed, the convex relaxation is solved approximately by a bundle approach yielding an online schedule in 5 to 12 minutes for up to 3 warehouses and 40000 articles; in contrast, computation times of state of the art LP-solvers are prohibitive for online application.

In extensive numerical experiments on a real world data stream, the approximate solutions exhibit negligible loss in quality; in long term simulations the proposed method reduces the average number of pallets needing transportation due to short term demand to less than half the number observed in the data stream.

Keywords:

Convex relaxation, integer programming, stochastic demand, network models, large scale problems, bundle method, logistics, vehicle routing MSC 2000: 90B06; 90C06, 90C90, 90B05