# 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.

88 questions
Filter by
Sorted by
Tagged with
1k views

### Multiple Travelling Salesmen - How to make the second slowest salesman matter?

I'm building a Mixed Integer Linear Program for a variant of TSP I'm dealing with, where there are multiple salesmen. The way I have formulated the problem is that each agent has a time variable $T_i$ ...
46 views

### Does there exist a constant factor approximate solution for capacitated vehicle routing problem?

I know that there is a 1.5 approximate solution for metric traveling salesman problem (TSP), e.g., Christofedes algorithm guarantees this. Is there an algorithm that guarantees a constant factor ...
• 97
77 views

### Hungarian Algorithm returns Boolean value for Traveling salesman problem

I am trying to implement Hungarian algorithm right off the shelf on a cost dictionary as part of Traveling salesman problem. The goal is to get path with minimum cost which hopefully covers all cities ...
• 109
24 views

### Defining augmenting path for Traveling salesman problem

I am currently looking into solving TSP using Branch and Bound method. In the book by Wayne and Winston, they have solved each subproblem (i.e. tree nodes) using Hungarian algorithm. Using the lecture ...
• 109
100 views

### TSP with Optional Nodes

Suppose I have a graph $G(N,V)$, where $V = R\cup S$. $R$ is a set of nodes which must be visited, $S$ is a set of supporting nodes, i.e. nodes which can be used to build the route. The graph is ...
• 101
117 views

### Optimizing a Route Selection Problem with Multiple Constraints and Objectives

I'm developing a solution to optimize a vehicle routing problem where each stop has an associated score (priority), specific geo coordinates, and a required stop duration. The goal is to maximize the ...
• 131
453 views

### solver for Travelling Salesman Problem (TSP) with precedence constraints

I am very new to OR. I am trying to find the minimum cost sequence for a set of tasks that need to be executed. These tasks (at least some of them) have precedence constraints. For example, task T1 ...
1 vote
33 views

### Modeling start point constraint for TSP in the Dantzig-Fulkerson-Johnson formulation

I'm trying to use the DFJ formulation to solve TSPLib problems using JuMP and Gurobi. I want to add a constraint to the starting point by fixing either the start or the end to the first node (because ...
• 21
1 vote
42 views

### Installing Concorde on M1 Mac Guide for building ANN around TSP Problem

Im looking for a guide to install the Concorde TSP Solver on a M1 Mac. I have looked everywhere and haven't found a solution that worked for me. Any help would be appreciated.
96 views

### Ensure complete cycle in binary succession matrix LP [PuLP]

I have a set of orders N, for which i have to determine an optimal sequence. I wrap this decision within a binary matrix x[i][j], meaning whether i is succeeded by j. For example [[0 1 0 0] [0 0 1 0] [...
124 views

### Continuous optimization with a Euclidean TSP objective

I am trying to solve a problem of the form $$\min_{x_1,\dots,x_n} f(x_1,\dots,x_n)$$ subject to a constraint that $\mathrm{length}(\mathrm{TSP}(x_1,\dots,x_n))\leq c$, where $x_1,\dots,x_n$ are all ...
• 149
108 views

### Grocery Store Problem

I have an issue with my Excel function for a grocery store problem and I am not sure where I messed up the constraints. I have the value of the solution it should be (cost = 8,283). I need to make a ...
63 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
97 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 &...
• 123
351 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 ...
• 163
68 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
124 views

• 517
360 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'...
1k 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,841
173 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,841
120 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,841
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,841
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,841
757 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,841
620 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 ...
• 629
1 vote
73 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
163 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 ...
137 views

• 659
161 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
523 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