How to model the Travelling Salesman problem, its constraints and solution using Opta Planner

Question

I have a requirement of finding the optimized route for a vehicle to dispatch the deliverable items.The optimized route should minimize the overall distance cost of the trip while ensuring the solution does not traverse the same path more than once. The maximum number of waypoints in the trip is 50. There is no time constraint for stopping at a waypoint. I was looking for a java library for my implementation and I found OptaPlanner to be a good choice. But, I have a hard time figuring out how to model my optimization problem, the constraints and its solution .

This is my problem entity modelling and other related Opta planner classes:

@PlanningEntity
@Entity
@Table(name = "trips")
@Getter
@Setter
@NoArgsConstructor
@AllArgsConstructor
@TypeDef(name = "jsonb", typeClass = JsonBinaryType.class)
public class Trips {

 
//Other fields

    @Column(name = "trip_total_distance")
    @PlanningVariable(valueRangeProviderRefs = "distanceRange")
    private Long tripTotalDistance;

    @Column(name = "trip_total_duration")
    @PlanningVariable(valueRangeProviderRefs = "durationRange")
    private Long tripTotalDuration;


    @Type(type = "jsonb")
    @Column(name = "trip_path_lat_lng_details", columnDefinition = "jsonb")
    private List<Coordinates> tripPathLatAndLngDetails;
  

    @OneToMany(targetEntity = Deliverable.class, cascade = CascadeType.ALL, fetch = FetchType.LAZY)
    @JoinColumn(name = "trip_id", referencedColumnName = "trip_id")
    private List<Deliverable> deliverables;




    // Custom value range providers for distance and duration
    @ValueRangeProvider(id="distanceRange")
    public CountableValueRange<Long> getDistanceRange(){
        // Set the upper bound for distance (180,000 meters)
        return ValueRangeFactory.createLongValueRange(0L, 180000L);
    }

    @ValueRangeProvider(id = "durationRange")
    public CountableValueRange<Long> getDurationRange(){
        // Set the upper bound for duration (21,600 seconds or 6 hours)
        return ValueRangeFactory.createLongValueRange(0L, 21600L);
    }
}



public abstract class Deliverable {

//Other fields
  
    @Column(name = "source_address")
    private String sourceAddress;
    @Column(name = "source_lat")
    private Double sourceLat;
    @Column(name = "source_lng")
    private Double sourceLng;
    @Column(name = "deliverable_address")
    private String deliverableAddress;
    @Column(name = "deliverable_lat")
    private Double deliverableLat;
    @Column(name = "deliverable_lng")
    private Double deliverableLng;
  

}



@Entity
@Table(name = "optimized_order")
@Getter
@Setter
@NoArgsConstructor
@PlanningEntity
public class OptimizedOrder {

  

    @OneToOne(fetch = FetchType.EAGER, cascade = CascadeType.ALL)
    @JoinColumn(name = "deliverable_id", referencedColumnName = "deliverable_id")
    private Deliverable deliverable;

    @OneToOne(fetch = FetchType.EAGER, cascade = CascadeType.ALL)
    @JoinColumn(name = "trips_id", referencedColumnName = "trip_id")
    private Trips trips;

    @Column(name = "sequence_id")
    @PlanningVariable(valueRangeProviderRefs = "dynamicSequenceIdRange")
    private Integer sequenceId;

    public OptimizedRoute(Trips trips, Deliverable deliverable, Integer sequenceId) {
        this.deliverable = deliverable;
        this.trips = trips;
        this.sequenceId = sequenceId;
    }

    @ValueRangeProvider(id = "dynamicSequenceIdRange")
    public List<Integer> getDynamicSequenceIdRange() {
        if (deliverable != null && trips.getDeliverables() != null) {
            int size = trips.getDeliverables().size();
            return IntStream.rangeClosed(0, size - 1).boxed().collect(Collectors.toList());
        } else {
            // Handle the case where the associated trip or deliverables are null
            return Collections.emptyList();
        }
    }

}





@Component
public class VehicleRoutingConstraintProvider implements ConstraintProvider {


