The Travelling Salesman Problem

Discuss the new AI features ("NoAI") introduced into OpenTTD 0.7, allowing you to implement custom AIs, and the new Game Scripts available in OpenTTD 1.2 and higher.

Moderator: OpenTTD Developers

Post Reply
User avatar
Zutty
Director
Director
Posts: 565
Joined: 22 Jan 2008 16:33

The Travelling Salesman Problem

Post by Zutty »

Hi all,

One of the things I love about this community is the great minds and great ideas of the people that make it. Thats why, when faced with a problem like this I can think of no better solution than to ask you guys! :D

As part of my AI I would like to be able to build a single road that connects all stations together in a loop. This ofcourse represents the travelling salesman problem. I have done some reading and implemented a simple solver based on stochastic optimisation, but I think my efforts could be vastly improved.

The solver works well for a small number of points. The shortest tour for 20 points can be adequately "solved" with 2,000 iterations taking 2 game days, but for a larger number of points the deficiencies in the approach become more apparent. To run for 200,000 iterations over 200 points takes about 4.5 game years, and you can clearly see it still isn't optimal!
ShortestTour.nut
Basic solver code
(3.27 KiB) Downloaded 231 times
A tour of 200 points after 200,000 iterations
A tour of 200 points after 200,000 iterations
200pointtour.png (29.15 KiB) Viewed 4315 times
The code can be used like this...

Code: Select all

local numPoints = 20;
local points = [];
for(local i = 0; i < numPoints; i++) {
	local p = AIMap.GetTileIndex(AIBase.RandRange(255), AIBase.RandRange(255));
	points.append(p);
}

local tour = ShortestTour(points);
tour.Run();

local prev = tour.GetPoints()[numPoints - 1]; 	
for(local i = 0; i < numPoints; i++) {
	local p = tour.GetPoints()[i];
	// Do something between prev & p
	prev = p;
}
The method I implemented works by simply shuffling the list of points randomly and then preserving the shuffled order if it reduces the tour length. I suppose the term "stochastic optimisation" is a bit generous, but it does work!

However there must be a better way. Perhaps a similar algorithm with a better heuristic? Simulated annealing or a genetic algorithm maybe? I'm sure one of you bright people has already thought about this, or already come up with a better solution. Thoughts?

Thanks very much :)
PathZilla - A networking AI - Now with tram support.
User avatar
Zuu
OpenTTD Developer
OpenTTD Developer
Posts: 4553
Joined: 09 Jun 2003 18:21
Location: /home/sweden

Re: The Travelling Salesman Problem

Post by Zuu »

Nice to see you are attempting to make a solver for the Travel salesman problem (TSP).

The TSP has some interesting heuristics in my first optimization book. So if you are "just" solving the TSP, and not the VRP (Vehicle routing problem) where you have several vehicles that can be used to visit all the nodes, then I'm quite sure there is a heuristic that guarantee a solution and is hopefully not to slow.

The wikipedia page on the TSP has some information on heuristics that should be worth to read if you haven't read it yet:
http://en.wikipedia.org/wiki/Travelling ... algorithms


In PAXLink I have a VRP problem for my buses in larger cities. At some point I though I could solve it using some heuristics, but it is probably too complicated. I would probably have to use the TSP and if the number of bus stops becomes to big, then split the town into two or more zones and solve the TSP for how to connect each of the zones to the airport.
My OpenTTD contributions (AIs, Game Scripts, patches, OpenTTD Auto Updater, and some sprites)
Junctioneer (a traffic intersection simulator)
Terkhen
OpenTTD Developer
OpenTTD Developer
Posts: 1034
Joined: 11 Sep 2008 07:32
Location: Spain

Re: The Travelling Salesman Problem

Post by Terkhen »

I love these problems! Ant colony optimization algorithms are designed for graph problems like the TSP. They don't consume a lot of resources, are relatively simple to implement (compared to other biologically inspired algorithms) and they find good solutions in small times. One of the best benefits of using these kind of algorithms on IAs is that they can easily adapt to changes in the environment in real time (for example, if somebody built a railroad between two cities, the cost of that connection would increase: the ants would start to reject using that connection). And I like the idea of a bunch of giant ants running around the map doing calculations :D

A possible improvement would be altering the basic algorithm to be able to get partial solutions. The normal algorithm only stores the best solution so far, but let's say that you store the best N solutions. After running the algorithm for a given number of iterations / milliseconds, the IA needs to start building something or the player will think that it is dead. To decide what you should build, you check the set of best solutions for similarities between them. If a given connection between cities is present in most of the set, you can conclude that it is a good connection and start building it. When you want to continue calculating the rest of connections, just force the subsequent ants to follow the connections that are already built.

Also, I think you should consider building roads with as less curves as possible. Their manhattan distance would be equal to the diagonal ones, but since road vehicles can't overtake on curves they will move faster when there is a lot of vehicles.
User avatar
Dustin
Transport Coordinator
Transport Coordinator
Posts: 272
Joined: 07 Dec 2005 19:22

