Walkthrough---Algorithm.md

Configure and create algorithm

Per xml

Structure of overall algorithm config:

Structure of overall (search) strategy:

Structure of individual search strategies and modules:

VehicleRoutingProblem problem = ...
String myAlgorithmConfigXmlFilname = ...
VehicleRoutingAlgorithm vra = VehicleRoutingAlgorithms.readAndCreateAlgorithm(problem, myAlgorithmConfigXmlFilename);

In code

AlgorithmConfig myAlgorithmConfig = new AlgorithmConfig();
XMLConfiguration xmlConfig = myAlgorithmConfig.getXMLConfiguration();
xmlConfig.setProperty("iterations", 2000);
xmlConfig.setProperty("construction.insertion[@name]","bestInsertion");
		
xmlConfig.setProperty("strategy.memory", 1);
String searchStrategy = "strategy.searchStrategies.searchStrategy";
		
xmlConfig.setProperty(searchStrategy + "(0).selector[@name]","selectBest");
xmlConfig.setProperty(searchStrategy + "(0).acceptor[@name]","schrimpfAcceptance");
xmlConfig.setProperty(searchStrategy + "(0).acceptor.alpha","0.4");
xmlConfig.setProperty(searchStrategy + "(0).acceptor.warmup","100");

xmlConfig.setProperty(searchStrategy + "(0).modules.module(0)[@name]","ruin_and_recreate");
xmlConfig.setProperty(searchStrategy + "(0).modules.module(0).ruin[@name]","randomRuin");
xmlConfig.setProperty(searchStrategy + "(0).modules.module(0).ruin.share","0.5");
xmlConfig.setProperty(searchStrategy + "(0).modules.module(0).insertion[@name]","bestInsertion");
xmlConfig.setProperty(searchStrategy + "(0).probability","0.5");
		
xmlConfig.setProperty(searchStrategy + "(1).selector[@name]","selectBest");
xmlConfig.setProperty(searchStrategy + "(1).acceptor[@name]","schrimpfAcceptance");
xmlConfig.setProperty(searchStrategy + "(1).modules.module(0)[@name]","ruin_and_recreate");
xmlConfig.setProperty(searchStrategy + "(1).modules.module(0).ruin[@name]","radialRuin");
xmlConfig.setProperty(searchStrategy + "(1).modules.module(0).ruin.share","0.3");
xmlConfig.setProperty(searchStrategy + "(1).modules.module(0).insertion[@name]","bestInsertion");
xmlConfig.setProperty(searchStrategy + "(1).probability","0.5");

VehicleRoutingAlgorithm vra = VehicleRoutingAlgorithms.createAlgorithm(problem,myAlgorithmConfig);

Search solution

Collection<VehicleRoutingProblemSolution> solutions = vra.searchSolutions();

Overwrite iterations in code

vra.setMaxIterations(nOfIterations);

Premature termination

Time

xml

<prematureBreak basedOn="time">
    <time>2.</time>
</prematureBreak>

in-code

TimeTermination prematureTermination = new TimeTermination(2.); //in seconds
vra.setPrematureAlgorithmTermination(prematureTermination);
vra.addListener(prematureTermination);

Iterations

xml

<prematureBreak basedOn="iterations">
    <iterations>200</iterations>
</prematureBreak>

in-code

vra.setPrematureAlgorithmTermination(new IterationWithoutImprovementTermination(200));

Variation Coefficient

xml

<prematureBreak basedOn="variationCoefficient">
    <threshold>0.01</threshold>
    <iterations>50</iterations>
</prematureBreak>

in-code

VariationCoefficientTermination prematureTermination = new VariationCoefficientTermination(50, 0.01);
vra.setPrematureAlgorithmTermination(prematureTermination);
vra.addListener(prematureTermination);

Add initial solution

vra.addInitialSolution(initialSolution);

Add your own code, or listen to the algorithm

The following figure shows the various entry points for your implementation.

core.algorithm.recreate.listener.InsertionListener in turn is parent to InsertionStartsListener, InsertionEndsListener, JobInsertedListener and VehicleSwitchedListener.

Implement one or many listener(s) and register your implementation in the algorithm like that:

IterationStartsListener iterationStartPrinter = new IterationStartsListener() {
			
        @Override
        public void informIterationStarts(int i, VehicleRoutingProblem problem, Collection solutions) {
              System.out.println("iteration " + i + " starts");
        }
			
};
vra.addListener(iterationStartPrinter);

Note that - depending on the listener - your implementation should be fast, otherwise it can significantly influence the performance of the algorithm.

Customize your algorithm with core.algorithm.VehicleRoutingAlgorithmBuilder

To use the builder, you need to use 1.2.1-SNAPSHOT version.

VehicleRoutingAlgorithmBuilder algorithmBuilder = new VehicleRoutingAlgorithmBuilder(problem, "myAlgorithmConfig.xml");

The basic structure of the meta-heuristic is still configured in the xml-file (myAlgorithmConfig.xml) or in AlgorithmConfig.java. However, you can set your own objective function and define your own constraints.

Set custom objective function

By default, the sum of fixed and variable transportation costs are minimized. Thus if you do not set your own objective, the algorithm grabs the costs-parameters you defined in core.problem.vehicle.VehicleTypeImpl.java and calculates total transportation costs accordingly. If you want to define your own, make it like this

algorithmBuilder.setObjectiveFunction(objectiveFunction);

Note that if you set your own objective function, your insertion heuristic should insert the jobs according this function. Therefore you need to find appropriate soft constraints to penalyze bad and/or reward good insertion moves.

Use default cost-calculators

algorithmBuilder.addDefaultCostCalculators();

This adds the default objective function and its corresponding insertion costs calculation to penalyze bad and/or reward good insertion moves.

Add default (core) constraints and updater

algorithmBuilder.addCoreConstraints();

This basically adds capacity and time-window constraints.

Set your own core.algorithm.state.StateManager

algorithmBuilder.setStateManager(stateManager);

Set your own core.problem.constraint.ConstraintManager

algorithmBuilder.setStateAndConstraintManager(stateManager, constraintManager);

If you want to add your own constraints you need to define your own stateManager as well.

Build the algorithm

VehicleRoutingAlgorithm vra = algorithmBuilder.build();

Note that

VehicleRoutingAlgorithm vra = VehicleRoutingAlgorithms.readAndCreateAlgorithm(routingProblem, "yourAlgorithmConfig");

is equivalent to

VehicleRoutingAlgorithmBuilder vraBuilder = new VehicleRoutingAlgorithmBuilder(routingProblem, "yourAlgorithmConfig");
vraBuilder.addCoreConstraints();
vraBuilder.addDefaultCostCalculators();
VehicleRoutingAlgorithm vra = vraBuilder.build();

which is in turn equivalent to

VehicleRoutingAlgorithmBuilder vraBuilder = new VehicleRoutingAlgorithmBuilder(routingProblem, "yourAlgorithmConfig");

StateManager stateManager = new StateManager(problem.getTransportCosts());
stateManager.updateLoadStates();
stateManager.updateTimeWindowStates();

ConstraintManager constraintManager = new ConstraintManager(problem, stateManager);
constraintManager.addLoadConstraint();
constraintManager.addTimeWindowConstraint();

vraBuilder.setStateAndConstraintManager(stateManager, constraintManager);

vraBuilder.addDefaultCostCalculators();
VehicleRoutingAlgorithm vra = vraBuilder.build();