Hi @jie31best, @stefan,
Please have a look at case:
Problem Sample problem code:
`
public static void main(String[] args) {
/*
* some preparation - create output folder
*/
File dir = new File("output");
// if the directory does not exist, create it
if (!dir.exists()) {
System.out.println("creating directory ./output");
boolean result = dir.mkdir();
if (result) System.out.println("./output created");
}
/*
Create locations and distance matrix
*/
Location loc_1 = Location.newInstance("loc_1");
Location loc_2 = Location.newInstance("loc_2");
Location loc_3 = Location.newInstance("loc_3");
VehicleRoutingTransportCostsMatrix.Builder costMatrixBuilder = VehicleRoutingTransportCostsMatrix.Builder.newInstance(true);
costMatrixBuilder.addTransportDistance(loc_1.getId(),loc_2.getId(),2500);
costMatrixBuilder.addTransportDistance(loc_1.getId(),loc_3.getId(),2500);
costMatrixBuilder.addTransportDistance(loc_2.getId(),loc_3.getId(),500);
VehicleRoutingTransportCostsMatrix costsMatrix =costMatrixBuilder.build();
/*
* get a vehicle type-builder and build a type with the typeId "vehicleType" and one capacity dimension, i.e. weight, and capacity dimension value of 2
*/
VehicleTypeImpl.Builder vehicleTypeBuilder = VehicleTypeImpl.Builder.newInstance("VehicleType").addCapacityDimension(0, 1).setCostPerDistance(1).setFixedCost(10);
VehicleType vehicleType = vehicleTypeBuilder.build();
/*
* get a vehicle-builder and build a vehicle located at (10,10) with type "vehicleType"
*/
Builder V1Builder = VehicleImpl.Builder.newInstance("V1");
V1Builder.setStartLocation(loc_1).setReturnToDepot(true);
V1Builder.setType(vehicleType);
VehicleImpl V1 = V1Builder.build();
Builder V3Builder = VehicleImpl.Builder.newInstance("V3");
V3Builder.setStartLocation(loc_3).setReturnToDepot(true);
V3Builder.setType(vehicleType);
VehicleImpl V3 = V3Builder.build();
/*
* build services at the required locations, each with a capacity-demand of 1.
*/
Shipment P1 = Shipment.Builder.newInstance("P1").addSizeDimension(0, 1).setPickupLocation(loc_3).setDeliveryLocation(loc_1).build();
Shipment P2 = Shipment.Builder.newInstance("P2").addSizeDimension(0,1).setPickupLocation(loc_3).setDeliveryLocation(loc_2).build();
VehicleRoutingProblem.Builder vrpBuilder = VehicleRoutingProblem.Builder.newInstance();
vrpBuilder.addVehicle(V1).addVehicle(V3);
vrpBuilder.addJob(P1).addJob(P2);
VehicleRoutingProblem problem = vrpBuilder.setRoutingCost(costsMatrix).build();
/*
Add constraints
*/
//Add default constraints
StateManager stateManager = new StateManager(problem);
stateManager.updateSkillStates();
ConstraintManager constraintManager = new ConstraintManager(problem, stateManager);
constraintManager.addSkillsConstraint();
StateId distanceStateId = stateManager.createStateId("total_distance");
Double maxDistance = 1500.;
stateManager.addStateUpdater(new maxTripDistanceConstraint.DistanceUpdater(distanceStateId, stateManager, costsMatrix));
constraintManager.addConstraint(new maxTripDistanceConstraint.DistanceConstraint(maxDistance, distanceStateId, stateManager, costsMatrix),ConstraintManager.Priority.CRITICAL);
/*
* get the algorithm out-of-the-box.
*/
VehicleRoutingAlgorithm algorithm = Jsprit.Builder.newInstance(problem).addCoreStateAndConstraintStuff(true).setStateAndConstraintManager(stateManager,constraintManager).buildAlgorithm();
algorithm.setMaxIterations(3);
/*
* and search a solution
*/
Collection<VehicleRoutingProblemSolution> solutions = algorithm.searchSolutions();
/*
* get the best
*/
VehicleRoutingProblemSolution bestSolution = Solutions.bestOf(solutions);
new VrpXMLWriter(problem, solutions).write("output/problem-with-solution.xml");
SolutionPrinter.print(problem, bestSolution, SolutionPrinter.Print.VERBOSE);
}
Distance Constraint implementation:
`public class maxTripDistanceConstraint {
static class DistanceUpdater implements StateUpdater, ActivityVisitor {
private final StateManager stateManager;
private final VehicleRoutingTransportCostsMatrix costsMatrix;
// private final StateFactory.StateId distanceStateId; //v1.3.1
private final StateId distanceStateId; //head of development - upcoming release
private VehicleRoute vehicleRoute;
private double distance = 0.;
private TourActivity prevAct;
// public DistanceUpdater(StateFactory.StateId distanceStateId, StateManager stateManager, VehicleRoutingTransportCostsMatrix costMatrix) { //v1.3.1
public DistanceUpdater(StateId distanceStateId, StateManager stateManager, VehicleRoutingTransportCostsMatrix transportCosts) { //head of development - upcoming release (v1.4)
this.costsMatrix = transportCosts;
this.stateManager = stateManager;
this.distanceStateId = distanceStateId;
}
public void begin(VehicleRoute vehicleRoute) {
distance = 0.;
prevAct = vehicleRoute.getStart();
this.vehicleRoute = vehicleRoute;
}
public void visit(TourActivity tourActivity) {
distance += getDistance(prevAct, tourActivity);
prevAct = tourActivity;
}
public void finish() {
distance += getDistance(prevAct, vehicleRoute.getEnd());
stateManager.putRouteState(vehicleRoute, distanceStateId, distance); //head of development - upcoming release (v1.4)
}
double getDistance(TourActivity from, TourActivity to) {
return this.costsMatrix.getDistance(from.getLocation().getId(), to.getLocation().getId());
}
}
static class DistanceConstraint implements HardActivityConstraint {
private final StateManager stateManager;
private final VehicleRoutingTransportCostsMatrix costsMatrix;
private final double maxDistance;
// private final StateFactory.StateId distanceStateId; //v1.3.1
private final StateId distanceStateId; //head of development - upcoming release (v1.4)
// DistanceConstraint(double maxDistance, StateFactory.StateId distanceStateId, StateManager stateManager, VehicleRoutingTransportCostsMatrix costsMatrix) { //v1.3.1
DistanceConstraint(double maxDistance, StateId distanceStateId, StateManager stateManager, VehicleRoutingTransportCostsMatrix transportCosts) { //head of development - upcoming release (v1.4)
this.costsMatrix = transportCosts;
this.maxDistance = maxDistance;
this.stateManager = stateManager;
this.distanceStateId = distanceStateId;
}
public ConstraintsStatus fulfilled(JobInsertionContext context, TourActivity prevAct, TourActivity newAct, TourActivity nextAct, double v) {
double additionalDistance = 0.;
double pickupDistance = 0.;
if(newAct instanceof DeliverShipment) {
if(((DeliverShipment) newAct).getJob().getId().equals("P2") && context.getNewVehicle().getId().equals("V1"))
System.out.print("P2 delivery by V1");
TourActivity pickupActivity = context.getAssociatedActivities().get(0);
TourActivity prevtoPickupActivity = null;
TourActivity nexttoPickupActivity = null;
int insertionIndex = context.getRelatedActivityContext().getInsertionIndex();
if(context.getRoute().getTourActivities().getActivities().size() == 0){
Double routeDistance = getDistance(pickupActivity,newAct);
routeDistance += this.costsMatrix.getDistance(context.getNewVehicle().getStartLocation().getId(),pickupActivity.getLocation().getId());
if(context.getNewVehicle().isReturnToDepot())
routeDistance += getDistance(newAct,nextAct);
if(routeDistance > this.maxDistance )return ConstraintsStatus.NOT_FULFILLED;
else return ConstraintsStatus.FULFILLED;
}else if (insertionIndex == 0) {
prevtoPickupActivity = context.getRoute().getStart();
nexttoPickupActivity = context.getRoute().getTourActivities().getActivities().get(0);
} else if (insertionIndex == context.getRoute().getTourActivities().getActivities().size()) {
prevtoPickupActivity = context.getRoute().getTourActivities().getActivities().get(insertionIndex - 1);
nexttoPickupActivity = context.getRoute().getEnd();
} else {
prevtoPickupActivity = context.getRoute().getTourActivities().getActivities().get(insertionIndex - 1);
nexttoPickupActivity = context.getRoute().getTourActivities().getActivities().get(insertionIndex);
}
if (nexttoPickupActivity instanceof End && !context.getNewVehicle().isReturnToDepot())
pickupDistance = getDistance(prevtoPickupActivity, pickupActivity);
else
pickupDistance = getDistance(prevtoPickupActivity, pickupActivity) + getDistance(pickupActivity, nexttoPickupActivity) - getDistance(prevtoPickupActivity, nexttoPickupActivity);
}
if (nextAct instanceof End && !context.getNewVehicle().isReturnToDepot())
additionalDistance = getDistance(prevAct, newAct);
else
additionalDistance = getDistance(prevAct, newAct) + getDistance(newAct, nextAct) - getDistance(prevAct, nextAct);
Double routeDistance = stateManager.getRouteState(context.getRoute(), distanceStateId, Double.class);
if (routeDistance == null) routeDistance = 0.;
double newRouteDistance = routeDistance + additionalDistance + pickupDistance;
if (newRouteDistance > maxDistance) {
return ConstraintsStatus.NOT_FULFILLED;
} else return ConstraintsStatus.FULFILLED;
}
double getDistance(TourActivity from, TourActivity to) {
return this.costsMatrix.getDistance(from.getLocation().getId(), to.getLocation().getId());
}
}
}`
Here I have 2 Shipments : P1 and P2
P1 has to be picked up from loc_3 and delivered at loc_1
P2 has to be picked up from loc_3 and delivered at loc_2
distance:
loc_1 - loc_2 = 2500
loc_1 - loc_3 = 2500
loc_2 - loc_3 = 500
Two vehicles : starting from loc_1 and loc_3 with Return to depot as True
Expected output is: P2 should be served by V3.
But this is what I’m getting:
When I tried to find out the issue by putting this in code:
if(((DeliverShipment) newAct).getJob().getId().equals("P2") && context.getNewVehicle().getId().equals("V1")) System.out.print("P2 delivery by V1");
I got none such case.
Means at no point does the algorithm checks constraint for a route when P2 is delivered by V1, but I still get in the output route.
Is this a bug?
Notice:
If I run only 2 iteration I get this answer:
But when I run more than 2 I get this:
Notice that total cost in second case is less
Does it violate hard constraint to reduce the cost?
`