Open briandilley opened 5 years ago
I've update my constraint to be more complete, but I still have the problem of solutions coming about that violate this constraint:
@Override
public ConstraintsStatus fulfilled(
JobInsertionContext iFacts, TourActivity prevAct, TourActivity newAct, TourActivity nextAct, double prevActDepTime) {
if (newAct instanceof PickupActivity) {
return fulfilledWhenPickup(iFacts, prevAct, newAct, nextAct, prevActDepTime);
} else if (nextAct instanceof End) {
return fulfilledWhenDelivery(iFacts, prevAct, newAct, nextAct, prevActDepTime);
}
return ConstraintsStatus.FULFILLED;
}
private ConstraintsStatus fulfilledWhenPickup(
JobInsertionContext iFacts, TourActivity prevAct, TourActivity newAct, TourActivity nextAct, double prevActDepTime) {
final boolean newIsDepot = isDepot(newAct.getLocation());
final boolean previousWasDepot = isDepot(prevAct.getLocation());
final Capacity previousLoad = stateManager.getActivityState(prevAct, stateId, Capacity.class);
final int pendingExternalDeliveries = previousLoad != null
? previousLoad.get(PassengerLoadUpdater.DIM_EXTERNAL_DELIVERIES)
: 0;
if (newIsDepot && !previousWasDepot && pendingExternalDeliveries > 0) {
return ConstraintsStatus.NOT_FULFILLED_BREAK;
}
return ConstraintsStatus.FULFILLED;
}
private ConstraintsStatus fulfilledWhenDelivery(
JobInsertionContext iFacts, TourActivity prevAct, TourActivity newAct, TourActivity nextAct, double prevActDepTime) {
final boolean newIsDepot = isDepot(newAct.getLocation());
final boolean nextIsDepot = isDepot(nextAct.getLocation());
final Capacity previousLoad = stateManager.getActivityState(prevAct, stateId, Capacity.class);
int pendingExternalDeliveries = previousLoad != null
? previousLoad.get(PassengerLoadUpdater.DIM_EXTERNAL_DELIVERIES)
: 0;
if (!newIsDepot) {
pendingExternalDeliveries = pendingExternalDeliveries - 1;
}
if (!newIsDepot && nextIsDepot && pendingExternalDeliveries > 0) {
return ConstraintsStatus.NOT_FULFILLED_BREAK;
}
return ConstraintsStatus.FULFILLED;
}
private boolean isDepot(Location location) {
// TODO: is close
return location.equals(stationLocation);
}
I've now narrowed it down to this and it's at about ~2% failure rate:
@Override
public ConstraintsStatus fulfilled(
JobInsertionContext iFacts, TourActivity prevAct, TourActivity newAct, TourActivity nextAct, double prevActDepTime) {
final boolean prevIsDepot = isDepot(prevAct.getLocation());
final boolean newIsDepot = isDepot(newAct.getLocation());
final Capacity currentLoad = stateManager.getActivityState(prevAct, currentStateId, Capacity.class);
int pendingExternalDeliveries = currentLoad != null
? currentLoad.get(PendingDeliveriesUpdater.DIM_PENDING_EXTERNAL_DELIVERIES)
: 0;
if (!prevIsDepot && newIsDepot && pendingExternalDeliveries > 0) {
return ConstraintsStatus.NOT_FULFILLED_BREAK;
}
if (prevIsDepot && !newIsDepot && pendingExternalDeliveries > 0) {
return ConstraintsStatus.NOT_FULFILLED_BREAK;
}
return ConstraintsStatus.FULFILLED;
}
I think the problem arises when it does this (all pickups at depot):
pickupShipment <- newly added
pickupShipment
pickupShipment
deliverShipment
deliverShipment
pickupShipment <- makes this invalid
pickupShipment
pickupShipment
pickupShipment
deliverShipment <- newly added
Hi Brian Im trying to build a test program with your code. Can you tell me the value of the constant PendingDeliveriesUpdater.DIM_PENDING_EXTERNAL_DELIVERIES pls.
@grantm009 the value of that is insignificant - it's just the index of the dimension within the StateManager
for the given StateId
- you can give it whatever you like.
@grantm009 here's the entire thing: https://gist.github.com/briandilley/33a36feef99b5fa3608db25c902d29b0
Thanks
-- Message protected by MailGuard: e-mail anti-virus, anti-spam and content filtering.http://www.mailguard.com.au/mg
@briandilley I assume you are using this: @Override public ConstraintsStatus fulfilled( JobInsertionContext iFacts, TourActivity prevAct, TourActivity newAct, TourActivity nextAct, double prevActDepTime) {
final boolean prevIsDepot = isDepot(prevAct.getLocation());
final boolean newIsDepot = isDepot(newAct.getLocation());
final Capacity currentLoad = stateManager.getActivityState(prevAct, currentStateId, Capacity.class);
int pendingExternalDeliveries = currentLoad != null
? currentLoad.get(PendingDeliveriesUpdater.DIM_PENDING_EXTERNAL_DELIVERIES)
: 0;
if (!prevIsDepot && newIsDepot && pendingExternalDeliveries > 0) {
return ConstraintsStatus.NOT_FULFILLED_BREAK;
}
if (prevIsDepot && !newIsDepot && pendingExternalDeliveries > 0) {
return ConstraintsStatus.NOT_FULFILLED_BREAK;
}
return ConstraintsStatus.FULFILLED;
}
and not the previous version. When I run this it pretty well fails every time (allows topups). I agree with your scenario where it is inserting a pickup at the start of the run and adding the delivery at the end of the run, ie p1p2d2p3d3d1
scratching head now.
let me expound some thought. We have a route and we multiple runs within the route. The definition of a run is load up and deliver followed by another run of load up and delivery or - p1p2d1d2p3d3p4d4 being 3 runs So I think we need a state manager for managing the runs. Then during the insert we check to see if the associated activity is already inserted and if so then in the same run. If not the same run then fail. Does this make sense ?
Yeah - this makes sense. I'll think on it a bit and try something this weekend.
So I created a state updater for the round that sets a "run id" on each activity. Here it is:
public class ActivityRunsUpdater
implements RouteVisitor,
StateUpdater {
public static final int START_RUN_ID = 0;
private StateManager stateManager;
private Location depotLocation;
private final StateId STATE_ID;
public ActivityRunsUpdater(StateManager stateManager, Location depotLocation) {
this.stateManager = stateManager;
this.depotLocation = depotLocation;
this.STATE_ID = stateManager.createStateId("run_id");
}
public StateId getStateId() {
return STATE_ID;
}
@Override
public void visit(VehicleRoute route) {
int runId = START_RUN_ID;
for (int i=0; i<route.getActivities().size(); i++) {
final TourActivity activity = route.getActivities().get(i);
if (i == 0) {
stateManager.putActivityState(activity, STATE_ID, runId);
continue;
}
final TourActivity previous = route.getActivities().get(i - 1);
final boolean currentIsDepot = isDepot(activity.getLocation());
final boolean previousIsDepot = isDepot(previous.getLocation());
if (currentIsDepot && !previousIsDepot) {
runId++;
}
stateManager.putActivityState(activity, STATE_ID, runId);
}
}
private boolean isDepot(Location location) {
// TODO: is close
return location.equals(depotLocation);
}
}
The problem I'm having is that the runId
state seems to never be set on the associated activities, so the following constraint doesn't seem to work:
int runId = Optional.ofNullable(stateManager.getActivityState(prevAct, routeIdStateId, Integer.class))
.orElse(ActivityRunsUpdater.START_RUN_ID);
for (int i=0; i < iFacts.getAssociatedActivities().size(); i++) {
final TourActivity otherActivity = iFacts.getAssociatedActivities().get(i);
final int otherRunId = Optional.ofNullable(otherActivity)
.map((a) -> stateManager.getActivityState(a, routeIdStateId, Integer.class))
.orElse(ActivityRunsUpdater.START_RUN_ID);
if (otherRunId != runId) {
return ConstraintsStatus.NOT_FULFILLED;
}
}
Hi Brian I'll play with this today.
Im getting the same. I have tested that the activity visitor does update the runId by logging the value after it is set: stateManager.putActivityState(activity, STATE_ID, runId); Utils.LOGGER.log(Level.INFO, " SM_ActivityMaxDepotsPerRunUpdater_EXP Incremented runId is now: " + stateManager.getActivityState(activity, STATE_ID, Integer.class));
but when I call getActivityState in the hard constraint it always returns the value of START_RUN_ID.
(If you change START_RUN_ID to 99 it returns 99). This means, I think, that there is a problem getting the state for the activity and it is always return the orElse value.
Still working on it. Let me know if you crack it :)
A bit more expounding Brian Your constraint fulfilled code looks something like this. ` public ConstraintsStatus fulfilled(JobInsertionContext iFacts, TourActivity prevAct, TourActivity newAct, TourActivity nextAct, double prevActDepTime) {
int runId = Optional.ofNullable(stateManager.getActivityState(prevAct, STATE_ID, Integer.class))
.orElse(SM_ActivityRunsUpdater_EXP.START_RUN_ID);
for (int i=0; i < iFacts.getAssociatedActivities().size(); i++) {
final TourActivity otherActivity = iFacts.getAssociatedActivities().get(i);
final int otherRunId = Optional.ofNullable(otherActivity)
.map((act) -> stateManager.getActivityState(act, STATE_ID, Integer.class))
.orElse(SM_ActivityRunsUpdater_EXP.START_RUN_ID);
if (otherRunId != runId) {
return ConstraintsStatus.NOT_FULFILLED;
}
}
return ConstraintsStatus.FULFILLED;
}
` Why are you doing the loop. Can you just do this (pseudo)
runIdD = getRunIdOf(prevAct)
runIdP = getRunIdOf(prevAct.AssociatedActivity)
if runIdD = runIdP then FULFILLED
or am I missing something
You could, I guess I was just being overly cautious... I'm not entirely sure how this API works and there is no documentation so I'm pretty much fumbling in the dark on this stuff.
On Mon, Jul 22, 2019, 1:10 AM grantm009 notifications@github.com wrote:
A bit more expounding Brian Your constraint fulfilled code looks something like this. ` public ConstraintsStatus fulfilled(JobInsertionContext iFacts, TourActivity prevAct, TourActivity newAct, TourActivity nextAct, double prevActDepTime) {
int runId = Optional.ofNullable(stateManager.getActivityState(prevAct, STATE_ID, Integer.class)) .orElse(SM_ActivityRunsUpdater_EXP.START_RUN_ID); for (int i=0; i < iFacts.getAssociatedActivities().size(); i++) { final TourActivity otherActivity = iFacts.getAssociatedActivities().get(i); final int otherRunId = Optional.ofNullable(otherActivity) .map((act) -> stateManager.getActivityState(act, STATE_ID, Integer.class)) .orElse(SM_ActivityRunsUpdater_EXP.START_RUN_ID); if (otherRunId != runId) { return ConstraintsStatus.NOT_FULFILLED; } } return ConstraintsStatus.FULFILLED; }
` Why are you doing the loop. Can you just do this (pseudo)
runIdD = getRunIdOf(prevAct) runIdP = getRunIdOf(prevAct.AssociatedActivity) if runIdD = runIdP then FULFILLED
or am I missing something
— You are receiving this because you were mentioned. Reply to this email directly, view it on GitHub https://github.com/graphhopper/jsprit/issues/475?email_source=notifications&email_token=AAIE3T6GZZ5VC6FLFLGF2KLQAVTQDA5CNFSM4H6N4YW2YY3PNVWWK3TUL52HS4DFVREXG43VMVBW63LNMVXHJKTDN5WW2ZLOORPWSZGOD2PEBVI#issuecomment-513687765, or mute the thread https://github.com/notifications/unsubscribe-auth/AAIE3T6AKUZCAVTQLJXLPQLQAVTQDANCNFSM4H6N4YWQ .
Hi Brian I think I have had some success. I have a set of jobs that was consistently routing for topups, now not doing so. I'll run a series of tests over the next few days and then share the code with you. We have lots of jobs so not difficult to run on older job queues. regards Grant
excellent - looking forward to it.
@grantm009 any updates?
Hi Brian Sorry bud I had to zoom off unexpectedly for a bit. But Im back. Here is what I have done. It still misbehaves very occasionally. Maybe you can see a flaw. @oblonski Could you maybe cast your eye over it please?
1st this is what I put in the main code. I use depotList because we have multiple depots.
if(!allowTopups){
Utils.LOGGER.log(Level.INFO, "ToUps disabled for this runs" );
StateId SINoTopups = stateManager.createStateId("allowTopups");
StateUpdater SMNoTopups = new SM_ActivityRunsUpdater_EXP(stateManager, depotList, SINoTopups );
stateManager.addStateUpdater(SMNoTopups);
Map<String, Set<String>> HC_NoMidRunReloadsMap = new HashMap<String, Set<String>>();
HC_NoMidRunReloadsMap.put("depots", depotList);
HC_NoMidRunReloads4EXP noMidRunReloads = new HC_NoMidRunReloads4EXP(stateManager, depotList, SINoTopups);
constraintManager.addConstraint(noMidRunReloads,Priority.CRITICAL);
}
Next is the state updater. There is a large chunk of commented code which I use to output debug info.
public class SM_ActivityRunsUpdater_EXP
implements RouteVisitor,
StateUpdater {
public static final int START_RUN_ID = 0;
private StateManager stateManager;
private Set<String> depotList;
private final StateId STATE_ID;
public SM_ActivityRunsUpdater_EXP(StateManager stateManager, Set<String> dlist, StateId id) {
this.stateManager = stateManager;
this.depotList = dlist;
this.STATE_ID = id;
}
@Override
public void visit(VehicleRoute route) {
int runId = START_RUN_ID;
for (int i=0; i<route.getActivities().size(); i++) {
final TourActivity activity = route.getActivities().get(i);
// pickups can happen anywhere regardless if it is from a depot or other (like customer pickup)
// also we use !delivery because it could be a pickup or it could be a break
if (i == 0 || activity instanceof DeliveryActivity){
stateManager.putActivityState(activity, STATE_ID, runId);
continue;
}
final TourActivity previous = route.getActivities().get(i - 1);
final boolean currentIsDepot = isDepot(activity.getLocation());
final boolean previousIsDepot = isDepot(previous.getLocation());
// if it is a pickup from a depot and the previous activity was not a pickup or was not a pickup from a depot
// then we are starting a new run
if (((activity instanceof PickupActivity) && currentIsDepot)
&& ( (previous instanceof DeliveryActivity)
|| (previous instanceof PickupActivity && !previousIsDepot)))
{
runId++;
stateManager.putActivityState(activity, STATE_ID, runId);
continue;
}
// all we have left is a pickup from a depot after another pickup from a depot so use the current runId
stateManager.putActivityState(activity, STATE_ID, runId);
// Utils.LOGGER.log(Level.INFO, " SM_ActivityMaxDepotsPerRunUpdater_EXP Incremented runId is now: " + stateManager.getActivityState(activity, STATE_ID, Integer.class));
}
// for debugging we output a summary
// if(route.getActivities().size() > 4){
// String outString = null;
// String leftAlgin = "| %-7d | %-7d | %-10s| %-7s%n";
// outString = outString+ String.format( "+--------------------------+%n\n");
// outString= outString + "| Run list |%n";
// outString = outString + String.format("+-----------+---------------%n");
// outString = outString + "| Index | Run | Activity | Depot |%n\n";
// outString = outString + String.format("+-----------+---------------%n");
// for (int index=0; index<route.getActivities().size(); index++) {
// TourActivity a = route.getActivities().get(index);
// String t = a instanceof PickupActivity ? "P" : "D";
// String d = (isDepot(a.getLocation())) ? "D":"";
// int r = this.stateManager.getActivityState(a, STATE_ID, Integer.class);
// outString = outString + String.format( leftAlgin, index, r, t, d);
// }
// outString = outString + String.format("+-----------+---------------%n");
// Utils.LOGGER.log(Level.INFO,outString);
// }
}
private boolean isDepot(Location l){
String name = l.getId();
if(depotList != null){
for(String n: depotList){
if(n.equalsIgnoreCase(name)){
return true;
}
}
}
return false;
}
}
Last is the constraint.
public class HC_NoMidRunReloads4EXP implements HardActivityConstraint {
private StateManager stateManager;
private Set<String> depotList;
private StateId STATE_ID;
HC_NoMidRunReloads4EXP( StateManager sm, Set<String> depotList, StateId id){
int count = depotList == null ? 0 : depotList.size();
this.STATE_ID = id;
Utils.LOGGER.log(Level.INFO, " HC_NoMidRunReloads4EXP multi arg started with depotList size: " + count );
Utils.LOGGER.log(Level.INFO, " HC_NoMidRunReloads4EXP depotList: " + depotList.toString() );
this.stateManager = sm;
this.depotList = depotList;
}
@Override
public ConstraintsStatus fulfilled(JobInsertionContext iFacts, TourActivity prevAct, TourActivity newAct, TourActivity nextAct, double prevActDepTime) {
if(newAct instanceof DeliveryActivity){
VehicleRoute route = iFacts.getRoute();
ActivityContext pickupContext = iFacts.getRelatedActivityContext();
int pickupInsertionIndex = pickupContext.getInsertionIndex();
int deliveryInsertionIndex = iFacts.getActivityContext().getInsertionIndex() ;
if(route.isEmpty() || deliveryInsertionIndex == 0 || pickupInsertionIndex == route.getActivities().size() )
return ConstraintsStatus.FULFILLED;
if(deliveryInsertionIndex == route.getActivities().size())
deliveryInsertionIndex--;
TourActivity pickupAct = route.getActivities().get(pickupInsertionIndex);
TourActivity deliveryAct = route.getActivities().get(deliveryInsertionIndex);
int pRunId = Optional.ofNullable(stateManager.getActivityState(pickupAct, STATE_ID, Integer.class))
.orElse(SM_ActivityRunsUpdater_EXP.START_RUN_ID);
int dRunId = Optional.ofNullable(stateManager.getActivityState(deliveryAct, STATE_ID, Integer.class))
.orElse(SM_ActivityRunsUpdater_EXP.START_RUN_ID);
if(pRunId != dRunId)
return ConstraintsStatus.NOT_FULFILLED_BREAK;
}
return ConstraintsStatus.FULFILLED;
}
}
The problem with our approaches is that the insertion may be fine for the current job being inserted... but it breaks an existing job that was already inserted.
I also still have top ups problem. Can you please share your solution?
Hi We have overcome this. Our method may/may not suit your situation but it works for us. First some terms and background. A Vehicle has a route made up of a number of runs. Each run consists of some pickups and deliveries which must occur as PPPDDD. A pattern of PPDPDD is what we call a top-up and is what we want to avoid. So - PPPDDDPPDDPPPDDD (3 runs) is ok but PPPDPDDPPDDD is not.
We do this in the solution checker which you add to the algorithm as:
VehicleRoutingAlgorithm algorithm = Utils.getAlgorithmBuilder(problem)
.setStateAndConstraintManager(stateManager, constraintManager)
.setObjectiveFunction(solutionCostCalculator)
.buildAlgorithm();
In this function (solutionCostCalculator) we check each route for "odd sized runs" which basically means a job is picked up in one run then delivered in another run. If you remove the "runs" overlay this means a topup occurred in the route. When we find this we remove the offending run from the solution and its jobs to the unassigned jobs and the iterations continue until the job is assigned nicely. If your environment has scheduled Breaks or other activities (aside from pickups and deliveries) then you would have to allow for those.
I hope this helps. If you find a better way or improvement - please share :)
public static void checkSolutionForOddSizedRuns(VehicleRoutingProblemSolution solution, UnassignedJobReasonTracker reasonTracker) {
List<String> unassignmentReason = new ArrayList<>();
unassignmentReason.add("Split Pickup/Delivery rejected");
for (VehicleRoute route : solution.getRoutes()) {
List<Job> discardedJobs = new ArrayList<>();
RouteRuns runs = new RouteRuns(route);
for(int run = 0; run < runs.size(); run++) {
if(runs.getActivities(run).size() % 2 != 0) {
for(TourActivity act: runs.getActivities(run)) {
if(act instanceof TourActivity.JobActivity && ! discardedJobs.contains(((TourActivity.JobActivity) act).getJob())) {
discardedJobs.add(((TourActivity.JobActivity) act).getJob());
}
}
}
}
for (Job discardJob : discardedJobs) {
solution.getUnassignedJobs().add(discardJob);
route.getTourActivities().removeJob(discardJob);
reasonTracker.informJobUnassigned(discardJob, unassignmentReason);
}
}
}
Thanks for your answer. What is RouteRuns? Can you share it too?
Routeruns is a class that manages our "runs" approach. It is quite proprietary and Im afraid I cant share that class. Essentially you just want a function that takes a route and iterates over it to identify the runs.
Here is a code snippet that should help.
private void findRuns() {
runs.clear();
// split the route into runs
int actCount = route.getActivities().size();
ArrayList
if( i < actCount-1 && acts.get(i-1) instanceof DeliverShipment && acts.get(i+1) instanceof PickupShipment){
// we are at the end of a run
runs.add(newRun);
newRun = new ArrayList
Thanks. Will take a look
@ifle is it working for you ?
@grantm009 Yes, thanks. We still not use it on production. The idea move splitted shipments to unassigned jobs works well. We found for some problems we must to increase the iterations otherwise, the result is suboptimal.
Yes we found it needed more iterations as well.
Do you have recommendations about number of iterations?
Hi @grantm009,
We have array index out of bounds exception when use initial routes. Do you fimilar with this issue?
I have a
HardActivityConstraint
for returningNOT_FULFILLED
when the new activity is a pickup at the depot following any activity that wasn't at the depot yet there are pending non-depot deliveries to be made (that's a mouth-full). The problem that I'm having is that I still get an invalid best solution that violates this constraint. How can i prevent invalid solutions as the best solution?Here's the constraint:
and the state updater: