MACRO NEPAL
Route Optimization in Java: Complete Guide with Algorithms and Implementation
awiskar acharya
November 22, 2025
3:55 pm

Route optimization involves finding the most efficient routes for vehicles or delivery personnel. This guide covers various algorithms and implementations for solving routing problems in Java.

Setup and Dependencies

Maven Dependencies
<properties>
<jsprit.version>1.9.0</jsprit.version>
<graphhopper.version>8.0</graphhopper.version>
<optaplanner.version>9.37.0.Final</optaplanner.version>
<spring-boot.version>3.1.0</spring-boot.version>
<gson.version>2.10.1</gson.version>
</properties>
<dependencies>
<!-- jsprit - Vehicle Routing Problem solver -->
<dependency>
<groupId>com.graphhopper</groupId>
<artifactId>jsprit</artifactId>
<version>${jsprit.version}</version>
</dependency>
<!-- GraphHopper - Routing engine -->
<dependency>
<groupId>com.graphhopper</groupId>
<artifactId>graphhopper-core</artifactId>
<version>${graphhopper.version}</version>
</dependency>
<!-- OptaPlanner - Constraint satisfaction solver -->
<dependency>
<groupId>org.optaplanner</groupId>
<artifactId>optaplanner-core</artifactId>
<version>${optaplanner.version}</version>
</dependency>
<!-- Spring Boot -->
<dependency>
<groupId>org.springframework.boot</groupId>
<artifactId>spring-boot-starter-web</artifactId>
<version>${spring-boot.version}</version>
</dependency>
<!-- JSON Processing -->
<dependency>
<groupId>com.google.code.gson</groupId>
<artifactId>gson</artifactId>
<version>${gson.version}</version>
</dependency>
<!-- Math and Utilities -->
<dependency>
<groupId>org.apache.commons</groupId>
<artifactId>commons-math3</artifactId>
<version>3.6.1</version>
</dependency>
</dependencies>

Core Domain Models

1. Basic Routing Models
public class Location {
private String id;
private double latitude;
private double longitude;
private String address;
// constructors, getters, setters
public Location() {}
public Location(String id, double latitude, double longitude) {
this.id = id;
this.latitude = latitude;
this.longitude = longitude;
}
public double distanceTo(Location other) {
double earthRadius = 6371; // kilometers
double latDistance = Math.toRadians(other.latitude - this.latitude);
double lonDistance = Math.toRadians(other.longitude - this.longitude);
double a = Math.sin(latDistance / 2) * Math.sin(latDistance / 2)
+ Math.cos(Math.toRadians(this.latitude)) * Math.cos(Math.toRadians(other.latitude))
* Math.sin(lonDistance / 2) * Math.sin(lonDistance / 2);
double c = 2 * Math.atan2(Math.sqrt(a), Math.sqrt(1 - a));
return earthRadius * c;
}
}
public class Vehicle {
private String id;
private String type;
private Location startLocation;
private Location endLocation;
private int capacity;
private double maxDistance;
private TimeWindow timeWindow;
private double costPerKm;
private double fixedCost;
// constructors, getters, setters
}
public class Job {
private String id;
private Location location;
private int demand;
private int serviceTime; // minutes
private TimeWindow timeWindow;
private JobPriority priority;
private List<String> requiredSkills;
// constructors, getters, setters
}
public class TimeWindow {
private LocalTime startTime;
private LocalTime endTime;
// constructors, getters, setters
public boolean contains(LocalTime time) {
return !time.isBefore(startTime) && !time.isAfter(endTime);
}
public Duration getDuration() {
return Duration.between(startTime, endTime);
}
}
public enum JobPriority {
HIGH, MEDIUM, LOW
}
2. Solution Models
public class Route {
private String vehicleId;
private List<RouteStop> stops;
private double totalDistance;
private double totalTime;
private double totalCost;
private int totalDemand;
// constructors, getters, setters
public Route(String vehicleId) {
this.vehicleId = vehicleId;
this.stops = new ArrayList<>();
}
public void addStop(RouteStop stop) {
this.stops.add(stop);
recalculateMetrics();
}
private void recalculateMetrics() {
this.totalDistance = calculateTotalDistance();
this.totalDemand = calculateTotalDemand();
this.totalTime = calculateTotalTime();
this.totalCost = calculateTotalCost();
}
private double calculateTotalDistance() {
if (stops.size() < 2) return 0;
double distance = 0;
for (int i = 0; i < stops.size() - 1; i++) {
distance += stops.get(i).getLocation().distanceTo(stops.get(i + 1).getLocation());
}
return distance;
}
private int calculateTotalDemand() {
return stops.stream()
.mapToInt(RouteStop::getDemand)
.sum();
}
// Other calculation methods...
}
public class RouteStop {
private String jobId;
private Location location;
private int sequence;
private LocalTime arrivalTime;
private LocalTime departureTime;
private int demand;
private int serviceTime;
// constructors, getters, setters
}
public class RoutingSolution {
private List<Route> routes;
private List<Job> unassignedJobs;
private double totalCost;
private double totalDistance;
private int totalVehiclesUsed;
private OptimizationMetrics metrics;
// constructors, getters, setters
}
public class OptimizationMetrics {
private double totalCost;
private double totalDistance;
private double totalTime;
private int vehiclesUsed;
private int jobsAssigned;
private int totalJobs;
private double utilizationRate;
private LocalDateTime calculationTime;
private Duration computationDuration;
// constructors, getters, setters
}

Distance Matrix Service

