org.openpnp.util

Class TravellingSalesman<T>

java.lang.Object

org.openpnp.util.TravellingSalesman<T>

Type Parameters:

T - The class of the objects to be travelled to. Use a Locator to query the Location from these objects.

public class TravellingSalesman<T>
extends java.lang.Object

A simple solver for the Travelling Salesman Problem. The solver tries to find good solution for the following question: "Given a list of Locations, what is the shortest possible route that visits each Location?" Optionally you can provide a start and/or end Location, e.g. the current machine Location, as the start Location and/or a Location for the next task after that, as the end Location. These Locations can also be the same, to form a loop. If left open (null) the solver will choose the best start and/or end Location for the route freely. The solver uses Simulated Annealing. The implementation is a bit extended from the typical school book examples to not only use "swaps" of two Locations but also "twists", that reverse the travel direction between the swapped out Locations. The latter really improves the solutions a lot, because it allows the solver to quickly "untwist" routes at (or near) crossing points. These crossing points appear frequently for the rectangularly arrayed Location patterns assumed to be typically found on a PNP machine.

Nested Class Summary

Nested Classes

Modifier and Type	Class and Description
static interface	TravellingSalesman.Locator<T>

Constructor Summary

Constructors

Constructor and Description
TravellingSalesman(java.util.List<T> travelInput, TravellingSalesman.Locator<? super T> locator, Location startLocation, Location endLocation)

Method Summary

Modifier and Type	Method and Description
java.lang.String	asSvg()
Location	getEndLocation()
long	getSolverDuration()
Location	getStartLocation()
java.util.List<T>	getTravel()
double	simulateAnnealing(double startingTemperature, double coolingRate, int maxIterations)
double	solve()

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Constructor Detail

TravellingSalesman

public TravellingSalesman(java.util.List<T> travelInput,
                          TravellingSalesman.Locator<? super T> locator,
                          Location startLocation,
                          Location endLocation)

Parameters:

travelInput - Contains the travelling problem to be solved.

locator - Lets the solver query the given list object for the relevant Location.

startLocation - Optional start Location, e.g. the current machine Location. If left open, the solver will choose the start of the route freely.

endLocation - Optional end Location, e.g. the Location for the next task after this. If left open, the solver will choose the end of the route freely.

Method Detail

simulateAnnealing

public double simulateAnnealing(double startingTemperature,
                                double coolingRate,
                                int maxIterations)

solve

public double solve()

getTravel

public java.util.List<T> getTravel()

getStartLocation

public Location getStartLocation()

getEndLocation

public Location getEndLocation()

getSolverDuration

public long getSolverDuration()

asSvg

public java.lang.String asSvg()