Overview  Package   Class  Tree  Deprecated  Index  Help 
 PREV CLASS   NEXT CLASS FRAMES    NO FRAMES
SUMMARY:  INNER | FIELD | CONSTR | METHOD DETAIL:  FIELD | CONSTR | METHOD

drasys.or.graph.tsp
Class Us

java.lang.Object
  |
  +--drasys.or.graph.tsp.TSPBase
        |
        +--drasys.or.graph.tsp.Geni
              |
              +--drasys.or.graph.tsp.Us
public class Us
extends Geni
implements ImproveI

An implementation of the 'US' improvement portion of the composite TSP heuristic 'GENIUS'. The 'GENIUS' algorithm is described in a paper by Michel Gendreau, Alain Hertz, Gilbert Laporte which was published in 'Operations Research' Vol.40, No.6, November-December 1992.

See Also:
Genius

Constructor Summary
Us(int sizeOfNeighborhood)
          Sets the neighborhood to the argument.
Us(int sizeOfNeighborhood, GraphI graph)
          Sets the neighborhood and the target graph.
 
Method Summary
protected  void forwardFindBestRemove(drasys.or.graph.tsp.Geni.Vert vv)
           
protected  void forwardRemoveType1(drasys.or.graph.tsp.Geni.Vert vv, drasys.or.graph.tsp.Geni.Vert vj, drasys.or.graph.tsp.Geni.Vert vk, drasys.or.graph.tsp.Geni.Vert vj1, drasys.or.graph.tsp.Geni.Vert vk1)
           
protected  void forwardRemoveType2(drasys.or.graph.tsp.Geni.Vert vv, drasys.or.graph.tsp.Geni.Vert vj, drasys.or.graph.tsp.Geni.Vert vk, drasys.or.graph.tsp.Geni.Vert vl, drasys.or.graph.tsp.Geni.Vert vj1, drasys.or.graph.tsp.Geni.Vert vk1, drasys.or.graph.tsp.Geni.Vert vl1)
           
protected  void forwardReplaceType1(drasys.or.graph.tsp.Geni.Vert vv, drasys.or.graph.tsp.Geni.Vert vj, drasys.or.graph.tsp.Geni.Vert vk, drasys.or.graph.tsp.Geni.Vert vj1, drasys.or.graph.tsp.Geni.Vert vk1)
           
protected  void forwardReplaceType2(drasys.or.graph.tsp.Geni.Vert vv, drasys.or.graph.tsp.Geni.Vert vj, drasys.or.graph.tsp.Geni.Vert vk, drasys.or.graph.tsp.Geni.Vert vl, drasys.or.graph.tsp.Geni.Vert vj1, drasys.or.graph.tsp.Geni.Vert vk1, drasys.or.graph.tsp.Geni.Vert vl1)
           
protected  void forwardSaveForRemoveType1(drasys.or.graph.tsp.Geni.Vert vv, drasys.or.graph.tsp.Geni.Vert vj, drasys.or.graph.tsp.Geni.Vert vk)
           
protected  void forwardSaveForRemoveType2(drasys.or.graph.tsp.Geni.Vert vv, drasys.or.graph.tsp.Geni.Vert vj, drasys.or.graph.tsp.Geni.Vert vk, drasys.or.graph.tsp.Geni.Vert vl)
           
protected  void forwardSequenceRemove(drasys.or.graph.tsp.Geni.Vert head)
           
protected  void improve()
           
 double improveClosedTour(java.util.Vector tour)
          Improve a closed tour solution.
 double improveOpenTour(java.util.Vector tour)
          Improve an open tour solution with arbitrary end points.
 double improveOpenTour(java.util.Vector tour, boolean fixedOrigin, boolean fixedDestination)
          Improve an open tour solution with fixed end points.
protected  void initTourUS(int head, int tail)
           
protected  void removeType0(drasys.or.graph.tsp.Geni.Vert vv)
           
protected  void replaceType0(drasys.or.graph.tsp.Geni.Vert vv)
           
protected  void reverseFindBestRemove(drasys.or.graph.tsp.Geni.Vert vv)
           
protected  void reverseRemoveType1(drasys.or.graph.tsp.Geni.Vert vv, drasys.or.graph.tsp.Geni.Vert vj, drasys.or.graph.tsp.Geni.Vert vk, drasys.or.graph.tsp.Geni.Vert vj1, drasys.or.graph.tsp.Geni.Vert vk1)
           
protected  void reverseRemoveType2(drasys.or.graph.tsp.Geni.Vert vv, drasys.or.graph.tsp.Geni.Vert vj, drasys.or.graph.tsp.Geni.Vert vk, drasys.or.graph.tsp.Geni.Vert vl, drasys.or.graph.tsp.Geni.Vert vj1, drasys.or.graph.tsp.Geni.Vert vk1, drasys.or.graph.tsp.Geni.Vert vl1)
           
