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 ...
- 3,168
19
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 ...
- 1,859
18
votes
17
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 ...
- 2,727
16
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 ...
- 37.5k
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 ...
- 2,705
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 ...
- 11.9k
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 ...
- 37.5k
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 ...
- 2,073
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 ...
- 2,362
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 ...
- 1,859
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 ...
- 2,295
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 ...
- 1,333
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 ...
- 6,033
9
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 ...
- 8,592
9
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/...
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:
...
- 271
9
votes
Accepted
TSP with Repeated City Visits
If the distance between your nodes follows the triangle inequality (you can never travel faster between two points by adding an intermediary step), then the shortest path visits each node only once.
...
- 3,965
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 ...
- 37.5k
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 ...
- 4,685
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 ...
- 1,542
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.
- 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 ...
- 2,910
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 ...
- 12.8k
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 ...
- 2,910
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. ...
- 3,352
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 ...
- 37.5k
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$ ...
- 12.8k
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 ...
- 8,592
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 ...
- 6,033
Only top scored, non community-wiki answers of a minimum length are eligible