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 Geni

java.lang.Object
  |
  +--drasys.or.graph.tsp.TSPBase
        |
        +--drasys.or.graph.tsp.Geni
Direct Known Subclasses:
Us
public class Geni
extends TSPBase
implements ConstructI

An implementation of the 'GENI' construction 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
Geni(int sizeOfNeighborhood)
          Sets the neighborhood to the argument.
Geni(int sizeOfNeighborhood, GraphI graph)
          Sets the neighborhood and the target graph.
 
Method Summary
protected  void addNeighbor(drasys.or.graph.tsp.Geni.Vert vv)
           
protected  void addToTour(drasys.or.graph.tsp.Geni.Vert vv)
           
protected  void applyForwardType1(drasys.or.graph.tsp.Geni.Vert v)
           
protected  void applyForwardType2(drasys.or.graph.tsp.Geni.Vert v)
           
protected  void applyReverseType1(drasys.or.graph.tsp.Geni.Vert v)
           
protected  void applyReverseType2(drasys.or.graph.tsp.Geni.Vert v)
           
protected  void applyType0(drasys.or.graph.tsp.Geni.Vert v)
           
protected  double calcCost()
          Returns the cost of the solution tour.
protected  int[] calcTour()
          Returns the solution tour.
protected  boolean checkList()
           
protected  void construct()
           
 double constructClosedTour()
          Construct a closed tour solution.
 double constructOpenTour()
          Construct an open tour solution with arbitrary end points.
 double constructOpenTour(java.lang.Object originKey, java.lang.Object destinationKey)
          Construct a tour with explicit end points.
 double constructOpenTourFrom(java.lang.Object originKey)
          Construct an open tour solution with an explicit origin and arbitrary destination.
 double constructOpenTourTo(java.lang.Object destinationKey)
          Construct an open tour solution with an explicit destination and arbitrary origin.
protected  void costOfType0(int v, drasys.or.graph.tsp.Geni.Vert vi)
           
protected  void forwardCostOfInsertType1(int v, drasys.or.graph.tsp.Geni.Vert vi, drasys.or.graph.tsp.Geni.Vert vj, drasys.or.graph.tsp.Geni.Vert vk)
           
protected  void forwardCostOfInsertType2(int v, drasys.or.graph.tsp.Geni.Vert vi, drasys.or.graph.tsp.Geni.Vert vj, drasys.or.graph.tsp.Geni.Vert vk, drasys.or.graph.tsp.Geni.Vert vl)
           
protected  void forwardFindBestInsert(drasys.or.graph.tsp.Geni.Vert vv)
           
protected  void forwardFlip(drasys.or.graph.tsp.Geni.Vert beg, drasys.or.graph.tsp.Geni.Vert end)
           
protected  void forwardSequenceInsert(drasys.or.graph.tsp.Geni.Vert head)
           
protected  void initTourGENI(int head, int tail)
           
protected  void newForwardEdge(drasys.or.graph.tsp.Geni.Vert from, drasys.or.graph.tsp.Geni.Vert to)
           
protected  void newReverseEdge(drasys.or.graph.tsp.Geni.Vert to, drasys.or.graph.tsp.Geni.Vert from)
           
protected  void reverseCostOfInsertType1(int v, drasys.or.graph.tsp.Geni.Vert vi, drasys.or.graph.tsp.Geni.Vert vj, drasys.or.graph.tsp.Geni.Vert vk)
           
protected  void reverseCostOfInsertType2(int v, drasys.or.graph.tsp.Geni.Vert vi, drasys.or.graph.tsp.Geni.Vert vj, drasys.or.graph.tsp.Geni.Vert vk, drasys.or.graph.tsp.Geni.Vert vl)
           
protected  void reverseFindBestInsert(drasys.or.graph.tsp.Geni.Vert vv)
           
protected  void reverseFlip(drasys.or.graph.tsp.Geni.Vert end, drasys.or.graph.tsp.Geni.Vert beg)
           
protected  void reverseSequenceInsert(drasys.or.graph.tsp.Geni.Vert tail)
           
 void selectVertex(boolean select)
          Selects all of the vertices in the graph to be in the tour if 'select' is true.
 void selectVertex(boolean[] select)
          Selects all of the vertices whose corresponding element in 'select' is true.
 void selectVertex(java.lang.Object key, boolean select)
          Selects the vertex to be in the tour if 'select' is true.
 java.lang.String 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

Geni

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

Geni

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

constructOpenTour

public double constructOpenTour(java.lang.Object originKey,
                                java.lang.Object destinationKey)
                         throws TourNotFoundException,
                                VertexNotFoundException
Construct a tour with explicit end points. An open tour is one where the origin and destination vertices are different.
Specified by:
constructOpenTour in interface ConstructI
Throws:
TourNotFoundException - if the tour can not be constructed.

constructOpenTourFrom

public double constructOpenTourFrom(java.lang.Object originKey)
                             throws TourNotFoundException,
                                    VertexNotFoundException
Construct an open tour solution with an explicit origin and arbitrary destination. An open tour is one where the origin and destination vertices are different.
Specified by:
constructOpenTourFrom in interface ConstructI
Throws:
TourNotFoundException - if the tour can not be constructed.

constructOpenTourTo

