HardActivityConstraint with CRITICAL Priority allowing invalid solutions. #475

briandilley · 2019-07-05T20:59:19Z

I have a HardActivityConstraint for returning NOT_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:

	@Override
	public ConstraintsStatus fulfilled(
			JobInsertionContext iFacts, TourActivity prevAct, TourActivity newAct, TourActivity nextAct, double prevActDepTime) {

		if (!(newAct instanceof PickupActivity)) {
			return ConstraintsStatus.FULFILLED;
		}

		if (prevAct == null) {
			return ConstraintsStatus.FULFILLED;
		}

		final Capacity load = stateManager.getActivityState(prevAct, stateId, Capacity.class);
		if (load == null) {
			return ConstraintsStatus.FULFILLED;
		}

		final int pendingExternalDeliveries = load.get(PassengerLoadUpdater.DIM_EXTERNAL_DELIVERIES);
		final boolean previousWasDepot = isDepot(prevAct.getLocation());
		final boolean currentIsDepot = isDepot(newAct.getLocation());

		if (currentIsDepot && !previousWasDepot && pendingExternalDeliveries > 0) {
			return ConstraintsStatus.NOT_FULFILLED;
		}

		return ConstraintsStatus.FULFILLED;
	}

and the state updater:

	@Override
	public void begin(VehicleRoute route) {
		currentValue = DEFAULT_VALUE;
	}

	@Override
	public void visit(TourActivity act) {
		boolean locationIsDepot = isDepot(act.getLocation());
		boolean pickup = act instanceof PickupActivity;
		boolean delivery = act instanceof DeliveryActivity;

		if (pickup) {
			currentValue = Capacity.addup(currentValue, createCapacity(
					locationIsDepot ? 0 : 1,
					locationIsDepot ? 1 : 0));
		} else if (delivery) {
			currentValue = Capacity.addup(currentValue, createCapacity(
					locationIsDepot ? -1 : 0,
					locationIsDepot ? 0 : -1));
		}

		stateManager.putActivityState(act, STATE_ID, currentValue);
	}

	@Override
	public void finish() {
		currentValue = DEFAULT_VALUE;
	}

The text was updated successfully, but these errors were encountered:

briandilley · 2019-07-13T16:26:03Z

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);
	}

briandilley · 2019-07-14T19:07:54Z

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

grantm009 · 2019-07-18T22:45:07Z

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.

briandilley · 2019-07-18T23:08:51Z

@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.

briandilley · 2019-07-18T23:10:12Z

@grantm009 here's the entire thing: https://gist.github.com/briandilley/33a36feef99b5fa3608db25c902d29b0

grantm009 · 2019-07-18T23:13:15Z

Thanks

…

-- Message protected by MailGuard: e-mail anti-virus, anti-spam and content filtering.http://www.mailguard.com.au/mg

grantm009 · 2019-07-18T23:55:27Z

@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.

grantm009 · 2019-07-18T23:59:50Z

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 ?

briandilley · 2019-07-19T19:52:51Z

Yeah - this makes sense. I'll think on it a bit and try something this weekend.

briandilley · 2019-07-20T00:12:05Z

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;
			}
		}

grantm009 · 2019-07-21T22:36:38Z

Hi Brian
I'll play with this today.

grantm009 · 2019-07-22T06:42:01Z

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 :)

grantm009 · 2019-07-22T08:10:33Z

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

briandilley · 2019-07-22T12:37:16Z

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 ***@***.***> 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 <#475?email_source=notifications&email_token=AAIE3T6GZZ5VC6FLFLGF2KLQAVTQDA5CNFSM4H6N4YW2YY3PNVWWK3TUL52HS4DFVREXG43VMVBW63LNMVXHJKTDN5WW2ZLOORPWSZGOD2PEBVI#issuecomment-513687765>, or mute the thread <https://github.com/notifications/unsubscribe-auth/AAIE3T6AKUZCAVTQLJXLPQLQAVTQDANCNFSM4H6N4YWQ> .

grantm009 · 2019-07-25T05:11:12Z

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

briandilley · 2019-07-26T02:51:36Z

excellent - looking forward to it.

briandilley · 2019-07-27T16:26:01Z

@grantm009 any updates?

briandilley · 2019-08-06T21:53:16Z

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.

ifle · 2020-04-06T12:40:01Z

I also still have top ups problem. Can you please share your solution?

grantm009 · 2020-04-06T18:51:13Z

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);
			}
		}
	}

ifle · 2020-04-06T20:59:14Z

