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

Class KruskalClusterer

java.lang.Object

com.graphhopper.jsprit.core.algorithm.ruin.KruskalClusterer

public class KruskalClusterer
extends Object

Clusters jobs in a route using Kruskal's Minimum Spanning Tree algorithm.

Algorithm: 1. Build complete distance graph between all jobs in route 2. Run Kruskal's algorithm to build MST 3. Remove longest edge in MST 4. Result: exactly 2 clusters (connected components)

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

Constructor Summary

Constructors

Constructor	Description
KruskalClusterer(VehicleRoutingTransportCosts costs)

Method Summary

Modifier and Type	Method	Description
List<List<Job>>	getClusters(VehicleRoute route)	Returns two clusters from the route by cutting the longest MST edge.
List<Job>	getOneCluster(VehicleRoute route, boolean preferSmaller)	Returns one cluster (randomly chosen or smaller) from the route.
void	setRandom(Random random)

Methods inherited from class java.lang.Object

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

Constructor Details

KruskalClusterer

public KruskalClusterer(VehicleRoutingTransportCosts costs)

Method Details

setRandom

public void setRandom(Random random)

getClusters

public List<List<Job>> getClusters(VehicleRoute route)

Returns two clusters from the route by cutting the longest MST edge.

Parameters:

route - the route to cluster

Returns:

list containing exactly 2 clusters, or empty list if route has invalid input: '<' 2 jobs

getOneCluster

public List<Job> getOneCluster(VehicleRoute route,
 boolean preferSmaller)

Returns one cluster (randomly chosen or smaller) from the route.

Parameters:

route - the route to cluster

preferSmaller - if true, returns smaller cluster; if false, random

Returns:

one cluster of jobs