22 votes

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 ...
user avatar
18 votes

TSP with revenue maximization

Search for orienteering problem or prize-collecting TSP.
user avatar
  • 21.7k
18 votes

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 ...
user avatar
16 votes

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 ...
user avatar
  • 2,667
15 votes

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 ...
user avatar
  • 28.7k
13 votes
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 ...
user avatar
  • 2,665
13 votes
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 ...
user avatar
13 votes

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 ...
user avatar
  • 28.7k
12 votes

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 ...
user avatar
12 votes
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 ...
user avatar
11 votes
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 ...
user avatar
11 votes
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 ...
user avatar
10 votes

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 ...
user avatar
  • 1,313
9 votes

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 ...
user avatar
9 votes
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: ...
user avatar
9 votes

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 ...
user avatar
  • 28.7k
8 votes

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 ...
user avatar
8 votes
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 ...
user avatar
  • 1,502
8 votes

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/...
user avatar
8 votes
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 ...
user avatar
  • 8,185
8 votes

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.
user avatar
  • 366
8 votes
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 ...
user avatar
  • 2,609
8 votes
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 ...
user avatar
  • 10k
8 votes

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 ...
user avatar
  • 2,609
8 votes

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. ...
user avatar
8 votes
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 ...
user avatar
  • 28.7k
8 votes
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$ ...
user avatar
  • 10k
7 votes

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 ...
user avatar
  • 8,185
7 votes

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

I am a researcher in vehicle routing, and my answer is based on my experience as a researcher, conversations with practitioners and consultants, and seminars and conference talks I have attended. You ...
user avatar
7 votes

Comparing formulation for traveling salesman

As suggested by Larry Snyder in the comments to your question, you can reduce your problem to a standard traveling salesman problem by means of precomputing the distances. In particular, consider the ...
user avatar

Only top scored, non community-wiki answers of a minimum length are eligible