# Tag Info

18

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 purposes it is free and easy to use (if you are familiar with C/C++)

17

Search for orienteering problem or prize-collecting TSP.

16

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 to find a good solution quickly. If you are interested in the best solution or need to know a bound on the best possible solution, then Concorde is the way to ...

13

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 make planning-level decisions. The online problem is solved as real-time information comes in, and tells us what to do at the low level (as in which vehicle should ...

13

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 hours to solve. One should probably add that "hard" always means "hard for some algorithm". So, for balance, here is a paper of Kate Smith-Miles & van ...

13

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 definitive book about TSPs ("In Pursuit of the Traveling Salesman: Mathematics at the Limits of Computation", Princeton University Press, 2012) and is one of ...

12

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 similar). But $n=30$ in that case. If you want to solve TSPs with, say, 1000 nodes, then $n^3$ is pretty big, and most of them are completely irrelevant. You will ...

11

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 more genetic search inspired aspects.

11

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 interesting to research finding tight compact formulations for the TSP from a theoretical perspective. In the paper by H. Sherali and P. Driscoll, the authors ...

11

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 general name of Travelling Salesman Problems with Profits. The main variants are: The Orienteering Problem (OP) in which you want to maximise the profit ...

10

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 suggest you have: 1.3.2 Multiple Depots 2.1.1.2 Heterogeneous Vehicles 2.2.1 Restrictions on Customer Waiting Time 2.2.2 Restrictions on Road Access 2.4 ...

9

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 separate variables Let $n$ be the number of customers and let $m \le n$ be the number of vehicles. For each vehicle $k = 1, \dots, m$, define the variables $$x_{ij}^k ... 9 Thanks to @Laurent Perron for their answer - I've tried modifying the code as follows, and it appears to work fine: from __future__ import print_function from ortools.constraint_solver import routing_enums_pb2 from ortools.constraint_solver import pywrapcp def create_data_model(): """Stores the data for the problem.""" data = {} data['... 8 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 visits: remove a number of sequential visits from a chain and insert it somewhere else in a chain, sometimes reversed swap 2 subchains ruin&recreate 8 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 instances with costs that satisfy the triangle inequality, if I am not mistaken. Nearest and cheapest insertion benefit from the fact that it can be shown that ... 8 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/VROOM-Project/vroom/blob/master/docs/API.md What you can is to start with the demo server to see if it can fit on small instances and then install it to use it as ... 8 Y. Kaempfer and L. Wolf, in their recent paper  applied ML techniques to solve the Multiple Traveling Salesmen Problem (mTSP). They provide a mathematical model for problem formulation which can be modified to cover what you need in the solution to your problem. You can replace the constraint (2d) which is:$$\forall 2\leq j \leq n: \sum\limits_{i=1}^{n}...

8

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

8

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 following the Dantzig–Fulkerson–Johnson formulation that you can easily find on the web (for example, on the Wikipedia page related to TSP). On the other, VRP is a ...

8

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 the constraint as follows: $$\sum_{i \in S}\sum_{j \in S, j\neq i} x_{ij} \le |S| -1 \quad \forall S \subset N, 2 \le |S| \le n-1$$ This means that you have ...

8

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 in polynomial time. Check the seminal paper "On the Complexity of Local Search for the Traveling Salesman Problem" by Papadimitriou and Steiglitz on ...

8

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. Punnen, eds. The traveling salesman problem and its variations. Vol. 12. Springer Science & Business Media, 2006.

7

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 bound to make the lemma more general. In the bound that you proposed the following assumption for the number of nodes must be true: $$|X|\ge 2$$ But in the ...

7

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 make a very interesting observation: solving VRP's to optimality is currently only possible for hundreds of customers, while problems in practice are ...

7

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 complete graph with nodes given by $S$. Moreover, consider as distance between nodes $s_1$ and $s_2$ the shortest path between those nodes in your original ...

7

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. However, if your network has nodes $a$, $b$, $c$ such that $$d(a,b) \geq d(a,c) + d(c,b)$$ any path that goes from $a$ to $b$ will always go through. So you can ...

7

So you are dealing with a configuration where for any path $A-B-...-Z$, the reverse path $Z-...-B-A$ is also valid. To break this symmetry, you can impose that the index of node $A$ must be smaller than the index of node $Z$: $$x_{i0} \le \sum_{j| j\le i}x_{0j}\quad \forall i$$ This way, if arc $(i,0)$ enters the depot, then there must be a lower indexed ...

6

Stating the obvious, even if you don't have a depot in its traditional definition, you can still use dummy nodes as your depot(s). I think an area closer to what you are looking for can be Ambulance dispatching. It has a richer literature compared to other roadside assistance type VRP. Moreover, during disasters, the roads can be blocked or very hard to ...

6

As @OguzToragay has mentioned, writing $\sqrt{2(n-1)ab}$ instead of $\sqrt{2(n-2)ab}$ allows for the trivial case of one point in the Euclidean plane since $|X|\ge1$ in section 2. The other point to make is that writing $2(a+b)$ instead of $3a/2+2b$ means that $T^*(X)$ can be succinctly expressed in terms of the perimeter of a rectangle, as in the case in ...

6

You can create three nodes for one city. In other words, You create a bus station, train station, airport in one city. If you arrive in city A with a train but leave with a plane, you have to move from the train station to Airport. And then you can assign 0 (or appropriate quantities, emission or time) for moving between any of them within the same city. ...

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