1. Distance Calculator
@Service
public class DistanceCalculatorService {
private static final Logger logger = LoggerFactory.getLogger(DistanceCalculatorService.class);
/**
* Calculate distance matrix using Haversine formula
*/
public double[][] calculateDistanceMatrix(List<Location> locations) {
int size = locations.size();
double[][] matrix = new double[size][size];
for (int i = 0; i < size; i++) {
for (int j = 0; j < size; j++) {
if (i == j) {
matrix[i][j] = 0;
} else {
matrix[i][j] = locations.get(i).distanceTo(locations.get(j));
}
}
}
return matrix;
}
/**
* Calculate time matrix based on distance and average speed
*/
public double[][] calculateTimeMatrix(double[][] distanceMatrix, double averageSpeedKmH) {
int size = distanceMatrix.length;
double[][] timeMatrix = new double[size][size];
for (int i = 0; i < size; i++) {
for (int j = 0; j < size; j++) {
timeMatrix[i][j] = (distanceMatrix[i][j] / averageSpeedKmH) * 60; // Convert to minutes
}
}
return timeMatrix;
}
/**
* Calculate actual travel time using GraphHopper (requires OSM data)
*/
public double[][] calculateRealTimeMatrix(List<Location> locations, String graphHopperConfig) {
// Implementation using GraphHopper for real routing
// This would require OSM data and GraphHopper setup
int size = locations.size();
double[][] timeMatrix = new double[size][size];
// Simplified implementation - in practice, you'd use GraphHopper API
for (int i = 0; i < size; i++) {
for (int j = 0; j < size; j++) {
if (i == j) {
timeMatrix[i][j] = 0;
} else {
// Estimate based on distance and typical urban speed
double distance = locations.get(i).distanceTo(locations.get(j));
timeMatrix[i][j] = estimateTravelTime(distance);
}
}
}
return timeMatrix;
}
private double estimateTravelTime(double distanceKm) {
// Simple estimation: 25 km/h average in urban areas
double averageSpeedKmH = 25.0;
return (distanceKm / averageSpeedKmH) * 60; // minutes
}
}
2. Cached Distance Service
@Service
public class CachedDistanceService {
private final DistanceCalculatorService distanceCalculator;
private final Map<String, double[][]> distanceMatrixCache = new ConcurrentHashMap<>();
private final Map<String, double[][]> timeMatrixCache = new ConcurrentHashMap<>();
public CachedDistanceService(DistanceCalculatorService distanceCalculator) {
this.distanceCalculator = distanceCalculator;
}
public double[][] getDistanceMatrix(List<Location> locations) {
String cacheKey = generateCacheKey(locations);
return distanceMatrixCache.computeIfAbsent(cacheKey, key -> 
distanceCalculator.calculateDistanceMatrix(locations)
);
}
public double[][] getTimeMatrix(List<Location> locations, double averageSpeed) {
String cacheKey = generateCacheKey(locations) + "_speed_" + averageSpeed;
return timeMatrixCache.computeIfAbsent(cacheKey, key -> {
double[][] distanceMatrix = getDistanceMatrix(locations);
return distanceCalculator.calculateTimeMatrix(distanceMatrix, averageSpeed);
});
}
private String generateCacheKey(List<Location> locations) {
return locations.stream()
.map(loc -> loc.getId() + ":" + loc.getLatitude() + ":" + loc.getLongitude())
.sorted()
.collect(Collectors.joining("|"));
}
public void clearCache() {
distanceMatrixCache.clear();
timeMatrixCache.clear();
}
}

Route Optimization Algorithms

