Stack Exchange Network

Stack Exchange network consists of 175 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

Questions tagged [traveling-salesman]

The Traveling Salesman Problem and variants

3
votes
2answers
49 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 ...
-1
votes
0answers
23 views

Can a function that produces a set of edges with a specific “aggregate graph property” multitask?

Background Let $G(V,E)$ be a graph. Let $S$ be the set of all combinations of $|V|$ edges. Let $A$ & $B$ be two subsets of $S$, where: each subset is a collection of all elements of $S$ that ...
0
votes
0answers
23 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
360 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
39 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
442 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?
21
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
50 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 ...
0
votes
0answers
87 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
120 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%. ...
1
vote
1answer
64 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
16 views

Can Heuristic repair algorithm be applied to TSP?

Can Heuristic repair algorithm (or it's modification) be applied to Traveling Sales Person problem ? My gut feeling is that it can. But I have no idea - what cost(s)/conflicts should be minimized. ...
0
votes
0answers
26 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
47 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
268 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
31 views

Mathematical modelling on Christofides algorithm

Does a mathematical modelling on Christofides algorithm exist, is it even possible to create one?
1
vote
1answer
227 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
78 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
186 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
54 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
38 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
74 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
103 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
135 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
186 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
125 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
34 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
121 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
18 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
43 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
18 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
70 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
304 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
81 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 ...
1
vote
1answer
120 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
159 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
489 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
137 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
28 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
216 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
304 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 ...
20
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
44 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
194 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 ...
-4
votes
1answer
3k 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
123 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
45 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
122 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 ...