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. Liefert vor allem wichtige Basisfunktionalitaeten fuer init(TspMatrix, Properties, Log), so dass im Prinzip nur TspSolver.solveTour(int[]) ueberschrieben werden muss. Zudem bietet sie einige simple Loesungsansaetze und erlaubt ein parametrisiertes Hintereinanderketten selbiger.

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

Field Summary
protected static char CMD_BRUTEFORCE
           
protected static char CMD_GREEDY
           
protected static char CMD_MOVE
           
protected static char CMD_TWOOPT
           
protected  Log log
           
protected  java.util.Properties params
           
protected  TspMatrix tspMatrix
           
 
Constructor Summary
TspSolverBase()
           
 
Method Summary
protected  float calcPartialCosts(int[] tour, int x)
          Berechnet die Summe der Nachbarschafts-Kosten tour[x-1]->tour[x]->tour[x+1].
protected  float calcPartialCosts(int a, int b, int c)
          Berechnet die Summe der Nachbarschafts-Kosten station[a]->station[b]->station[c].
protected  float calcPartialExtraCosts(int a, int b, int c)
          Berechnet die absolute Verschlechterung (Umwegkosten) beim Einfuegen einer Station B zwischen A und C.
protected  float calcPartialTension(int a, int b, int c)
          Berechnet die prozentuale Verschlechterung (Dehnung) beim Einfuegen einer Station B zwischen A und C.
protected  float calcTourCosts(int[] tour, float costLimit)
          Berechnet die Kosten einer Tour (Besuchsreihenfolge), bricht allerdings bereits mit Float.NaN ab, sobald ein Kosten-Limit ueberschritten wurde.
 float calcTourCosts(int[] tour, int x, int y, float costLimit)
          Berechnet die Kosten einer SubTour (Besuchsreihenfolge), bricht allerdings bereits mit Float.NaN ab, sobald ein Kosten-Limit erreicht wird und somit keine Verbesserung eintritt.
protected  boolean improve(int[] tour, char cmd)
          Wendet eine von mehreren Strategien zum Verbessern einer Tour an.
protected  boolean improveBruteForce(int[] tour)
          Permutiert ueber alle Kombinationen und ermittelt die kuerzeste Tour.
protected  boolean improveGreedy(int[] tour)
          Erzeugt eine einfache Greedy-Tour.
protected  boolean improveMove(int[] tour)
          Laesst jede Station einmal im Kreis wandern und schaut, ob etwas Besseres dabei herauskommt.
protected  boolean improveTwoOpt(int[] tour)
          Fuehrt solange alle moeglichen 2-Opt-Schritte aus bis keine Verbesserung mehr moeglich ist.
 void init(TspMatrix tspMatrix, java.util.Properties params, Log log)
          Quasi-Konstruktor.
 
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

CMD_BRUTEFORCE

protected static final char CMD_BRUTEFORCE
See Also:
Constant Field Values

CMD_TWOOPT

protected static final char CMD_TWOOPT
See Also:
Constant Field Values

CMD_GREEDY

protected static final char CMD_GREEDY
See Also:
Constant Field Values

CMD_MOVE

protected static final char CMD_MOVE
See Also:
Constant Field Values

log

protected Log log

params

protected java.util.Properties params

tspMatrix

protected TspMatrix tspMatrix
Constructor Detail

TspSolverBase

public TspSolverBase()
Method Detail

init

public final void init(TspMatrix tspMatrix,
                       java.util.Properties params,
                       Log log)
Description copied from interface: TspSolver
Quasi-Konstruktor.

Specified by:
init in interface TspSolver
Parameters:
tspMatrix - TspMatrix
params - Properties NULLABLE
log - Log, NULLABLE

improve

protected boolean improve(int[] tour,
                          char cmd)
Wendet eine von mehreren Strategien zum Verbessern einer Tour an. Diese Methode wird intern in einer Schleife aufgerufen und erlaubt so das Hintereinanderketten mehrerer Massnahmen.

Parameters:
tour - int[] zu modifierende Tour.
cmd - char z.B. CMD_BRUTEFORCE, erweiterbar!
Returns:
boolean true: Uebergebene Tour verbessert/modifiert.

calcTourCosts

protected final float calcTourCosts(int[] tour,
                                    float costLimit)
