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
1
vote
1answer
105 views

Travelling salesman problem variant without returning to the starting point

I tried the code provided on the link : https://developers.google.com/optimization/routing/tsp The actual requirement is to traverse all paths without returning to the start point with minimum ...
5
votes
1answer
167 views

Subtour elimination constraint in Travelling Salesman Problem

I am trying to understand travelling salesman problem, the Dantzig, Fulkerson, Johnson(1954) formulation. In the general formulation given below I am having trouble to implement subtour elimination in ...
-2
votes
1answer
63 views

how to linearize the full model for TSP quadratic formulation?

I tried to solve this problem but I failed, please how to linearized full model.
1
vote
1answer
188 views

Textbook recommendation for multiple traveling salesman problem transformation to standard TSP

I am looking for a good textbook explaining: "Transformation of Multiple Traveling Salesmen Problem to the Standard Traveling Salesman Problem."
3
votes
1answer
194 views

TSP with Repeated City Visits

Suppose that we have a standard TSP, except that it is required to visit each city at least once instead of exactly once. The challenge is: how to transform this problem to a standard TSP? To that ...
1
vote
1answer
37 views

Equivalence of Shortest Hamiltonian Paths with a Starting Node to Traveling Salesman Problem

Q- Can someone explain the equivalence in detail please?
1
vote
1answer
63 views

Equivalence of Shortest Hamiltonian Paths to Traveling Salesman Problem

Two questions: Q1- Why do we need to add "bidirectional" arcs (instead of single directional arcs) between the new node n + 1 and with every node in the original network? Q2- Why is the ...
0
votes
1answer
104 views

Miller-Tucker-Zemlin subtour elimination constraints to obtain a minimum spanning tree

I need Miller-Tucker-Zemlin subtour elimination formulation for symmetric traveling salesman problem (STSP) to use to construct a minimum spanning tree. Ie, I need Miller-Tucker-Zemlin formulation ...
6
votes
2answers
185 views

Solving the (Directed) Hamiltonian Cycle problem

I need to solve instances of the Directed Hamiltonian Cycle Problem (DHCP). I know that I can reduce the problem to TSP and then use a TSP solver like concorde. I am unable to figure out though how to ...
4
votes
0answers
94 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
305 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
151 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
170 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
216 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
250 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 ...
11
votes
1answer
291 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
604 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: ...
25
votes
5answers
1k 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
1k 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
339 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
436 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
739 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
352 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
205 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
2answers
141 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
222 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
545 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
138 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 ...