# 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
Filter by
Sorted by
Tagged with
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
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
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
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
104 views

• 517
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'...
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
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
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
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
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
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
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
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
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 ...
127 views

• 2,495
1 vote
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
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 ...
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
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
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
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
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
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