1. Nearest Neighbor Algorithm
@Service
public class NearestNeighborOptimizer {
private static final Logger logger = LoggerFactory.getLogger(NearestNeighborOptimizer.class);
/**
* Simple Nearest Neighbor algorithm for TSP
*/
public List<Location> solveTSP(Location start, List<Location> locations) {
List<Location> tour = new ArrayList<>();
Set<Location> unvisited = new HashSet<>(locations);
Location current = start;
tour.add(current);
while (!unvisited.isEmpty()) {
Location nearest = findNearestLocation(current, unvisited);
if (nearest != null) {
tour.add(nearest);
unvisited.remove(nearest);
current = nearest;
}
}
// Return to start
tour.add(start);
return tour;
}
/**
* Multi-vehicle routing with capacity constraints
*/
public List<Route> solveVRP(List<Vehicle> vehicles, List<Job> jobs, 
double[][] distanceMatrix, Map<String, Integer> locationIndex) {
List<Route> routes = new ArrayList<>();
List<Job> unassignedJobs = new ArrayList<>(jobs);
// Initialize routes
for (Vehicle vehicle : vehicles) {
routes.add(new Route(vehicle.getId()));
}
// Assign jobs to vehicles using nearest neighbor
while (!unassignedJobs.isEmpty()) {
boolean assigned = false;
for (Route route : routes) {
if (unassignedJobs.isEmpty()) break;
Vehicle vehicle = findVehicle(route.getVehicleId(), vehicles);
if (vehicle == null) continue;
Job nearestJob = findNearestJob(route, unassignedJobs, vehicle, 
distanceMatrix, locationIndex);
if (nearestJob != null && canAssignJob(route, nearestJob, vehicle)) {
RouteStop stop = createRouteStop(nearestJob, route.getStops().size());
route.addStop(stop);
unassignedJobs.remove(nearestJob);
assigned = true;
}
}
if (!assigned) {
// No more jobs can be assigned
break;
}
}
return routes;
}
private Location findNearestLocation(Location current, Set<Location> candidates) {
Location nearest = null;
double minDistance = Double.MAX_VALUE;
for (Location candidate : candidates) {
double distance = current.distanceTo(candidate);
if (distance < minDistance) {
minDistance = distance;
nearest = candidate;
}
}
return nearest;
}
private Job findNearestJob(Route route, List<Job> jobs, Vehicle vehicle, 
double[][] distanceMatrix, Map<String, Integer> locationIndex) {
Job nearest = null;
double minDistance = Double.MAX_VALUE;
Location lastLocation = getLastLocation(route, vehicle);
for (Job job : jobs) {
if (!hasRequiredSkills(vehicle, job)) continue;
int fromIndex = locationIndex.get(lastLocation.getId());
int toIndex = locationIndex.get(job.getLocation().getId());
double distance = distanceMatrix[fromIndex][toIndex];
if (distance < minDistance) {
minDistance = distance;
nearest = job;
}
}
return nearest;
}
private boolean canAssignJob(Route route, Job job, Vehicle vehicle) {
// Check capacity constraints
int totalDemand = route.getTotalDemand() + job.getDemand();
if (totalDemand > vehicle.getCapacity()) {
return false;
}
// Check time window constraints (simplified)
// In practice, you'd need to calculate actual arrival times
return true;
}
// Helper methods...
private Location getLastLocation(Route route, Vehicle vehicle) {
if (route.getStops().isEmpty()) {
return vehicle.getStartLocation();
}
return route.getStops().get(route.getStops().size() - 1).getLocation();
}
private boolean hasRequiredSkills(Vehicle vehicle, Job job) {
if (job.getRequiredSkills() == null || job.getRequiredSkills().isEmpty()) {
return true;
}
// Simplified skill matching
return true;
}
private Vehicle findVehicle(String vehicleId, List<Vehicle> vehicles) {
return vehicles.stream()
.filter(v -> v.getId().equals(vehicleId))
.findFirst()
.orElse(null);
}
private RouteStop createRouteStop(Job job, int sequence) {
RouteStop stop = new RouteStop();
stop.setJobId(job.getId());
stop.setLocation(job.getLocation());
stop.setSequence(sequence);
stop.setDemand(job.getDemand());
stop.setServiceTime(job.getServiceTime());
return stop;
}
}
2. jsprit Integration
@Service
public class JspritOptimizer {
private static final Logger logger = LoggerFactory.getLogger(JspritOptimizer.class);
/**
* Solve Vehicle Routing Problem using jsprit
*/
public RoutingSolution solveVRP(RoutingProblem problem) {
try {
// Build vehicle routing problem
VehicleRoutingProblem.Builder vrpBuilder = VehicleRoutingProblem.Builder.newInstance();
// Add vehicles
for (Vehicle vehicle : problem.getVehicles()) {
VehicleType vehicleType = createVehicleType(vehicle);
com.graphhopper.jsprit.core.problem.vehicle.Vehicle jspritVehicle = 
createJspritVehicle(vehicle, vehicleType);
vrpBuilder.addVehicle(jspritVehicle);
}
// Add jobs (services)
for (Job job : problem.getJobs()) {
Service service = createService(job);
vrpBuilder.addJob(service);
}
// Set distance matrix
if (problem.getDistanceMatrix() != null) {
vrpBuilder.setRoutingCost(new MatrixRoutingCost(problem.getDistanceMatrix(), 
problem.getLocationIndex()));
}
VehicleRoutingProblem vrp = vrpBuilder.build();
// Configure and run solver
VehicleRoutingAlgorithm algorithm = createAlgorithm(vrp);
Collection<VehicleRoutingProblemSolution> solutions = algorithm.searchSolutions();
// Get best solution
VehicleRoutingProblemSolution bestSolution = Solutions.bestOf(solutions);
// Convert to our domain model
return convertToRoutingSolution(bestSolution, vrp, problem);
} catch (Exception e) {
logger.error("Jsprit optimization failed", e);
throw new OptimizationException("Failed to solve routing problem", e);
}
}
private VehicleType createVehicleType(Vehicle vehicle) {
return VehicleTypeImpl.Builder.newInstance(vehicle.getId() + "-type")
.addCapacityDimension(0, vehicle.getCapacity())
.setCostPerDistance(vehicle.getCostPerKm())
.setFixedCost(vehicle.getFixedCost())
.build();
}
private com.graphhopper.jsprit.core.problem.vehicle.Vehicle createJspritVehicle(
Vehicle vehicle, VehicleType vehicleType) {
return VehicleImpl.Builder.newInstance(vehicle.getId())
.setStartLocation(Location.newInstance(
vehicle.getStartLocation().getLatitude(), 
vehicle.getStartLocation().getLongitude()))
.setEndLocation(Location.newInstance(
vehicle.getEndLocation().getLatitude(), 
vehicle.getEndLocation().getLongitude()))
.setType(vehicleType)
.build();
}
private Service createService(Job job) {
Service.Builder serviceBuilder = Service.Builder.newInstance(job.getId())
.addSizeDimension(0, job.getDemand())
.setLocation(Location.newInstance(
job.getLocation().getLatitude(), 
job.getLocation().getLongitude()));
if (job.getServiceTime() > 0) {
serviceBuilder.setServiceTime(job.getServiceTime());
}
return serviceBuilder.build();
}
private VehicleRoutingAlgorithm createAlgorithm(VehicleRoutingProblem vrp) {
VehicleRoutingAlgorithmBuilder algorithmBuilder = 
new VehicleRoutingAlgorithmBuilder(vrp, "algorithm-config.xml");
return algorithmBuilder.build();
}
private RoutingSolution convertToRoutingSolution(
VehicleRoutingProblemSolution jspritSolution,
VehicleRoutingProblem vrp,
RoutingProblem problem) {
RoutingSolution solution = new RoutingSolution();
List<Route> routes = new ArrayList<>();
for (VehicleRoute jspritRoute : jspritSolution.getRoutes()) {
Route route = convertJspritRoute(jspritRoute, vrp);
routes.add(route);
}
solution.setRoutes(routes);
solution.setTotalCost(jspritSolution.getCost());
solution.setMetrics(calculateMetrics(solution, problem));
return solution;
}
private Route convertJspritRoute(VehicleRoute jspritRoute, VehicleRoutingProblem vrp) {
Route route = new Route(jspritRoute.getVehicle().getId());
for (TourActivity activity : jspritRoute.getActivities()) {
if (activity instanceof ServiceActivity) {
RouteStop stop = convertActivityToStop((ServiceActivity) activity, vrp);
route.addStop(stop);
}
}
return route;
}
private RouteStop convertActivityToStop(ServiceActivity activity, VehicleRoutingProblem vrp) {
RouteStop stop = new RouteStop();
stop.setJobId(activity.getJob().getId());
// Set other properties...
return stop;
}
private OptimizationMetrics calculateMetrics(RoutingSolution solution, RoutingProblem problem) {
OptimizationMetrics metrics = new OptimizationMetrics();
metrics.setTotalCost(solution.getTotalCost());
metrics.setVehiclesUsed(solution.getRoutes().size());
metrics.setTotalJobs(problem.getJobs().size());
metrics.setJobsAssigned(calculateAssignedJobs(solution));
metrics.setCalculationTime(LocalDateTime.now());
return metrics;
}
private int calculateAssignedJobs(RoutingSolution solution) {
return solution.getRoutes().stream()
.mapToInt(route -> route.getStops().size())
.sum();
}
}
// Custom routing cost implementation for jsprit
class MatrixRoutingCost implements VehicleRoutingTransportCosts {
private final double[][] distanceMatrix;
private final Map<String, Integer> locationIndex;
public MatrixRoutingCost(double[][] distanceMatrix, Map<String, Integer> locationIndex) {
this.distanceMatrix = distanceMatrix;
this.locationIndex = locationIndex;
}
@Override
public double getTransportCost(Location from, Location to, double departureTime, 
Driver driver, Vehicle vehicle) {
int fromIdx = locationIndex.get(from.getId());
int toIdx = locationIndex.get(to.getId());
return distanceMatrix[fromIdx][toIdx];
}
@Override
public double getTransportTime(Location from, Location to, double departureTime, 
Driver driver, Vehicle vehicle) {
// Estimate transport time based on distance
int fromIdx = locationIndex.get(from.getId());
int toIdx = locationIndex.get(to.getId());
double distance = distanceMatrix[fromIdx][toIdx];
return (distance / 50.0) * 60; // Assume 50 km/h average speed
}
// Other required methods...
@Override public double getDistance(Location from, Location to, double departureTime, Vehicle vehicle) {
int fromIdx = locationIndex.get(from.getId());
int toIdx = locationIndex.get(to.getId());
return distanceMatrix[fromIdx][toIdx];
}
@Override public TransportTime getTransportTime() { return null; }
@Override public List<Location> getLocationIds() { return null; }
}
3. Genetic Algorithm Implementation
@Service
public class GeneticAlgorithmOptimizer {
private static final Logger logger = LoggerFactory.getLogger(GeneticAlgorithmOptimizer.class);
private static final int POPULATION_SIZE = 100;
private static final int GENERATIONS = 1000;
private static final double MUTATION_RATE = 0.01;
private static final double CROSSOVER_RATE = 0.8;
private static final int TOURNAMENT_SIZE = 5;
/**
* Solve TSP using Genetic Algorithm
*/
public List<Location> solveTSP(Location start, List<Location> locations, 
double[][] distanceMatrix) {
List<Chromosome> population = initializePopulation(start, locations, POPULATION_SIZE);
for (int generation = 0; generation < GENERATIONS; generation++) {
population = evolvePopulation(population, distanceMatrix);
if (generation % 100 == 0) {
Chromosome best = getBestChromosome(population, distanceMatrix);
logger.debug("Generation {}: Best fitness = {}", generation, 
1.0 / best.calculateFitness(distanceMatrix));
}
}
Chromosome bestSolution = getBestChromosome(population, distanceMatrix);
return bestSolution.getLocations();
}
private List<Chromosome> initializePopulation(Location start, List<Location> locations, 
int populationSize) {
List<Chromosome> population = new ArrayList<>();
for (int i = 0; i < populationSize; i++) {
List<Location> shuffled = new ArrayList<>(locations);
Collections.shuffle(shuffled);
// Always start with the starting location
List<Location> tour = new ArrayList<>();
tour.add(start);
tour.addAll(shuffled);
tour.add(start); // Return to start
population.add(new Chromosome(tour));
}
return population;
}
private List<Chromosome> evolvePopulation(List<Chromosome> population, 
double[][] distanceMatrix) {
List<Chromosome> newPopulation = new ArrayList<>();
// Elitism: keep the best chromosome
newPopulation.add(getBestChromosome(population, distanceMatrix));
// Create rest of population
while (newPopulation.size() < population.size()) {
Chromosome parent1 = tournamentSelection(population, distanceMatrix);
Chromosome parent2 = tournamentSelection(population, distanceMatrix);
Chromosome offspring;
if (Math.random() < CROSSOVER_RATE) {
offspring = crossover(parent1, parent2);
} else {
offspring = new Chromosome(parent1.getLocations());
}
if (Math.random() < MUTATION_RATE) {
mutate(offspring);
}
newPopulation.add(offspring);
}
return newPopulation;
}
private Chromosome tournamentSelection(List<Chromosome> population, 
double[][] distanceMatrix) {
Chromosome best = null;
for (int i = 0; i < TOURNAMENT_SIZE; i++) {
Chromosome candidate = population.get((int) (Math.random() * population.size()));
if (best == null || candidate.calculateFitness(distanceMatrix) > 
best.calculateFitness(distanceMatrix)) {
best = candidate;
}
}
return best;
}
private Chromosome crossover(Chromosome parent1, Chromosome parent2) {
// Ordered crossover (OX)
List<Location> parent1Tour = parent1.getLocations();
List<Location> parent2Tour = parent2.getLocations();
int size = parent1Tour.size();
int startPos = (int) (Math.random() * size);
int endPos = (int) (Math.random() * size);
if (startPos > endPos) {
int temp = startPos;
startPos = endPos;
endPos = temp;
}
List<Location> childTour = new ArrayList<>(Collections.nCopies(size, null));
// Copy segment from parent1
for (int i = startPos; i <= endPos; i++) {
childTour.set(i, parent1Tour.get(i));
}
// Fill remaining positions from parent2
int currentIndex = (endPos + 1) % size;
for (Location gene : parent2Tour) {
if (!childTour.contains(gene)) {
childTour.set(currentIndex, gene);
currentIndex = (currentIndex + 1) % size;
}
}
return new Chromosome(childTour);
}
private void mutate(Chromosome chromosome) {
// Swap mutation
List<Location> tour = chromosome.getLocations();
int index1 = (int) (Math.random() * (tour.size() - 2)) + 1; // Avoid swapping start/end
int index2 = (int) (Math.random() * (tour.size() - 2)) + 1;
Collections.swap(tour, index1, index2);
}
private Chromosome getBestChromosome(List<Chromosome> population, 
double[][] distanceMatrix) {
return population.stream()
.max(Comparator.comparingDouble(ch -> ch.calculateFitness(distanceMatrix)))
.orElseThrow();
}
}
class Chromosome {
private List<Location> locations;
public Chromosome(List<Location> locations) {
this.locations = new ArrayList<>(locations);
}
public double calculateFitness(double[][] distanceMatrix) {
double totalDistance = calculateTotalDistance(distanceMatrix);
return 1.0 / totalDistance; // Fitness is inverse of distance
}
public double calculateTotalDistance(double[][] distanceMatrix) {
double totalDistance = 0;
Map<String, Integer> locationIndex = createLocationIndex();
for (int i = 0; i < locations.size() - 1; i++) {
String fromId = locations.get(i).getId();
String toId = locations.get(i + 1).getId();
int fromIndex = locationIndex.get(fromId);
int toIndex = locationIndex.get(toId);
totalDistance += distanceMatrix[fromIndex][toIndex];
}
return totalDistance;
}
private Map<String, Integer> createLocationIndex() {
Map<String, Integer> index = new HashMap<>();
for (int i = 0; i < locations.size(); i++) {
index.put(locations.get(i).getId(), i);
}
return index;
}
// Getters
public List<Location> getLocations() { return locations; }
}

