de.cm.osm2po.tsp
Class TspSolverBase

java.lang.Object
  extended by de.cm.osm2po.tsp.TspSolverBase
All Implemented Interfaces:
TspSolver
Direct Known Subclasses:
TspDefaultSolver

public abstract class TspSolverBase
extends java.lang.Object
implements TspSolver

Abstrakte Basisklasse zum Loesen eines osm2po-TSP, genauer genommen, einer bestehenden Kostenmatrix.

Author:
(c) 2013 - Carsten Moeller - info@osm2po

Field Summary
protected  Log log
           
protected  TspMatrix tspMatrix
           
 
Constructor Summary
TspSolverBase()
           
 
Method Summary
protected  float calcNeighborhoodCost(int[] tour, int x)
          Berechnet die Nachbarschafts-Kosten.
protected  float calcTourCost(int[] tour, float costLimit)
          Berechnet die Kosten einer Tour (Besuchsreihenfolge), bricht allerdings bereits mit Float.NaN ab, sobald ein Kosten-Limit ueberschritten wurde.
 int[] createInitialTour(boolean asRing)
          Erstellt eine Anfangskonfiguration fuer eine Tour auf der kompletten Matrix.
 TspSolver init(TspMatrix tspMatrix, Log log)
          Quasi-Konstruktor.
 int[][] makePaths(int[] tour)
          Generiert aus einer Besuchsreihenfolge die entsprechenden Pfade.
protected  void moveStation(int[] tour, int x, int y)
          Verschiebt den Vertex an Position x an Position y.
protected  boolean solveOptimalTour(int[] tour)
          Permutiert ueber alle Kombinationen und ermittelt die kuerzeste Tour.
protected  void swapStations(int[] tour, int x, int y)
          Tauscht die Positionen x und y innerhalb der Tour.
 
Methods inherited from class java.lang.Object
clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait
 
Methods inherited from interface de.cm.osm2po.tsp.TspSolver
solveTour
 

Field Detail

log

protected Log log

tspMatrix

protected TspMatrix tspMatrix
Constructor Detail

TspSolverBase

public TspSolverBase()
Method Detail

init

public TspSolver init(TspMatrix tspMatrix,
                      Log log)
Description copied from interface: TspSolver
Quasi-Konstruktor.

Specified by:
init in interface TspSolver
Parameters:
tspMatrix - TspMatrix
log - Log, NULLABLE
Returns:
this

makePaths

public final int[][] makePaths(int[] tour)
Description copied from interface: TspSolver
Generiert aus einer Besuchsreihenfolge die entsprechenden Pfade.

Specified by:
makePaths in interface TspSolver
Parameters:
tour - int[] Besuchsreihenfolge.
Returns:
int[][] Pfade.

createInitialTour

public final int[] createInitialTour(boolean asRing)
Description copied from interface: TspSolver
Erstellt eine Anfangskonfiguration fuer eine Tour auf der kompletten Matrix.

Specified by:
createInitialTour in interface TspSolver
Parameters:
asRing - boolean true: Start = Ziel (TSP)
Returns:
int[] Besuchsreihenfolge {0,1,2,3,...,[0]}

swapStations

protected final void swapStations(int[] tour,
                                  int x,
                                  int y)
Tauscht die Positionen x und y innerhalb der Tour.

Parameters:
tour - int[] Besuchsreihenfolge von Vertices der Matrix
x - int Erste Tauschposition
y - int Zweite Tauschposition

moveStation

protected final void moveStation(int[] tour,
                                 int x,
                                 int y)
Verschiebt den Vertex an Position x an Position y. Ist x kleiner y, so rutscht y eine Position runter. Ist x groesser y, so schiebt sich y eine Position vor. Dies ist kein Ringtausch!

Parameters:
tour - int[] Besuchsreihenfolge von Vertices der Matrix
x - int Zu verschiebene Position
y - int Zielposition

calcTourCost

protected final float calcTourCost(int[] tour,
                                   float costLimit)
Berechnet die Kosten einer Tour (Besuchsreihenfolge), bricht allerdings bereits mit Float.NaN ab, sobald ein Kosten-Limit ueberschritten wurde.

Parameters:
tour - int[] Besuchsreihenfolge.
costLimit - float Maximale Kosten, Abbruchkriterium.
Returns:
float Kosten oder Float.NaN

calcNeighborhoodCost

protected final float calcNeighborhoodCost(int[] tour,
                                           int x)
Berechnet die Nachbarschafts-Kosten.

Parameters:
tour - int[] Besuchsreihenfolge.
x - int Station
Returns:
Kosten oder Float.NaN

solveOptimalTour

protected final boolean solveOptimalTour(int[] tour)
Permutiert ueber alle Kombinationen und ermittelt die kuerzeste Tour.
Wichtig:
Aufgrund der Laufzeit (n-1)! wird bei mehr als 14 Stationen (Start->[Permut12]->Ziel) abgeriegelt und stattdessen eine Exception geworfen.

Parameters:
tour - int[] Initial- und Rueckgabe-Array von Positionen. Moegliche Werte: [0,1,2,3, ... ,8,0], wenn Ring aber auch [0,1,2, ... ,9] wenn kein Ring.
Returns:
boolean true: Loesung gefunden.

osm2po-core-4.8.8 (c) 2012 Carsten Moeller - info@osm2po.de