Questions tagged [traveling-salesman]
For questions related to the traveling salesman problem (TSP), which seeks, for a given set of nodes, the shortest path that visits every node and returns to the starting node.
76
questions
0
votes
0
answers
61
views
Travelling Salesman problem and Vehicle routing problems
Can someone explain to me why are we doing the $x_{ij}=1$ and and the constraint $U_j \geq u_i+1-n(1-x_{ij})$
Also do you have any books or sources in mind from where I could learn in more detail from ...
- 39
0
votes
2
answers
71
views
"GLPK: No Primal Feasible Solution" for Travelling Salesman Problem (Dantzig–Fulkerson–Johnson formulation)
I have a problem with implementing the Dantzig–Fulkerson–Johnson formulation to solve the following Travelling Salesman Problem:
\begin{bmatrix}
M & 21 & 17 & 19 & 21 & 22\\
26 &...
- 113
0
votes
2
answers
157
views
TSP problem using Google's OR tools
This is the Travelling Salesperson Problem code from Google's OR tools. I used a simple instance that is defined in the data dictionary and has optimal value (sum of Euclidean distances) of 36.26 for ...
- 165
-1
votes
1
answer
54
views
does mTSP/CVRP always minimize number of vehicles used?
Context:
I was working on some VRP solvers and realized that tractability deproved when I added Fixed Cost for each vehicle (in an attempt to reduce number of vehicles used).
Questions:
1-
Due to the ...
- 63
3
votes
0
answers
104
views
Number of Subtour Elimination Constraints for ATSP (DFJ Formulation)
In the DFJ formulation of the symmetric TSP, the subtour elimination constraints are typically written as:
$$\sum_{\{i,j\} \in E: \ i \in S, j \notin S} x_{ij} \geq 2, \qquad \forall S \subset V, \; 3 ...
- 31
1
vote
0
answers
98
views
Node swap and edge swap for TSP
When devising heuristics for the TSP I often see edge exchange algorithms suggested. But I also find them a bit hard to understand and somewhat cumbersome to implement.
When I think about a TSP, I ...
- 1,133
3
votes
0
answers
120
views
TSP-PD with time constraints between pickups and deliveries
Has anyone ever encountered the following variation of TSP? You have a TSP with pickups and deliveries, and in addition, for each pickup-delivery pair $(i,j)$, you have a constraint that the time you ...
- 163
1
vote
2
answers
459
views
Subtour elimination in SDVRP
I have the model below, based on this paper. It's a vehicle routing problem with split deliveries, i.e the locations/customers can be visited by multiple vehicles that share the demand at that vehicle....
- 207
2
votes
2
answers
385
views
Best exact method to solve TSP
What is currently the exact method to solve the TSP which performs best on average regarding computation time?
- 1,110
3
votes
1
answer
102
views
Can a TSP K-OPT operator be completed with a sequence of 2-OPT moves?
This seems intuitive and is likely correct, but I'm looking for a paper or perhaps a more thorough proof on how a K-OPT move is equivalent to a sequence of 2-OPT moves. Or if this is wrong, something ...
- 335
3
votes
1
answer
231
views
Solution for a TSP with Branch and Cut for Gurobi in Java?
We have a group project and our job is to create an algorithm for solving a TSP with Branch and Cut. (Use of lazy constraints.) We tried around but don´t know what is the best way to start. We get the ...
- 31
6
votes
2
answers
407
views
Metaheuristics vs Column generation for VRP
I am solving a vrp and its variants (pick up drop off, milk-run problem) using genetic algorithms. The issue that I am getting with the genetic algorithm is the randomness associated with the ...
- 619
2
votes
0
answers
203
views
Trying to add lazy constraints to traveling salesman problem
For a simple traveling salesman problem, I am trying to add the "miller-tucker-zemlin subtour elimination constraints" by using ILOLAZYCONSTRAINTCALLBACK.
...
- 29
4
votes
0
answers
192
views
How to overcome overflow issues with Concorde?
Concorde is a well-known exact solver for instances of the traveling salesman problem. It can also be used to solve asymmetric TSPs, if the user implements a trick to convert ATSP to TSP.
However, if ...
- 273
5
votes
2
answers
223
views
Lin-Kernighan TSP edge choice
Step 4a of the original paper describing the Lin-Kernighan TSP algorithm states that the choice of edge $x_i = (t_{2i}, t_{2i+1})$ to be deleted is uniquely determined by the choice of edge $y_{i-1} =...
- 61
2
votes
1
answer
574
views
Model the TSP as a shortest path
We have a directed graph $G=(N,A)$ where $N$ are the verticies $N=0,1,2,3,4,5,..,n$ the starting location is node 0.
For each arc $a=i-j$ in A we have a distance $d_a>0$
So we want to start and ...
0
votes
1
answer
110
views
How to model a simple routing problem using nodes and arcs
I have the following problem.
I have a route which begins at node $0$.
I want to begin and end in $0$ which is a depot.
Now in this route even customer will be visited in order for example customer 2 ...
7
votes
4
answers
711
views
Interpretation of a subtour elimination constraint in the TSP
I have a problem with understanding the following mathematical model of the TSP.
Given that the TSP is:
$$\min \sum_{i,j\in N} d_{i,j} \cdot x_{i,j}$$
subjected to:
$$\begin{array}{rrrr}\sum_{j\in N}...
- 517
7
votes
3
answers
344
views
TSPs and VRPs in real world
I have a CS background, I took some optional courses in Optimization.
I stumbled upon classic transport problems like TSP and VRP.
Maybe I am not familiar with the domain, but I think that there aren'...
- 71
6
votes
2
answers
781
views
Confusion Between Different Types of Optimization Problems
I do not have a background in optimization and I am trying to teach myself more about this topic. I find myself having a lot of trouble understanding the different "types" of optimization ...
- 1,821
2
votes
1
answer
142
views
Sensitivity Analysis for Traveling Salesman
I am trying to understand how the idea of Sensitivity Analysis would apply to the Traveling Salesman Problem.
For instance, suppose my optimization algorithm returned the following path as the ...
- 1,821
2
votes
1
answer
114
views
Traveling Salesman Reference
Can anyone recommend a reference which shows the amount of time required for the Traveling Salesman Problem (TSP) to be solved using brute force as the number of cities increase?
I have informally ...
- 1,821
5
votes
2
answers
1k
views
Is Traveling Salesman Problem "Combinatorial Optimization" or "Integer Optimization"?
I am looking at the Traveling Salesman Problem and I can not figure out if this problem is a type of "Integer Optimization Problem", or is a type of "Combinatorial Optimization Problem&...
- 1,821
10
votes
3
answers
2k
views
Are Metaheuristics and Evolutionary Algorithms the "Gold Standard" for the Traveling Salesman Problem?
Are Metaheuristics and Evolutionary Algorithms the "Gold Standard" for the Traveling Salesman Problem?
I am interested in learning more about how we have been able to solve the (famous) ...
- 1,821
5
votes
1
answer
701
views
Is the Travelling Salesman Problem Considered as "Gradient Free Optimization"?
I was thinking about the Traveling Salesman Problem the other day - for such types of discrete combinatorial optimization problems, do they have a "loss function"?
It seems that there is ...
- 1,821
4
votes
2
answers
456
views
Multiple Pick-Up Delivery Problem with Time Windows
I am learning pick-up drop-off problems (variant of vehicle routing problems) with time windows. My problem is as follows:
There are orders that need to to shipped from pickup locations to delivery ...
- 619
1
vote
0
answers
66
views
GENIUS (General Insertion (GENI) + Unstringing / Stringing (US) - Anyone familiar with the procedure? I have questions
I am currently trying to understand the concept of GENIUS.
It was a method devoloped to solve the tsp.
The first step seems logical to me:
GENI (construction phase): start of with an tour of 3 nodes ...
- 533
2
votes
1
answer
155
views
Number of paths in asymmetric capacitated vehicle routing problem
This seems like a natural question, but I was not able to find an answer. My question is this. Consider a CVRP where $n$ customers have to be serviced by $m$ vehicles on any given day. All the ...
6
votes
1
answer
127
views
Lower bounds for TSP with k missing nodes
I'm struggling with this question for several weeks already and seem to be either stuck, or the bound is not going to be any better. Let's jump right into the problem:
Given a standard TSP on a graph $...
- 121
4
votes
1
answer
358
views
The difference between subtour-elimination constraints in the symmetric and asymmetric TSP
We know that there are lots of formulations for traveling salesman problem. Some of them are based on the directed graph (asymmetric) and others are based on the undirected graph (symmetric). Also, ...
- 8,382
2
votes
1
answer
89
views
How can I find the shortest path solution or even begin to finding the most optimal solution to a weld robot sequencing problem?
Not sure this belongs here, but I thought I'd ask: How should I come to an understanding of an optimal weld sequence for a weld robot that welds a physical item on a revolving carousel (the gray T ...
- 121
6
votes
3
answers
2k
views
Traveling Salesman Problem: How to avoid symmetry?
I solved a Traveling Salesman Problem (TSP) by the cutting plane method, i.e. adding violated sub-tour constraints until the LP relaxation is a tour. Now, I am realizing that, in this symmetric TSP, ...
- 63
6
votes
1
answer
233
views
How to cope with the rigidity of solutions?
Consider the following problem of Technician Routing and Scheduling Problem.
We have:
A set of customers where each customer needs the intervention of a technician to do some job. Each customer has a ...
- 309
7
votes
2
answers
723
views
Which approaches exist to solve a TSP?
Exists a list of categories that include possibilities to solve a travelling salesman problem (TSP)? I know, for example:
Exact methods
Integer Linear Programming
Dynamic Programming
Constraint ...
- 659
6
votes
1
answer
302
views
In which time complexity operates the Savings algorithm for the TSP?
In which time complexity operates the Savings algorithm from Clarke and Wright for the TSP? I mean the parallel version of Savings. I think it is in $\mathcal O(|V|\log|V|)$ with V as vertex/node ...
- 659
2
votes
0
answers
157
views
Why is exact TDTSP solving much harder to do than TSP solving?
I was thinking about exact methods for solving the Time Dependent TSP (TDTSP). Clearly, it is at least as complex as TSP because it extends TSP, but why is it for exact approaches that difficult to ...
- 659
9
votes
5
answers
472
views
Do better construction heuristics increase the performance of improvement heuristics?
Improvement heuristics for the TSP like 2-Opt need construction heuristics (also called constructive heuristics) like the Nearest Neighbour to start. Intuitively, I would say that a better ...
- 659
7
votes
2
answers
735
views
Is there a ranking of heuristics for the travelling salesman problem?
Does a ranking of TSP heuristics exist that is based on the quality of the solutions? For example a paper or another resource that compares the performance of TSP heuristics like the nearest neighbour,...
- 659
5
votes
0
answers
187
views
Reduction from Steiner Tree to TSP
The Steiner Tree version that I am considering is the following: given an undirected weighted graph $G=(V,E)$ and a subset of vertices $T \subseteq V$, find a minimum tree that connects all the ...
- 111
8
votes
0
answers
157
views
Traveling Salesman Problem: determine k-exchange feasibility
Given a current solution $S$ and a $k$-exchange move $(v_1, .., v_{2k+1})$ with $v_1 = v_{2k+1}$, $v_i \neq v_j$, $(v_i, v_{i+1}) \in E(S)$ iff $i$ odd, i.e. we remove all edges $(v_i, v_{i+1})$ for $...
- 2,495
1
vote
1
answer
212
views
Christofides algorithm, transform from Eulerian tour to Hamiltonian cycle
How do I do the change from an Eulerian tour to a Hamiltonian cycle in the Christofides algorithm? In the original paper from Christofides (1976)1 I found that
A Hamiltonian circuit $i$ of $G$ can be ...
- 659
5
votes
1
answer
170
views
Concorde with Apple Silicon M1
I am trying to install Concorde linked with QSOPT following these instructions. Regarding QSOPT, I downloaded files from section Intel MacOS 10.6 (64-Bit). But, as I have Apple M1 chip, it does not ...
- 89
4
votes
1
answer
206
views
Which constructive heuristics exist for the time-dependent TSP?
A constructive heuristic is a type of heuristic method which starts
with an empty solution and repeatedly extends the current solution
until a complete solution is obtained. (Wikipedia)
Which ...
- 659
2
votes
1
answer
398
views
Which constructive heuristics exist for the TSP?
A constructive heuristic is a type of heuristic method which starts with an empty solution and repeatedly extends the current solution until a complete solution is obtained. (Wikipedia)
Which ...
- 659
4
votes
1
answer
101
views
Size timesteps for time-dependent TSP
I'm solving a time-dependent travelling salesman problem. I have data from a whole year. I'm thinking about the size of the time steps. I think that the time-steps shouldn't be too large to be ...
- 659
7
votes
1
answer
143
views
Is there a real life application for the Bottleneck travelling salesman problem?
The bottleneck TSP tries to find a Hamiltonian circle which minimizes the longest edge. Is there any real world application for this for example in transportation?
- 659
1
vote
0
answers
320
views
Implement sequential formulation in TSP (Miller, Tucker, Zemlin)
I'm trying to solve a TSP in different ways. I already did it with the formulation of Dantzig, Fulkerson and Johnson und now I want to do use the Miller, Tucker, Zemlin constraint. $$u_i-u_j+nx_{ij}\...
- 659
3
votes
2
answers
3k
views
Travelling salesman problem variant without returning to the starting point
I tried the code provided on the link :
https://developers.google.com/optimization/routing/tsp
The actual requirement is to traverse all paths without returning to the start point with minimum ...
- 131
6
votes
2
answers
3k
views
Subtour elimination constraint in Travelling Salesman Problem
I am trying to understand travelling salesman problem, the Dantzig, Fulkerson, Johnson(1954) formulation. In the general formulation given below I am having trouble to implement subtour elimination in ...
user5245
-2
votes
1
answer
116
views
how to linearize the full model for TSP quadratic formulation?
I tried to solve this problem but I failed, please how to linearized full model.
- 45