Travelling Salesdrone Bot Strategy

Here are some suggestions of strategies to improve your bot's performance.

Only submit a solution if you know it can win

Only submit a solution if you know it is better than the current best solution. The goal here is to save processing time. If you submit every solution you calculate, you lose time waiting for your code to be called again. If you only submit solutions that are better than the current best, you will be able to iterate through more possible solutions in the time available.

Do not submit a route which is the same as your opponents best route

Do not submit the same route as your opponents best solution, again you will waste time and the route will only be rejected by the server. Please note the starting at different point and going in the same order will count as the same solution eg [0,1,2,3,4,5,6,7,8,9] is the same as [5,6,7,8,9,0,1,2,3,4] or doing the same route in reverse [9,8,7,6,5,4,3,2,1,0] etc

Nearest Neighbour

Pick a city and then travel to the next closest city that you haven't already visited. So for example if you have the following 10 city map:

tsp_example_map.png

Starting at city 'A' you can plot a reasonably good route around the cities by just going to the next closest city as shown below:

tsp_example_map2.png

Make sure you keep track of the distance as you go around the cities to follow the rule of only submitting a route if you know it can win.

Swap your starting point

Using nearest neighbour try a different starting city as this will quite often lead to a different result which may or may not be better. So starting at city 'J' would yield the result below:

tsp_example_map3.png

Reduce cross overs

Reducing the number of times you cross over your previous path can lead to a better solution. So if you use the nearest neighbour starting at city 'A' you can see that move 'C' to 'D' crosses move 'I' to 'A'.

tsp_example_map2.png

If you swap these over ie 'C' to 'I' and 'D' to 'A' you will have a better solution as shown below:

tsp_example_map4.png
iconSalesDroneBlack.png
Unless otherwise stated, the content of this page is licensed under Creative Commons Attribution-ShareAlike 3.0 License