Last call to make your voice heard! Our 2022 Developer Survey closes in less than a week. Take survey.

Questions tagged [traveling-salesman]

The Traveling Salesman Problem and variants

Filter by
Sorted by
Tagged with
-1 votes
0 answers
25 views

approximation ratio of TSP problem where the weights are bounded by an inequality

Consider a variant of the TSP problem where the cost function $c$ is not only symmetric but also satisfies $c(u, v) ≤ 2c(u, w) + c(w, v)$ for arbitrary vertices $u, v, w ∈ V$ . Give a polynomial time ...
user avatar
1 vote
1 answer
37 views

Why DFS transversal without the duplicates is a valid cycle?

So I am studying apporiximation algorithms for TSP problem and there is a step that I don't get. Essentially trying to solve TSP means we are looking for a minimum cost Hamiltonian path. The well-...
user avatar
3 votes
1 answer
57 views

Approximation ratio on (1, 2)-metric Travelling Salesman Problem (TSP)

I encountered a problem, where I am given a (fully-connected) graph within a metric space, where each edge weight is either 1 or 2. My task is to prove that the following greedy algorithm gives a $\...
user avatar
  • 149
3 votes
1 answer
71 views

$k$-Opt TSP Local Search is exact when $k = |V| - 1$

I've been self-studying the book Algorithms by Papadimitriou, Dasgupta and Vazirani. I am having a hard time with a question about local search involving the traveling salesman problem (TSP). We'll ...
user avatar
4 votes
1 answer
98 views

$k$-Opt TSP Local Search is NOT exact when $k = \lceil |V|/2 \rceil$

I've been self-studying the book Algorithms by Papadimitriou, Dasgupta and Vazirani. I am having a hard time with a question about local search involving the traveling salesman problem (TSP). We'll ...
user avatar
1 vote
0 answers
42 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
0 votes
1 answer
60 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
2 answers
49 views

Solving time of large TSP instances

The optimization variant of TSP is NP-hard, hence, finding an optimal tour takes $2^n$ steps for $n$ cities. According to Wikipedia, the largest instance solved so far consists of $n=85,900$ cities ...
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
2 votes
1 answer
34 views

What is the exclusion-inclusion algorithm for TSP?

I was looking at the wikipedia page for the Travelling Salesman Problem and found a reference to another exact algorithm besides Held-Karp that's also $O(2^nn^2)$. Specifically: "This bound has ...
user avatar
1 vote
0 answers
35 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
56 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
0 votes
0 answers
26 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
60 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
1 vote
1 answer
66 views

Euler Tour in Christofides Algorithm

The penultimate step of the Christofides algorithm in solving the TSP asks us to find an Eulerian tour of the subgraph formed by uniting the MST of the original graph and MPM of a subgraph. I ...
user avatar
1 vote
0 answers
25 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
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
1 vote
1 answer
29 views

Heuristics for a variant of the traveling salesman problem

I am looking at a variant of TSP in which rather than visiting every node, there is a given collection of (possibly overlapping) subset, and the salesman must pass through one node from each subset. ...
user avatar
0 votes
0 answers
45 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
1 answer
70 views

Nearest neighbor algorithm for TSP when triangle inequality holds

The output given by this nearest neighbor algorithm for the Travelling Salesman Problem can be arbitrarily bad. In the example constructed here, the triangle inequality doesn't hold in most cases. Let ...
user avatar
0 votes
1 answer
54 views

Can the "closest neighbor" algorithm get arbitrarily bad in TSP?

Let's consider the following simple algorithm for attacking the Travelling Salesman Problem: Choose the pair of cities $(A,B)$ where $A\neq B$ and the distance between $A, B$ is minimal amongst all ...
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
0 votes
0 answers
57 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
1 answer
41 views

Is this variation of the traveling salesman problem NP-hard

Consider the following setting. You have $n$ cities, and there is a cost to travel from a city $i$ to a city $j$ given by $c_{ij}>0$ where $c_{ij}\neq c_{ji}$. Moreover, if you are traveling to ...
user avatar
1 vote
1 answer
26 views

CVRP and removing edges from a graph

I am solving a CVRP (Constrained Vehicle Routing Problem) on a connected graph, that is not necessarily complete. Edge weights represent Euclidean distances. I know that, in general, the complexity of ...
user avatar
2 votes
1 answer
411 views

Shortest path given correct order of colours?

