The Stack Overflow podcast is back! Listen to an interview with our new CEO.

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
6
votes
1answer
917 views

2-opt algorithm for the Traveling Salesman and/or SRO

In this question I present a method to solve the Traveling Salesman Problem and/or the Single Route Optimization problem. I am extracting 100 lat/long points from Google Maps and placing these into a ...
8
votes
2answers
3k views

Genetic algorithm for Traveling Salesman

I have implemented a genetic algorithm in python 3 for a programming assignment, and I think all the logic is correct. A friend of mine has also implemented one which carries out similar logic, ...
3
votes
1answer
5k views

Traveling Salesman Solution

The intended purpose for posting here is to have more experienced software developers review my code, test it, and improve it. Should it to hold up, my ultimate goal is to construct a proof that ...
3
votes
0answers
109 views

Creating a TSP level with a linked list

I am trying to solve the Travelling Salesman Problem. This function creates the first level in the form of a linked list. This is what the levels look like: This is the code that creates it: ...
-1
votes
2answers
739 views

Travelling salesman with something like MST

My objective is to solve travelling salesman problem. Program input is 100 lines, each having three numbers: first of them is city ID, and the next two are x and y coordinates. Example line: ...
6
votes
1answer
143 views

Low C performance for TSP heuristic

I've been recently doing classes on the traveling salesman problem. I've been tackling the nearest neighbor heuristic for the problem and seeing that the algorithm was simplistic, I've decided to see ...
3
votes
2answers
6k views

Traveling Salesman Problem genetic algorithm

This is my take on this problem. I don't pre determine the distances, it's not suitable for the application I'll use it for. I'll use it in shool to determine some a mean total distance and how to ...
0
votes
1answer
785 views

Attempting to solve the Travelling Salesman Problem using idiomatic C++

Please tell me anything that comes to mind. However, I am most interested in ways to make my code more idiomatic (modern) C++. tsp.h: ...
1
vote
0answers
2k views

Comparing a recursive and iterative traveling salesman problem algorithms in Java

This snippet is about two (brute-force) algorithms for solving the traveling salesman problem. Since there is plenty of boiler-plate code, I arranged a GitHub repository for the entire program, in ...
2
votes
1answer
92 views

Traveling Salesman Planet Edition

I completed this problem for an interview and my solution as rejected; of course no reasons were provided. I opted to use the nearest neighbour algo based on the timeframe allotted and having no ...
2
votes
1answer
1k views

Travelling Salesman Problem solver

I am writing a program that can implement algorithms to solve the TSP. My goals: The solver can record every algorithm step, so that the whole solving process can be later visualised by charts or ...
7
votes
1answer
2k views

Travelling Salesman problem using GA, mutation, and crossover

I created a short python program that can create a list of random unique nodes with a given length and a given number of strategies. The GA runs through a given number of generations, changing a ...
3
votes
1answer
5k views

TSP via Nearest Neighbour

I have written code to implement the nearest neighbour algorithm to produce a solution for the TSP problem On my machine, the code takes roughly 10 seconds. Since this is so short, a lot of the ...
3
votes
3answers
5k views

TSP Brute Force Optimization in Python

I am currently working on a Python 3.4.3 project which includes solving the Traveling Salesman Problem using different algorithms. I have just written a brute force algorithm and I would love some ...
3
votes
3answers
1k views

Genetic search algorithm for TSP

I made a genetic search algorithm in Python for the Travelling Salesman Problem for a midterm project. The grade was fine, but I was hoping to get some pointers on style and documentation. Please ...
6
votes
2answers
552 views

Bitonic Tour algorithm

This is my implementation of Bitonic Tour (simplification of the Traveling Salesman Problem). Tests are not done very well, but it is not the point. I would be particularly interested in the comments ...
3
votes
1answer
1k views

Travelling Salesman Problem with visualisation in Java

For practicing purposes, I challenged myself to write a program that solves the TSP and visualises the results step by step. As for now, my program uses a simple nearest neighbour algorithm. I want ...
3
votes
1answer
4k views

Genetic Algorithm for TSP

This is something that I am proud of and would like to have people dissect and tell me where my faults are in. I feel that if I open my best for criticism then maybe it will reveal the deep seeded bad ...
1
vote
0answers
4k views

Travelling Salesmen Problem - Dynamic Programming

I wanted to review my TSP program for correctness in my approach, although I have not implemented one function subset which would be simple. ...
11
votes
2answers
23k views

Travelling salesman using brute-force and heuristics

I have implemented both a brute-force and a heuristic algorithm to solve the travelling salesman problem. ...
2
votes
1answer
8k views

2-opt algorithm for traveling salesman [closed]

I wrote a 2-opt algorithm to be used in a program and noticed (using profile) that the 2-opt is eating up a lot of time. I have tried a few things to make it run faster, but I am out of ideas. Any ...
10
votes
4answers
12k views

Simple attempt to solve the travelling salesman prob

For practicing purposes, I created an application that attempts to find an optimal route between given points. The algorithm is: Connect two randomly selected points Select a point that's still ...
8
votes
3answers
6k views

Travelling Salesman in Qt

I am writing a recursive function based on the Travelling Salesman Problem. Is this a correct way of doing things, or am I creating memory leaks? Prerequisites are: a two dimensional matrix ...
12
votes
1answer
2k views

Travelling salesman with four cities

I am writing a program that is based on the Travelling Salesman Problem. There are four cities in which the user determines its x and y coordinates. The salesman always starts at city1 and ends up at ...
6
votes
2answers
236 views

Visualization of the Traveling Salesmen Problem

I am working on a little project to visualize the algorithm for the Traveling Salesman Problem. I have cities, which are movable objects painted with AWT and Swing. Also I can make a connection ...
3
votes
1answer
5k views

Calculating Travelling Salesman - memory consumption and speed

I need to implement the dynamic programming algorithm for the travelling salesman problem. My input is a text file with first line indicates the number of cities. Each city is a point in the plane, ...
6
votes
1answer
948 views

Solving the travelling salesman problem using a genetic algorithm

I've got a simple program written in Golang that takes a map as input and tries to solve the travelling salesman problem by using a genetic algorithm. My Crossover method is a real performance killer ...