Route Optimization Service

1. Main Optimization Service
@Service
public class RouteOptimizationService {
private static final Logger logger = LoggerFactory.getLogger(RouteOptimizationService.class);
private final NearestNeighborOptimizer nearestNeighborOptimizer;
private final JspritOptimizer jspritOptimizer;
private final GeneticAlgorithmOptimizer geneticAlgorithmOptimizer;
private final CachedDistanceService distanceService;
public RouteOptimizationService(NearestNeighborOptimizer nearestNeighborOptimizer,
JspritOptimizer jspritOptimizer,
GeneticAlgorithmOptimizer geneticAlgorithmOptimizer,
CachedDistanceService distanceService) {
this.nearestNeighborOptimizer = nearestNeighborOptimizer;
this.jspritOptimizer = jspritOptimizer;
this.geneticAlgorithmOptimizer = geneticAlgorithmOptimizer;
this.distanceService = distanceService;
}
/**
* Optimize routes based on problem type and constraints
*/
public RoutingSolution optimizeRoutes(RoutingRequest request) {
logger.info("Starting route optimization for {} vehicles and {} jobs", 
request.getVehicles().size(), request.getJobs().size());
long startTime = System.currentTimeMillis();
try {
// Prepare data
List<Location> allLocations = collectAllLocations(request);
double[][] distanceMatrix = distanceService.getDistanceMatrix(allLocations);
Map<String, Integer> locationIndex = createLocationIndex(allLocations);
RoutingProblem problem = new RoutingProblem(request, distanceMatrix, locationIndex);
// Choose solver based on problem size and constraints
RoutingSolution solution = selectAndRunSolver(problem, request.getOptimizationStrategy());
// Calculate metrics
solution.setMetrics(calculateDetailedMetrics(solution, problem, startTime));
logger.info("Route optimization completed in {} ms", 
System.currentTimeMillis() - startTime);
return solution;
} catch (Exception e) {
logger.error("Route optimization failed", e);
throw new OptimizationException("Failed to optimize routes", e);
}
}
/**
* Compare different optimization algorithms
*/
public OptimizationComparison compareAlgorithms(RoutingRequest request) {
List<Location> allLocations = collectAllLocations(request);
double[][] distanceMatrix = distanceService.getDistanceMatrix(allLocations);
Map<String, Integer> locationIndex = createLocationIndex(allLocations);
RoutingProblem problem = new RoutingProblem(request, distanceMatrix, locationIndex);
List<AlgorithmResult> results = new ArrayList<>();
// Test Nearest Neighbor
results.add(testAlgorithm("NEAREST_NEIGHBOR", problem, 
() -> nearestNeighborOptimizer.solveVRP(
problem.getVehicles(), problem.getJobs(), distanceMatrix, locationIndex)));
// Test jsprit
results.add(testAlgorithm("JSPRIT", problem, 
() -> jspritOptimizer.solveVRP(problem)));
// Test Genetic Algorithm for TSP
if (problem.getVehicles().size() == 1) {
Vehicle vehicle = problem.getVehicles().get(0);
List<Location> locations = problem.getJobs().stream()
.map(Job::getLocation)
.collect(Collectors.toList());
results.add(testTSPAlgorithm("GENETIC_ALGORITHM", vehicle.getStartLocation(), 
locations, distanceMatrix));
}
return new OptimizationComparison(results);
}
private RoutingSolution selectAndRunSolver(RoutingProblem problem, OptimizationStrategy strategy) {
switch (strategy) {
case FAST:
return solveWithNearestNeighbor(problem);
case BALANCED:
return jspritOptimizer.solveVRP(problem);
case THOROUGH:
return solveWithGeneticAlgorithm(problem);
default:
return jspritOptimizer.solveVRP(problem);
}
}
private RoutingSolution solveWithNearestNeighbor(RoutingProblem problem) {
List<Route> routes = nearestNeighborOptimizer.solveVRP(
problem.getVehicles(), problem.getJobs(), 
problem.getDistanceMatrix(), problem.getLocationIndex());
RoutingSolution solution = new RoutingSolution();
solution.setRoutes(routes);
solution.setTotalCost(calculateTotalCost(routes));
return solution;
}
private RoutingSolution solveWithGeneticAlgorithm(RoutingProblem problem) {
if (problem.getVehicles().size() != 1) {
logger.warn("Genetic algorithm currently supports single vehicle only, using jsprit instead");
return jspritOptimizer.solveVRP(problem);
}
Vehicle vehicle = problem.getVehicles().get(0);
List<Location> locations = problem.getJobs().stream()
.map(Job::getLocation)
.collect(Collectors.toList());
List<Location> optimizedTour = geneticAlgorithmOptimizer.solveTSP(
vehicle.getStartLocation(), locations, problem.getDistanceMatrix());
// Convert to route
Route route = new Route(vehicle.getId());
for (int i = 1; i < optimizedTour.size() - 1; i++) { // Skip start and end (same)
Location location = optimizedTour.get(i);
Job job = findJobByLocation(location, problem.getJobs());
if (job != null) {
RouteStop stop = createRouteStop(job, i - 1);
route.addStop(stop);
}
}
RoutingSolution solution = new RoutingSolution();
solution.setRoutes(List.of(route));
solution.setTotalCost(calculateTotalCost(List.of(route)));
return solution;
}
// Helper methods...
private List<Location> collectAllLocations(RoutingRequest request) {
List<Location> locations = new ArrayList<>();
// Add vehicle locations
for (Vehicle vehicle : request.getVehicles()) {
locations.add(vehicle.getStartLocation());
locations.add(vehicle.getEndLocation());
}
// Add job locations
for (Job job : request.getJobs()) {
locations.add(job.getLocation());
}
return locations.stream()
.distinct()
.collect(Collectors.toList());
}
private Map<String, Integer> createLocationIndex(List<Location> locations) {
Map<String, Integer> index = new HashMap<>();
for (int i = 0; i < locations.size(); i++) {
index.put(locations.get(i).getId(), i);
}
return index;
}
private OptimizationMetrics calculateDetailedMetrics(RoutingSolution solution, 
RoutingProblem problem, long startTime) {
OptimizationMetrics metrics = new OptimizationMetrics();
metrics.setTotalCost(solution.getTotalCost());
metrics.setTotalDistance(calculateTotalDistance(solution.getRoutes()));
metrics.setVehiclesUsed(solution.getRoutes().size());
metrics.setTotalJobs(problem.getJobs().size());
metrics.setJobsAssigned(calculateAssignedJobs(solution));
metrics.setUtilizationRate(calculateUtilizationRate(solution, problem));
metrics.setCalculationTime(LocalDateTime.now());
metrics.setComputationDuration(
Duration.ofMillis(System.currentTimeMillis() - startTime));
return metrics;
}
private double calculateTotalCost(List<Route> routes) {
return routes.stream()
.mapToDouble(Route::getTotalCost)
.sum();
}
private double calculateTotalDistance(List<Route> routes) {
return routes.stream()
.mapToDouble(Route::getTotalDistance)
.sum();
}
private int calculateAssignedJobs(RoutingSolution solution) {
return solution.getRoutes().stream()
.mapToInt(route -> route.getStops().size())
.sum();
}
private double calculateUtilizationRate(RoutingSolution solution, RoutingProblem problem) {
int totalCapacity = problem.getVehicles().stream()
.mapToInt(Vehicle::getCapacity)
.sum();
int totalAssignedDemand = solution.getRoutes().stream()
.mapToInt(Route::getTotalDemand)
.sum();
return totalCapacity > 0 ? (double) totalAssignedDemand / totalCapacity : 0;
}
private Job findJobByLocation(Location location, List<Job> jobs) {
return jobs.stream()
.filter(job -> job.getLocation().getId().equals(location.getId()))
.findFirst()
.orElse(null);
}
private AlgorithmResult testAlgorithm(String algorithmName, RoutingProblem problem, 
Supplier<RoutingSolution> solver) {
long startTime = System.currentTimeMillis();
try {
RoutingSolution solution = solver.get();
long duration = System.currentTimeMillis() - startTime;
AlgorithmResult result = new AlgorithmResult();
result.setAlgorithmName(algorithmName);
result.setSolution(solution);
result.setComputationTime(duration);
result.setSuccess(true);
return result;
} catch (Exception e) {
logger.error("Algorithm {} failed", algorithmName, e);
AlgorithmResult result = new AlgorithmResult();
result.setAlgorithmName(algorithmName);
result.setSuccess(false);
result.setErrorMessage(e.getMessage());
return result;
}
}
private AlgorithmResult testTSPAlgorithm(String algorithmName, Location start, 
List<Location> locations, double[][] distanceMatrix) {
long startTime = System.currentTimeMillis();
try {
List<Location> tour = geneticAlgorithmOptimizer.solveTSP(start, locations, distanceMatrix);
long duration = System.currentTimeMillis() - startTime;
// Calculate tour distance
double totalDistance = calculateTourDistance(tour, distanceMatrix);
AlgorithmResult result = new AlgorithmResult();
result.setAlgorithmName(algorithmName);
result.setComputationTime(duration);
result.setSuccess(true);
result.setAdditionalMetric("tourDistance", totalDistance);
return result;
} catch (Exception e) {
logger.error("TSP algorithm {} failed", algorithmName, e);
AlgorithmResult result = new AlgorithmResult();
result.setAlgorithmName(algorithmName);
result.setSuccess(false);
result.setErrorMessage(e.getMessage());
return result;
}
}
private double calculateTourDistance(List<Location> tour, double[][] distanceMatrix) {
double totalDistance = 0;
Map<String, Integer> locationIndex = createLocationIndex(tour);
for (int i = 0; i < tour.size() - 1; i++) {
String fromId = tour.get(i).getId();
String toId = tour.get(i + 1).getId();
int fromIndex = locationIndex.get(fromId);
int toIndex = locationIndex.get(toId);
totalDistance += distanceMatrix[fromIndex][toIndex];
}
return totalDistance;
}
}

