Does Jsprit balance the work load like distance travelled across all the vehicle it used? If so, how?
It does not do it out of the box, but you can make use of soft constraint and objective function to fulfill it. For example, the following tries to minimize the maximum route travel time so that it balances travel time across routes:
Not sure if it’s OK for me to post like this, but here I go (sorry).
I have tried implementing this to my problem, however, the problem state of max-transport-time keeps getting set to null at the start of every iteration. I have put a placeholder workaround to set currentMaxTransportTime to 0.0, though that does not solve the problem well. JSprit version used is 1.7.2. Here is the code:
static class UpdateMaxTransportTime implements ActivityVisitor, StateUpdater {
private StateManager stateManager;
private ActivityTimeTracker timeTracker;
public UpdateMaxTransportTime(StateManager stateManager, ForwardTransportTime transportTime, VehicleRoutingActivityCosts activityCosts) {
super();
this.stateManager = stateManager;
this.timeTracker = new ActivityTimeTracker(transportTime, activityCosts);
}
@Override
public void begin(VehicleRoute route) {
timeTracker.begin(route);
}
@Override
public void visit(TourActivity activity) {
timeTracker.visit(activity);
}
@Override
public void finish() {
timeTracker.finish();
double newRouteEndTime = timeTracker.getActArrTime();
double currentMaxTransportTime;
StateId stateId = stateManager.createStateId("max-transport-time");
try {
currentMaxTransportTime = stateManager.getProblemState(
stateId, Double.class);
}
catch (NullPointerException ne) {
currentMaxTransportTime = 0.0;
}
if(newRouteEndTime > currentMaxTransportTime){
stateManager.putProblemState(stateId, Double.class, newRouteEndTime);
}
}
}
I have mainly changed the finish method, but also added VehicleRoutingActivityCosts to the overload of the constructor of UpdateMaxTransportTime, as it was needed for ActivityTimeTracker. I am unable to find why max-transport-time keeps being set to null, even though at the start, before giving it a new value for the first time, it has the value of 0.0.
For those interested, here is the working/updated code for the software constraint:
SoftActivityConstraint penalyzeShiftOfMaxTransportTime = new SoftActivityConstraint() {
private final VehicleRoutingTransportCosts routingCosts = vrp.getTransportCosts();
private final double penaltyForEachTimeUnitAboveCurrentMaxTime = 3.;
@Override
public double getCosts(JobInsertionContext iFacts, TourActivity prevAct, TourActivity newAct, TourActivity nextAct, double depTimeAtPrevAct) {
/*
* determines maximum of all routes' transport times, which is here basically a state that can be fetched via the stateManager
*/
double maxTime = stateManager.getProblemState(stateManager.createStateId("max-transport-time"), Double.class);
/*
* determines additional time of route when inserting newAct between prevAct and nextAct
*
*/
double tp_time_prevAct_newAct = routingCosts.getTransportTime(prevAct.getLocation(), newAct.getLocation(), depTimeAtPrevAct, iFacts.getNewDriver(), iFacts.getNewVehicle());
double newAct_arrTime = depTimeAtPrevAct + tp_time_prevAct_newAct;
double newAct_endTime = newAct_arrTime + newAct.getOperationTime();
/*
* open routes - if route is set to be open, i.e. end is endogeneously determined by the algorithm, then inserting of newAct between prevAct
* and end just shifts the route's end time to by tp_time_prevAct_newAct
*
*/
if(nextAct instanceof End){
if(!iFacts.getNewVehicle().isReturnToDepot()){
double additionalTime = tp_time_prevAct_newAct;
double new_routes_transport_time = iFacts.getRoute().getEnd().getArrTime() - iFacts.getRoute().getStart().getEndTime() + additionalTime;
return penaltyForEachTimeUnitAboveCurrentMaxTime*Math.max(0,new_routes_transport_time-maxTime);
}
}
double tp_time_newAct_nextAct = routingCosts.getTransportTime(newAct.getLocation(), nextAct.getLocation(), newAct_endTime, iFacts.getNewDriver(), iFacts.getNewVehicle());
double nextAct_arrTime = newAct_endTime + tp_time_newAct_nextAct;
double oldTime;
if(iFacts.getRoute().isEmpty()){
oldTime = (nextAct.getArrTime() - depTimeAtPrevAct);
}
else{
oldTime = (nextAct.getArrTime() - iFacts.getRoute().getDepartureTime());
}
double additionalTime = (nextAct_arrTime - iFacts.getNewDepTime()) - oldTime;
double tpTime = iFacts.getRoute().getEnd().getArrTime() - iFacts.getRoute().getStart().getEndTime() + additionalTime;
return penaltyForEachTimeUnitAboveCurrentMaxTime*Math.max(0,tpTime-maxTime);
}
};
constraintManager.addConstraint(penalyzeShiftOfMaxTransportTime);Hi PHillner,
I’ve experienced the same problem and figured out the root cause.
getProblemState might return null as an instance of Double. In that case, converting Double to double would generates NullPointerException.
Here is an example to avoid it:
Double maxTimeObject = stateManager.getProblemState(stateManager.createStateId(“max-transport-time”), Double.class);
double maxTime;
if(maxTimeObject == null || maxTimeObject.isNaN()) {
maxTime = 0.0;
}else {
maxTime = maxTimeObject.doubleValue();
}
Hope this helps.
Regards,
Junsei
Hi，PHillner，the reason why problemstate is been set to null is that the informIterationStarts method in StateManager call the clear() method which clear all the states in StateManager before an iteration start
Okay, well that clears things. It was part of the design, not a bug. Thank you!
Hi PHillner and jie31best,
Thanks a lot for your code. However in my case my solution is still not balancing the work across vehicles.
If it’s possible for one vehicle to do all of the work, then the solution will utilise just that one vehicle. I’ve checked and I’m setting fixedCosts to 0 on each vehicle, and also setting Jsprit.Parameter.FIXED_COST_PARAM to “0.” just in case that affects anything.
It appears as though the issue is because throughout all of my 1500 iterations, jsprit will only ever create solutions with 1 route and never 2 or more. I.e., the ruin and insertion parts of the algorithm never attempt to utilise more than 1 vehicle!
If I penalise solutions with a solution cost calculator that leave vehicles unutilised then the iterations end with a best solution with quite high costs. Then, if I use “skills” to force just one job to each vehicle therefore forcing more than one vehicle to be part of the solution then I do get a solution which balances the remaining jobs between vehicles.
So I know that it’s possible for the balancing to happen if ever a solution is passed to the solution cost calculator with more than one route/vehicle used! When that happens, the costs are much lower and so the best solution is the one with balanced routes. However, if I remove the contrivance of using skills to force more than one vehicle to be part of the solution then I never see a solution that uses more than one vehicle/route.
Is there any one who can offer any help/advice? I’ve attempted to write my own insertions using an InsertionStartsListener, however this didn’t affect the result.
I know that the Graphhopper Route Optimization API is able to do this, by using min-max objectives, so I’m guessing it must be possible somehow?
Regards,
Luke
a quick potential solution/workaround: maybe you can try starting with an initial solution which uses all vehicles? It does not need to be optimal or anything, perhaps it can contain unassigned jobs or even break some constraints? I’m not sure, but it might be worth a try.
Thanks for your reply!
I did try that. I built a Collection of VehicleRoutes, one per Vehicle. Each route had a single job. Then that was added to the algorithm as an initialSolution. It didn’t appear to change anything - I would still only get solutions with one route. However, I couldn’t find a good resource about how to build an initial solution from scratch using Java, so it’s possible I may have done it incorrectly. If anyone has a good example of an initial solution in code that’d be great!
I just found a conversation here A way to force a fixed number of vehicles · Issue #239 · graphhopper/jsprit · GitHub and one of the suggestions was to back up the initial solution with a ruin “which leaves at least a single job in place on each route (random job)”. I’m working on another problem at the moment, but will try that when I switch back to this!
The full suggestion (in case the above link ever 404s) was:
It may be more reliable to actually modify the insertion and ruin heuristics a bit. Assuming you want n vehicles, for the initial solution construction, randomly choose n jobs, assigning one per vehicle and then apply cheapest or regret based construction to assign all other jobs and finish building the first solution. For subsequent ruin-and-recreate iterations, use a modified ruin which leaves at least a single job in place on each route (where the job is randomly chosen each time).
This kind of strategy would force the algorithm to always use n vehicles, but still allow it to optimise them.