Thanks for your answer. What is RouteRuns? Can you share it too?

grantm009 · 2020-04-06T23:08:41Z

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 newRun = new ArrayList();
List acts = route.getActivities();
for(Integer i = 0; i < actCount; i++){
if(acts.get(i) instanceof PickupShipment){
newRun.add(i);
} else if((acts.get(i) instanceof Break)){
newRun.add(i);
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();
}
} else { // delivery
newRun.add(i);
if( ( i < actCount-1 && acts.get(i+1) instanceof PickupShipment ) || i == actCount-1){
// we are at the end of a run
runs.add(newRun);
newRun = new ArrayList();
}
}
}
}

ifle · 2020-04-07T11:43:18Z

Thanks. Will take a look

grantm009 · 2020-04-16T22:19:51Z

@ifle is it working for you ?

ifle · 2020-04-17T04:41:34Z

@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.

grantm009 · 2020-04-17T04:49:32Z

Yes we found it needed more iterations as well.

ifle · 2020-04-17T08:26:39Z

Do you have recommendations about number of iterations?

ifle · 2020-07-04T18:00:51Z

Hi @grantm009,

We have array index out of bounds exception when use initial routes. Do you fimilar with this issue?

This comment has been minimized.

Sign in to view

Provide feedback

Saved searches

Use saved searches to filter your results more quickly

HardActivityConstraint with CRITICAL Priority allowing invalid solutions. #475

HardActivityConstraint with CRITICAL Priority allowing invalid solutions. #475

briandilley commented Jul 5, 2019

briandilley commented Jul 13, 2019

briandilley commented Jul 14, 2019 •

edited

Loading

grantm009 commented Jul 18, 2019

briandilley commented Jul 18, 2019

briandilley commented Jul 18, 2019

grantm009 commented Jul 18, 2019 via email

grantm009 commented Jul 18, 2019

grantm009 commented Jul 18, 2019 •

edited

Loading

briandilley commented Jul 19, 2019

briandilley commented Jul 20, 2019

grantm009 commented Jul 21, 2019

grantm009 commented Jul 22, 2019

grantm009 commented Jul 22, 2019

briandilley commented Jul 22, 2019 via email

grantm009 commented Jul 25, 2019

briandilley commented Jul 26, 2019

briandilley commented Jul 27, 2019

This comment has been minimized.

briandilley commented Aug 6, 2019

ifle commented Apr 6, 2020

grantm009 commented Apr 6, 2020 •

edited

Loading

ifle commented Apr 6, 2020 •

edited

Loading

grantm009 commented Apr 6, 2020

ifle commented Apr 7, 2020

grantm009 commented Apr 16, 2020

ifle commented Apr 17, 2020

grantm009 commented Apr 17, 2020

ifle commented Apr 17, 2020

ifle commented Jul 4, 2020

HardActivityConstraint with CRITICAL Priority allowing invalid solutions. #475

HardActivityConstraint with CRITICAL Priority allowing invalid solutions. #475

Comments

briandilley commented Jul 5, 2019

briandilley commented Jul 13, 2019

briandilley commented Jul 14, 2019 • edited Loading

grantm009 commented Jul 18, 2019

briandilley commented Jul 18, 2019

briandilley commented Jul 18, 2019

grantm009 commented Jul 18, 2019 via email

grantm009 commented Jul 18, 2019

grantm009 commented Jul 18, 2019 • edited Loading

briandilley commented Jul 19, 2019

briandilley commented Jul 20, 2019

grantm009 commented Jul 21, 2019

grantm009 commented Jul 22, 2019

grantm009 commented Jul 22, 2019

briandilley commented Jul 22, 2019 via email

grantm009 commented Jul 25, 2019

briandilley commented Jul 26, 2019

briandilley commented Jul 27, 2019

This comment has been minimized.

briandilley commented Aug 6, 2019

ifle commented Apr 6, 2020

grantm009 commented Apr 6, 2020 • edited Loading

ifle commented Apr 6, 2020 • edited Loading

grantm009 commented Apr 6, 2020

ifle commented Apr 7, 2020

grantm009 commented Apr 16, 2020

ifle commented Apr 17, 2020

grantm009 commented Apr 17, 2020

ifle commented Apr 17, 2020

ifle commented Jul 4, 2020

briandilley commented Jul 14, 2019 •

edited

Loading

grantm009 commented Jul 18, 2019 •

edited

Loading

grantm009 commented Apr 6, 2020 •

edited

Loading

ifle commented Apr 6, 2020 •

edited

Loading