Questions tagged [traveling-salesman]

The "traveling salesman problem" is a classical computer science problem which involves finding the shortest path which could be taken by a hypothetical salesman to make a single visit to each location on a map (in a graph).

Filter by
Sorted by
Tagged with
0 votes
0 answers
35 views

How to create an heuristic for the TSP algorithm with specific description? [closed]

I'm trying to execute the TSP algorithm in python (using aima-python environment) and I have to create the following heuristic: h1: Heuristic that considers the minimum arcs of the cities that remain ...
gitblanc_'s user avatar
0 votes
0 answers
33 views

Traveling Salesman Problem (Dynamic Solution)

I have managed to implement a dynamic TSP algorithm and the code works and runs but it produces the wrong output for larger data sets This is my code //TSP Dynamic Application public static ...
Akshat Newal's user avatar
0 votes
0 answers
23 views

Discrepancy in Routing Results Between pgr_TSP Versions (3.1.2 vs. 3.2.1)

I've been working with the pgr_TSP function in the pgrouting library, and I noticed a change in its behavior between versions 3.1.2 and 3.2.1. Specifically, it seems that in 3.2.1, the algorithm was ...
postgis-user's user avatar
0 votes
0 answers
23 views

RuntimeError: Index tensor must have the same number of dimensions as self tensor

I am running a deep reinforcement learning code and I got this error: RuntimeError: Index tensor must have the same number of dimensions as self tensor The code snippet that is related to this error ...
白茶三斤's user avatar
0 votes
1 answer
38 views

TSP with CP-SAT: How to set certain node-visits at specific time

I am solving a TSP with CP-SAT as shown in https://github.com/google/or-tools/blob/master/examples/python/tsp_sat.py, but i have some constraints that i am not able to formulate: I have some "...
BRaabe99's user avatar
0 votes
0 answers
14 views

Using DEAP for TSP with Disconnected Vertices: Seeking Guidance on Penalty Variable Failures

I am trying to use the DEAP package to solve the TSP where the matrix represents the distances between the vertices, taking into account that some of the vertices are not connected. How can I make ...
Julio Trujillo Gonzalez's user avatar
1 vote
2 answers
128 views

Travelling Salesman Problem - Best path to go through all points

I am trying to solve an exercise based on the travelling salesman problem. Basically I am provided with a list of points with their coordinates, like this: [(523, 832), (676, 218), (731, 739), ..] (a ...
Shark44's user avatar
  • 653
0 votes
0 answers
13 views

Traveling Salesman Problem - Eliminating Subtours?

I'm trying to optimize a road trip across the U.S. in an iJulia notebook. I'm currently having issues with subtours. Instead of creating one fluid trip, the solution jumps around from place to place. ...
Liamilus's user avatar
1 vote
0 answers
18 views

TSP Solver Issue. Can't find correct tour

I want to solve the TSP given a distance matrix. However my code only returns "array([0, 0, 0, 0])" meaning it wants to just stay in the current location and not leave. But i obviously want ...
Lino's user avatar
  • 51
0 votes
0 answers
9 views

Can I use different cost functions in prior( η) and posterior(τ) functiona in Ant Colony Optimization?

For TSP(Traveling Salesman Problem) solving by ACO(Ant Colony Optimization), I've read something like Ant Colonies for traveling salesman problem, The Ant Colony Optimization Meta Heustic, aco2004.prn....
fulltopic163's user avatar
0 votes
0 answers
33 views

Scipy.optimize.linprog : OptimizeWarning for A_eq Rank, how do I find redundant constraints for TSP?

I was solving the TSP and I got this error : "OptimizeWarning: A_eq does not appear to be of full row rank. To improve performance, check the problem formulation for redundant equality ...
NEWO-o's user avatar
  • 1
0 votes
1 answer
108 views

Defining the linear programming constraints in the Traveling Salesman Problem (TSP) for the scipy.optimize.linprog Python function

I am trying to solve the Linear Programming formulation of the Traveling Salesman Problem (TSP) using scipy.optimize.linprog in Python. This document clearly defines the problem and, though I ...
NEWO-o's user avatar
  • 1
0 votes
1 answer
57 views

Using Scipy's linprog and the simplex method, how do I solve a simple tableau and get the expected results?

I am trying to solve a simple simplex tableau using the python library scipy. c = [7, 9, 18, 17] A = [ [2, 4, 5, 7], [ 1, 1, 2, 2], [ 1, 2, 3, 3] ] b = [42, 17, 24] from scipy.optimize ...
NEWO-o's user avatar
  • 1
0 votes
0 answers
73 views

Dummy node for TSP and finding shortest Hamiltonian Path

Can anyone provide assistance to the problem I'm facing? I'm working on implementing a delivery system algorithm. I have attempted to solve it using a graph, where addresses are represented as nodes ...
IlayAsayag's user avatar
0 votes
0 answers
16 views

Loop in R, VNS for TSP

I am doing a VNS algorithm in R for a TSP (Travelling Salesman Problem), however I'm having trouble with selecting more than one neighbours. When I solve the first combination of cities and one ...
Han's user avatar
  • 1
0 votes
1 answer
154 views

Modified TSP with Branch-and-Bound algorithm

I've been struggling to solve it using branch-and-bound to find the optimal path for the next task: There's a list of cities, that are all connected with each other, basically, a complete graph, each ...
unfavourite's user avatar
1 vote
1 answer
37 views

TSP with only one key to identify a road

I need to solve Traveling Salesman Problem in Python using PuLP. import pulp import numpy as np import matplotlib.pyplot as plt n = 50 np.random.seed(42) x = 1.5*np.random.rand(n) y = np.random.rand(...
john347231's user avatar
4 votes
1 answer
201 views

The Travelling Salesman Problem Using Genetic Algorithm

I was looking to learn about AI and found the traveling salesman problem very interesting. I also wanted to learn about genetic algorithms, so it was a fantastic combo. The task is to find the ...
zellez's user avatar
  • 398
1 vote
0 answers
61 views

OR Tools taking infinite time for MVRP

I am trying to solve MVRP problem using Google OR-Tools where I have 1000 points and 30 fleets(Vehicles). This seems to take indefinite amount of time but when I am reducing the fleets(vehicles) to 1 ...
Varun Singh's user avatar
0 votes
0 answers
48 views

How to implement an algorithm for an optimised schedule for a person on holiday based on multiple factors?

Hi i want to do a trip planner application using android studio application using java i have set up firebase, google maps and places apis. From user inputs of several saved locations, i hope to ...
shjonz's user avatar
  • 11
0 votes
0 answers
32 views

TSP using Simulated annealing

I am doing the problem "Deliverer's Path" (TSP) using Simulated annealing algorithm. The problem is that after solving, the evaluation difference has reached a good value, but the optimal ...
Trọng Minh's user avatar
0 votes
0 answers
111 views

Using LKH solver to find the shortest route for a tsptw

I need to solve a bunch of tsp with time windows, I'm working with python and using the LKH package (since it is the state of art solver next to concorde). The goal of my work is to optimize a given ...
Beatriz Santos's user avatar
1 vote
0 answers
33 views

JavaScript/JQuery - Object property values are changing when looping through them

We are attempting to create a routing (TSP) algorithm that loops through a data structure that holds our vehicles and our trip information. It all starts with an ASYNC function called acquireData that ...
acc_it's user avatar
  • 11
0 votes
0 answers
115 views

Evaluate algorithm for the Travelling Salesman Problem (TSP)

It is my first post in this site, so please excuse if something is not clearly explained (and please, provide feedback to improve wording if necessary!). I have been thinking on an algorithm to ...
Juan Moreno's user avatar
0 votes
0 answers
20 views

How integrate time window constraints to dynamic programming to solve tsp problem?

I have recursive dynamic programming code that solve TSP while minimizing the travelling cost. But I can't integrate the time window constraints. Please, I need your help.
atef's user avatar
  • 11
0 votes
1 answer
177 views

Optimization of Travelling Salesman Problem Nearest Neighbor algorithm with Limited Weight per cycle

Currently working on a TSP problem, and the idea is to optimize it for the use of restaurants, thus making food delivery easier. One of the criteria is that each path the courier takes has to have ...
huntrese's user avatar
0 votes
1 answer
102 views

tidying igraph plot and routing or TSP question

I have less experience in R and I need help tidying my plot as it looks messy. Also, my project is to find the best minimal route from Seoul to every city and back to Seoul. It is almost like ...
zwen hms's user avatar
0 votes
1 answer
112 views

In R, is it possible to solve the traveling salesman problem exactly without using Cygwin?

I am trying to find a solution to a traveling salesman problem (TSP) in R. The "TSP" package gives heuristic and often stochastic solutions unless one uses the external Concorde solver. ...
L. Mann's user avatar
  • 143
1 vote
0 answers
69 views

Pulp creates LpProblem as a NoneType

I'm currently studying TSP formulations using Pulp in Python. Originally, I was using three different point sets with 29, 38 and 194 cities, and the code solved them pretty well and even got the ...
Gabriel Sanches da Silva's user avatar
-1 votes
1 answer
96 views

How can I visualize an adjecency matrix as a graph in C#?

So, I have a winforms application with travelling salesman problem using Prim's algorithm and I need to convert my adjacency matrix, that is realized as DataGridView, to graph. Is it possible to do ...
neonbones's user avatar
0 votes
0 answers
64 views

Collect all pickups while passing on the street for the first time in Jsprit

I'm trying to solve a simple TSP with Jsprit. I only have 1 vehicle and a total of about 200 pickups. This is my vehicle routing algorithm code: val vrpBuilder = VehicleRoutingProblem.Builder....
devmatteo's user avatar
0 votes
1 answer
173 views

Christofides TSP; let start and end node be those that are the farthest apart

I'm using Christofides algorithm to calculate a solution for a Traveling Salesman Problem. The implementation is the one integrated in networkx library for Python. The algorithm accepts an undirected ...
Hendrik Wiese's user avatar
0 votes
0 answers
59 views

Python IndexError in my Nearest Neighbour Algorithm for TSP

I am trying to solve TSP using the nearest algorithm, but I got stuck at the IndexError: boolean index did not match indexed array along dimension 0; dimension is 1 but corresponding boolean dimension ...
iri's user avatar
  • 21
0 votes
0 answers
213 views

Implementation cuckoo search algorithm (TSPLIB, python

I am implementing an improved cuckoo search algorithm for research (link below). This algorithm should work very very well, however my implementation is approximately 1.5 times of the optimal on the ...
kGame's user avatar
  • 21
1 vote
0 answers
58 views

How to find the optimal path and values from a subset of multi-dimensional variables?

I am working on designing an experiment, where a system can receive 5 inputs [x1, x2, x3, x4, x5] and record target data associated with this "state". Given a new input state, the system ...
tishafok's user avatar
0 votes
1 answer
66 views

Python and Pandas - Distances with latitude and longitude

I am trying compare distances between points (in this case fake people) in longitudes and latitudes. I can import the data, then convert the lat and long data to radians and get the following output ...
Milo's user avatar
  • 33
0 votes
0 answers
20 views

How can I write a heuristics function for a tsp problem?

I am running a graph search(with different types of search like ucs, bfs, dfs, greedy, and a*) on a tsp problem, I am however running into an issue with greedy and a* search because I am stuck with ...
CyberSham's user avatar
0 votes
0 answers
34 views

Is it possible to show edges in the front layer of a multigraph based on colour since edges are overlapping?

I have a complete graph G of 214 nodes and therefore a looot of edges. In this graph I have a subset of edges that are coloured red, however almost all edges are overlapped by other edges and ...
kGame's user avatar
  • 21
0 votes
0 answers
80 views

Define start point for TSP using mlrose

I followed a tutorial on how to use mlrose for TSP. The tutorial didn't cover on how can I define the start point (and also end point of the optimized route). How can I do it (if I can do it). I'll ...
JM Aido's user avatar
  • 13
0 votes
0 answers
123 views

Solving Dynamic Programming for Travelling Salesman Problem - Java

I want to implement a dynamic programming solution for travelling salesman problem. I have managed to solve it with the code below: `package tsp; import java.util.Arrays; import java.util.Collections; ...
Jeremy's user avatar
  • 21
0 votes
0 answers
134 views

Travelling Salesman Problem, It takes so long to implement

I got Travelling Salesman Problem code from geeksforgeeks website ( https://www.geeksforgeeks.org/traveling-salesman-problem-tsp-implementation/ ) and try to implemented on 26 different city, but when ...
Mr.ZeroX's user avatar
-1 votes
1 answer
236 views

Find shortest path in graph with a set starting node and that goes through a subset of nodes

Basically my goal is to find the target node to solve the TSP. In order to find this target node I need to know the shortest path between two nodes, specifying only the starting point where: The ...
Joan's user avatar
  • 1
1 vote
0 answers
23 views

Switch positions in array and switch order

As a uni project I'm trying to implement the simulated annealing to solve the traveling salesman problem using python. I need to find the neighbors of my initial solution and I'm not quite sure how ...
João Oliveira's user avatar
0 votes
0 answers
210 views

How to draw a line that crosses all points by using a list of point indices?

I have the following lists that correspond to 6 (clients) points (each one having an id, and x and y coordinates) allIds = [0, 1, 2, 3, 4, 5], allxs = [50, 25, 43, 80, 25, 18] allys = [50, 54, 96, 50,...
Yannis_Tr's user avatar
3 votes
1 answer
69 views

what does n^O(1/ε) means?

I often find n^O(1/ε) in approximation algorithms. for example, in euclidean tsp, the number of portals(with its possible state) is equal to n^O(1/ε). here is the link to the source http://algo2.iti....
ryan chandra's user avatar
1 vote
0 answers
28 views

how do we know the L = 4n^2 in euclidean TSP algorithm?

I am trying to understand the euclidean TSP algorithm. From most of the explanations available online, we set the value of L = 4n^2. is there any explanation for why L has that value? Here is the ...
ryan chandra's user avatar
3 votes
2 answers
430 views

How to verify if a graph has crossing edges in networkx?

I am creating a genetic algorithm to solve the traveling salesman problem using python and networkx. And I'm adding a condition to converge to a satisfactory solution: the path must not have crossing ...
Fabricio Brum's user avatar
2 votes
1 answer
151 views

Wrong answer due to precision issues?

I am implementing Greedy Approach to TSP: Start from first node. Go to nearest node not visited yet. (If multiple, go to the one with the lowest index.) Don't forget to include distance from node 1 ...
MangoPizza's user avatar
0 votes
0 answers
127 views

Nearest neighbor/Travelling salesman problem in Neo4j

I want to solve nearest neighbors/travelling salesman problem using Neo4j database. I have 200 cities that are connect with one another. I have tried using this code below to solve the problem but it ...
fhoidhdoi's user avatar
0 votes
2 answers
657 views

Find the final path of Traveling Salesman Problem

I am trying to implement the Traveling Salesman Problem and I need to return the path that lead to the minimum cost. I have a distance matrix, and this is the code: static int TSP(int[][] distance, ...
Oana's user avatar
  • 19

1
2 3 4 5
15