REST Controllers

1. Route Optimization Controller
@RestController
@RequestMapping("/api/routing")
@Validated
public class RouteOptimizationController {
private final RouteOptimizationService optimizationService;
public RouteOptimizationController(RouteOptimizationService optimizationService) {
this.optimizationService = optimizationService;
}
@PostMapping("/optimize")
public ResponseEntity<RoutingSolution> optimizeRoutes(
@Valid @RequestBody RoutingRequest request) {
RoutingSolution solution = optimizationService.optimizeRoutes(request);
return ResponseEntity.ok(solution);
}
@PostMapping("/compare-algorithms")
public ResponseEntity<OptimizationComparison> compareAlgorithms(
@Valid @RequestBody RoutingRequest request) {
OptimizationComparison comparison = optimizationService.compareAlgorithms(request);
return ResponseEntity.ok(comparison);
}
@PostMapping("/tsp")
public ResponseEntity<List<Location>> solveTSP(
@Valid @RequestBody TSPRequest request) {
List<Location> tour = optimizationService.solveTSP(request);
return ResponseEntity.ok(tour);
}
}
2. Request/Response Models
public class RoutingRequest {
@NotEmpty
private List<Vehicle> vehicles;
@NotEmpty
private List<Job> jobs;
private OptimizationStrategy optimizationStrategy = OptimizationStrategy.BALANCED;
private RoutingConstraints constraints;
// constructors, getters, setters
}
public class TSPRequest {
@NotNull
private Location startLocation;
@NotEmpty
private List<Location> locations;
private TSPAlgorithm algorithm = TSPAlgorithm.GENETIC;
// constructors, getters, setters
}
public enum OptimizationStrategy {
FAST, BALANCED, THOROUGH
}
public enum TSPAlgorithm {
NEAREST_NEIGHBOR, GENETIC, ANT_COLONY
}
public class RoutingConstraints {
private boolean timeWindows = false;
private boolean capacityConstraints = true;
private boolean skillRequirements = false;
private int maxRouteDuration = 480; // minutes
private int maxStopsPerRoute = 20;
// constructors, getters, setters
}
public class OptimizationComparison {
private List<AlgorithmResult> results;
private AlgorithmResult bestResult;
// constructors, getters, setters
public OptimizationComparison(List<AlgorithmResult> results) {
this.results = results;
this.bestResult = findBestResult(results);
}
private AlgorithmResult findBestResult(List<AlgorithmResult> results) {
return results.stream()
.filter(AlgorithmResult::isSuccess)
.min(Comparator.comparingDouble(r -> r.getSolution().getTotalCost()))
.orElse(null);
}
}
public class AlgorithmResult {
private String algorithmName;
private RoutingSolution solution;
private long computationTime;
private boolean success;
private String errorMessage;
private Map<String, Object> additionalMetrics;
// constructors, getters, setters
}

