jsprit: HardActivityConstraint with CRITICAL Priority allowing invalid solutions.

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

About this issue

Original URL
State: open
Created 5 years ago
Comments: 29

Most upvoted comments

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

grantm009 on Apr 6, 2020