Shipping multiple items by capacitated vehicles: An optimal dynamic programming approach

Shipping multiple items by capacitated vehicles: An optimal dynamic programming approach

0.00 Avg rating0 Votes
Article ID: iaor2006906
Country: United States
Volume: 39
Issue: 2
Start Page Number: 233
End Page Number: 248
Publication Date: May 2005
Journal: Transportation Science
Authors: ,
Keywords: inventory, programming: dynamic
Abstract:

We consider a system in which multiple items are transferred from a warehouse or a plant to a retailer through identical capacitated vehicles, or by identical freight wagons. Any mixture of the items may be loaded onto a vehicle. The retailer is facing dynamic deterministic demand for several items, over a finite planning horizon. A vehicle incurs a fixed cost for each trip made from the warehouse to the retailer. In addition, there exist item-dependent variable shipping costs and inventory holding costs at the retailer, which are both constant over time. The objective is to find a shipment schedule that minimizes the total cost, while satisfying demand on time. We address and partially resolve the question regarding the problem's complexity by introducing a dynamic programming algorithm whose complexity is polynomial for a fixed number of items, but exponential otherwise. Our dynamic programming formulation is based on properties satisfied by the optimal solution, and uses an innovative way for partitioning the problem into subproblems.

Reviews

Required fields are marked *. Your email address will not be published.