A tabu search heuristic for redesigning a multi-echelon supply chain network over a planning horizon

This paper addresses the problem of redesigning a supply chain network with multiple echelons and commodities. The problem belongs to a comprehensive class of network redesign problems previously introduced in the literature. Redesign decisions comprise the relocation of existing facilities to new sites under an available budget over a finite time horizon, the supply of commodities by upstream facilities, the inventory levels at storage facilities, and the flow of commodities through the network. The problem is modeled as a large-scale mixed-integer linear program. Feasible solutions are obtained by using a tabu search procedure that explores the space of the facility location variables. The latter prescribe the time periods in which changes in the network configuration occur. They are triggered by the setup of new facilities, which operate with capacity transferred from the existing facilities, and by closing the latter upon their entire relocation. As the problem is highly constrained, infeasible solutions with excess budget are allowed during the course of the search process. However, such solutions are penalized for their infeasibility. Computational experiments on realistically sized randomly generated instances indicate that this strategic oscillation scheme used in conjunction with tabu search performs very well. (C) 2011 Elsevier B.V. All rights reserved.