Stack Exchange Network

Stack Exchange network consists of 174 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

The Traveling Salesman Problem and variants

1
vote
1answer
11 views

Christofides algorithm (by hand)

I am following this algorithm example: https://en.wikipedia.org/wiki/Christofides_algorithm#example The graph: ...
0
votes
0answers
22 views

New proof for lower bound asymetric tsp?

I read about this article https://www.quantamagazine.org/sci-fi-writer-greg-egan-and-anonymous-math-whiz-advance-permutation-problem-20181105/. Can someone explain it to me? Is this related to a new ...
0
votes
1answer
34 views

Do you >have< to define the upper and lower bound? (context: traveling salesman)

Do one have to define the upper and lower bound to be able to solve the tsp, or is that just an unnecessary intermediate step? And if so, why would one define those bounds? (context: the traveling ...
0
votes
0answers
20 views

How to prove that this TSP variation is NP-Hard?

The problem is as follows: given a list of cities, a list of distances between them, and upper bounds for date/times that the cities must have been visited by, compute the shortest (optimal) going ...
0
votes
0answers
26 views

The Traveling Salesman Problem algorithm overview

There is currently a lot of algorithm for The Traveling Salesman Problem. As a rookie on this subject, I have a hard time figuring what algorithms is the optimal to use in different scenarios. Can ...
0
votes
0answers
13 views

Questions regarding Particle Swarm Optimization (for TSP) algorithm (paper)

I'm trying to re-implement an algorithm from a paper regarding the Particle Swarm Optimization metaheuristic for the Traveling Salesman Problem. The paper is the following: Goldbarg et al. (2006): ...
0
votes
1answer
13 views

Grid Based DP: How do we tweak the Travelling Salesman Problem to work with Grids

The question is: There is a n x n grid (Maze) which has either 0, 1 or 2. 0 means a path exists, 1 means the cell is blocked and 2 means there exists gold in that cell. Task is to start from 0,...
0
votes
0answers
24 views

min-weight perfect matching for christofides algorithm

I read all the topics like: Min-weight bipartite matching in Christofides' algorithm Faster maximum weight matching algorithm in bipartite graph but I still don't understand one step in coding ...
2
votes
0answers
41 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 (...
0
votes
0answers
81 views

Which dynamic programming algorithm can be used to solve this variation of TSP problem?

A company has been appointed to look at building floating roads connecting all cities of the Kingdom. The adjacent cities of the kingdom are connected by a perimeter road (P) and the other cities ...
3
votes
2answers
72 views

Is there a solution for this maze problem in polynomial time?

Suppose you have a maze represented by a graph where each vertex represents a room and edges represent paths between rooms and each edge has a weight denoting the time it takes to go that way. Now ...
6
votes
2answers
134 views

Does there exist a travelling salesmen generating algorithm?

I'm curious if somebody has already figured this out. Is there an efficient algorithm that will generate (in $\mathbb{R}^2$) a sequence of points in such a way that the solution to the travelling ...
1
vote
0answers
35 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 ...
1
vote
1answer
39 views

Why does Travelling Salesman Problem pose the restriction that each vertex can only be visited once?

According to the wiki page of TSP as a graph problem, It is a minimization problem starting and finishing at a specified vertex after having visited each other vertex exactly once Then what if a ...
0
votes
0answers
31 views

mLP to mAGTSP formulation

In the paper Scheduling Twin Yard Cranes in a Container Block authors provide a mILP to solve scheduling twin cranes to execute requests in a block at a seaport to minimize makespan of the cranes. ...
2
votes
1answer
30 views

Reducing closed TSP to open with fixed starting vertex

I have implemented a branch and bound algoritm for finding a Hamiltonian cycle in my software, but I actually need to find a shortest route from fixed vertex through all verticies ending at any of ...
2
votes
0answers
14 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 \...
1
vote
2answers
38 views

In the Traveling Salesperson Problem, is the shortest tour the same regardless of the start/return city? How do you prove it?

This is the form of the problem where you start at a city, visit every other city, and return to the start city. Since you "return" to every city in the completed cycle, it seems intuitive that the ...
1
vote
1answer
10 views

How to get initial flow for TSP with missing edges

I need to solve a version of the traveling salesman problem with missing edges. I've decided to use simulated annealing. How do I generate a valid initial path effectively? I would use a greedy ...
1
vote
0answers
40 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 ...
1
vote
2answers
99 views

if traveling salesman problem is decidable in polynomial time, can an actual solution be proposed in polynomial time?

I'm asking because it seems that P problems refer to decision problems rather than actually propose a solution.
1
vote
1answer
53 views

Improvement Heuristics for Asymmetric TSP

i have been solving the Time-Dependent Traveling Salesman Problem using an Ant Colony Optimization. Upon reading the ACO papers, there are several reminders which state that ACO performs best with ...
0
votes
0answers
38 views

Algorithms to try for solving a variation of the TSP problem

I am trying to solve the TSP problem in its symmetric variation, where the triangle inequality does not hold, for around 400 cities. Do you know some algorithms that perform particularly well on this ...
1
vote
1answer
56 views

Is Euclidean TSP strongly NP-hard

Is Euclidean TSP strongly NP-hard? What I mean is if it is NP-hard with weights specified in unary? Can someone provide a reference?
1
vote
1answer
96 views

Travelling salesman problem with small edge weights

Are there any advantages in finding the shortest tour for the problem if edge weights are much smaller than the number of vertices? Let's say the maximum edge weight is $n$, and the number of ...
0
votes
1answer
184 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 (...
0
votes
0answers
68 views

How to find the best parameters of a Genetic Algorithm applied to the TSP problem?

I have an assignement where I need to use a Genetic Algorithm to solve the TSP (Traveling Salesman Problem). I alrerady implemented a solution in C# but the problem is we're asked to use some kind of ...
1
vote
1answer
27 views

TSP when cost depends only on location in sequence

I want to change the original TSP problem as follows: the cost to visit a city is not related to the previous city that it visited just now, but only on its position in the sequence. Is the problem of ...
1
vote
1answer
93 views

Traveling salesman problem with disconnected cities / infinite length edge

I am looking to solve a variant of the traveling salesman problem with a certain set of constraints: the graph is not complete, i.e. some nodes are not connected to each other the weight of an edge ...
0
votes
1answer
175 views

What if the travelling salesman travelled by plane?

It seems intuitive to solve a 2D dot-to-dot travelling salesman problem by eye using a greedy strategy. However we can only solve the TSP by eye if the graph is topographically accurate e.g. if A to B ...
0
votes
0answers
23 views

A variant of VRP

I have a variant of VRP as follow: There are a set of customers $C$ and a set of fuel stations $F$ ($C \cap F = \emptyset$) locate on a complete graph $G = (V, E)$, where $V = C \cup F \cup \{v_0\}$,...
19
votes
2answers
3k views

How is the traveling salesman problem verifiable in polynomial time?

So I understand the idea that the decision problem is defined as Is there a path P such that the cost is lower than C? and you can easily check this is true by verifying a path you receive. ...
1
vote
1answer
42 views

Flexible Team Orienteering Problem

In Team Orienteering Problem (TOP) we have a graph $G=(V,E)$ and $K$ participants, We are supposed to find $K$ paths with total edge cost less than a threshold ...
0
votes
0answers
90 views

How To Solve TSP With Multiple Routes, Visits And Constraints

I've got an TSP problem which I can't seem to solve somehow. It consists of about 1200 addresses for which all distances (measured in seconds) between them, a frequency (once a week, twice a week, 3 ...
-5
votes
1answer
2k views

Traveling Salesman Solution [closed]

This problem has been heavily studied, and at last may have a potential solution. The concept I have come up with was made entirely on my own, but is close to some other theories that will be ...
1
vote
1answer
111 views

Size of neighborhood in local search for symmetric TSP

I read about local search / neighborhood search methods for the symmetric TSP and I'm not quite sure about a few things. The given example said: Suppose we have an instance of the symmetric TSP ...
1
vote
1answer
40 views

What algorithm to use for this kind of routing optimization?

Let's imagine a situation in order to fully understand the problem : let's say a lone human is walking back home at a very late time. He needs to find the safest path home. He naturally use the GPS ...
4
votes
1answer
107 views

How to prove non-existence of $O(2^n)$ approximation algorithm solving TSP?

The following theorem (from "The Design of approximation algorithms" by Williamson & Shmoys, pg 43) states: For any $\alpha > 1$, there does not exist an $\alpha$-approximation algorithm for ...
4
votes
1answer
179 views

Traveling Salesman — number of qubits required?

I'm trying (in vain) to get a beginner's grasp of quantum computing, so doing a lot of reading. I've started looking at IBM's QISkit Jupyter Notebooks, and came across the one on MaxCut problems. In ...
4
votes
2answers
610 views

Rearranging strings so that the Hamming distance between them is 1

This is a question from CodeFights.com: Given an array of equal-length strings, check if it is possible to rearrange the strings in such a way that after the rearrangement the strings at ...
1
vote
2answers
806 views

TSP decision problem vs TSP optimization problem

Let's check together whether the TSP-decision problem is NP-complete. Maybe it will help me to understand things better. Question for TSP-decision problem: Given n cities and a tour from length $k$. ...
1
vote
2answers
107 views

complexity theory NP [duplicate]

Ok, I really need help because I have read in so many books but still don't understand the complexity class NP. These are the books: Theoretische Informatik; Katrin Erk, Lutz Priese (german) ...
5
votes
2answers
324 views

Why does this not prove $P\neq NP$?

Fiorini, Massar, Pokutta, Tiwary and De Wolf (Exponential Lower Bounds for Polytopes in Combinatorial Optimization, Journal of the ACM 62(2):article 17, 2015; PDF, ArXiv) show any linear program that ...
1
vote
2answers
87 views

What is the importance of disjoint edges in k-opt algorithms?

I'm trying to implement a k-opt algorithm and I'm bogged down on a detail: the importance of choosing disjoint edges. My question: Is there any benefit to considering adjacent edges, or is the full ...
-1
votes
1answer
114 views

How to polynomially reduce euclidean tsp to regular tsp?

The normal tsp seems way harder than the euclidean one, is the euclidean tsp np complete? If so is there a simple reduction that gives an answer to the tsp if you have the euclidean tsp algorithm?
6
votes
0answers
197 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 ...
2
votes
2answers
189 views

MSTs in Christofides Algorithm

I am implementing the Christofides algorithm for TSP problem and currently I have one issue with the MST result. Let's assume that I have one graph $G$, whereas I can get $MST_1$ and $MST_2$ where ...
2
votes
0answers
33 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 ...
2
votes
0answers
121 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 ...
1
vote
1answer
100 views

Which algorithm suits this problem best?

I have an optimization problem and I'm looking to find an algorithm whitch best fits this. The problem is the following: There are several points of interest (POI), each has a value (for the user), ...