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
4
votes
0answers
86 views

Can this problem be modelled with a transformation from a known TSP with profits?

The profitable tour problem (PTP) is defined on a graph $G=(V,E)$ with $|V|=n$, where each vertex $i \in V$ has an associated prize $m_i \geq 0$ and each edge $e \in E$ has an associated cost $c_e \...
9
votes
5answers
251 views

How to model a TSP where the salesman can choose between flight, train and bus for every single connection?

I want to model a multiobjective TSP where the salesman can choose between a flight, train and bus to go from city $i$ to city $j$. The aim of this multiobjective optimization problem is to minimize ...
8
votes
1answer
128 views

Heuristic Search Planning Tree Leading to Worse TSP Solutions than Naive Greedy

I'm doing a Traveling Salesman Problem (TSP) homework for a coursera optimization course. My first attempt was a regular naive greedy approach, from each point, moving to the closest node (that hadn't ...
4
votes
1answer
129 views

TSP subtour elimination with multiple formulations

Referring to the question here. Given a set $S$, which we need to travel following TSP rules. I was wondering if this sub tour elimination method is good enough or not? Let $b_{i,j}$ denote edge ...
3
votes
1answer
204 views

Comparing formulation for traveling salesman

I have a graph $G$ and have a set $S$ which are the points in the graph to visit in a TSP manner. Since the length of the TSP route can't be known as it can use any number of nodes to complete the ...
5
votes
1answer
173 views

TSP with constraints in OR Tools

I am completely new to OR Tools, but what I have tried so far seems very powerful. I have, however, run into a problem that I cannot seem to figure out how to solve. I am trying to model a TSP ...
10
votes
0answers
103 views

Column generation for TSP

For teaching purposes, I would like to solve the Travelling Salesman Problem with a column generation approach. In the academic literature, an approach is proposed (for example here), where columns ...
8
votes
1answer
545 views

Travelling salesman problem with given number of locations to visit

There's a great example here of how to find a solution to the travelling salesman problem: ...
17
votes
3answers
563 views

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

After a bit of reading I think I've been able to conclude that state-of-the-art VRP can get solutions for 100~500 stops. My question is around how this actually affects logistics (like Amazon for ...
17
votes
3answers
864 views

TSP with revenue maximization

How to approach a travelling salesman problem with an aim to maximize revenue at each town visited in a certain number of days (total number of towns is greater than what can be visited in the given ...
11
votes
4answers
332 views

Proof of bound on optimal TSP tour length in rectangular region

Lemma 3 in Haimovich and Rinnooy Kan (1985) (Math of OR 10(4):527–542) says: If $X$ [the set of nodes] is contained in a rectangle with sides $a$ and $b$, then $$ T^*(X) \le \sqrt{2(n-1)ab} + 2(a+...
11
votes
1answer
318 views

How to solve the Cumulative Traveling Salesman Problem using or-tools in python?

The objective of the Cumulative Traveling Salesman Problem (CTSP) is to minimize the sum of arrival times at customers, instead of the total travelling time. This is different than minimizing the ...
11
votes
5answers
711 views

What is the following VRP?

I am researching a Vehicle Routing Problem for a safety insurance company that provides roadside assistance. The company does not have a depot, as in classical VRP, and has a set of heterogeneous ...
25
votes
1answer
279 views

The rationale to improve MTZ?

Currently I need to solve a quite specific problem involving symmetric TSP as a sub-problem (i.e., a Hamiltonian cycle is a necessary condition for optimizing some problem-specific variables that ...
14
votes
3answers
2k views

A variant of the Multiple Traveling Salesman Problem

I am trying to find a reference (or a reformulation) of a variant of the multiple Traveling Salesman Problem, where multiple agents need to visit each vertex in a graph with minimal cost. Most of the ...
18
votes
2answers
181 views

Small Traveling Salesman Problem instance

The Traveling Salesman Problem is perhaps the most studied of all combinatorial optimization problems. There has been a lot work in solving TSP instances to provable optimality. Concorde solves very ...
11
votes
1answer
89 views

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

For some insertion-type heuristics for the traveling salesman problem, we have a fixed worst-case error bound of the form: $$\frac{z^H}{z^*} \le \eta,$$ where $z^H$ is the objective value of the ...
14
votes
2answers
172 views

Subtour elimination constraints - enumeration vs dynamically adding

The classical constraints to prevent subtours in routing problems (i.e., to make sure every route is connected to a depot), are of the following form, $$ \sum_{(i,j) \in \delta(S)} x_{ij} \leq |S| - 1 ...
21
votes
5answers
377 views

Solving ATSP problem for large-scale problem

I want to solve the Asymmetric TSP for a large-scale problem for an industrial application where the company cannot buy a commercial software license. For their applications, it is very important to ...
11
votes
2answers
121 views

Neigbourhoods in Large Neighbourhood Search (LNS) algorithms

I have been trying to implement a variant of LNS on a graph for TSP. One of the ways that I can define a neighborhood for TSP is to find $k$-shortest path between two nodes. But the choice of these ...