Package com.graphhopper.jsprit.core.algorithm.recreate

Class BestInsertion

java.lang.Object

com.graphhopper.jsprit.core.algorithm.recreate.AbstractInsertionStrategy

com.graphhopper.jsprit.core.algorithm.recreate.BestInsertion

All Implemented Interfaces:

InsertionStrategy

public final class BestInsertion
extends AbstractInsertionStrategy

Sequential insertion that processes jobs in random order, inserting each at its best position.

Note: Despite the name, this is NOT "Best Insertion" as defined in VRP literature. This implementation:

1. Shuffles jobs randomly
2. Sorts by priority
3. For each job in this order, inserts it at the position with minimum additional cost

This is more accurately called "Sequential Insertion with Random Order" or "Random Order Insertion".

For true Best Insertion (Cheapest Insertion) as defined in literature, where the globally cheapest (job, position) pair is selected at each iteration, use CheapestInsertion.

Author:

stefan schroeder

See Also:

• CheapestInsertion

Nested Class Summary

Nested classes/interfaces inherited from class com.graphhopper.jsprit.core.algorithm.recreate.AbstractInsertionStrategy

AbstractInsertionStrategy.Insertion

Field Summary

Fields inherited from class com.graphhopper.jsprit.core.algorithm.recreate.AbstractInsertionStrategy

NO_NEW_DEPARTURE_TIME_YET, NO_NEW_DRIVER_YET, NO_NEW_VEHICLE_YET, random, vrp

Constructor Summary

Constructors

Constructor	Description
BestInsertion(JobInsertionCostsCalculator jobInsertionCalculator, VehicleRoutingProblem vehicleRoutingProblem)

Method Summary

Modifier and Type	Method	Description
Collection<Job>	insertUnassignedJobs(Collection<VehicleRoute> vehicleRoutes, Collection<Job> unassignedJobs)
String	toString()

Methods inherited from class com.graphhopper.jsprit.core.algorithm.recreate.AbstractInsertionStrategy

addListener, getListeners, insertJob, insertJobs, markUnassigned, removeListener, setRandom

Methods inherited from class java.lang.Object

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

Constructor Details

BestInsertion

public BestInsertion(JobInsertionCostsCalculator jobInsertionCalculator,
 VehicleRoutingProblem vehicleRoutingProblem)

Method Details

toString

public String toString()

Overrides:

toString in class Object

insertUnassignedJobs

public Collection<Job> insertUnassignedJobs(Collection<VehicleRoute> vehicleRoutes,
 Collection<Job> unassignedJobs)

Specified by:

insertUnassignedJobs in class AbstractInsertionStrategy