Advanced Features

1. Real-time Route Updates
@Service
public class RealTimeRoutingService {
private static final Logger logger = LoggerFactory.getLogger(RealTimeRoutingService.class);
private final RouteOptimizationService optimizationService;
private final Map<String, ActiveRoute> activeRoutes = new ConcurrentHashMap<>();
/**
* Add new job to existing routes
*/
public RoutingSolution addJobToRoutes(String routeId, Job newJob) {
ActiveRoute activeRoute = activeRoutes.get(routeId);
if (activeRoute == null) {
throw new RouteNotFoundException("Active route not found: " + routeId);
}
// Create updated routing request
RoutingRequest updatedRequest = createUpdatedRequest(activeRoute, newJob);
// Re-optimize
RoutingSolution updatedSolution = optimizationService.optimizeRoutes(updatedRequest);
// Update active route
activeRoute.setSolution(updatedSolution);
activeRoute.setLastUpdated(LocalDateTime.now());
return updatedSolution;
}
/**
* Handle vehicle breakdown or delay
*/
public RoutingSolution handleVehicleIssue(String vehicleId, String issueType) {
// Find routes affected by the issue
List<ActiveRoute> affectedRoutes = findRoutesByVehicle(vehicleId);
// Reassign jobs from affected vehicle
List<Job> jobsToReassign = collectJobsFromVehicle(vehicleId, affectedRoutes);
// Create new routing request excluding the problematic vehicle
RoutingRequest reassignmentRequest = createReassignmentRequest(
jobsToReassign, affectedRoutes, vehicleId);
// Optimize with remaining vehicles
RoutingSolution newSolution = optimizationService.optimizeRoutes(reassignmentRequest);
// Update active routes
updateActiveRoutes(newSolution, affectedRoutes);
return newSolution;
}
// Helper methods...
private RoutingRequest createUpdatedRequest(ActiveRoute activeRoute, Job newJob) {
// Implementation for creating updated routing request
return new RoutingRequest();
}
private List<ActiveRoute> findRoutesByVehicle(String vehicleId) {
return activeRoutes.values().stream()
.filter(route -> route.getSolution().getRoutes().stream()
.anyMatch(r -> r.getVehicleId().equals(vehicleId)))
.collect(Collectors.toList());
}
private List<Job> collectJobsFromVehicle(String vehicleId, List<ActiveRoute> routes) {
List<Job> jobs = new ArrayList<>();
for (ActiveRoute activeRoute : routes) {
Route route = activeRoute.getSolution().getRoutes().stream()
.filter(r -> r.getVehicleId().equals(vehicleId))
.findFirst()
.orElse(null);
if (route != null) {
// Convert route stops back to jobs
List<Job> routeJobs = convertStopsToJobs(route.getStops());
jobs.addAll(routeJobs);
}
}
return jobs;
}
private List<Job> convertStopsToJobs(List<RouteStop> stops) {
return stops.stream()
.map(this::convertStopToJob)
.collect(Collectors.toList());
}
private Job convertStopToJob(RouteStop stop) {
Job job = new Job();
job.setId(stop.getJobId());
job.setLocation(stop.getLocation());
job.setDemand(stop.getDemand());
return job;
}
}
public class ActiveRoute {
private String id;
private RoutingSolution solution;
private LocalDateTime createdTime;
private LocalDateTime lastUpdated;
private RouteStatus status;
private List<RouteUpdate> updates;
// constructors, getters, setters
}
public enum RouteStatus {
PLANNED, ACTIVE, COMPLETED, CANCELLED
}
2. Route Visualization
@Service
public class RouteVisualizationService {
/**
* Generate GeoJSON for route visualization
*/
public String generateRouteGeoJson(RoutingSolution solution) {
JsonObject geoJson = new JsonObject();
geoJson.addProperty("type", "FeatureCollection");
JsonArray features = new JsonArray();
// Add routes as LineString features
for (Route route : solution.getRoutes()) {
JsonObject routeFeature = createRouteFeature(route);
features.add(routeFeature);
}
// Add stops as Point features
for (Route route : solution.getRoutes()) {
for (RouteStop stop : route.getStops()) {
JsonObject stopFeature = createStopFeature(stop, route.getVehicleId());
features.add(stopFeature);
}
}
geoJson.add("features", features);
return new Gson().toJson(geoJson);
}
private JsonObject createRouteFeature(Route route) {
JsonObject feature = new JsonObject();
feature.addProperty("type", "Feature");
// Geometry (LineString)
JsonObject geometry = new JsonObject();
geometry.addProperty("type", "LineString");
JsonArray coordinates = new JsonArray();
for (RouteStop stop : route.getStops()) {
JsonArray coord = new JsonArray();
coord.add(stop.getLocation().getLongitude());
coord.add(stop.getLocation().getLatitude());
coordinates.add(coord);
}
geometry.add("coordinates", coordinates);
feature.add("geometry", geometry);
// Properties
JsonObject properties = new JsonObject();
properties.addProperty("vehicleId", route.getVehicleId());
properties.addProperty("totalDistance", route.getTotalDistance());
properties.addProperty("totalTime", route.getTotalTime());
properties.addProperty("totalCost", route.getTotalCost());
feature.add("properties", properties);
return feature;
}
private JsonObject createStopFeature(RouteStop stop, String vehicleId) {
JsonObject feature = new JsonObject();
feature.addProperty("type", "Feature");
// Geometry (Point)
JsonObject geometry = new JsonObject();
geometry.addProperty("type", "Point");
JsonArray coordinates = new JsonArray();
coordinates.add(stop.getLocation().getLongitude());
coordinates.add(stop.getLocation().getLatitude());
geometry.add("coordinates", coordinates);
feature.add("geometry", geometry);
// Properties
JsonObject properties = new JsonObject();
properties.addProperty("jobId", stop.getJobId());
properties.addProperty("vehicleId", vehicleId);
properties.addProperty("sequence", stop.getSequence());
properties.addProperty("arrivalTime", stop.getArrivalTime().toString());
feature.add("properties", properties);
return feature;
}
}

