CODEWITHSUNDEEP
optaplanner
Gloria Leyva
Gloria Leyva

Reputation: 61

Using OptaPlanner to solve a Vehicle Routing Problem with Capacities

Hello to all optaplanners. I am a novice in the use of optaplanner and here I have some questions about planning vehicle routes with dimensioned capacities in weight and volume. Thank you for your help, I appreciate any suggestions.

I am implementing a VRP with capacities but require that the capacity be dimensioned in weight and volume. The path I have followed is to take the example of optaplanner and refactor the vehicle capacity in volume and weight, and the demand of the visit also in weight and volume. Then I modified the Constraint Provider that worked the capacities with quantities, to work with weight and then I implemented another Constraint Provider very similar but to work with volume. From now on I will also require other dimensions for the capacity of the vehicle and the load of the visitors (customer).

1- As I am a novice, I would like to know if my suppositions are correct, if I am on the right road?

2- I would like to know if it is right to work with a Constraint Provider for each dimension, or if I should join in a single Constraint Provider all the calculations for Weight and Volume or other. If possible, how can I do it?

3- If I have a vehicle with only a capacity in weight and another vehicle with only a capacity in volume, but I have visits (customer) whose demands require covering a weight and at the same time a volume, therefore I will never obtain a feasible route, since only one vehicle passes through the same visit. How can I solve this problem?

4- How can I manage that when the demands of the visits (customer) exceed the capacity of the vehicle, the vehicle makes more trips to the same visit until it covers the total demand of the visit (customer)?

Here I share my modifications for a better context. Thanks!

Refactored the vehicle capacity:

public class PlanningVehicle implements Standstill {

@PlanningId
private long id;
private int weightCapacity;
private int volumeCapacity;
...
}

Refactored the demand of the visit:

@PlanningEntity(difficultyWeightFactoryClass = DepotAngleVisitDifficultyWeightFactory.class)
public class PlanningVisit implements Standstill {

    @PlanningId
    private long id;
    private PlanningLocation location;
    private int weightDemand;
    private int volumeDemand;
    ...
}

I implemented two Hard Scores, one for each dimension (weight and volume):

@ConstraintConfiguration(constraintPackage = "com.router.solver")
public class VehicleRoutingConstraintConfiguration {
     ...    
   public static final String VEHICLE_WEIGHT_CAPACITY = "Vehicle capacity in weight";
   public static final String VEHICLE_VOLUME_CAPACITY = "Vehicle capacity in volume";
     ...
   @ConstraintWeight(VEHICLE_WEIGHT_CAPACITY)
   private HardSoftLongScore vehicleWeightCapacity = HardSoftLongScore.ONE_HARD;
   @ConstraintWeight(VEHICLE_VOLUME_CAPACITY)
   private HardSoftLongScore vehicleVolumeCapacity = HardSoftLongScore.ONE_HARD;
}

I implemented two separate constraints:

 public class FirstConstraintProvider implements ConstraintProvider {
      ...
     
      protected Constraint vehicleWeightCapacity(ConstraintFactory constraintFactory) {
            return constraintFactory.from(TimeWindowedVisit.class)
              .groupBy(PlanningVisit::getVehicle, sum(PlanningVisit::getWeightDemand))
              .filter((vehicle, demand) -> demand > vehicle.getWeightCapacity())
              .penalizeConfigurableLong(
                    VEHICLE_WEIGHT_CAPACITY,
                    (vehicle, demand) -> demand - vehicle.getWeightCapacity());
      }

      protected Constraint vehicleVolumeCapacity(ConstraintFactory constraintFactory) {         
        return constraintFactory.from(TimeWindowedVisit.class)
              .groupBy(PlanningVisit::getVehicle, sum(PlanningVisit::getVolumeDemand))
              .filter((vehicle, demand) -> demand > vehicle.getVolumeCapacity())
              .penalizeConfigurableLong(
                      VEHICLE_VOLUME_CAPACITY,
                      (vehicle, demand) -> demand - vehicle.getVolumeCapacity());
      }
     ...
 }

Upvotes: 0

Views: 308

Answers (1)

Geoffrey De Smet
Geoffrey De Smet

Reputation: 27327

Reading diagonally:

    1. Yes, I prefer to also split up weight and volume into separate constraints, to keep them isolated, which is better for maintenance. Also, once you start "explaining the score" with ConstraintMatchTotals etc to the user, this will definitely be better.
  • 3 & 4) The typical approach is to split up the one customer visit into multiple visits at the same location. So in multiple pieces. If a vehicle picks up for example 3 of the 5 pieces at a location, the driving time between those 3 locations is zero and the loading/unloading time is collapsed (see automatic collapse design pattern). The big challenge is deciding the granularity of those pieces, before optaplanner solves. That is a fine-tuning exercise. This works well if you're moving boxes, palets, items, etc. The possible exception to this is if you're moving water, money, gas etc. In such cases, it could be intresting to power tweak similar how the InvestementPortofio example did it instead.

Upvotes: 0

Related Questions