Re: The Travelling Salesman Problem

Post by Dustin »

You can use well known genetic algorithms, the ant colony version (which I adapted in part [minus pheremones, I couldn't get them right] for my pathfinder). But the travelling salesman problem is a one that grows exponentailly more expensive as you add nodes. So for larger maps, you are going to be in trouble with just about any algorithm I think.

I suggest divide and conquer. Something like this:
  • Divide the map into quadrants of some manageable size. Solve all the quadrants.
  • Pick the biggest city in in quad
  • Solve one more time for the major cities
That will get you efficient local networks and good connections to the big cities. You also don't need to solve big TSP grids.
Chruker
Engineer
Engineer
Posts: 49
Joined: 01 Jun 2009 20:13

Re: The Travelling Salesman Problem

Post by Chruker »

Nice timing on this topic. I was just about to start writing something that would optimize the orders my intra-city busline gets.

Zutty, one thing I dont like about you approach is the fixed number of iterations. How about keeping track of the number of iterations since you last found a better route. Then when you over ex. 100 iterations havent found a better route, you just exit.

Anyway, here is my attempt at something different:

Code: Select all

local towns = AITownList();
towns.Valuate(AITown.GetLocation);
local points = List.GetArrayValues(towns);
Debug.Info("Towns: " + towns.Count());
// 
// local points = [];
// for(local i = 0; i < 20; i++) {
// 	local p = AIMap.GetTileIndex(AIBase.RandRange(255), AIBase.RandRange(255));
// 	AISign.BuildSign(p, "I'm a sign bigger than all the");
// 	points.append(p);
// }

Debug.Info("Starting");
local start = GetTick();
local available = AIList();
for (local i = 1; i < points.len(); i++) {
	available.AddItem(points[i], 0);
}
available.Sort(AIAbstractList.SORT_BY_VALUE, AIAbstractList.SORT_ASCENDING);

local sorted = [];
local point = points[0];
Debug.Sign(point, "Starting here");
sorted.push(point);
while (!available.IsEmpty()) {
	available.Valuate(AIMap.DistanceSquare, point);
	point = available.Begin();
	local distance = available.GetValue(point);
	available.RemoveItem(point);
	sorted.push(point);
}

Debug.Info("So far it took: " + (GetTick() - start));

sorted.push(sorted[0]);
sorted.push(sorted[1]);
sorted.push(sorted[2]);

for(local i = 0; i < (sorted.len() - 3); i++) {
	local a = sorted[i];
	local b = sorted[i + 1];
	local c = sorted[i + 2];
	local d = sorted[i + 3];
	
	local a2b = AIMap.DistanceSquare(a, b);
// 	local b2c = AIMap.DistanceSquare(b, c);
	local c2d = AIMap.DistanceSquare(c, d);

	local a2c = AIMap.DistanceSquare(a, c);
// 	local c2b = b2c;
	local b2d = AIMap.DistanceSquare(b, d);

	if (
		(a2b + c2d)
		>
		(a2c + b2d)
	) {
		local swappee = sorted[i + 1];
		sorted[i + 1] = sorted[i + 2];
		sorted[i + 2] = swappee;
	}
}

Debug.Info("It took: " + (GetTick() - start));

local prev = -1;
for(local i = 0; i < sorted.len() - 2; i++) {
	local p = sorted[i];
	if (i > 0) DrawLine(prev, p);
	prev = p;
}
When I run it with 20 points, it does it in less than 1 tick. With 200 points it took around 10 ticks. Given how that went I changed to a 2048x2048 map, after a bit of waiting for the AI to be done, I decided to see how many towns the map had. It had 2944 towns... oops.

Anyway I let it run and after 1665 ticks it had the basic route. The look for pairs that could be swapped took an additional 12 ticks.

I had added your Drawline function so that I could see the output of the tests, and it happily started drawing the route, but lets just says the route easily used the 64000 available sign slots :-)
Chruker
Engineer
Engineer
Posts: 49
Joined: 01 Jun 2009 20:13

Re: The Travelling Salesman Problem

Post by Chruker »

Anyway, arent the graph functions suppose to be the thing for solving this stuff?

I did a failed attempt at using the AyStar lib function, but it stranded - probably because I didnt bother to make a class, and just used some very crude inline functions :-)

One of the issues I found myself wondering about was how to trick it into the visiting all points.
phejukiras
Engineer
Engineer
Posts: 1
Joined: 06 Feb 2018 22:00

Re: The Travelling Salesman Problem

Post by phejukiras »

Travel Salesman Problem (TSP) is a very well know computer science problem. The roblem has the peculiarity that is very easy to understand, but it's really hard for computer to solve it. TSP is about finding shortest route that visits every city exactly once and retuns to the starting city.

Do you know if the metric-TSP could be used as a solution?
Post Reply

Return to “OpenTTD AIs and Game Scripts”

Who is online

Users browsing this forum: No registered users and 6 guests