public double constructOpenTourTo(java.lang.Object destinationKey)
                           throws TourNotFoundException,
                                  VertexNotFoundException
Construct an open tour solution with an explicit destination and arbitrary origin. An open tour is one where the origin and destination vertices are different.
Specified by:
constructOpenTourTo in interface ConstructI
Throws:
TourNotFoundException - if the tour can not be constructed.

constructOpenTour

public double constructOpenTour()
                         throws TourNotFoundException
Construct an open tour solution with arbitrary end points. An open tour is one where the origin and destination vertices are different.
Specified by:
constructOpenTour in interface ConstructI
Throws:
TourNotFoundException - if the tour can not be constructed.

constructClosedTour

public double constructClosedTour()
                           throws TourNotFoundException
Construct a closed tour solution. A closed tour is one where the origin and destination vertices are the same.
Specified by:
constructClosedTour in interface ConstructI
Throws:
TourNotFoundException - if the tour can not be constructed.

initTourGENI

protected void initTourGENI(int head,
                            int tail)

construct

protected void construct()
                  throws TourNotFoundException

calcCost

protected double calcCost()
Returns the cost of the solution tour.
Throws:
TSPError - if no solution was created.

calcTour

protected int[] calcTour()
Returns the solution tour.
Throws:
TSPError - if no solution was created.

checkList

protected boolean checkList()

forwardFlip

protected void forwardFlip(drasys.or.graph.tsp.Geni.Vert beg,
                           drasys.or.graph.tsp.Geni.Vert end)

reverseFlip

protected void reverseFlip(drasys.or.graph.tsp.Geni.Vert end,
                           drasys.or.graph.tsp.Geni.Vert beg)

costOfType0

protected void costOfType0(int v,
                           drasys.or.graph.tsp.Geni.Vert vi)

forwardCostOfInsertType1

protected void forwardCostOfInsertType1(int v,
                                        drasys.or.graph.tsp.Geni.Vert vi,
                                        drasys.or.graph.tsp.Geni.Vert vj,
                                        drasys.or.graph.tsp.Geni.Vert vk)

forwardCostOfInsertType2

protected void forwardCostOfInsertType2(int v,
                                        drasys.or.graph.tsp.Geni.Vert vi,
                                        drasys.or.graph.tsp.Geni.Vert vj,
                                        drasys.or.graph.tsp.Geni.Vert vk,
                                        drasys.or.graph.tsp.Geni.Vert vl)

reverseCostOfInsertType1

protected void reverseCostOfInsertType1(int v,
                                        drasys.or.graph.tsp.Geni.Vert vi,
                                        drasys.or.graph.tsp.Geni.Vert vj,
                                        drasys.or.graph.tsp.Geni.Vert vk)

reverseCostOfInsertType2

protected void reverseCostOfInsertType2(int v,
                                        drasys.or.graph.tsp.Geni.Vert vi,
                                        drasys.or.graph.tsp.Geni.Vert vj,
                                        drasys.or.graph.tsp.Geni.Vert vk,
                                        drasys.or.graph.tsp.Geni.Vert vl)

forwardFindBestInsert

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

reverseFindBestInsert

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

newForwardEdge

protected void newForwardEdge(drasys.or.graph.tsp.Geni.Vert from,
                              drasys.or.graph.tsp.Geni.Vert to)

newReverseEdge

protected void newReverseEdge(drasys.or.graph.tsp.Geni.Vert to,
                              drasys.or.graph.tsp.Geni.Vert from)

applyType0

protected void applyType0(drasys.or.graph.tsp.Geni.Vert v)

applyForwardType1

protected void applyForwardType1(drasys.or.graph.tsp.Geni.Vert v)

applyForwardType2

protected void applyForwardType2(drasys.or.graph.tsp.Geni.Vert v)

applyReverseType1

protected void applyReverseType1(drasys.or.graph.tsp.Geni.Vert v)

applyReverseType2

protected void applyReverseType2(drasys.or.graph.tsp.Geni.Vert v)

addNeighbor

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

addToTour

protected void addToTour(drasys.or.graph.tsp.Geni.Vert vv)
                  throws TourNotFoundException

forwardSequenceInsert

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

reverseSequenceInsert

protected void reverseSequenceInsert(drasys.or.graph.tsp.Geni.Vert tail)

toString

public java.lang.String toString()
Overrides:
toString in class java.lang.Object

selectVertex

public void selectVertex(boolean[] select)
Selects all of the vertices whose corresponding element in 'select' is true. Unselects all of the vertices whose corresponding element in 'select' is false. All of the vertices are selected by default when the algorithm is constructed.
Specified by:
selectVertex in interface ConstructI

selectVertex

public void selectVertex(boolean select)
Selects all of the vertices in the graph to be in the tour if 'select' is true. Unselects all of the vertices if 'select' is false. All of the vertices are selected by default when the algorithm is constructed.
Specified by:
selectVertex in interface ConstructI

selectVertex

public void selectVertex(java.lang.Object key,
                         boolean select)
                  throws VertexNotFoundException
Selects the vertex to be in the tour if 'select' is true. Unselects the vertex if 'select' is false. All of the vertices are selected by default when the algorithm is constructed.
Specified by:
selectVertex in interface ConstructI
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