    private final GeodesicDistanceCalculator distanceCalculationService = new GeodesicDistanceCalculator();
    

    @Override
    public Constraint[] defineConstraints(ConstraintFactory constraintFactory) {
        return new Constraint[]{
                totalDistance(constraintFactory),
                totalDuration(constraintFactory),
                visitAtleastOnce(constraintFactory),
                visitEachCoordinateUtmostOnce(constraintFactory),
                ensureProximityToTripSource(constraintFactory)
        };
    }

    protected Constraint visitEachCoordinateUtmostOnce(ConstraintFactory factory) {

        return factory.forEach(Trips.class)
                .penalizeLong(
                        HardSoftLongScore.ONE_HARD,
                        trip -> isCoordinateVisitedMoreThanOnce(distanceCalculationService.calculateBulkDistance(trip.getTripPathLatAndLngDetails(), trip.getTripPathLatAndLngDetails())))
                .asConstraint("visitEachCoordinateOnce");

    }
    
    protected Constraint visitAtleastOnce(ConstraintFactory factory){
        return factory.forEach(Trips.class)
                .penalizeLong(HardSoftLongScore.ONE_HARD,
                        trip-> hasUnvisitedCoordinate(distanceCalculationService.calculateBulkDistance(trip.getTripPathLatAndLngDetails(), trip.getTripPathLatAndLngDetails())))
                                .asConstraint("visitAtleastOnce");
    }

    protected Constraint ensureProximityToTripSource(ConstraintFactory factory){
        return factory.forEach(Trips.class)
                .join(Coordinates.class)
                .penalizeLong(HardSoftLongScore.ONE_HARD,
                        (trip, coordinates)->  isProximalToTripSource(trip,coordinates))
                .asConstraint("penalizeFartherFromWarehouse");

    }

    public Long isProximalToTripSource(Trips trips, Coordinates coordinates){

        List<Coordinates> tripPath = trips.getTripPathLatAndLngDetails();
        if (trips.getTripPathLatAndLngDetails().isEmpty()) {
            // No coordinates, penalize the constraint
            return -1L;
        }

        Coordinates tripSourceLocation = new Coordinates(trips.getSourceLat(), trips.getSourceLng());
        long maxDistance = 0L;


        for (Coordinates currentCoordinate : tripPath) {
            // Skip the currentCoordinate if it is the trip start location coordinate
            if (currentCoordinate.equals(tripSourceLocation)) {
                continue;
            }

            // Use your distance calculation method to get the distance between currentCoordinate and tripSourceLocation
            long distance = currentCoordinate.getDistanceTo(tripSourceLocation);
            // Update maxDistance if the current distance is greater
            maxDistance = Math.max(maxDistance, distance);
        }

        return maxDistance;
    }

    private Long isCoordinateVisitedMoreThanOnce(Map<Coordinates, Map<Coordinates, Long>> distanceMatrix) {
        // Collect all visited coordinates in a set
        Set<Coordinates> visitedCoordinates = new HashSet<>();

        for (Coordinates sourceCoordinate : distanceMatrix.keySet()) {
            Map<Coordinates, Long> destinationDistances = distanceMatrix.get(sourceCoordinate);

            // Iterate over the destination coordinates in the distance matrix
            for (Coordinates destinationCoordinate : destinationDistances.keySet()) {
                // Implement logic to check if the destination coordinate is already visited
                if (!visitedCoordinates.add(destinationCoordinate)) {
                    // If it's already in the set, it means it's visited more than once
                    return 1L;
                }
            }
        }

        return 0L; // The coordinate is visited at most once
    }

    private long hasUnvisitedCoordinate(Map<Coordinates, Map<Coordinates, Long>> distanceMatrix) {
        // Implement logic to check if there is any unvisited coordinate
        // Return 1L if there is any unvisited coordinate, 0L otherwise
        // You need to check that each coordinate is visited at least once
        // For simplicity, let's assume you have a method isCoordinateVisited(Map<Coordinates, Map<Coordinates, Long>> distanceMatrix, Coordinates coordinate)
        // to check if a coordinate is visited
        for (Coordinates coordinate : distanceMatrix.keySet()) {
            if (!isCoordinateVisited(distanceMatrix, coordinate)) {
                return 1L; // There is an unvisited coordinate
            }
        }

        return 0L; // All coordinates are visited at least once
    }

