Heuristics for multiple facility location in a network using the variance criterion

In cyclic networks the p-variance location problem is NP-hard, and therefor e it is suitable to use heuristic methods to find approximate solutions to the problem. To this end two strategies are explored the first using combin atorial search procedures over the Vertex set, whereas the second searches for the solution over the entire network. The initial vertex set solutions are generated by using tabu search, variable neighbourhood search and inter change procedures. The heuristics have been tested on instances of up to 30 vertices and 70 edges, and their performances compared.