Questions tagged [traveling-salesman]

The Traveling Salesman Problem and variants

66 questions with no upvoted or accepted answers
Filter by
Sorted by
Tagged with
9 votes
0 answers
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 ...
user avatar
6 votes
0 answers
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 ...
user avatar
  • 3,023
5 votes
0 answers
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 ...
user avatar
  • 101
5 votes
0 answers
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?
user avatar
5 votes
1 answer
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 ...
user avatar
  • 374
4 votes
0 answers
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,...
user avatar
3 votes
0 answers
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 ...
user avatar
3 votes
0 answers
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....
user avatar
  • 81
3 votes
0 answers
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 ...
user avatar
2 votes
0 answers
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 ...
user avatar
  • 121
2 votes
0 answers
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 (...
user avatar
  • 151
2 votes
0 answers
25 views

Partial TSP in Euclidian plane

I'm interested in the following variant of Travelling Salesman Problem sometimes called Partial TSP. I'm particulary interested in the euclidian version : Input : A set $\{x_1,\dots,x_n\}\subset \...
user avatar
2 votes
1 answer
2k views

Using 2-opt Heuristic in a Genetic Algorithm for TSP

I read few papers while trying to find some better approachs to solve the TSP (Traveling salesman problem) as close to the optimal solution as possible. I implemented a Improved Greedy Crossover (...
user avatar
  • 123
2 votes
0 answers
38 views

Dividing a set of goals among two search agents

Say we had two agents and we want them both to traverse a map concurrently. Their goal is to collectively visit a collection of certain points on the map. If there was just one agent, it would be ...
user avatar
  • 23
2 votes
0 answers
319 views

Why shortcutting euler circuit creates a hamilton circuit in Christofides algorithm

In step 6 of the Christofides algorithm it is implicitly suggested that there is an invarient that the euler circuit can always be shortcutted to an hamilton circuit, what exactly assures us that? e.g ...
user avatar
  • 355
2 votes
0 answers
51 views

Bead-tiling algorithm for Dubins' TSP

I'm confused about how the bead-tiling algorithm for the Dubins' TSP from this article works: On the Dubins Traveling Salesperson Problems: novel approximation algorithms Ketan Savla, Emilio ...
user avatar
2 votes
0 answers
1k views

Travelling Salesman Problem with unknown shortest paths between nodes

I have a Travelling Salesman Problem, where I want to retrieve the "shortest" (approximate solution) circuit including the nodes n_1..n_n in a graph. The graph, however, includes a second set of nodes,...
user avatar
2 votes
0 answers
296 views

Min-weight bipartite matching in Christofides' algorithm

Content: The Christofides algorithm finds a minimum spanning tree, then finds all the odd degree vertices, and adds extra edges using a minimum weight bipartite matching on those odd vertices to make ...
user avatar
  • 171
2 votes
0 answers
68 views

Algorithm to collect items before they expire

I thought about the following problem: There are goods $\mathbb{G} = (g_1, \dots, g_k)$ on the line. Coordinates are expressed in meters and sorted in increasing order. All goods have different ...
user avatar
2 votes
0 answers
292 views

Ideas on reducing Traveling Salesman to Metric Traveling Salesman?

I want to show a polynomial reduction from TSP to Metric TSP. I know the rule is: $(G, k) \in TSP \iff (G', k') \in MTSP$ where $G$ is some graph, and $k$ is some bound. It seems like whatever I map $...
user avatar
2 votes
0 answers
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 ...
user avatar
  • 337
1 vote
0 answers
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 ...
user avatar
  • 441
1 vote
0 answers
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 ...
user avatar
  • 11
1 vote
1 answer
64 views

Reducing euclidean TSP of smaller size to euclidean TSP of bigger size

Assume I have a euclidean TSP solver that is optimal, but it can only solve inputs with exactly $N$ vertices. Let's call it the N-solver. Now, I have an input with $K$ vertices in the 2D plane, where $...
user avatar
1 vote
0 answers
56 views

combination of traveling salesman with knapsack

I am trying to create an optimisation process for a variant of the travelling salesman problem which is combined with a knapsack problem in the following way: Let there be a set of points $P$ on a two-...
user avatar
  • 111
1 vote
0 answers
41 views

Using circles to determine shortest path in tsp

New to tsp and christofide algorithm pls help What if instead of using a spanning tree as described in christofide algorithm we use two or more intersecting circles of the input points to determine ...
user avatar
1 vote
0 answers
57 views

Does the standard 4/3 integrality gap for TSP example work for Euclidean TSP?

The standard LP gap example for the held karp relaxation for TSP min $ c^tx $ $x(\delta(S)) \geq 2 $ $x(\delta(v))=2 $ $x \geq 0$ Is to have two triangles and three long paths connecting the ...
user avatar
  • 83
1 vote
0 answers
28 views

Covering Salesman Problem (CSP) polynomial reduction to the TSP

I am facing one problem that consists in polynomially reducing the Coverging Salesmen Problem (CSP) to the Traveling Salesman Problem (TSP). So, let me first define the CSP. The CSP, I am working on, ...
user avatar
1 vote
0 answers
45 views

Delivery problem, unsure which exact problem it is

I'm looking for guidance on how to reduce the following problem to a known problem or a suggestion for solving it altogether. Optimal / heuristic solutions or any other suggestions are greatly ...
user avatar
  • 51
1 vote
1 answer
227 views

Time complexity of Tsp using DP

this is the recursion formula for problem : C(i,S) = min { d(i,j) + C(j,S-{j}) } In fact, when I tried to implement it as a code, the following code came to my ...
user avatar
  • 21
1 vote
0 answers
103 views

TSP with knapsack combo

My problem statement is that my agent has to visit multiple pickup points once to collect orders, say Item A, Item B, Item C...... etc. We are using TSP for that. Now say Item A are stored in 3 ...
user avatar
  • 11
1 vote
0 answers
44 views

Delivering to two or more locations in one go while respecting deadlines?

Assume that I have a business where people can place product orders. Each order must be delivered within a time limit, say $x$ minutes. I need 15 minutes to make each product. However, multiple ...
user avatar
  • 152
1 vote
0 answers
260 views

Travelling Salesman problem using Guided Local Search

I am doing Week_4 of https://www.coursera.org/learn/discrete-optimization/ stuck in solving TSP. As there are a lot of methods to solve this problem, I am currently coding Guided Local Search as ...
user avatar
  • 94
1 vote
0 answers
520 views

Minimum weight Hamiltonian path on a weighted (0 and 1) tournament graph

Suppose we have a weighted tournament graph. (A directed graph in which every pair of distinct vertices is connected by a single directed edge.) The weights are constrained to be 0 and 1. I know ...
user avatar
1 vote
0 answers
87 views

Comparison of time-dependent traveling salesman heuristics

I'm looking into implementing a heuristic for the time-dependent traveling traveling salesman problem (TDTSP) that completes in a certain amount of time. There are a wide range of possible ways to ...
user avatar
  • 173
1 vote
0 answers
79 views

Best route around confirmed appts - Traveling Salesman Problem

First, I am not a programmer, but an end user. We are trying to come up with a solution to a TSP issue that is causing us SIGNIFICANT time being wasted "manually" routing. Here is the issue. We ...
user avatar
1 vote
0 answers
26 views

Given a set of sets and a storage area, find an order that minimizes the sum of the differences between each set and the storage area

This problem is based on an order picking problem with a forward area. The problem description is as follows. We have a warehouse with a set of items $I$ and a forward area $F$ of size $k$. Each day,...
user avatar
  • 11
1 vote
0 answers
42 views

Finding the upper bound of the length of a closed walk

I am having trouble understanding a part of the proof of Lemma 2 (Page 184). It says the length of the tour is $$ \leq \lceil n^{1/2} \rceil + \triangle(n + \lceil n^{1/2} \rceil) + \sqrt{2} $$ I ...
user avatar
1 vote
0 answers
2k views

Traveling Salesman with Held and Karp Algorithm

I am well aware of the DP solution to the traveling salesman problem; also known as the Held and Karp algorithm for TSP. I have implemented it with bitmask, and it's something like this: ...
user avatar
  • 11
1 vote
1 answer
69 views

Reduction from TSP to ATSP does not imply constant factor approximation algorithm

As I understand there is a constant factor approximation algorithm (e.g Christofides algorithm) for the symmetric TSP problem. This is however not the case for the asymmetric TSP problem (I am ...
user avatar
  • 69
0 votes
0 answers
21 views

TSP given a length oracle

Consider given a code $C$ that takes as input an edge-weighted graph $((V,E), w)$ and returns the weight of the shortest path that traverses all nodes. How is the minimal number of invocations of $C$ ...
user avatar
  • 1
0 votes
0 answers
16 views

How to plot the 'back-to-home-city-path' in TSA without repeating cities

I'm doing an implementation of the traveling salesman problem using genetic algorithms, but I can't get it: If we need to get the best route in a certain set of cities and then go back to the first ...
user avatar
0 votes
1 answer
63 views

How can i do this type of swap(4-opt) between 4 edges of a graph?

The double bridge move is a specific type of swap between 4 edges of a graph, also called 4-opt. It consists of removing 2 pairs of edges. Let`s call them (I, I+1), (J, J+1) and (P, P+1), (Q, Q+1). ...
user avatar
0 votes
0 answers
26 views

Complex profit optimisation problem (logistics and trading)

Problem statement There is a number of towns $\{T_1 \dots T_n\}$, a number of items $\{I_1 \dots I_n\}$ and a number of lorries $\{L_1 \dots L_n\}$. Each town $T_n$ has a market which offers a ...
user avatar
0 votes
0 answers
28 views

Traveling Purchaser Problem exact algorithms

how you doing? Im here to ask for you help. Im writing my bachelor paper as an implementation/review of the TPP algorithms out there. Almost every paper that I read references the Ramesh algorithm, ...
user avatar
0 votes
0 answers
84 views

traveling salesman problem with k-nearest-neighbor algorithm

I tried to solve a problem similar to the TSP problem using the Nearest Neighbor algorithm. The solution was not efficient enough. Then I tried sorting the items with nearest neighbor first and then ...
user avatar
0 votes
0 answers
51 views

Find minimum cost cycle in graph G=(V,E) that visits vertices in required subset V′⊂V exactly once & covers edges in required subset E′⊂E atleast once

I have been researching about general routing problems and came across a problem similar to the Travelling Salesman Problem: Find a minimum cost cycle in a graph $G = (V, E)$ which visits vertices in ...
user avatar
0 votes
0 answers
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 ...
user avatar
0 votes
0 answers
65 views

A paper claiming that optimization version of symmetric TSP can be solved in polynomial time

In the following paper : Czopik, J. (2019) An Application of the Hungarian Algorithm to Solve Traveling Salesman Problem. American Journal of Computational Mathematics,9, 61-67. In the Introduction, ...
user avatar
0 votes
0 answers
34 views

The shortest path that visits every specified node before finally reaching the specified end node?

After asking another question(Is the last step in the Christofides' algorithm necessary), I have decided Christofide's algorithm probably doesn't solve the problem I'm facing. Is there any ...
user avatar