DKRouteFinder

A practical Cocoa solution for the Travelling Salesman Problem (TSP)

Download Source code [10K zip file]

The Travelling Salesman Problem is a well-known "classic" in computer science that is NP hard. This means that it's practically insoluble for many real-world applications at least if you need the mathematically perfect solution. Luckily, we rarely do, and so there have been many useful heuristics developed that provide useful solutions that work for many practical applications. This class provides one such solution that can be used with Cocoa. The solution here is based on the classic code published in "Numerical Recipes in C", 2nd Edition (Cambridge University Press, 1992) which uses a simulated annealing technique. For further information, you can read the original text online here: http://www.nrbook.com/a/bookcpdf.php

For Cocoa use, the DKRouteFinder class wraps the functionality up in an easy to use fashion, leveraging Cocoa's containers and KVC. Internally, the algorithm sorts a list of points (x,y coordinates) so objects that can be sorted by this class need to expose some property that returns an NSPoint value. DKRouteFinder uses KVC to obtain a list of points from the property given, sorts it using the simulated annealing algorithm, then returns an array of the original objects sorted into this order. Other class and instance methods allow you to break this process down further if you need it. It also provides a way to get progress feedback if you want it, though tests show that execution time is barely noticeable up to about 1000 objects (tested on a MacBook). Much larger numbers of objects may need a progress bar.

While this class is bundled with DrawKit (Beta 5 onwards) it is not in any way tied to that framework or has any dependencies on it. Because it is general purpose, I've decided to create a separate page for it here.

Usage

The simplest use is to use the class method:

+ (NSArray*) [DKRouteFinder sortedArrayOfObjects:(NSArray*) objects byShortestRouteForKey:(NSString*) key];

This is the highest-level method, taking an array of arbitrary <objects> having a property given by <key> that returns an NSPoint. The method returns the same objects sorted into optimum order.

Other class methods can be used for lower-level approaches:

+ (DKRouteFinder*) routeFinderWithArrayOfPoints:(NSArray*) arrayOfPoints;
+ (DKRouteFinder*) routeFinderWithObjects:(NSArray*) objects withValueForKey:(NSString*) key;

Note that there is no public init method, you create a DKRouteFinder using one of these methods. You can retain the route finder to extract multiple results from it, but the route finder is immutable with respect to its original data set - to run the algorithm on a new data set requires a new route finder instance. Each instance of the route finder only ever runs the algorithm once, but the returned sort order can be used with multiple data sets as long as the data sets have the same size (number of items) as the original data set.

Instance methods allow you to pull data from a route finder object:

- (NSArray*) shortestRoute;
- (NSArray*) shortestRouteOrder;
- (NSArray*) sortedArrayFromArray:(NSArray*) anArray;

-shortestRoute returns an array of NSValues (NSPoint values) which are the original x, y coordinates sorted into optimal order. In general this may not be all that useful but can be used to construct e.g. a path that shows the computed order.

-shortestRouteOrder returns an array of NSNumbers (integers) representing the optimal sorting order .

-sortedArrayFromArray: is likely to be the most useful method. It takes an array of objects and rearranges them into the sorted order. In addition, it keeps the first object in the input array the same so you can specify the starting point for any "tour" by placing this object at index 0. Typically the input to this method will be the same set of objects used to create the route finder, but it need not be as long as the number of items is the same. If the item counts are not the same, this method returns nil.

Finally, to get progress feedback you can use:

- (void) setProgressDelegate:(id) aDelegate;

The delegate can be any object that implements the following informal protocol:

- (void) routeFinder:(DKRouteFinder*) rf progressHasReached:(float) value;

<value> will progress from 0 to 1 over the execution time of the route finder. The route finder guarantees to send 0 and 1 at the start and end of the operation respectively.

Note: The route finder requires a minimum of four objects to operate. If there are fewer than this, it will not be initialised and the construction methods will return nil. If the property given by the key doesn't reference an NSPoint value, an exception will be thrown during the initialisation of the route finder.

Typical Results

These images show typical outcomes for a variety of test cases.

Practical Applications

Route-finding of this kind finds many useful applications, especially in the realm of Computer-Aided Manufacturing (CAM). A typical use might be to compute a drillpath for a CNC machine where for quickest and most efficient machining you want to reduce the amount of motion of the drill from place to place as much as possible. In this kind of application, you would also partition the holes to be drilled into sets according to size, and routefind each one. Then the machine needs only to change drills once per piece. Many other similar applications can be envisaged. This class represents one less excuse for developers not to develop Mac applications for industrial use! Other uses might include AI for a game.