Package com.graphhopper.jsprit.core.algorithm.ruin

Class RuinKruskalClusters

java.lang.Object

com.graphhopper.jsprit.core.algorithm.ruin.AbstractRuinStrategy

com.graphhopper.jsprit.core.algorithm.ruin.RuinKruskalClusters

All Implemented Interfaces:

RuinStrategy

public final class RuinKruskalClusters
extends AbstractRuinStrategy

Ruin strategy that removes clusters of jobs identified using Kruskal's MST algorithm.

Algorithm: 1. Select target route (random or via job neighborhoods) 2. Build MST of jobs in route using Kruskal's algorithm 3. Cut longest edge to get 2 clusters 4. Remove one cluster 5. Repeat with neighboring routes until q jobs removed

Ranked #2 in Voigt (2025) "A review and ranking of operators in adaptive large neighborhood search for vehicle routing problems."

Advantages over DBSCAN-based clustering: - No parameters to tune (ε, minPts) - Always produces exactly 2 clusters - Never fails (no fallback needed) - Deterministic given the distances

Field Summary

Fields inherited from class com.graphhopper.jsprit.core.algorithm.ruin.AbstractRuinStrategy

jobFilter, random, ruinShareFactory

Constructor Summary

Constructors

Constructor	Description
RuinKruskalClusters(VehicleRoutingProblem vrp, int initialNumberJobsToRemove, JobNeighborhoods jobNeighborhoods)

Method Summary

Modifier and Type	Method	Description
Collection<Job>	ruinRoutes(Collection<VehicleRoute> vehicleRoutes)
void	setPreferSmallerCluster(boolean preferSmallerCluster)	If true, prefers removing the smaller of the two clusters.
String	toString()

Methods inherited from class com.graphhopper.jsprit.core.algorithm.ruin.AbstractRuinStrategy

addListener, filterJobs, getListeners, getRuinShareFactory, removeJob, removeJob, removeListener, ruin, setJobFilter, setRandom, setRuinShareFactory

Methods inherited from class java.lang.Object

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

Constructor Details

RuinKruskalClusters

public RuinKruskalClusters(VehicleRoutingProblem vrp,
 int initialNumberJobsToRemove,
 JobNeighborhoods jobNeighborhoods)

Method Details

setPreferSmallerCluster

public void setPreferSmallerCluster(boolean preferSmallerCluster)

If true, prefers removing the smaller of the two clusters. If false, randomly chooses between clusters.

ruinRoutes

public Collection<Job> ruinRoutes(Collection<VehicleRoute> vehicleRoutes)

Specified by:

ruinRoutes in class AbstractRuinStrategy

toString

public String toString()

Overrides:

toString in class Object