Solving Weber Problem on Plane with Minimax Criterion and Forbidden Gaps

G. G. Zabudsky   ; N. S. Veremchuk

The Bulletin of Irkutsk State University. Series Mathematics, Tome 9 (2014), pp. 10-25

Résumé

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.

Détail

Keywords: location problem, integer programming, minimax Weber problem, forbidden gaps, algorithm branch and bounds.

Bibliographie

[1] Zabudsky G. G., “About Minimax and Minsum Location Problems on Plane with Forbidden Gaps”, Materials of 13th Baikal International Triannual School-Seminar “Methods of Optimization and Their Applications” (Irkutsk, 2005), v. 1, 455–460 (in Russian)

[2] Zabudskii G. G., “Model Building and Location Problem Solving in a Plane with Forbidden Gaps”, Automation and Remote Control, 67:12 (2006), 1986–1990 | DOI | MR | Zbl

[3] Zabudskii G. G., Amzin I. V., “Search Region Contraction of the Weber Problem Solution on the Plane with Rectangular Forbidden Zones”, Automation and Remote Control, 73:5 (2012), 821–830 | DOI | MR | Zbl

[4] Zabudsky G. G., Veremchuk N. S., “Minimax Weber Problem on Plane with Forbidden Gaps”, Materials of International conference “Discrete Optimization and Operations Research”, Institute of mathematics, Novosibirsk, 2013, 123 (in Russian)

[5] Zabudsky G. G., Veremchuk N. S., “Solving Minimax Weber Problem on Plane with Forbidden Gaps”, Materials of 16th Baikal International Triannual School-Seminar “Methods of Optimization and Their Applications” (Irkutsk, 2014), 54 (in Russian)

[6] Preparata P., Shamos M., Computational Geometry: an Introduction, Springer-Verlag, 1985, 478 pp. | MR | MR | Zbl

[7] H. V. Dearing, R. L. Francis, “A Network Flow Solution to a Multifacility Minimax Location Problem Involving Rectilinear Distances”, Transportation Science, 8 (1974), 126–141 | DOI | MR

[8] T. Ichimori, “A Shortest Path Approach to a Multifacility Minimax Location Problem with Rectilinear Distances”, Journal of the Operation Research Society of Japan, 1985, no. 4, 269–284 | MR | Zbl

[9] K. Klamroth, Single-Facility Location Problems with Barriers, Springer Series in Operation Research, 2002, 197 pp. | MR

[10] J. G. Morris, “A Linear Programming Approach to the Solution of Constrained Multi-Facility Minimax Location Problems Where Distances are Rectangular”, Operation Research Quarterly, 24 (1973), 419–435 | DOI | Zbl