Algorithms for Finding an Approximate Solution for Locating Obnoxious Facilities on Networks

The problems of locating several obnoxious facilities on networks are studied. The facilities serve populated areas, but have a negative impact on the population. The negative impact decreases with increasing distance to the facilities. A mathematical model is given for an arbitrary number of the facilities. Approximate algorithms for solving of the problem for two facilities are developed. The original network is decomposed into two connected subnets. In each of the resulting subnet, the problem of locating one facility is solved using an exact algorithm. Calculations are performed on test examples for the shortest paths metric. For the case of network located on a plane, Euclidean metric and the shortest paths metric are used. Experiments to solve the problem on a road network of highways of France are conducted.