# Questions tagged [traveling-salesman]

The Traveling Salesman Problem and variants

66 questions with no upvoted or accepted answers
Filter by
Sorted by
Tagged with
721 views

### How can the shortest traveling salesman tour be found in $O(2^n poly(n))$ time and less than exponential space?

I'm stuck on problem 9.4 from The Nature of Computation which reads: Dynamic Salesman. A naive search algorithm for TSP takes $O(n!)$ time to check all tours. Use dynamic programming to reduce this ...
• 1,038
141 views

### NP-hardness of a special traveling salesman problem

Consider we have $n$ vertices, $v_1,\ldots,v_n$. We have two positive values $(a_i,b_i)$ associated with each $v_i$. The edge weight $w(v_iv_j)=a_ia_j+b_ib_j$. Is it NP-hard to solve the traveling ...
• 3,023
451 views

### How to apply ant colony optimization to the TSP but repeating nodes and edges

I'm learning the Ant Colony Optimization Algorithm and I would like to apply it to a variation of the TSP problem (find the path that start from a node, crosses all nodes and finish in the initial ...
• 101
114 views

### Minimum spanning tree and Hamiltonian path

For a graph $G(V,E)$, under what conditions is a minimum spanning tree of $G$ equal to a hamiltonian path on $G$? IS there any body of literature connecting these two?
2k views

### Are there current benchmarks for algorithms solving Travelling Salesman?

I'm researching the travelling salesman problem and looking for data regarding the current state of affairs regarding solutions and performance. So far the only data I've states that the current ...
• 374
130 views

### What is this prize-collecting optimization problem with travel times?

There exist very rich literature on discrete optimization problems such as variants of knapsack problem, traveling salesman problem, orienteering problem, tourist trip design problem and etc. Recently,...
119 views

### Planar TSP: no node insertion?

Since planar TSP with n nodes is NP-hard, we cannot simply find an optimal solution with n-1 nodes and then insert the remaining node at one of the solution's edges to find the optimal solution of the ...
• 2,385
64 views

### Heuristics to Find Circuits Allowing for Vertex Revists

I'm currently working on a project discussing applications of the Delaunay Triangulation, and the primary use-case is applications to TSP (or relaxations of the problem). See: http://www.lancaster....
• 81
388 views

### Finding partial traveling salesman path of specified length

For a given set of nodes, I can find optimal paths that visit all nodes using various traveling salesman algorithms. As a subset of this problem, I would like to be able to find shortest partial ...
57 views

### Why should 3-Opt be used over 2-opt for solving TSP?

I know the working of 2-opt and 3-opt local search algorithm. But I could not find any example where solution improvement is not possible using 2-opt but 3-opt. I am looking for a proper explanation ...
• 121
149 views

### Shortest route through ordered points

My algorithm-fu is really weak and I do not know how to express following problem in terms of any other problem known to me: Given a small rectilinear grid and coordinates of four cells in this grid (...
• 151
25 views

235 views

### Travelling salesman problem with detours

I am interested if there exists a following version of the travelling salesman problem: INSTANCE: A finite set $C = \{1,2,\dots,k\}$ of cities, a positive integer distance $\delta(i,j)$ for each pair ...
• 337
1 vote
44 views

### Do all NP-Complete problems run in $O(c^n)$ time, as opposed to $O(c^{n^k})$?

According to the Wiki article on NP-Completeness, NP-Complete problems can be solved in $O(c^{n^k})$ time (I'll call this EXP-POLY time). However, shouldn't the bound on all their run times be the ...
• 441
1 vote
28 views

### Bounding function for Travelling Salesman Problem

I have been studying the Branch and Bound paradigm. I came across an approach to solve the Travelling Salesman Problem using branch and bound where a specific kind of bounding function was used. I've ...
• 11
1 vote
64 views

• 101
60 views

### Traversal algorithm for an optimal item collecting route in the game "Eternal Return: Black Survival"

I am currently trying to implement a algorithm for the game "Eternal Return: Black Survival" as a kind of exercise in Rust. Since the game may not be familiar to many, here is a quick ...