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

Class CheapestInsertion

java.lang.Object

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

com.graphhopper.jsprit.core.algorithm.recreate.CheapestInsertion

All Implemented Interfaces:

InsertionStrategy

public final class CheapestInsertion
extends AbstractInsertionStrategy

True Best Insertion (Cheapest Insertion) as defined in VRP literature.

This algorithm repeatedly:

1. Evaluates ALL unassigned jobs at ALL possible positions
2. Selects the (job, position) pair with the globally minimum insertion cost
3. Inserts that job
4. Repeats until all jobs are inserted or no feasible insertion exists

This differs from BestInsertion which processes jobs in random order, inserting each at its best position (Sequential/Random Order Insertion).

Time complexity: O(J² × R × P) where J = jobs, R = routes, P = positions per route. This is more expensive than random order insertion but typically produces better solutions.

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
CheapestInsertion(JobInsertionCostsCalculator insertionCostsCalculator, VehicleRoutingProblem vrp)

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

CheapestInsertion

public CheapestInsertion(JobInsertionCostsCalculator insertionCostsCalculator,
 VehicleRoutingProblem vrp)

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