An effective heuristic for the P-median problem with application to ambulance location

We consider the p-median problem which is to find the location of p-facilitiesso as to minimize the average weighted distance or time between demandpoints and service centers. Many heuristic algorithms have been proposed for thisproblem. In this paper we present a simple new heuristic which is effective formoderately size problem.The heuristic uses a reduction and an exchange procedure.Our methodology is tested on 400 randomly generated problems with 10 to 50customer locations as well as 6 well known literature test problems. We also compareour method with the Branch and Bound method in terms of quality and computationaltime using a larger problem size of 150 customer locations. For the random problemsthe generated solutions were on average within 0.61 % of the optimum. A similarresult was achieved for the literature test problems. A comparative analysis withliterature heuristics supports the superiority of our method. The computational time ofour heuristic is 0.75 % of the Branch and Bound Method. We also apply our heuristicto a case study involving the location of emergency vehicles (ambulances) in PerthCity (Australia).