A revised formulation and two complementary optimization procedures for the two-echelon uncapacitated facility location problem

In both the private and public sectors, products commonly pass through multiple echelons of facilities as they flow from production plants to final consumers. A typical facility arrangement is to consolidate multiple products at central distribution centers (DCs). The DCs perform break bulk and product mixing operations, and supply district, market-oriented warehouses (WHSEs). The WHSEs in turn serve retailers or final consumer demands.; In general, a multi-echelon distribution system design must specify (1) the number of echelons in the distribution system, (2) the number and location of facilities at each echelon in the system, (3) the flow of product between facilities at the different echelon levels, and (4) the assignment of customers (retailers or consumers) to supplying facilities. The objective is to determine the least cost system design such that all demand is satisfied within acceptable delivery lead times.; This dissertation proposes a new mixed-integer programming (MIP) formulation and two branch-and-bound solution procedures for the two-echelon, uncapacitated facility location problem (TUFLP). The formulation is based on the observation that the problem can be represented as a fixed-charge arborescent network model. The new model captures the logical relationship between two levels of facilities and invites the development of efficient solution procedures which exploit the special mathematical structure of the problem.; A linear programming (LP) based branch-and-bound solution procedure is developed to solve the TUFLP and to examine the analytical properties of the problem formulation. The computational results show that the LP relaxations of the MIP are tight and possess strong integrality properties.; Also developed is a dual based branch-and-bound solution procedure which solves the TUFLP extremely fast. The excellent performance of the procedure is attributed to (1) the fixed-charge arborescent network representation of the problem; (2) the tight formulation of the network model; and (3) the effective heuristic solution procedures in deriving tight lower and upper bounds in the branch-and-bound solution process.; The research reported in this dissertation is an extension of previous work on the single-echelon and multi-echelon uncapacitated facility location problems. In addition to the theoretical advances in modeling and algorithm development, the new model and the solution procedures provide a fresh set of analytical tools to aid practitioners in solving large scale, complex, logistics system design problems.