protected  void reverseReplaceType1(drasys.or.graph.tsp.Geni.Vert vv, drasys.or.graph.tsp.Geni.Vert vj, drasys.or.graph.tsp.Geni.Vert vk, drasys.or.graph.tsp.Geni.Vert vj1, drasys.or.graph.tsp.Geni.Vert vk1)
           
protected  void reverseReplaceType2(drasys.or.graph.tsp.Geni.Vert vv, drasys.or.graph.tsp.Geni.Vert vj, drasys.or.graph.tsp.Geni.Vert vk, drasys.or.graph.tsp.Geni.Vert vl, drasys.or.graph.tsp.Geni.Vert vj1, drasys.or.graph.tsp.Geni.Vert vk1, drasys.or.graph.tsp.Geni.Vert vl1)
           
protected  void reverseSaveForRemoveType1(drasys.or.graph.tsp.Geni.Vert vv, drasys.or.graph.tsp.Geni.Vert vj, drasys.or.graph.tsp.Geni.Vert vk)
           
protected  void reverseSaveForRemoveType2(drasys.or.graph.tsp.Geni.Vert vv, drasys.or.graph.tsp.Geni.Vert vj, drasys.or.graph.tsp.Geni.Vert vk, drasys.or.graph.tsp.Geni.Vert vl)
           
protected  void reverseSequenceRemove(drasys.or.graph.tsp.Geni.Vert tail)
           
protected  void saveForRemoveType0(drasys.or.graph.tsp.Geni.Vert vv)
           
 
Methods inherited from class drasys.or.graph.tsp.Geni
addNeighbor, addToTour, applyForwardType1, applyForwardType2, applyReverseType1, applyReverseType2, applyType0, calcCost, calcTour, checkList, construct, constructClosedTour, constructOpenTour, constructOpenTour, constructOpenTourFrom, constructOpenTourTo, costOfType0, forwardCostOfInsertType1, forwardCostOfInsertType2, forwardFindBestInsert, forwardFlip, forwardSequenceInsert, initTourGENI, newForwardEdge, newReverseEdge, reverseCostOfInsertType1, reverseCostOfInsertType2, reverseFindBestInsert, reverseFlip, reverseSequenceInsert, selectVertex, selectVertex, selectVertex, toString
 
Methods inherited from class drasys.or.graph.tsp.TSPBase
checkChangeCount, countVertices, forwardCost, getCost, getTour, initVertices, initVertices, reverseCost, rotateClosedTour, setEdgeKey, setGraph, setProperties
 
Methods inherited from class java.lang.Object
clone, equals, finalize, getClass, hashCode, notify, notifyAll, wait, wait, wait
 

Constructor Detail

Us

public Us(int sizeOfNeighborhood)
Sets the neighborhood to the argument. The graph must be set with 'setGraph()' before constructing a tour.

Us

public Us(int sizeOfNeighborhood,
          GraphI graph)
Sets the neighborhood and the target graph.
Method Detail

improveOpenTour

public double improveOpenTour(java.util.Vector tour)
                       throws TourNotFoundException
Improve an open tour solution with arbitrary end points. An open tour is one where the origin and destination vertices are different.
Specified by:
improveOpenTour in interface ImproveI

improveOpenTour

public double improveOpenTour(java.util.Vector tour,
                              boolean fixedOrigin,
                              boolean fixedDestination)
                       throws TourNotFoundException
Improve an open tour solution with fixed end points. An open tour is one where the origin and destination vertices are different. The arguments can be used to fix either end.
Specified by:
improveOpenTour in interface ImproveI

improveClosedTour

public double improveClosedTour(java.util.Vector tour)
                         throws TourNotFoundException
Improve a closed tour solution. An closed tour is one where the origin and destination vertices are the same.
Specified by:
improveClosedTour in interface ImproveI

initTourUS

protected void initTourUS(int head,
                          int tail)

improve

protected void improve()
                throws TourNotFoundException

removeType0

protected void removeType0(drasys.or.graph.tsp.Geni.Vert vv)

replaceType0

protected void replaceType0(drasys.or.graph.tsp.Geni.Vert vv)

forwardRemoveType1

protected void forwardRemoveType1(drasys.or.graph.tsp.Geni.Vert vv,
                                  drasys.or.graph.tsp.Geni.Vert vj,
                                  drasys.or.graph.tsp.Geni.Vert vk,
                                  drasys.or.graph.tsp.Geni.Vert vj1,
                                  drasys.or.graph.tsp.Geni.Vert vk1)

forwardReplaceType1

protected void forwardReplaceType1(drasys.or.graph.tsp.Geni.Vert vv,
                                   drasys.or.graph.tsp.Geni.Vert vj,
                                   drasys.or.graph.tsp.Geni.Vert vk,
                                   drasys.or.graph.tsp.Geni.Vert vj1,
                                   drasys.or.graph.tsp.Geni.Vert vk1)

forwardRemoveType2

