Neighborhood Search Heuristicsfor the Uncapacitated Facility Location Problem

Diptesh Ghosh ()

No WP2002-01-01, IIMA Working Papers from Indian Institute of Management Ahmedabad, Research and Publication Department

Abstract: The uncapacitated facility location problem is one of choosing sites among a set of candidates in which facilities can be located, so that the demands of a given set of clients are satisfied at minimum costs. Applications of neighborhood search methods to this problem have not been reported in the literature. In this paper we first describe and compare several neighborhood structures used by local search to solve this problem. We then describe neighborhood search heuristics based on tabu search and complete local search with memory to solve large instances of the uncapacitated facility location problem. Our computational experiments show that on medium sized problem instances, both these heuristics return solutions with costs within 0.075% of the optimal with execution times that are often several orders of magnitude less than those required by exact algorithms. On large sized instances, the heuristics generate low cost solutions quite fast, and terminate with solutions whose costs are within 0.0345% of each other.

Date: 2002-01-01
References: Add references at CitEc
Citations:

There are no downloads for this item, see the EconPapers FAQ for hints about obtaining it.

Related works:
Journal Article: Neighborhood search heuristics for the uncapacitated facility location problem (2003)
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:iim:iimawp:wp00001

Access Statistics for this paper

More papers in IIMA Working Papers from Indian Institute of Management Ahmedabad, Research and Publication Department Contact information at EDIRC.
Bibliographic data for series maintained by ().