Pseudogeometric version of the traveling salesman problem, its application in quantum physics models and some heuristic algorithms for its solution. (English) Zbl 07924226
Vlachos, Dimitrios (ed.), Mathematical modeling in physical sciences. 12th IC-MSQUARE, Belgrade, Serbia, August 28–31, 2023. Cham: Springer. Springer Proc. Math. Stat. 446, 391-401 (2024).
Summary: The geometric version of the traveling salesman problem (TSP) has been extensively studied, leading to the development of various approaches for solving its special cases. However, these algorithms often fall short when applied to problems beyond the geometric TSP. In this paper, we explore the pseudo-geometric TSP version, a generalization of the geometric TSP, and propose an adapted geometric algorithm for solving its specific instances. We leverage the knowledge of error bounds to estimate the reconstruction error of the TSP solution even when using geometric approaches for the pseudo-geometric TSP. This allows us to achieve reliable results despite uncertainties or noise in the data. We provide a concise description of our algorithmic adaptation and present the results of computational experiments to demonstrate its effectiveness.
For the entire collection see [Zbl 1541.00044].
For the entire collection see [Zbl 1541.00044].
MSC:
| 90C27 | Combinatorial optimization |
| 90C59 | Approximation methods and heuristics in mathematical programming |
| 65D25 | Numerical differentiation |
| 68N15 | Theory of programming languages |
| 68Q25 | Analysis of algorithms and problem complexity |
| 90B10 | Deterministic network models in operations research |
Keywords:
mathematical model; Hamilton cycles; traveling salesman problem; pseudo-geometric version; geometric approach; heuristic algorithmsReferences:
| [1] | Garey, M., Johnson, D.: Computers and Intractability. W. H. Freeman and Company, USA (1979), 388 p · Zbl 0411.68039 |
| [2] | Hromkovič, J.: Theoretical Computer Science. An Introduction to Automata, Computability, Complexity, Algorithmics, Randomization, Communication, and Cryptography. Springer (2003), 321 p |
| [3] | Hromkovič, J.: Algorithmics for Hard Problems. Introduction to Combinatorial Optimization, Randomization, Approximation, and Heuristics. Springer, Berlin (2003), 538 p |
| [4] | Gutin G., Punnen A. (eds.): The Traveling Salesman Problem. Kluwer Academic Publishers, Boston (1997), 856 p |
| [5] | Melnikov, B., Multiheuristic approach to discrete optimization problems, Cybern. Syst. Anal., 42, 3, 335-341, 2006 · Zbl 1119.90045 · doi:10.1007/s10559-006-0070-y |
| [6] | Melnikov B., Radionov A., Gumayunov V.: Some special heuristics for discrete optimization problems. In: Proceedings of 8th International Conference on Enterprise Information Systems, ICEIS-2006, pp. 360-364 |
| [7] | Melnikov, B.; Romanov, N., Once again about heuristics for the traveling salesman problem, Theor. Probl. Inform. Expansions, 4, 81-92, 2001 |
| [8] | Liew, S.: Introducing Convex Layers to the Traveling Salesman Problem. Preprint: arXiv:1204.2348 (2012) (Internet resource) |
| [9] | Somhom, S.; Modares, A.; Enkawa, T., Competition-based neural network for the multiple travelling salesmen problem with minimax objective, Comput. Oper. Res., 26, 4, 395-407, 1999 · Zbl 0940.90016 · doi:10.1016/S0305-0548(98)00069-0 |
| [10] | Korostensky, C., Gonnet, G.: Near optimal multiple sequence alignments using a travelling salesman problem approach. In: String Processing and Information Retrieval Symposium & International Workshop on Groupware (1999), pp. 105-114 |
| [11] | Melnikov, B., Panin, A.: On a parallel implementation of the multi-heuristic approach in the problem of comparison of genetic sequences Vektor Nauki of Togliatti State University (2012), vol. 4, no. 22, pp. 83-86 (in Russian) |
| [12] | Makarkin, S.; Melnikov, B.; Panin, A., On the metaheuristics approach to the problem of genetic sequence comparison and its parallel implementation, Appl. Math., 4, 10, 35-39, 2013 · doi:10.4236/am.2013.410A1006 |
| [13] | Melnikov, B.: An algorithm for proving the equivalence of the infinite iteration of finite languages. Vestnik of Moscow University. Series 15: Computing Mathematics and Cybernetics (1996), no. 4, pp. 49-53 (in Russian) |
| [14] | Melnikov, B.; Kashlakova, E., Some grammatical structures of programming languages as simple bracketed languages, Informatica (Lithuania), 11, 4, 441-453, 2000 · Zbl 0974.68027 |
| [15] | Korostensky, C.; Gonnet, G., Using traveling salesman problem algorithms for evolutionary tree construction, Bioinformatics, 16, 619-627, 2000 · doi:10.1093/bioinformatics/16.7.619 |
| [16] | Hanke, M.; Scherzer, O., Inverse problems light: numerical differentiation, Am. Math. Mon., 108, 512-521, 2001 · Zbl 1002.65029 · doi:10.1080/00029890.2001.11919778 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
