Maximin and Maxisum Network Location Problems with Various Metrics and Minimum Distance Constraints

The paper considers the problems of locating a facility on a road network connecting several settlements. The facility services the settlements, but has adverse effects on the population. The effects decrease as the distance from the facility to the settlements decreases. The study is conducted on the problems with criteria for maximizing the minimum distance from the facility to the nearest settlement (maximin) and maximizing the sum of distances from the facility to the settlements (maxisum). Constraints are imposed on the minimum feasible distances from the settlements to the facility and a budget for transportation costs for servicing the settlements by the facility. Euclidean metric is applied in objective functions and in constraints on minimum feasible distances. The shortest path metric is used to calculate transportation costs. Polynomial algorithms for searching all local optima of the problems are proposed.