Efficient primal–dual heuristic for a dynamic location problem

Efficient primal–dual heuristic for a dynamic location problem

0.00 Avg rating0 Votes
Article ID: iaor20082186
Country: United Kingdom
Volume: 34
Issue: 6
Start Page Number: 1800
End Page Number: 1823
Publication Date: Jun 2007
Journal: Computers and Operations Research
Authors: , ,
Keywords: heuristics, programming: branch and bound
Abstract:

In this paper the dynamic location problem with opening, closure and reopening of facilities is formulated and an efficient primal–dual heuristic that computes both upper and lower limits to its optimal solution is described. The problem here studied considers the possibility of reconfiguring any location more than once over the planning horizon. This problem is NP-hard (the simple plant location problem is a special case of the problem studied). A primal–dual heuristic based on the work of Erlenkotter and Van Roy & Erlenkotter was developed and tested over a set of randomly generated test problems. The results obtained are quite good, both in terms of the quality of lower and upper bounds calculated, and in terms of the computational time spent by the heuristic. A branch-and-bound procedure that enables to optimize the problem is also described and tested over the same set of randomly generated problems.

Reviews

Required fields are marked *. Your email address will not be published.