protected void forwardRemoveType2(drasys.or.graph.tsp.Geni.Vert vv,
                                  drasys.or.graph.tsp.Geni.Vert vj,
                                  drasys.or.graph.tsp.Geni.Vert vk,
                                  drasys.or.graph.tsp.Geni.Vert vl,
                                  drasys.or.graph.tsp.Geni.Vert vj1,
                                  drasys.or.graph.tsp.Geni.Vert vk1,
                                  drasys.or.graph.tsp.Geni.Vert vl1)

forwardReplaceType2

protected void forwardReplaceType2(drasys.or.graph.tsp.Geni.Vert vv,
                                   drasys.or.graph.tsp.Geni.Vert vj,
                                   drasys.or.graph.tsp.Geni.Vert vk,
                                   drasys.or.graph.tsp.Geni.Vert vl,
                                   drasys.or.graph.tsp.Geni.Vert vj1,
                                   drasys.or.graph.tsp.Geni.Vert vk1,
                                   drasys.or.graph.tsp.Geni.Vert vl1)

reverseRemoveType1

protected void reverseRemoveType1(drasys.or.graph.tsp.Geni.Vert vv,
                                  drasys.or.graph.tsp.Geni.Vert vj,
                                  drasys.or.graph.tsp.Geni.Vert vk,
                                  drasys.or.graph.tsp.Geni.Vert vj1,
                                  drasys.or.graph.tsp.Geni.Vert vk1)

reverseReplaceType1

protected void reverseReplaceType1(drasys.or.graph.tsp.Geni.Vert vv,
                                   drasys.or.graph.tsp.Geni.Vert vj,
                                   drasys.or.graph.tsp.Geni.Vert vk,
                                   drasys.or.graph.tsp.Geni.Vert vj1,
                                   drasys.or.graph.tsp.Geni.Vert vk1)

reverseRemoveType2

protected void reverseRemoveType2(drasys.or.graph.tsp.Geni.Vert vv,
                                  drasys.or.graph.tsp.Geni.Vert vj,
                                  drasys.or.graph.tsp.Geni.Vert vk,
                                  drasys.or.graph.tsp.Geni.Vert vl,
                                  drasys.or.graph.tsp.Geni.Vert vj1,
                                  drasys.or.graph.tsp.Geni.Vert vk1,
                                  drasys.or.graph.tsp.Geni.Vert vl1)

reverseReplaceType2

protected void reverseReplaceType2(drasys.or.graph.tsp.Geni.Vert vv,
                                   drasys.or.graph.tsp.Geni.Vert vj,
                                   drasys.or.graph.tsp.Geni.Vert vk,
                                   drasys.or.graph.tsp.Geni.Vert vl,
                                   drasys.or.graph.tsp.Geni.Vert vj1,
                                   drasys.or.graph.tsp.Geni.Vert vk1,
                                   drasys.or.graph.tsp.Geni.Vert vl1)

saveForRemoveType0

protected void saveForRemoveType0(drasys.or.graph.tsp.Geni.Vert vv)

forwardSaveForRemoveType1

protected void forwardSaveForRemoveType1(drasys.or.graph.tsp.Geni.Vert vv,
                                         drasys.or.graph.tsp.Geni.Vert vj,
                                         drasys.or.graph.tsp.Geni.Vert vk)

forwardSaveForRemoveType2

protected void forwardSaveForRemoveType2(drasys.or.graph.tsp.Geni.Vert vv,
                                         drasys.or.graph.tsp.Geni.Vert vj,
                                         drasys.or.graph.tsp.Geni.Vert vk,
                                         drasys.or.graph.tsp.Geni.Vert vl)

reverseSaveForRemoveType1

protected void reverseSaveForRemoveType1(drasys.or.graph.tsp.Geni.Vert vv,
                                         drasys.or.graph.tsp.Geni.Vert vj,
                                         drasys.or.graph.tsp.Geni.Vert vk)

reverseSaveForRemoveType2

protected void reverseSaveForRemoveType2(drasys.or.graph.tsp.Geni.Vert vv,
                                         drasys.or.graph.tsp.Geni.Vert vj,
                                         drasys.or.graph.tsp.Geni.Vert vk,
                                         drasys.or.graph.tsp.Geni.Vert vl)

forwardFindBestRemove

protected void forwardFindBestRemove(drasys.or.graph.tsp.Geni.Vert vv)

reverseFindBestRemove

protected void reverseFindBestRemove(drasys.or.graph.tsp.Geni.Vert vv)

forwardSequenceRemove

protected void forwardSequenceRemove(drasys.or.graph.tsp.Geni.Vert head)

reverseSequenceRemove

protected void reverseSequenceRemove(drasys.or.graph.tsp.Geni.Vert tail)
Overview  Package   Class  Tree  Deprecated  Index  Help 
 PREV CLASS   NEXT CLASS FRAMES    NO FRAMES
SUMMARY:  INNER | FIELD | CONSTR | METHOD DETAIL:  FIELD | CONSTR | METHOD
Copyright(C)1997-2000 by DRA Systems all rights reserved. OpsResearch.com