Fraunhofer-Gesellschaft

Publica

Hier finden Sie wissenschaftliche Publikationen aus den Fraunhofer-Instituten.

A primal decomposition scheme for a dynamic capacitated phase-in/phase-out location problem

 
: Melo, M.T.; Saldanha da Gama, F.; Silva, M.M.
: University of Lisbon, Operations Research Center -CIO-

:
Fulltext (PDF; )

Lissabon: CIO, 2005, 25 pp.
CIO - Working Paper, 9/2005; ITWM-Berichte
English
Report, Electronic Publication
Fraunhofer ITWM ()

Abstract
We consider a dynamic capacitated facility location problem. Given a set os customers with known demands for a single product, a set of facilities operating at the beginning of the planning horizon, and a set of potential sites to locate new facilities, the objective is to find the location-allocation plan that minimizes the overall costs and satisfies the customer demands without violating the finite capacitite of the operating facilities. The problem is modelled as a mixed integer linear program with binary variables associated with location decisions, that is, phase-in (phase-out) of new (existing) facilitiers, and continuous variables representing the distribution flows from the facilities to the customers. These two different types of decisions lead to a natural separation of the variables, thereby making the problem an attractive candidate for applying a decomposition technique. We propose a method based on primal Benders decomposition, and improve its performance not only by introducing valid inequalities that tighten the lower bound of the linear relaxation but also by developing a heuristic approach that strenghten the usual Benders cuts. For randomly generated problem instances, the computational results show that the new Benders algorithm clearly outperforms standard mathematical programming software, thus making the method attractive for decision-makers who can use it as a tool to redesign their logistics networks and evaluate the impact of alternative network configurations.

: http://publica.fraunhofer.de/documents/N-51862.html