Questions tagged [traveling-salesman]
The Traveling Salesman Problem and variants
169
questions
0
votes
1answer
27 views
Grouping n points into groups of size m with objective to have least traveling distance in each group
Assumptions:
There are "n" jobs which are distributed over the city.
Company has "k" available workers.
Each worker can do "x" jobs per day.
"x" is dependent to the worker skills and the distance ...
2
votes
1answer
14 views
Performant algorithm to find edges without cross overs
I have a series of graphs with points plotted like this:
Like in the image, I need to join these points to create a complete edge. I am currently doing this with nearest-neighbour, but because I don'...
2
votes
1answer
50 views
Arranging Colors in a Grid; Two Dimensional TSP?
I am working on an interesting problem, which I believe can be solved algorithmically. I have a 6x8 on which I am attempting to arrange 48 color swatches, such that the transition from each swatch to ...
1
vote
2answers
65 views
Can non-metric TSP be approximated within some non-constant value?
It is known that metric TSP can be approximated within some constant value, such as 3/2 through Christofides' algorithm. It is also known that non-metric TSP cannot be approximated within some ...
-2
votes
2answers
81 views
Why haven't I solved the Travelling Salesman problem with the following argument using djikstras algorithm?
I claim to have solved the travelling salesman problem as follows.
(You will have to be familiar with djikstra's algorithm for this.)
1) I am about to start using djikstra's algorithm on any given ...
0
votes
0answers
95 views
What is the difference between nearest and cheapest insertion algorithms for a Traveling salesman problem?
I know that in the cheapest insertion algorithm we include the node which is not in the "base group" that has smaller cost given all possible combinations, and for the nearest we include the node with ...
-2
votes
1answer
27 views
Question about complexity of TSP Optimization problem
Is this statement true?
Optimization TSP problems are known to be NP-hard, as we do not have a minimum cost to compare against, and in order to verify a solution is optimal, we need to iterate ...
2
votes
2answers
103 views
For what applications of the traveling salesman problem, does visiting each city at most once truely matter?
Traditionally, the traveling salesman problem has you visit a city at least once and at most once.
However, if you were an actual traveling salesman, you would want the least cost route to visit each ...
1
vote
2answers
91 views
TSP Variant — Colored Path
Recently I came up with a traveling-salesman-esque problem. As usual, we have $n$ vertices, and a weighted edge between any two vertices. However, each vertex is associated with a color, which may be ...
0
votes
1answer
21 views
Comparison of constructive and local-search heuristics for TSP
In my high school class, we are currently looking at evaluating heuristic methods for intractable problems - especially TSP.
My question is what is the advantages or disadvantages of using a ...
1
vote
1answer
205 views
Hamilton Circuit
The Dirac's theorem states that:
"For a Graph G with N vertices, if the degree of each vertex is atleast N/2 then, the Graph has a Hamilton Circuit."
Can the same be said if a graph has a Hamilton ...
0
votes
1answer
138 views
Given n sets of points in the plane find the shortest path which passes from exactly one point from each set
I am trying to find an algorithm for this. You can imagine each set $(S_1, S_2, \ldots, S_n)$ as points with different colour. Also it isn't necessarily $|S_1|=|S_2|=\cdots=|S_n|$.
For $n=1$ we ...
0
votes
3answers
164 views
How to compute number of possible paths in directed Traveling Salesman problem?
If we have directed modification of TSP, so that some routes are possible in one direction, given directed graph, could you compute number of possible tours?
What if we have supercomputer, does it ...
1
vote
1answer
28 views
Dubins TSP NP-hardness proof detail
In Le Ny et al.'s paper On the Dubins Traveling Salesman Problem (https://tinyurl.com/y59f7d8x) the authors prove, among other works, that the Dubins Traveling Salesman Problem (DTSP) is NP-hard. I ...
0
votes
1answer
236 views
Travelling Salesman: Big O Complexity when starting city is fixed
We are studying the Travelling Salesman problem in my high school class, and I am wondering what the Big O complexity of the TSP is when you MUST start and end at the same city. For example, given 4 ...
0
votes
1answer
24 views
Number of Solutions for Brute Force Algorithm of Travelling Salesperson Problem
We are learning about the travelling salesperson problem in my high school class and we are discussing how computers could solve for the problem, even though the problem is intractable, using a brute ...
1
vote
0answers
25 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 ...
0
votes
1answer
28 views
Dubins TSP crossing trajectory theorem
In the Dubins TSP (DTSP for short), one needs to visit a set of given points in the plane, and return to the starting point, minimizing the distance of such a trajectory. The difference with the ...
2
votes
1answer
40 views
Why isn't the search space size of TSP $(n-1)!$ instead of $n!$?
I'm just learning about the travelling salesman problem, and I've been playing around with it. I'm not sure if what I've found is just a special case or not. My professor says the search space size is ...
2
votes
1answer
38 views
Approximation algorithm to visit all nodes in an undirected, weighted, complete graph, with shortest sum of edge weights
I'm looking for an algorithm that gives a smallest value of 'travel cost' within the following constraints:
a complete, connected, weighted graph,
vertices are defined in 3d euclidean space,
...
1
vote
2answers
168 views
What is the graphic TSP?
I'm not sure if I understand the following definition of the (well-known apparently) Graphic TSP, also known as graph-TSP :
...graph-TSP, that is, the traveling salesman problem where distances ...
3
votes
2answers
70 views
League and Divisions problem (np-hard)
There is a League. And there are Divisions, that are the disjoint subsets of this League. There are n teams (unique locations are given, let's assume it's x and y for simplicity reasons). Every team ...
0
votes
0answers
48 views
Traveling Salesman Problem with profit and time limit as ILP formulation
How to formulate the following problem?
The salesman gains a profit $p_{i}$ when visiting a city i, trip between city i and city j costs $c_{ij}$ and takes $t_{ij}$ time. The trip must not exceed a ...
1
vote
0answers
42 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 ...
4
votes
2answers
367 views
Linear Path Optimization with Two Dependent Variables
Alright, so this is a fairly interesting problem I have but also slightly difficult to explain so I will try my best.
There are two runners on a line that goes from $x=0$ to $x=100$. The two runners ...
1
vote
1answer
50 views
A problem to maximize the number of edges in a cycle while minimizing the total weight
I encountered the problem below and the only solution I came up with is branch and bound like that is used in TSP and I don’t think the bound I used is good enough. Are there any better idea on this?
...
3
votes
2answers
597 views
Is there an efficient solution to the travelling salesman problem with binary edge weights?
Is there a way to solve TSP in polynomial time if there are only two kinds of weights, 0 and 1?
23
votes
2answers
5k views
If I can solve Sudoku, can I solve the Travelling Salesman Problem (TSP)? If so, how?
Let us say there is a program such that if you give a partially filled Sudoku of any size it gives you corresponding completed Sudoku.
Can you treat this program as a black box and use this to solve ...
2
votes
1answer
121 views
Overall time complexity of Heuristical Algorithm for travelling salesman problem [TSP]
I am trying to figure out the time complexity of a heuristical algorithm used to solve the Travelling Salesman Problem in a more efficient way than by brute force, ($\theta(n!)$ or similar)
The ...
1
vote
0answers
157 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 ...
2
votes
1answer
465 views
2-opt vs 3-opt comparison
I have a question regarding performance of 2-opt and 3-opt algorithms.
I tried implementing the 3-opt and 2-opt algorithms and most of the time 3-opt outperforms the 2-opt algorithm around 5%.
...
2
votes
1answer
70 views
Is TSP a more detailed form of the “Set Inclusion” question?
Background
Set Inclusion
GIVEN: set of cards, some with blue backs, and each with a positive, integer face value.
QUESTION: Are there any [blue-backed cards] with a [face value <= L]?
2 ...
0
votes
2answers
2k views
Which of the following statements are true for the given special cases of the Traveling Salesman Problem?
I'm taking the Algorithms: Design and Analysis II class, one of the questions asks:
Which of the following statements is true?
Consider a TSP instance in which every edge cost is either 1 ...
0
votes
0answers
44 views
can someone provide a good resource for understanding 2 opt heuristic?
I have looked into wikipedia and this MIT slide. A step by step iteration of the algorithm with a clear example would be appreciated.
-1
votes
2answers
53 views
Solve this integer program (problem: Travelling salesman problem)
How do one solve the following integer program?
$$
\begin{align*}
\text{minimize} \quad &\sum_{(i,j) \in E} d_{ij} x_{ij} \\
\text{subject to} \quad & \sum_{j \in V} x_{ij} = 2 \;\; \forall i ...
0
votes
2answers
270 views
Clarify the steps: what happened in this mathematical modelling of TSP?
Source: http://examples.gurobi.com/traveling-salesman-problem
I don't get this part: (look at the source)
$$\sum_{i,j\in\{1,2,3\},i\neq j} x_{ij}=3>2=|\{1,2,3\}|-1$$
I get that $x_{ij}$ is ...
-2
votes
1answer
48 views
Mathematical modelling on Christofides algorithm
Does a mathematical modelling on Christofides algorithm exist, is it even possible to create one?
1
vote
1answer
437 views
Nearest Insertion Traveling Salesman Heuristic: is it faster to insert nearest nodes first?
I am trying to implement the nearest insertion TSP heuristic. However, I am wondering if it matters which node I insert into the subgraph first.
For example, should I start with one node; calculate ...
2
votes
2answers
117 views
How to Solve TSP Given Length of Path?
I am trying to devise an algorithm in which given the length of a path that satisfies the constraints of the Traveling Salesman Problem, I can find the path. Currently, my only solution is to find a ...
3
votes
1answer
475 views
Christofides algorithm (by hand)
I am following this algorithm example: https://en.wikipedia.org/wiki/Christofides_algorithm#example
The graph:
[![enter image description here][1]][1]
...
0
votes
1answer
93 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
1answer
76 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,...
2
votes
0answers
116 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 (...
3
votes
2answers
131 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
139 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
338 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 ...
3
votes
1answer
296 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 ...
2
votes
1answer
184 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
21 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
45 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 ...
