Warehouse Allocation Problem

MANAGEMENT SCIENCE Vol 20, No, 5, January, 1974 Printed in U.S.A.

BENDERS

'

t

A, M, GEOFFRION AND G, W, GRAVES! University of California, Los Angeles A commonly occurring problem in distribution system design is the optimal location of intermediate distribution facilities between plants and customers, A multicommodity capacitated single-period version of this problem is formulated as a mixed integer linear program, A solution technique based on Benders Decomposition is developed, implemented, and successfully applied to a real problem for ai major food firm with 17 commodity classes, 14 plants, 45 possible distribution center sites, and 121 customer zones. An essentially optimal solution was found and proven with a surprisingly small number of Benders cuts. Some discussion is given concerning why this problem class appears to be so amenable to solution by Benders' method, and also concerning what we feel to be the proper professional use of the present computational technique,

1. Introduction

1,1 The Model

The simplest version of the problem to be modeled is this. There are several commodities produced at several plants with known production capacities. There is a known demand for each commodity at each of a number of customer zones. This demand is satisfied by shipping via regional distribution centers (abbreviated DC), with each customer zone being assigned exclusively to a single DC, There are lower as well as upper bounds on the allowable total annual throughput of each DC. The possible locations for the DCs are given, but the particular sites to be used are to be selected so as to result in the least total distribution cost. The DC costs are expressed as fixed charges (imposed for the sites actually used) plus a linear variable charge. Transportation costs are taken to be linear. Thus the problem is to determine which DC sites to use, what size DC to have at each selected site, what customer zones should be served by each DC, and what the pattern of...