Two Efficient Algorithms for Weighted P-Median Problem

Abstract

We propose a genetic algorithm for a weighted p-median problem. It is a facility location problem. The algorithm generates a good solution quickly. Computational tests were realized on five different tasks from 21 vertices to 100 vertices and from p-median from p=3 to p=6. The tests were performed 100 times on every task. There were created some modifications of these tasks for a proposed genetic algorithm.

The best solution generated by this algorithm is within 0.6% of the optimum for 80% of the tasks. The other 20% of the tasks is within 1.6% of the optimum. Time of realization is within 5.9 s.