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

Class PositionBasedRegretInsertionFast

java.lang.Object

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

com.graphhopper.jsprit.core.algorithm.recreate.PositionBasedRegretInsertionFast

All Implemented Interfaces:

InsertionStrategy

public class PositionBasedRegretInsertionFast
extends AbstractInsertionStrategy

Fast position-based regret insertion with hybrid optimization.

Combines the speed of route-based regret with the accuracy of position-based regret:

1. Route-level screening: Use route-based best insertions to identify promising routes
2. Position expansion: Only expand to all positions for top-m candidate routes
3. Cascading filters: Use cheap lower bounds to prune positions before expensive constraint checks

Supports regret-k for any k (regret-2, regret-3, regret-4, etc.)

The pruning strategy:

• Distance lower bound: skip positions where marginal distance alone exceeds top-k threshold
• Time window check: skip positions that violate job's time window
• Full constraint check: only for positions that pass the cheaper filters

Author:

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
PositionBasedRegretInsertionFast(JobInsertionCostsCalculator insertionCostsCalculator, VehicleRoutingProblem vrp, VehicleFleetManager fleetManager)

Method Summary

Modifier and Type	Method	Description
Collection<Job>	insertUnassignedJobs(Collection<VehicleRoute> routes, Collection<Job> unassignedJobs)
void	setDependencyTypes(DependencyType[] dependencyTypes)
void	setRegretK(int k)	Sets the number of best positions to track for regret calculation.
void	setScoringFunction(RegretKScoringFunction scoringFunction)
void	setSwitchAllowed(boolean switchAllowed)
void	setTopRoutesToExpand(int m)	Sets the number of top routes to expand for position-level analysis.
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

PositionBasedRegretInsertionFast

public PositionBasedRegretInsertionFast(JobInsertionCostsCalculator insertionCostsCalculator,
 VehicleRoutingProblem vrp,
 VehicleFleetManager fleetManager)

Method Details

setRegretK

public void setRegretK(int k)

Sets the number of best positions to track for regret calculation. Use k=2 for regret-2, k=3 for regret-3, etc.

setTopRoutesToExpand

public void setTopRoutesToExpand(int m)

Sets the number of top routes to expand for position-level analysis. Routes beyond this are only considered at route-level (best position only).

setScoringFunction

public void setScoringFunction(RegretKScoringFunction scoringFunction)

setSwitchAllowed

public void setSwitchAllowed(boolean switchAllowed)

setDependencyTypes

public void setDependencyTypes(DependencyType[] dependencyTypes)

toString

public String toString()

Overrides:

toString in class Object

insertUnassignedJobs

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

Specified by:

insertUnassignedJobs in class AbstractInsertionStrategy