Exact and Heuristic Algorithms for Solving Discrete Weber Problem for a Simple Cycle

R. E. Shangin

Sibirskij žurnal čistoj i prikladnoj matematiki, Tome 14 (2014) no. 2, pp. 98-107

Résumé

Here is set the exact and heuristic algorithms, which solves discrete Veber problem for simple cycle and finite set of location position. On a problem class, which was generated in a random way, the comparison of action period of a given algorithm and a model of integer linear programming, which was realized in IBM ILOG CPLEX, is carried out.

Détail

Keywords: location problem, Weber problem, simple cycle, exact algorithm, dynamic programming.
Mots-clés : heuristic algorithm

Bibliographie

[1] A. V. Panyukov, B. V. Pelzwerger, A. Yu. Shafir, “Optimal placement of fork points of the transport network on a digital terrain model”, Avt. i Telemech., 1990, no. 9, 153–162 (in Russian)

[2] Panyukov A. V., Pelzwerger B. V., “Polynomial Algorithms to Finite Veber Problem for a Tree Network”, J. of Computational and Applied Math., 35 (1991), 291–296 | DOI | MR | Zbl

[3] G. G. Zabudskiy, D. V. Filimonov, “About minimax and minisum problems of placement on networks”, Proc. of XII Baikal Int. Conf. “Optimization methods and their applications” (Omsk, 2001), 150–155 (in Russian)

[4] R. E. Shangin, “Deterministic algorithm for solving the Weber problem for $n$ sequentially connected chain”, Diskr. Analiz i Issl. Oper., 20:5 (2013), 84–96 (in Russian) | MR

[5] A. V. Panyukov, R. E. Shangin, “The exact algorithm for solving the discrete Weber problem for $k$-tree”, Diskr. Analiz i Issl. Oper., 21:3 (2014), 63–74 (in Russian)

[6] A. V. Panyukov, Models and methods for solving construction and identification of geometrical arrangement, Thes. Doc. Math.-Phys. Degree, M., 1999 (in Russian)

[7] S. A. Sergeev, “The quadratic assignment problem I”, Avt. i Telemech., 1999, no. 8, 127–147 (in Russian)

[8] R. E. Shangin, “Study of the effectiveness of approximate algorithms for solving a special case of the problem Weber”, Economics, Statistics and Informatics. Vestnik UMO, 2012, no. 1, 163–168 (in Russian)

[9] A. V. Panyukov, B. V. Pel'tsverger, “The optimal distribution of a tree in a finite set”, USSR Comp. Math. and Math. Phys., 28:2 (1988), 204–206 | DOI | MR | Zbl

[10] R. E. Shangin, “Development and analysis of algorithms for the Weber problem”, Optimization Problems and Economic Applications, Omsk, 2012, 121–122 (in Russian) | MR

[11] V. A. Trubin, “Efficient algorithm for the Weber problem with a rectangular metric”, Kibernetika, 1978, no. 6, 67–70 (in Russian) | MR

[12] Zabudsky G. G., Filimonov D. V., “An Algorithm for Minimax Location Problem on Tree with Maximal Distances”, Proc. of the $2^\text{nd}$ Int. Workshop “Discrete Optimization Methods in Production and Logistics”, DOM2004, 2004, 81–85

[13] D. V. Filimonov, “Solution of discrete minimax distribution problem on tree network”, Proc. of Sci. Sem. of Post-grad. Students, Omsk, 2003, 58–61 (in Russian)