Abstract: Searching for cycling routes of minimum cost is an urgent task of transport nets designing, traffic flows routing, etc. Each locality, transport node can be the vertex of the graph, and each cut line, linking localities, − the edge of the graph. The edge’s cost represents distance, repair cost, channel bandwidth, circuit resistance, etc. If closed route reaches all vertexes of the graph exactly once, it is called Hamiltonian cycle (HC), and the task of searching for minimum cost is the Hamiltonian Traveling Salesman’s Problem (HTSP). HTSP is NP-hard and not always has a solution Майника, 1981. Algorithms delivering optimum to HTSP are described as an exhaustive search reduction. If restriction of visiting only once every vertex is taken off, then such task can be called Common Traveling Salesman Problem (CTSP). Besides completeness of the route is an additional restriction for this task. CTSP seems the generalization of HTSP Бондаренко, 2004. For every linked graph always the CTSP’s set of solutions is not empty, and it allows using approximate algorithms and heuristics. The authors have no data about exact methods, bringing optimum of closed CTSP. This article offers exact algorithm of CTSP solution, bringing the cycle of minimum cost, which includes all vertexes of the graph at least once and contains the less number of edges.

Keywords: TSP, Traveling Salesman Problem, Hamiltonian cycle, closed route, optimal route, exact algorithm.

ACM Classification Keywords: Algorithms, Theory.

Link:

CYCLE ROUTES OPTIMIZATION FOR NOT FULL GRAPH

Anatoly Panishev, Anton Levchenko

http://foibg.com/ibs_isc/ibs-19/ibs-19-p54.pdf