All Questions
Tagged with heuristics traveling-salesman
26 questions
0
votes
0
answers
206
views
2 opt algorithm providing inconsistent results and no improvements
To summarise the issue I will cover the implementation explanation and results.
The problem I am aiming to solve with the algorithm is to correct some results gathered through a Randomised nearest ...
- 11
0
votes
0
answers
546
views
Recommend a good heuristic for longest Hamiltonian path in polynomial time
I have a complete weighted graph with 1000 nodes and need to find the longest possible Hamiltonian path in the graph (the sequence of nodes, to be more precise). I am supposed to fit in 5 sec (for ...
- 65
-2
votes
1
answer
616
views
Useful algorithms for TSP
I'm currently working on TSP which has been given to me as my end of year project in my computer science course.
In this problem we are given a list of the top 1000 colleges in the world. Then ...
user7010212
0
votes
1
answer
513
views
Simulated annealing Initial solution
Can we initialise the first best solution in Simulated Annealing with some other optimization algorithm like nearest neighbour algorithm(I am solving TSPTW)?if it is better then what are some other ...
- 233
0
votes
1
answer
408
views
TSP with a twist
I've encountered a problem that is very similar to the Traveling Salesman Problem, except with a few twists:
You are able to visit the same node multiple times
Traveling an edge that you have already ...
0
votes
2
answers
868
views
Heuristics for the Asymmetric Traveling Salesman
I am using A* in order to solve the Asymmetric Traveling Salesman problem.
My state representation has 4 variables:
1 - Visited cities (List)
2 - Unvisitied cities (List)
3 - Current City (Integer)
...
2
votes
0
answers
1k
views
calculating a good initial temperature for simulated annealing
I've done some testing of different initial temperatures in my simulating annealing algorithm and noticed the starting temperature has an affect on the performance of the algorithm.
Is there any way ...
- 21
7
votes
4
answers
2k
views
Travelling Salesman with multiple salesmen with a limit on number of cities per salesman?
Problem: I need to drop (n) employees from office to their homes(co-ordinates available). I have (x) 7-seater & (y) 4-seater cabs available.
I have to design an algorithm to drop all the employees ...
- 2,108
0
votes
1
answer
748
views
Strategy to tackle knapsack binded with travelling salesman
I have been assigned the following problem as a research topic for summer. However, I have not been able to successfully find related problem, except that it seems to be a combination of travelling ...
2
votes
1
answer
775
views
Proving approximation for TSP-metric
I got stuck with the following question:
Consider the following heuristic: Start with a tour containing only one vertex. At each step, find the vertex outside the tour with the lesser distance to ...
- 448
3
votes
1
answer
481
views
How should I unit test a heuristic algorithm?
So I've written an implementation of the ant colony optimization (ACO) meta-heuristic, and I'd like to write some unit tests. However, I'm not sure of the best way to test a method whose ability to ...
- 179
7
votes
2
answers
9k
views
3-Opt Local Search for TSP?
I understand that the 3-Opt Heuristic involves removing three edges from a graph and adding three more to re-complete the tour. However, I've seen many papers that mention that when three edges are ...
- 3,412
2
votes
3
answers
3k
views
What is a solution for a TSP with multiple salesmen and no return but known vertices and end points?
I don't know if I worded that correctly and I am not sure if it is even a TSP problem but here is the scenario.
I am designing and trying to optimize a route planner for a delivery service. I have ...
4
votes
1
answer
5k
views
How does Google Maps´ "optimizeWaypoints" solve Travelling Salesmen?
I want to solve a Travelling Salesman Problem like Google Maps does in its DirectionsRequest with request.setOptimizeWaypoints(true);. It orders some Waypoints in a route so that the travelling-costs ...
- 1,070
2
votes
2
answers
3k
views
Heuristics for the travelling salesman
I am working on evolutionary optimization and on this project I need
heuristics for the travelling salesman problem. In this context,
genetic algorithms, we apply small mutations and hope that ...
- 5,805