Berechnet die Kosten einer Tour (Besuchsreihenfolge), bricht allerdings bereits mit Float.NaN ab, sobald ein Kosten-Limit ueberschritten wurde. Delegiert an TspMatrix.calcTourCosts(int[], int, int, float) mit 0 und n-1.

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

calcTourCosts

public final float calcTourCosts(int[] tour,
                                 int x,
                                 int y,
                                 float costLimit)
Berechnet die Kosten einer SubTour (Besuchsreihenfolge), bricht allerdings bereits mit Float.NaN ab, sobald ein Kosten-Limit erreicht wird und somit keine Verbesserung eintritt. Delegiert an TspMatrix.calcTourCosts(int[], int, int, float)

Parameters:
tour - int[] Besuchsreihenfolge.
x - StartIndex innerhalb der Tour
y - EndIndex der Tour
costLimit - float Maximale Kosten, Abbruchkriterium.
Returns:
float Kosten oder Float.NaN

calcPartialCosts

protected final float calcPartialCosts(int[] tour,
                                       int x)
Berechnet die Summe der Nachbarschafts-Kosten tour[x-1]->tour[x]->tour[x+1].

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

calcPartialCosts

protected final float calcPartialCosts(int a,
                                       int b,
                                       int c)
Berechnet die Summe der Nachbarschafts-Kosten station[a]->station[b]->station[c].

Parameters:
a - Index der Station A in der Matrix
b - Index der Station B
c - Index der Station C
Returns:
Kostensumme a->b->c oder Float.NaN

calcPartialTension

protected final float calcPartialTension(int a,
                                         int b,
                                         int c)
Berechnet die prozentuale Verschlechterung (Dehnung) beim Einfuegen einer Station B zwischen A und C.

Parameters:
a - Index der Station A in der Matrix
b - Index der Station B
c - Index der Station C
Returns:
float, Bsp.: 0.2 => a->b->c = a->c + 20%, oder Float.NaN.

calcPartialExtraCosts

protected final float calcPartialExtraCosts(int a,
                                            int b,
                                            int c)
Berechnet die absolute Verschlechterung (Umwegkosten) beim Einfuegen einer Station B zwischen A und C.

Parameters:
a - Index der Station A (0 ist erste Station)
b - Index der Station B
c - Index der Station C
Returns:
float Umweg-Mehrkosten oder Float.NaN.

improveGreedy

protected final boolean improveGreedy(int[] tour)
Erzeugt eine einfache Greedy-Tour.

Parameters:
tour - int[] zu modifierende Tour. Moegliche Werte: [0,1,2,3, ... ,8,0], wenn Ring aber auch [0,1,2, ... ,9] wenn kein Ring.
Returns:
boolean true: Uebergebene Tour verbessert/modifiert.

Wichtig:
Sollte ausgerechnet die letzte Kante nicht durchfahrbar sein, so wird dieser Algo scheitern und false zurueckliefern!

improveMove

protected final boolean improveMove(int[] tour)
Laesst jede Station einmal im Kreis wandern und schaut, ob etwas Besseres dabei herauskommt.

Parameters:
tour - int[] zu modifierende Tour. Moegliche Werte: [0,1,2,3, ... ,8,0], wenn Ring aber auch [0,1,2, ... ,9] wenn kein Ring.
Returns:
boolean true: Uebergebene Tour verbessert/modifiert.

improveBruteForce

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

Parameters:
tour - int[] zu modifierende Tour. Moegliche Werte: [0,1,2,3, ... ,8,0], wenn Ring aber auch [0,1,2, ... ,9] wenn kein Ring.
Returns:
boolean true: Uebergebene Tour verbessert/modifiert.

improveTwoOpt

protected final boolean improveTwoOpt(int[] tour)
Fuehrt solange alle moeglichen 2-Opt-Schritte aus bis keine Verbesserung mehr moeglich ist.

Parameters:
tour - int[] zu modifierende Tour Moegliche Werte: [0,1,2,3, ... ,8,0], wenn Ring aber auch [0,1,2, ... ,9] wenn kein Ring.
Returns:
boolean true: Uebergebene Tour verbessert/modifiert.

osm2po-core-5.0.0 (c) December 24 2014 Carsten Moeller - info@osm2po.de