Performance Monitoring

@Service
public class OptimizationMetricsService {
private final MeterRegistry meterRegistry;
private final Counter optimizationRequests;
private final Timer optimizationTimer;
private final DistributionSummary solutionQuality;
public OptimizationMetricsService(MeterRegistry meterRegistry) {
this.meterRegistry = meterRegistry;
this.optimizationRequests = meterRegistry.counter("routing.optimization.requests");
this.optimizationTimer = meterRegistry.timer("routing.optimization.duration");
this.solutionQuality = meterRegistry.summary("routing.solution.quality");
}
public void recordOptimization(RoutingSolution solution, long duration) {
optimizationRequests.increment();
optimizationTimer.record(duration, TimeUnit.MILLISECONDS);
if (solution != null && solution.getTotalCost() > 0) {
solutionQuality.record(solution.getTotalCost());
}
}
public OptimizationStats getOptimizationStats() {
OptimizationStats stats = new OptimizationStats();
stats.setTotalRequests(optimizationRequests.count());
stats.setAverageDuration(optimizationTimer.mean(TimeUnit.MILLISECONDS));
stats.setAverageCost(solutionQuality.mean());
return stats;
}
}
@Component
public class OptimizationHealthCheck {
@Scheduled(fixedRate = 300000) // 5 minutes
public void checkOptimizationPerformance() {
// Monitor optimization performance and alert if degradation detected
logger.debug("Optimization health check completed");
}
}

