drasys.or.graph.vrp
Class GillettMillerBase

java.lang.Object
  |
  +--drasys.or.graph.vrp.VRPBase
        |
        +--drasys.or.graph.vrp.ConstructBase
              |
              +--drasys.or.graph.vrp.RandomizableBase
                    |
                    +--drasys.or.graph.vrp.GillettMillerBase

public class GillettMillerBase

extends RandomizableBase

implements ConstructI, RandomizableI

A randomizable greedy VRP construction algorithm. A strength value of '0' makes the algorithm deterministic. A strength of '1' causes the algorithm to randomly select a starting angle and direction. A strength of '2' or more allows the algorithm to randomly select nodes beyond the current but no farther than 'strength - 1' unused nodes away. If a TSP subalgorithm is supplied in the constructor the algorithm will use it to improve the current tour any time a node insertion fails because of the cost constraint.

References:

Local Search in Combinatorial Optimization
    Jan Karel Lenstra (Editor), Emile Aarts (Editor) / Paperback / Published 1997
The Traveling Salesman Problem : A Guided Tour of Combinatorial Optimization
    E.L. Lawler (Editor) / Paperback / Published 1985

Fields inherited from class drasys.or.graph.vrp.ConstructBase

_selected

 

Fields inherited from class drasys.or.graph.vrp.VRPBase

_closed, _depotKey, _edgeKey, _graph, _maxCost, _maxLoad, _out, _properties, _vehicleCost

 

Constructor Summary

GillettMillerBase()

GillettMillerBase(ImproveI improveSubalgorithm)

 

Method Summary
double	constructClosedTours(java.lang.Object depotKey)           Construct a solution with closed tours that begin and end at the depot vertex.
double	constructInboundTours(java.lang.Object depotKey)           Construct a solution with open tours that begin at arbitrary vertices and end at the depot vertex.
double	constructOutboundTours(java.lang.Object depotKey)           Construct a solution with open tours that begin at the depot vertex and end at arbitrary vertices.
double	getCost()           Returns the total cost of the solution tours.
double[]	getCosts()           Returns the cost of each of the solution tours.
double[]	getLoads()           Returns the load for each of the solution tours.
java.util.Vector[]	getTours()           Returns the solution tours generated by the algorithm.

 

Methods inherited from class drasys.or.graph.vrp.RandomizableBase

getRandom, setRandom, setStrength

 

Methods inherited from class drasys.or.graph.vrp.ConstructBase

isSelected, selectVertex, selectVertex, selectVertex, setEdgeKey, setGraph, setProperties, sizeOfSelected

 

Methods inherited from class drasys.or.graph.vrp.VRPBase

copyTours, getCost, getGraph, getLoad, getLoads, setCapacityConstraint, setCostConstraint, setVehicleCost

 

Methods inherited from class java.lang.Object

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

 

Constructor Detail

GillettMillerBase

public GillettMillerBase()

GillettMillerBase

public GillettMillerBase(ImproveI improveSubalgorithm)

constructOutboundTours

public double constructOutboundTours(java.lang.Object depotKey)
                              throws SolutionNotFoundException,
                                     VertexNotFoundException

Construct a solution with open tours that begin at the depot vertex and end at arbitrary vertices.

Specified by:

constructOutboundTours in interface ConstructI

Throws:

SolutionNotFoundException - if a solution can not be constructed.

constructInboundTours

public double constructInboundTours(java.lang.Object depotKey)
                             throws SolutionNotFoundException,
                                    VertexNotFoundException

Construct a solution with open tours that begin at arbitrary vertices and end at the depot vertex.

Specified by:

constructInboundTours in interface ConstructI

Throws:

SolutionNotFoundException - if a solution can not be constructed.

constructClosedTours

public double constructClosedTours(java.lang.Object depotKey)
                            throws SolutionNotFoundException,
                                   VertexNotFoundException

Construct a solution with closed tours that begin and end at the depot vertex.

Specified by:

constructClosedTours in interface ConstructI

Throws:

SolutionNotFoundException - if a solution can not be constructed.

getCost

public double getCost()
               throws SolutionNotFoundException

Returns the total cost of the solution tours.

Throws:

VRPError - if no solution was created.

getCosts

public double[] getCosts()
                  throws SolutionNotFoundException

Returns the cost of each of the solution tours.

Throws:

VRPError - if no solution was created.

getLoads

public double[] getLoads()
                  throws SolutionNotFoundException

Returns the load for each of the solution tours.

Throws:

VRPError - if no solution was created.

getTours

public java.util.Vector[] getTours()
                            throws SolutionNotFoundException

Returns the solution tours generated by the algorithm. Each tour vector contains all the edges and the vertices in alternating order starting and ending with a vertex. The elements will always be arranged in the order of forward tour traversal.

Throws:

VRPError - if no solution was created.