PROBLEM STATEMENT:
I have a use case where I am trying to run routing on 3 orders(each order has its own service time and its own time window).
I want to run routing on these 3 orders where the driver takes a break after every 14 hours(840 mins) and the break duration is of 10 hrs (600 mins)
Following are the details of the 3 orders:
The column delsertime indicates delivery service time.
The columns starttime and endtimes indicate the time window of the order i.e. the order shall be delivered only in this time window
Since this case is for multiday routing I intend to add a custom multibreak and swap constraint to the builder.
I have implemented this in the following way:-
JOB BUILDER:-
jobs = jspritRoutingService.getJspritJobs(routingProblem, isContainsWeightLimit, weightSkillMap, maxReturnTime);
The Time Window is added in the following way:-
int startTime = routingUtils.convertStringTimeToMinutes(order.getStartTime());
int endTime = routingUtils.convertStringTimeToMinutes(order.getEndTime());
if (startTime > endTime) {
throw new RuntimeException(" ========== Invalid Slot Id " + order.getOrderId() + " Start " + order.getStartTime() + " End " + order.getEndTime());
}
jobBuilder.addTimeWindow(startTime, endTime);
com.graphhopper.jsprit.core.problem.job.Delivery jspritJobService = (com.graphhopper.jsprit.core.problem.job.Delivery) jobBuilder.build();
jobs.add(jspritJobService);
JSPRIT BUILDER :
Jsprit.Builder vraBuilder = Jsprit.Builder.newInstance(vrp)
.setProperty(Jsprit.Parameter.THREADS, jspritThreadCount.toString())
.setProperty(Jsprit.Parameter.FIXED_COST_PARAM, "2.0");
VariationCoefficientTermination prematureTermination;
if(routingProblem.isDynamicRoutingProblem()){
vraBuilder.setProperty(Jsprit.Parameter.CONSTRUCTION, "best_insertion");
}
// if problem is complex, try getting results faster
if (!isLoopOptimizationProblem(routingProblem)) {
prematureTermination = new VariationCoefficientTermination(40, 0.001);
} else {
vraBuilder.setProperty(Jsprit.Parameter.ITERATIONS, "10000");
prematureTermination = new VariationCoefficientTermination(100, 0.001);
}
if (minimumLoadUtilizationConstraint.isMinCapacityUtilConstraintActive(routingProblem)) {
// if minimum load utilization constraint is required, set objective function in the problem builder
Map<String, RoutingFleet> fleetIdMap = routingProblem.getFleets().stream().collect(Collectors.toMap(RoutingFleet::getFleetId, Function.identity()));
Map<String, RoutingOrder> jobIdMap = routingProblem.getJobs().stream().collect(Collectors.toMap(ro -> ro.getOrderId().toString(), Function.identity()));
vraBuilder.setObjectiveFunction(getSolutionCalculator(vrp, jobIdMap, routingProblem, fleetIdMap));
} else if(singleBreakActive.get()){
log.trace("Applying single break constraint RequestId {}", requestId);
Map<String, RoutingFleet> fleetIdMap = routingProblem.getFleets().stream().collect(Collectors.toMap(RoutingFleet::getFleetId, Function.identity()));
vraBuilder.setObjectiveFunction(getSolutionCalculatorForSingleBreakActive(vrp, fleetIdMap, requestId));
}
boolean isMultipleBreakConstraintActive = multipleBreakConstraint.isMultipleBreakConstraintActive(routingProblem);
boolean isDriverSwapEnabled = driverSwapConstraint.isDriverSwapEnabled(routingProblem);
if (isMultipleBreakConstraintActive || isDriverSwapEnabled) { //// MULTI BREAK AND SWAP CASE
StateManager stateManager = new StateManager(vrp);
StateId timeStateId = stateManager.createStateId("time");
stateManager.addStateUpdater(new TimeUpdater(stateManager, costMatrix, timeStateId));
ConstraintManager constraintManager = new ConstraintManager(vrp, stateManager);
vraBuilder.addCoreStateAndConstraintStuff(true);
constraintManager.addConstraint(new BreakNSwapTimeConstraintsService(costMatrix, stateManager, timeStateId, routingProblem.getBreakTimeDuration(), routingProblem.getMaxWorkingTimeBeforeBreak(), routingProblem.getDriverSwapTime(), routingProblem.getMaxWorkingTimePerDay()), ConstraintManager.Priority.CRITICAL);
vraBuilder.setStateAndConstraintManager(stateManager, constraintManager);
}
VehicleRoutingAlgorithm vra = vraBuilder.buildAlgorithm();
vra.setPrematureAlgorithmTermination(prematureTermination);
vra.addListener(prematureTermination);
TimeTermination timeTermination = new TimeTermination(480000); // 8 minutes
vra.addTerminationCriterion(timeTermination);
vra.addListener(timeTermination);
UnassignedJobReasonTracker reasonTracker = new UnassignedJobReasonTracker();
vra.addListener(reasonTracker);
Collection<VehicleRoutingProblemSolution> solutions = vra.searchSolutions();
PROBLEM :-
As given in the input orders every order has its own start time and end time(i.e. the order shall be delivered only in that specific time window). Upon checking the vrp, the jobs object take correct time windows and correct service time but in the solution, one of the jobs is taking an unusually long service time.
When I am adding a custom input of break and swap constraint the end time of one of the jobs is computed wrongly
For eg:
- One of the jobs (say job1) has a time window from 300 to 960 minutes and we select the route for three days. We pass an array of time windows for three days i.e. 300-960, 1740-2400, 3180-3840.
- The service time for the job1 is 28 mins
Following is the solution obtained:
±-------------------------------------------------------------------------------------------------------------------------------+
| detailed solution |
±--------±---------------------±----------------------±----------------±----------------±----------------±----------------+
| route | vehicle | activity | job | arrTime | endTime | costs |
±--------±---------------------±----------------------±----------------±----------------±----------------±----------------+
| 1 | 29 1 | start | - | undef | 1 | 0 |
| 1 | 29 1 | delivery | 1 | 447 | 478 | 553722 |
| 1 | 29 1 | delivery | 3 | 483 | 513 | 559269 |
| 1 | 29 1 | delivery | 2 | 529 | 1768 | 571546 |
| 1 | 29 1 | end | - | 2214 | undef | 1131311 |
±-------------------------------------------------------------------------------------------------------------------------------+
As observed in the solution, the second job for which the time window was from 05:00 to 16:00 and the service time was 28 mins, the job is starting at 529 mins and is ending on the next day 1768. While it should have been 529 + 28 = 557.
Also this issue arises only when I am trying to add the following custom constraint:-
constraintManager.addConstraint(new BreakNSwapTimeConstraintsService(costMatrix, stateManager, timeStateId, routingProblem.getBreakTimeDuration(), routingProblem.getMaxWorkingTimeBeforeBreak(), routingProblem.getDriverSwapTime(), routingProblem.getMaxWorkingTimePerDay()), ConstraintManager.Priority.CRITICAL);
This particular constraint in the builder is causing the issue. On removing this constraint the solution comes out to be correct sometimes but not always. There have been cases where the solution was wrong even when this constrant was removed.
I also tried to add vehicle time window constraint as a hard constraint but that also gave the same result
The BreakNSwapTimeConstraintsService.java :
public class BreakNSwapTimeConstraintsService implements HardActivityConstraint {
public BreakNSwapTimeConstraintsService(VehicleRoutingTransportCostsMatrix costsMatrix,
StateManager stateManager, StateId timeStateId, double breakTime, double breakAfterMinutes ,
double swapTime, double swapTimeEveryMinutes) {
this.costsMatrix = costsMatrix;
this.stateManager=stateManager;
this.timeStateId= timeStateId;
this.breakTime= breakTime;
this.breakAfterMinutes= breakAfterMinutes;
this.swapTime=swapTime;
this.swapTimeEveryMinutes=swapTimeEveryMinutes;
}
private final VehicleRoutingTransportCostsMatrix costsMatrix;
private final StateManager stateManager;
private final StateId timeStateId;
private final double breakTime;
private final double breakAfterMinutes;
private final double swapTime;
private final double swapTimeEveryMinutes;
Can you please advise on which step is going wrong which is resulting in this issue.