Budget Constrained Location Problem with Opening and Closing of Facilities

UNCG Author/Contributor (non-UNCG co-authors, if there are any, appear on document)
Joyendu Bhadury, Associate Dean - Graduate Programs and Research (Creator)
Institution
The University of North Carolina at Greensboro (UNCG )
Web Site: http://library.uncg.edu/

Abstract: In this paper, we study a budget constrained location problem in which we simultaneously consider opening some new facilities and closing some existing facilities. Motivations for this problem stem from applications where, due to a change in the distribution of customer demand, the existing facility system no longer provides adequate service. The objective is to minimize the total weighted travel distance for customers subject to a constraint on the budget for opening and/or closing facilities and a constraint on the total number of open facilities desired. For this problem, we develop a mathematical programming model and examine its theoretical properties. We then develop three heuristic algorithms (greedy interchange, tabu search and Lagrangian relax-ation approximation) for this NP-hard problem. Computational testing of these algorithms includes an analysis of the sensitivity of the solution to the budget and the desired number of facilities. The intended application in this testing is that of locating/relocating bank branches in a large-size town such as in our data set from Amherst, New York. We also discuss the situation where operating costs are part of the objective function.

Additional Information

Publication
Computers and Operations Research, Vol. 30, 2047-2069 (2003) doi:10.1016/S0305-0548(02)00123-5
Language: English
Date: 2003
Keywords
Facility location, Greedy algorithm, Lagrangian relaxation, Tabu search