Solving Loop super problem using Jsprit

Hi,

I am wondering if we could solve the following problem using Jsprit,

N- bikers with M- vans are send from Depot so that whenever a bike is loaded with shipment and requires to unload it, it goes to nearby van, and unload the shipment(kind of Delivery) instead of going back to depot. Also note that there are some place where van can not visit(skill feature).

1 Like

Hi @shivkrishnajaiswal,

I don’t think Jsprit out of the box can address this type of problem, since it is not able to handle flexible job/activity locations yet.

Your problem reminds me of the following paper:

Best regards,
He

1 Like

I was thinking to implement it using some HardActivityConstraint. For this I defined some locations to be delivery location. I changed SolutionCostCalculator so that now it does not impose penalty for unassigned delivery location. I made vehicle to be incapacitated(setting vehicle volume to be very large) and imposed the condition that between two delivery location which lie on the vehicle route, picked volume must not exceed some number(which is actually the vehicle original volume). There was case that delivery can occur back to back. So I also imposed that between two delivery points, picked volume must be greater than some value(which I took 33% of original vehicle vol).

It is observed that HardActivityConstraint does not work. Here is the code:

final class MilkRunConstraint implements HardActivityConstraint {

private final int VEHICLE_CAPACITY , THRESHOLD;

MilkRunConstraint(int vehicleCapacity, double percent) {
	this.VEHICLE_CAPACITY = vehicleCapacity;
	this.THRESHOLD = (int) (vehicleCapacity * percent);
}

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

	List<TourActivity> tourActivities = iFacts.getRoute().getActivities();

	Job newJob = ((JobActivity) newAct).getJob();

	int cumShipments = 0;

	boolean isNewJobDelivery = newJob.getName().equals("drop") , wasLastJobDelivery = false;

	if (!isNewJobDelivery && newJob.getSize().get(0) > VEHICLE_CAPACITY)
		return ConstraintsStatus.NOT_FULFILLED_BREAK;

	if ((prevAct instanceof Start || nextAct instanceof End) && isNewJobDelivery)
		return ConstraintsStatus.NOT_FULFILLED;

	for (TourActivity currAct : tourActivities) {

		Job currJob = ((JobActivity) currAct).getJob();

		boolean isDelivery = currJob.getName().equals("drop");

		if (isDelivery && wasLastJobDelivery)
			return ConstraintsStatus.NOT_FULFILLED_BREAK;

		if (isDelivery) {
			if (cumShipments < THRESHOLD || cumShipments > VEHICLE_CAPACITY)
				return ConstraintsStatus.NOT_FULFILLED_BREAK;
			cumShipments = 0;
		}

		cumShipments += currJob.getSize().get(0);

		wasLastJobDelivery = isDelivery;

		if (prevAct.equals(currAct)) {
			if (cumShipments < THRESHOLD && isNewJobDelivery)
				return ConstraintsStatus.NOT_FULFILLED;

			wasLastJobDelivery = isNewJobDelivery;

			if (isNewJobDelivery)
				cumShipments = 0;

			cumShipments += newJob.getSize().get(0);
		}

		if (cumShipments > VEHICLE_CAPACITY)
			return ConstraintsStatus.NOT_FULFILLED;

	}

	if (wasLastJobDelivery)
		return ConstraintsStatus.NOT_FULFILLED_BREAK;

	return cumShipments <= VEHICLE_CAPACITY ? ConstraintsStatus.FULFILLED : ConstraintsStatus.NOT_FULFILLED_BREAK;
}

}

I think I have found the reason why putting hard constraint of this type does not work. It is the not the insertion (recreate) process that causes problem but it is ruin process. Unlike other constraints such as skill one, where removing the job from route X and inserting into other route Y does not depend on the jobs that come before the jobs to be removed in route X.

But if we remove the job from route X in the current scenario then removing the delivery job may itself render the problem infeasible in the first place.