Solving Weber Problem on Plane with Minimax Criterion and Forbidden Gaps

Abstract

Location problems of various facilities are a wide class of operations research. The variety of statements of location problems is depends on the area in which are to be placed facilities and various restrictions and types of criteria. Important subclass of location problems of the interconnected facilities is the Weber problem. Two criteria of optimality are considered: minimization of total cost of communications between facilities or minimization of the maximum communication cost. Minimax Weber problem with a rectangular metrics is researched by J. G. Morris, R. L. Francis and T. Ichimori. In this paper, the problem of optimum location of facilities on the plane with the fixed facilities located on it and the rectangular forbidden gaps, with the borders parallel to axes of coordinates is considered. The located facilities are connected among themselves and with fixed facilities. The criterion is minimization of the maximum cost of communications between all facilities. Location in forbidden gaps is not allowed. The rectangular metrics is used. Properties of the problem, model of integer linear programming with Boolean variables are described. It is proved that it is sufficient to consider a subset of admissible solutions to find the optimum. Three variants of branch and bounds algorithm with different lower bounds on the goal function are developed. Computational experiment on comparison of efficiency of one of these algorithms and the IBM ILOG CPLEX is presented. Usage of the obtained property is perspective both in combinatorial methods as well as in integer programming methods for solving the problem.

Keywords

• location problem
• integer programming
• minimax Weber problem
• forbidden gaps
• algorithm branch and bounds