# Tag Info

### Are Metaheuristics and Evolutionary Algorithms the "Gold Standard" for the Traveling Salesman Problem?

The answer to the question is: No. (Although one can debate what exactly is a "metaheuristic") The "gold standard" for finding high quality feasible solutions for the TSP is the ...
• 2,699

### TSP with revenue maximization

Search for orienteering problem or prize-collecting TSP.
• 21.7k

### Solving ATSP problem for large-scale problem

If you are interested in solving the TSP, the Concorde TSP solver is a very powerful and easy-to-use tool. I do not know what the licensing options are for commercial applications, but for research ...
• 1,839

### Solving ATSP problem for large-scale problem

If you cannot use Concorde as suggested by Albert, I'd suggest you look for an implementation of the Lin-Kerninghan-Heuristic (which is also included in Concorde). It iterates between 2-opt and 3-opt ...
• 2,667

### Is Traveling Salesman Problem "Combinatorial Optimization" or "Integer Optimization"?

I'm not sure that the terminology is used consistently enough to give a firm answer. Pretty much everyone would agree (I think) that the TSP is a combinatorial optimization problem. To me, asking ...
• 28.7k
Accepted

### Small Traveling Salesman Problem instance

There is a paper of Ahammed and Moscato on finding hard instances for Concorde using Lindenmeyer systems. They were able to find small instances with about 1500 cities that took (in 2011) more than 4 ...
• 2,665
Accepted

### What's the current status of the Vehicle Routing Problem in the logistics industry?

The answer to this question is quite complicated. There are two main types of vehicle routing problems, the offline and the online problem. Solving the offline problem takes longer and is used to ...
• 11.1k

### Which approaches exist to solve a TSP?

I doubt there is a complete listing of every possible approach to TSPs. You can find a significant amount of information on Bill Cook's site. Bill Cook wrote what I believe many consider the ...
• 28.7k

### TSP with revenue maximization

There are a few problems in this category. They are variants of the Travelling Salesman Problem in which you don't need to visit all customers, but can choose which ones to visit. They fall under the ...
• 1,993
Accepted

### Subtour elimination constraints - enumeration vs dynamically adding

This has to depend on instance size. For a sports scheduling problem I worked on, it definitely made life easier to simply put in all the $|S| \le 3$ constraints (not exactly subtour, but very ...
• 2,227
Accepted

### Neigbourhoods in Large Neighbourhood Search (LNS) algorithms

This paper by Pisinger and Ropke is particularly useful when working on (A)LNS, and provides great guidance and an overview of operators/neighborhoods. I would suggest this paper by Vidal et al. for ...
• 1,839
Accepted

### The rationale to improve MTZ?

Why would people spend time improving MTZ, if DFJ is much tighter and all compact MTZ improvements never come close to DFJ? Although this might not be used in TSP solvers, it could still be ...
• 2,244

### What is the following VRP?

This recent review on rich routing problems may be helpful: http://repository.psau.edu.sa/jspui/retrieve/6358c84c-e14d-4e4c-8645-c8f7320606ab/EJOR_2015.pdf A quick scan on the categories would ...
• 1,313

### A variant of the Multiple Traveling Salesman Problem

You can model your problem by defining separate variables for each traveling salesman. Below I will use 'vehicle' instead of 'traveling salesman', which is more common in this setting. Defining ...
• 5,873
Accepted

### Travelling salesman problem with given number of locations to visit

Thanks to @Laurent Perron for their answer - I've tried modifying the code as follows, and it appears to work fine: ...

### Confusion Between Different Types of Optimization Problems

I'm inclined to treat "discrete optimization" and "combinatorial" optimization as synonyms, but I'm not sure everyone does. "Integer programing/optimization" is a ...
• 28.7k

### Neigbourhoods in Large Neighbourhood Search (LNS) algorithms

These common neighborhoods for TSP/VRP might be useful: 2-opt, 3-opt, ..., k-opt change 1 visit: remove 1 visit from a chain and insert it somewhere else in a chain swap 2 visits change a subchain of ...
• 4,377
Accepted

### Is there a fixed worst-case error bound for farthest-insertion?

To my knowledge, there is yet no known constant worst-case error bound $\eta$ for farthest insertion nor a proof that no constant bound exists. The results you mention here require symmetric TSP ...
• 1,502

### Solving ATSP problem for large-scale problem

You could also give a try to VROOM, which can be used for commercial use. It can solve TSP and some variants of the VRP such as VRPTW and CVRP. Here is the API documentation : https://github.com/...
Accepted

### A variant of the Multiple Traveling Salesman Problem

Y. Kaempfer and L. Wolf, in their recent paper [1] applied ML techniques to solve the Multiple Traveling Salesmen Problem (mTSP). They provide a mathematical model for problem formulation which can be ...
• 8,185

### Small Traveling Salesman Problem instance

There is a paper by Papadimitriou and Steiglitz here to construct instances, which are very hard for local searches to find optimal solution.
• 366
Accepted

### Column generation for TSP

As Marco briefly explained in his comment, TSP is not the ideal problem to teach the column generation approach. TSP is suited for the row generation approach, also known as branch-and-cut, by ...
• 2,609
Accepted

### Subtour elimination constraint in Travelling Salesman Problem

I think one of the reasons you have difficulties implementing the constraint is because it is not written correctly. You need to be more precise with your indexes. If $N:=\{1,...,n \}$, you can write ...
• 10k

### Do better construction heuristics increase the performance of improvement heuristics?

There are some proofs of the contrary: whatever the starting point, your local search can be stuck in solutions far away from the optimum. Here "local" means that each iteration must be done ...
• 2,609

### Which approaches exist to solve a TSP?

Some additional sources to help you answer your question: Cook, W. "In pursuit of the traveling salesman: mathematics at the limits of computation. 2012." Gutin, Gregory, and Abraham P. ...
• 3,046
Accepted

### Is the Travelling Salesman Problem Considered as "Gradient Free Optimization"?

In no particular order ... I wouldn't call the objective function of the TSP "vague". It is quite explicit. The term "gradient-free" applies to algorithms, not to problems. You ...
• 28.7k
Accepted

### Interpretation of a subtour elimination constraint in the TSP

These constraints are called Miller-Tucker-Zemlin (MTZ) constraints, you can find a lot of technical notes online. They impose that a node can only be visited once. You can think of the $u_i$ ...
• 10k

### Proof of bound on optimal TSP tour length in rectangular region

I went over all the math included in the proof and confirmed that your claim which is: $$\frac{3a}2+2b+\sqrt{2(n-2)ab}\le\sqrt{2(n-1)ab}+2(a+b)$$ is true. But I think they didn't use the tighter ...
• 8,185