Skip to main content

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.

Filter by
Sorted by
Tagged with
6 votes
2 answers
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$ ...
John Smith's user avatar
2 votes
0 answers
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 ...
Krypt's user avatar
  • 97
0 votes
1 answer
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 ...
jayant's user avatar
  • 109
0 votes
0 answers
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 ...
jayant's user avatar
  • 109
0 votes
1 answer
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 ...
gdm's user avatar
  • 101
2 votes
1 answer
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 ...
Rastislav's user avatar
  • 131
3 votes
1 answer
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 ...
charumathi vasudevan's user avatar
1 vote
0 answers
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 ...
skittish's user avatar
1 vote
0 answers
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.
user14789444's user avatar
0 votes
1 answer
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] [...
QuestioningPanda's user avatar
3 votes
0 answers
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 ...
Tom Solberg's user avatar
-1 votes
1 answer
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 ...
zoomonkey101's user avatar
0 votes
0 answers
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 ...
uni_lad's user avatar
  • 39
0 votes
2 answers
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 &...
satk0's user avatar
  • 123
0 votes
2 answers
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 ...
Andrew's user avatar
  • 163
-1 votes
1 answer
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 ...
Abilash's user avatar
  • 63
3 votes
0 answers
124 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 ...
user11589's user avatar
1 vote
0 answers
147 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 ...
Djames's user avatar
  • 1,143
3 votes
0 answers
123 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 ...
Kathryn Twomey's user avatar
1 vote
2 answers
540 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....
Parseval's user avatar
  • 207
2 votes
2 answers
528 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?
J Fabian Meier's user avatar
3 votes
1 answer
117 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 ...
jkschin's user avatar
  • 365
3 votes
1 answer
251 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 ...
Philip's user avatar
  • 31
6 votes
2 answers
542 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 ...
mars's user avatar
  • 629
2 votes
0 answers
233 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. ...
Ozan Aksu's user avatar
5 votes
0 answers
224 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 ...
Ike348's user avatar
  • 343
5 votes
2 answers
232 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} =...
llilibbou's user avatar
2 votes
1 answer
580 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 ...
Fernando Martinez's user avatar
0 votes
1 answer
112 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 ...
Fernando Martinez's user avatar
7 votes
4 answers
1k 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}...
Snowflake's user avatar
  • 517
7 votes
3 answers
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'...
SomeThoughts's user avatar
6 votes
2 answers
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 ...
stats_noob's user avatar
  • 1,841
2 votes
1 answer
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 ...
stats_noob's user avatar
  • 1,841
2 votes
1 answer
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 ...
stats_noob's user avatar
  • 1,841
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&...
stats_noob's user avatar
  • 1,841
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) ...
stats_noob's user avatar
  • 1,841
5 votes
1 answer
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 ...
stats_noob's user avatar
  • 1,841
5 votes
2 answers
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 ...
mars's user avatar
  • 629
1 vote
0 answers
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 ...
Eddiee's user avatar
  • 533
2 votes
1 answer
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 ...
arunisnowhere's user avatar
6 votes
1 answer
137 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 $...
azaryc2s's user avatar
  • 121
4 votes
1 answer
411 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, ...
A.Omidi's user avatar
  • 8,960
2 votes
1 answer
92 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 ...
Loie Benedicte's user avatar
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, ...
LamBadaMan's user avatar
6 votes
1 answer
237 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 ...
BloodyOrange's user avatar
7 votes
2 answers
768 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 ...
maxmitz's user avatar
  • 659
6 votes
1 answer
388 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 ...
maxmitz's user avatar
  • 659
2 votes
0 answers
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 ...
maxmitz's user avatar
  • 659
9 votes
5 answers
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 ...
maxmitz's user avatar
  • 659
7 votes
2 answers
1k 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,...
maxmitz's user avatar
  • 659