I was asking some time ago, a very similar question here https://discuss.graphhopper.com/t/fuel-delivery-problem/1660 (the product compartmentation problem)
I’ve managed to solve this using capacities.
Basically you make shipments with capacities this way:
Let’s assume you got order O with three products. P1 (3000 liters), P2 (5000 liters), P3 (7000 liters)
Now you add capacities this way
shipmentBuilder.addSizeDimension(1, 3000)
shipmentBuilder.addSizeDimension(2, 5000)
shipmentBuilder.addSizeDimension(3, 7000)
//using dimension 0 for the total amount
shipmentBuilder.addSizeDimension(0, 15000)
Now, if you don’t have any truck that can carry 3 products, this order can’t be served.
Let’s assume you do have a 3 tank (compartment) truck.
Let’s assume that the truck tanks have the capacities as follows:
T1(4000 liters),T2(8000) and T3(10000)
Same as for shipments:
vehicleTypeBuilder.addCapacityDimension(1,10000)
vehicleTypeBuilder.addCapacityDimension(2,10000)
vehicleTypeBuilder.addCapacityDimension(3,10000)
vehicleTypeBuilder.addCapacityDimension(0,22000)
//this basically is saying that the truck can carry 10000 liters of product 1,2 or 3 (because it has a tank able to), but max 25000 liters.
Till now we have solved the capacity problems, but it’s not 100% accurate.
We can see that truck can carry the order, but if we slighly modify the order to have 7000 liters of P1 instead of 3000 it would work for Jsprit because we set that the truck can carry for each tank 10000 and the sum is smaller than the max capacity of the truck (23000liters).
But this wouldn’t work in reality because we can fit P3 in T3, P2 in T2 but, P1 that now have 7000liters couldn’t fit in T1.
Here comes the second implementation to solve the problem.
//passing the information about tanks as user data truck_tanks = [4000,8000,10000]
vehicleTypeBuilder.setUserData(truck_tanks)
add
StateManager stateManager = new StateManager(vrp)
ConstraintManager constraintManager = new ConstraintManager(vrp, stateManager)
HardActivityConstraint compartmentationConstraint = new CompartmentationConstraint(stateManager)
constraintManager.addConstraint(compartmentationConstraint, ConstraintManager.Priority.CRITICAL)
Now we have to implement the CompartmentationConstraint class this way :
CompartmentationConstraint(RouteAndActivityStateGetter stateManager) {
super()
this.stateManager = stateManager
defaultValue = Capacity.Builder.newInstance().build()
}
/**
* Checks whether there is enough capacity to insert newAct between prevAct and nextAct.
*/
@Override
HardActivityConstraint.ConstraintsStatus fulfilled(JobInsertionContext iFacts, TourActivity prevAct, TourActivity newAct, TourActivity nextAct, double prevActDepTime) {
if (!(newAct instanceof PickupShipment) && !(newAct instanceof DeliverShipment)) {
return HardActivityConstraint.ConstraintsStatus.FULFILLED
}
Capacity loadAtPrevAct
if (prevAct instanceof Start) {
loadAtPrevAct = stateManager.getRouteState(iFacts.getRoute(), InternalStates.LOAD_AT_BEGINNING, Capacity.class)
if (loadAtPrevAct == null) {
loadAtPrevAct = defaultValue
}
}
else {
loadAtPrevAct = stateManager.getActivityState(prevAct, InternalStates.LOAD, Capacity.class)
if (loadAtPrevAct == null) {
loadAtPrevAct = defaultValue
}
}
//here we add upp the products the orders
Capacity capacity
VehicleType vehicleType = iFacts.getNewVehicle().getType()
if (newAct instanceof PickupShipment) {
capacity = Capacity.addup(loadAtPrevAct, newAct.getSize())
if (!capacity.isLessOrEqual(vehicleType.getCapacityDimensions())) {
return HardActivityConstraint.ConstraintsStatus.NOT_FULFILLED
}
}
if (newAct instanceof DeliverShipment) {
capacity = Capacity.addup(loadAtPrevAct, Capacity.invert(newAct.getSize()))
if (!capacity.isLessOrEqual(vehicleType.getCapacityDimensions())) {
return HardActivityConstraint.ConstraintsStatus.NOT_FULFILLED_BREAK
}
}
//we need to implement this method
if (!productsFitOnTruck(capacity, (List) vehicleType.getUserData())) {
return HardActivityConstraint.ConstraintsStatus.NOT_FULFILLED_BREAK
}
return HardActivityConstraint.ConstraintsStatus.FULFILLED
}
The last thing is to implement a FAST working method
private Boolean productsFitOnTruck(capacity, (List) vehicleType.getUserData()) {…}
i’m not going to write the implementation code here, because it’s not Jsprit related, but the general idea here is:
You have some products in
capacity
and you have some tanks in
(List) vehicleType.getUserData()
and have to write an algorithm that determines if the products will fit in the truck tanks or not.
Like in your case where you have a limited amount of tanks (max 3) and a limited amount of products (max 4)
i would write an algorithm that fits the first product on the empty tanks, then the next product on empty and non empty tanks (because there is product 1 in one ore more of them) and then the last product.
If you can fit (in some way) all of the products you return true else false.
Hope this helps.