drasys.or.graph.vrp
Class ClarkeWrightBase

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

public class ClarkeWrightBase

extends RandomizableBase

implements ConstructI, RandomizableI

A randomizable greedy VRP construction algorithm based on the savings list algorithm described by Clarke and Wright. A strength value of '0' makes the algorithm deterministic. A strength of '1' or more allows the algorithm to randomly select savings lower than the current but no farther than 'strength' savings away. If a TSP subalgorithm is supplied in the constructor the algorithm will use it to improve the two tours involved in a merge if the merge failed 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

ClarkeWrightBase()

ClarkeWrightBase(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

ClarkeWrightBase

public ClarkeWrightBase()

ClarkeWrightBase

public ClarkeWrightBase(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.