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

Class RegretInsertionFast

java.lang.Object

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

com.graphhopper.jsprit.core.algorithm.recreate.RegretInsertionFast

All Implemented Interfaces:

InsertionStrategy

public class RegretInsertionFast
extends AbstractInsertionStrategy

Insertion based on regret approach with affected-job tracking optimization.

Basically calculates the insertion cost of the firstBest and the secondBest alternative. The score is then calculated as difference between secondBest and firstBest, plus additional scoring variables that can defined in this.ScoringFunction. The idea is that if the cost of the secondBest alternative is way higher than the first best, it seems to be important to insert this customer immediatedly. If difference is not that high, it might not impact solution if this customer is inserted later.

Affected-Job Tracking Optimization: After inserting a job into route R, only jobs that had R in their top-2 (best or second-best) routes need full recalculation. Other jobs use cheap lower-bound checks to determine if R became competitive. Combined with spatial filtering, this provides significant speedup for large instances (5-10x typical).

Author:

stefan schroeder

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
RegretInsertionFast(JobInsertionCostsCalculator jobInsertionCalculator, VehicleRoutingProblem vehicleRoutingProblem, VehicleFleetManager fleetManager)

Method Summary

Modifier and Type	Method	Description
AdaptiveSpatialFilter	getSpatialFilter()
Collection<Job>	insertUnassignedJobs(Collection<VehicleRoute> routes, Collection<Job> unassignedJobs)	Runs insertion.
boolean	isAffectedJobTrackingEnabled()
void	setAffectedJobTrackingEnabled(boolean enabled)	Enables or disables affected-job tracking optimization.
void	setDependencyTypes(DependencyType[] dependencyTypes)
void	setRegretK(int k)
void	setRegretKScoringFunction(RegretKScoringFunction regretKScoringFunction)
void	setRegretScoringFunction(RegretScoringFunction regretScoringFunction)
void	setScoringFunction(ScoringFunction scoringFunction)	Sets the scoring function.
void	setSpatialFilter(AdaptiveSpatialFilter spatialFilter)
void	setSwitchAllowed(boolean switchAllowed)
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

RegretInsertionFast

public RegretInsertionFast(JobInsertionCostsCalculator jobInsertionCalculator,
 VehicleRoutingProblem vehicleRoutingProblem,
 VehicleFleetManager fleetManager)

Method Details

setScoringFunction

public void setScoringFunction(ScoringFunction scoringFunction)

Sets the scoring function.

By default, the this.TimeWindowScorer is used.

Parameters:

scoringFunction - to score

setRegretScoringFunction

public void setRegretScoringFunction(RegretScoringFunction regretScoringFunction)

setRegretKScoringFunction

public void setRegretKScoringFunction(RegretKScoringFunction regretKScoringFunction)

setRegretK

public void setRegretK(int k)

setSwitchAllowed

public void setSwitchAllowed(boolean switchAllowed)

setDependencyTypes

public void setDependencyTypes(DependencyType[] dependencyTypes)

setSpatialFilter

public void setSpatialFilter(AdaptiveSpatialFilter spatialFilter)

getSpatialFilter

public AdaptiveSpatialFilter getSpatialFilter()

setAffectedJobTrackingEnabled

public void setAffectedJobTrackingEnabled(boolean enabled)

Enables or disables affected-job tracking optimization. When enabled, only jobs affected by a route modification are recalculated. Default is enabled.

Parameters:

enabled - true to enable (default), false to disable

isAffectedJobTrackingEnabled

public boolean isAffectedJobTrackingEnabled()

toString

public String toString()

Overrides:

toString in class Object

insertUnassignedJobs

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

Runs insertion.

Before inserting a job, all unassigned jobs are scored according to its best- and secondBest-insertion plus additional scoring variables.

Specified by:

insertUnassignedJobs in class AbstractInsertionStrategy