Premium
A dual‐based optimization procedure for the two‐echelon uncapacitated facility location problem
Author(s) -
Gao LiLian,
Robinson E. Powell
Publication year - 1992
Publication title -
naval research logistics (nrl)
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.665
H-Index - 68
eISSN - 1520-6750
pISSN - 0894-069X
DOI - 10.1002/1520-6750(199203)39:2<191::aid-nav3220390205>3.0.co;2-t
Subject(s) - facility location problem , 1 center problem , mathematical optimization , generalization , computer science , heuristic , dual (grammatical number) , location model , integer (computer science) , integer programming , product (mathematics) , extension (predicate logic) , operations research , mathematics , art , mathematical analysis , literature , programming language , geometry
The two‐echelon uncapacitated facility location problem (TUFLP) is a generalization of the uncapacitated facility location problem (UFLP) and multiactivity facility location problem (MAFLP). In TUFLP there are two echelons of facilities through which products may flow in route to final customers. The objective is to determine the least‐cost number and locations of facilities at each echelon in the system, the flow of product between facilities, and the assignment of customers to supplying facilities. We propose a new dual‐based solution procedure for TUFLP that can be used as a heuristic or incorporated into branch‐and‐bound procedures to obtain optimal solutions to TUFLP. The algorithm is an extension of the dual ascent and adjustment procedures developed by Erlenkotter for UFLP. We report computational experience gained by solving over 420 test problems. The largest problems solved have 25 possible facility locations at each echelon and 35 customer zones, implying 650 integer variables and 21,875 continuous variables.