Article citationsMore>>

Melnikov, B. and Melnikova, E. (2022) On the Classical Version of the Branch and Bound Method. Computer Tools in Education, 2, 41-58.

has been cited by the following article:

• TITLE: On the “Onion Husk” Algorithm for Approximate Solution of the Traveling Salesman Problem

  AUTHORS: Mikhail E. Abramyan, Nikolai I. Krainiukov, Boris F. Melnikov

  KEYWORDS: Branch and Bound Method, Contour Algorithm, “Onion Husk” Algorithm, Simulated Annealing Method, Traveling Salesman Problem

  JOURNAL NAME: Journal of Applied Mathematics and Physics, Vol.12 No.4, April 30, 2024

  ABSTRACT: The paper describes some implementation aspects of an algorithm for approximate solution of the traveling salesman problem based on the construction of convex closed contours on the initial set of points (“cities”) and their subsequent combination into a closed path (the so-called contour algorithm or “onion husk” algorithm). A number of heuristics related to the different stages of the algorithm are considered, and various variants of the algorithm based on these heuristics are analyzed. Sets of randomly generated points of different sizes (from 4 to 90 and from 500 to 10,000) were used to test the algorithms. The numerical results obtained are compared with the results of two well-known combinatorial optimization algorithms, namely the algorithm based on the branch and bound method and the simulated annealing algorithm.