Abstract: p-median problem is a classical model in facility location and it has vast applications in related areas such as transportation and logistics. An extended p-median problem is investigated in this paper, in which the number of facilities to be located is uncertain and an investment constraint is considered. This makes the extended problem more applicable in the real lifes. Three heuristics are proposed for solving this extended p-median problem: the first is a simple heuristic algorithm; the second is a variable neighborhood search algorithm; and the third is an improved genetic algorithm. Experimental results show that the variable neighborhood search algorithm and the improved genetic algorithm are efficient for solving this problem.

Key words: operations research, facility location, extended p-median problem, variable neighborhood search algorithm, improved genetic algorithm