Best Practices

  1. Algorithm Selection: Choose algorithm based on problem size and constraints
  2. Distance Caching: Cache distance matrices to avoid recalculation
  3. Constraint Handling: Implement flexible constraint management
  4. Real-time Updates: Support dynamic route modifications
  5. Performance Monitoring: Track optimization metrics and quality
  6. Fallback Strategies: Have backup algorithms for different scenarios
@Component
public class OptimizationConfig {
@Bean
public VehicleRoutingAlgorithmBuilder algorithmBuilder() {
// Configure jsprit algorithm parameters
Properties properties = new Properties();
properties.setProperty("construction.sweep.considerFaces", "true");
properties.setProperty("ruin.random.probability", "0.1");
return VehicleRoutingAlgorithmBuilder.newInstance(properties);
}
}

Conclusion

This comprehensive route optimization implementation provides:

  • Multiple algorithm support (Nearest Neighbor, jsprit, Genetic Algorithm)
  • Flexible constraint handling (capacity, time windows, skills)
  • Real-time route updates and dynamic optimization
  • Performance monitoring and comparison tools
  • Visualization support for route analysis

The system can handle various routing scenarios from simple TSP problems to complex multi-vehicle routing with multiple constraints, making it suitable for delivery services, field service management, and logistics operations.

Category : JAVA

Leave a Reply

Your email address will not be published. Required fields are marked *


Macro Nepal Helper