    private boolean isCoordinateVisited(Map<Coordinates, Map<Coordinates, Long>> distanceMatrix, Coordinates coordinate) {
        // Implement logic to check if the coordinate is visited
        // You can use the distanceMatrix to determine if the coordinate is visited
        // For example, check if there is any non-null distance value for the coordinate in the matrix
        // Return true if visited, false otherwise
        // This logic depends on how your distanceMatrix represents visited coordinates
        // For simplicity, let's assume the presence of a distance value indicates the coordinate is visited
        return distanceMatrix.values().stream()
                .anyMatch(destinationDistances -> destinationDistances.containsKey(coordinate) && destinationDistances.get(coordinate) != null);
    }


    // Soft constraint to penalize larger total distance
    protected Constraint totalDistance(ConstraintFactory factory) {
        return factory.forEach(Trips.class)
                .penalizeLong(HardSoftLongScore.ONE_SOFT,
                        Trips::getTripTotalDistance)
                .asConstraint("penalizeGreaterTotalDistance");
    }

    // Soft constraint to penalize larger total duration
    protected Constraint totalDuration(ConstraintFactory factory) {
        return factory.forEach(Trips.class)
                .penalizeLong(HardSoftLongScore.ONE_SOFT,
                        Trips::getTripTotalDuration)
                .asConstraint("penalizeGreaterTotalDuration");
    }

}



@Configuration
public class OptaPlannerConfiguration {

    @Autowired
    private VehicleRoutingConstraintProvider constraintProvider;

    @Bean
    public SolverConfig solverConfig() {
        SolverConfig solverConfig = new SolverConfig();

        // Set construction heuristic type
        ConstructionHeuristicPhaseConfig constructionHeuristicPhaseConfig = new ConstructionHeuristicPhaseConfig();
        constructionHeuristicPhaseConfig.setConstructionHeuristicType(ConstructionHeuristicType.FIRST_FIT);
        solverConfig.setPhaseConfigList(Collections.singletonList(constructionHeuristicPhaseConfig));

        // Set local search type
        LocalSearchPhaseConfig localSearchPhaseConfig = new LocalSearchPhaseConfig();
        localSearchPhaseConfig.setLocalSearchType(LocalSearchType.HILL_CLIMBING);


        solverConfig.setPhaseConfigList(Collections.singletonList(localSearchPhaseConfig));

        // Solver termination conditions
        // Set forager type and accepted count limit
        TerminationConfig terminationConfig = new TerminationConfig();
        terminationConfig.setSecondsSpentLimit(30L);
        solverConfig.setTerminationConfig(terminationConfig);

        // Optimization algorithms and constraints
        ScoreDirectorFactoryConfig scoreDirectorFactoryConfig = new ScoreDirectorFactoryConfig();
        scoreDirectorFactoryConfig.setConstraintProviderClass(constraintProvider.getClass());
        solverConfig.setScoreDirectorFactoryConfig(scoreDirectorFactoryConfig);

        // Planning entities and problem facts
        solverConfig.setSolutionClass(VehicleRoutingSolution.class);
        solverConfig.setEntityClassList(Arrays.asList(Trips.class, OptimizedRoute.class));

        return solverConfig;
    }

    @Bean
    public SolverManager<VehicleRoutingSolution, Long> solverManager() {
        return SolverManager.create(solverConfig(), new SolverManagerConfig());
    }

}

Ideally, what I want from the solution instance is to return me the optimized route's total distance, duration and more importantly the optimized waypoint order.The sequenceId is the field that capture the priority of the particular deliverable for the trip (0 being the top priority).

I tried modelling my entities according to OptaPlanner based on my understanding of Optaplanner. But I could not make it working and I can't figure out the right way.