I have a directed graph $G=(V,E)$ where each vertex is a 4-D coordinate $v: (x, y, z, c)$ representing spatial coordinates $x, y, z \in \mathbb{R}$ and the non-physical parameter colour $c \in (c_{1}, ...
user avatar
  • 123
1 vote
1 answer
65 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
1 vote
1 answer
116 views

$P = NP$, what am I missing?

First post here so hope I'm not missing too many guidelines. I've had this idea for a few weeks now and I can't myself see where I'm going wrong with it, hope it makes some sense to you and thanks in ...
user avatar
  • 13
0 votes
1 answer
74 views

Clarification for binary search in solving optimal TSP when a polynomial algorithm with a budge exists

Below is Question 8.1 in Algorithms by Dasgupta et al. There's a solution to this problem that uses binary search from here. Pasting the answer for posterity. My questions are: When they say input ...
user avatar
1 vote
1 answer
92 views

Why is crossing paths bad in Traveling Salesman?

I'm learning about Traveling Salesman in an online course (sorry I can't share the link it's paid only) and the first step to solving it then just state "as a heuristic we avoid crossed paths&...
user avatar
0 votes
1 answer
61 views

Reducing the Hamiltonian cycle to the travelling salesman problem and self loops

If this is my adjacency matrix for the hamiltonian cycle: $$\begin{pmatrix}0&1&0&1\\ 1&0&1&0\\ 0&1&0&1\\ 1&0&1&0\end{pmatrix}$$ Then a reduction ...
user avatar
  • 123
2 votes
0 answers
46 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
0 votes
2 answers
50 views

Route finding on a graph that must go through multiple edges

I have this graph It shows a graph of a map that has nodes and segments (or edges), with weights, that connect these nodes. Some of these segments have addresses on, and some of these addresses are ...
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
1 vote
0 answers
63 views

Is the last step in the Christofides' algorithm necessary [closed]

I am using Christofides' algorithm to calculate the best route from one location to another given multiple nodes on a map that the route must pass through. The last step in the algorithm requires the ...
user avatar
1 vote
1 answer
42 views

Cyclic tour minimizing total weight

I asked the following question on math.se but it wasn't really answered so moved it over here as I feel it's more relevant. I saw the question below on an old stack exchange question when looking to ...
user avatar
1 vote
1 answer
201 views

Time complexity of the travelling salesman problem (Recursive formulation)

According to this recursion formula for dynamic programming (Held–Karp algorithm), the minimum cost can be found. I entered this code in C ++ and this was achieved (...
user avatar
  • 21
1 vote
1 answer
205 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
0 votes
0 answers
47 views

How to create mathematical proof of TSP and SLAP equivalence?

In my thesis, I'm dealing with SLAP (storage location assignment problem) -- which is finding optimal distribution of products to location slots in a generic warehouse. My aim was to implement ...
user avatar
  • 101
2 votes
2 answers
50 views

For a set of points P, connected by weighted edges (distances) I need a path through all points while minimizing the travel on any edge longer than X

For a given set of coordinates (lat/lng) I need a path which will visit each coordinate only once. The path needs to be selected to minimize the number of times the haversine distance between two ...
user avatar
  • 121
0 votes
0 answers
124 views

TSP - Held-Karp vs Dantzig et al

I'm having trouble understanding the difference between the Held-Karp $O(n^2 2^n)$ solution and the cutting-plane method pioneered by Dantzig, Fulkerson and Johnson. Held-Karp is $O(n^2 2^n)$ which ...
user avatar
0 votes
0 answers
55 views

Travelling Salesman Problem: Distance between solutions

I'm designing a genetic algorithm to solve the travelling salesman problem. So far, I've gotten fairly good results. I'm now trying to improve on them by implementing some sort of diversification ...
user avatar
  • 101
1 vote
2 answers
66 views

What is the shortest total path between pairs of points?

I have 2n random points on a plane. Join pairs of points to make paths. Pair the points such that the summed path length is a minimum. In the picture below, we are trying to minimise the total length ...
user avatar
0 votes
1 answer
79 views

Bottleneck TSP with repeated nodes

I am aware that the traveling salesman problem (TSP) and the bottleneck TSP problem is NP-hard for complete directed graphs. I am also aware that regular TSP that allows a path with repeating is also ...
user avatar
2 votes
1 answer
124 views

Approximation concerning Asymmetric TSP, Symmetric TSP, and Metric TSP

I always considered Symmetric TSP to be inapproximable in general, and thus by extension Asymmetric TSP as well. Once you add the condition of the triangle inequality however, you obtain Metric TSP (...
user avatar
0 votes
2 answers
66 views

Schedule Optimization With Priority and Weighted Costs

I need an algorithm to determine the best itinerary for a series of events. Each event has a time, location, and reward. Arriving at an event in time yields the reward; too late means no reward. Each ...
user avatar
  • 1
3 votes
1 answer
59 views

Combinatorial Problem similar in nature to a special version of max weighted matching problem

I have a problem and want to know if there is any combinatorial optimization that is similar in nature to this problem or how to solve this special version of the max weight matching problem. I have a ...
user avatar
  • 131
1 vote
1 answer
63 views

TSP 200-approximation, given $c(x,z)\le c(x,y) + 100\cdot c(y,z)$ for all nodes $x,y,z$

Input: complete, undirected graph $G=(V,E)$ and cost function $c$ Assume for all nodes $x,y,z \in V$: $c(x,z)\le c(x,y) + 100\cdot c(y,z)$ Find a 200-approximation polynomial time algorithm for the ...
user avatar
  • 31
0 votes
1 answer
156 views

What complexity class is the TSP problem?

Is the travelling salesman problem (TSP) $FNP$-complete or is it $FP^{NP}$-complete?
user avatar
2 votes
1 answer
47 views

Constrain traveling salesman: visit a given city within a given distance from start

I would like to add an additional constraint to the traveling salesman problem: that a given city is visited within a given distance (say 100) from start. Is there ...
user avatar

1
2 3 4 5