Preventing load "top ups"

jsprit
41

Hi @grantm009

I checked the service time of all the shipments. The pickup service time is 10units (1unit = 1min) and delivery service time is 60mins for each shipment.

Below are the pickup and delivery time windows for the jobs (10AM to 4PM):

Pickup:
[start=600.0][end=960.0]
[start=2040.0][end=2400.0]
[start=3480.0][end=3840.0]
[start=4920.0][end=5280.0]
[start=6360.0][end=6720.0]
[start=7800.0][end=8160.0]
[start=9240.0][end=9600.0]
[start=10680.0][end=11040.0]
[start=12120.0][end=12480.0]
[start=13560.0][end=13920.0]

Delivery:
[start=600.0][end=900.0]
[start=2040.0][end=2340.0]
[start=3480.0][end=3780.0]
[start=4920.0][end=5220.0]
[start=6360.0][end=6660.0]
[start=7800.0][end=8100.0]
[start=9240.0][end=9540.0]
[start=10680.0][end=10980.0]
[start=12120.0][end=12420.0]
[start=13560.0][end=13860.0]

Vehicle EarliestStart time is 600 (10AM).

				VehicleType vehicleType = VehicleTypeImpl.Builder.newInstance(vehicleCount + "_type")
						.addCapacityDimension(DimensionIndex.VOLUME_METRIC_INDEX.getIndex(),volumeMtWt)
						.setCostPerWaitingTime(2.5)
						.setCostPerTransportTime( 5)
						.setCostPerDistance(5)
						.setFixedCost(3).build();

The optimized route considering all service time and time windows should be as mentioned below, where vehicle arrives at depot 24/11/2021 10:00:00 AM:

Facility Name Arrival Time Departure Time Distance
WIC ,SACS_Karnataka 24/11/2021 10:00:00 AM 24/11/2021 10:10:00 AM 0
ICTC - Vydehi Medical College & Hospital, Vija Nag 24/11/2021 10:55:00 AM 24/11/2021 11:55:00 AM 23
ICTC - Srirampura Referal Hospital, Goripalya, BU 24/11/2021 12:31 PM 24/11/2021 1:31:00 PM 23
ICTC - Unani Medical College(SJIIM), K. R. Market 24/11/2021 1:38 PM 24/11/2021 2:38:00 PM 3
ICTC - K.C. General Hospital, Shivajinagar, BU 24/11/2021 2:54 PM 24/11/2021 3:54:00 PM 5
ICTC - Bowring & Lady Curzon Hospital, City Market 24/11/2021 4:03 PM 25/11/2021 11:00:00 AM 5
ICTC - ESI Hospital, Indiranagar, Okalipuram, BU 25/11/2021 11:10 AM 25/11/2021 12:10:00 PM 3
ICTC - Hosahalli Referal Hospital, Chamaraj Road 25/11/2021 12:15 PM 25/11/2021 1:15:00 PM 3
ICTC - General Hospital, K.R. Puram, BU 25/11/2021 1:56 PM 25/11/2021 2:56:00 PM 19
WIC ,SACS_Karnataka 25/11/2021 3:32 PM - 20

But the route jsprit provides after implementing the suggestions is as mentioned below (takes more time around 2 days):

Facility Name Arrival Time Departure Time Distance
WIC ,SACS_Karnataka 24/11/2021 10:00:00 24/11/2021 10:10:00 0
ICTC - Vydehi Medical College & Hospital, Vija Nag 24/11/2021 10:55:00 24/11/2021 11:55:00 23
WIC ,SACS_Karnataka 24/11/2021 12:40:00 24/11/2021 13:50:00 23
ICTC - Srirampura Referal Hospital, Goripalya, BU 24/11/2021 13:54:00 24/11/2021 14:54:00 2
ICTC - Unani Medical College(SJIIM), K. R. Market 24/11/2021 15:01:00 25/11/2021 11:00:00 3
ICTC - K.C. General Hospital, Shivajinagar, BU 25/11/2021 11:08:00 25/11/2021 12:08:00 4
ICTC - Bowring & Lady Curzon Hospital, City Market 25/11/2021 12:17:00 25/11/2021 13:17:00 5
ICTC - ESI Hospital, Indiranagar, Okalipuram, BU 25/11/2021 13:27:00 25/11/2021 14:27:00 3
ICTC - Hosahalli Referal Hospital, Chamaraj Road 25/11/2021 14:32:00 25/11/2021 15:32:00 3
ICTC - General Hospital, K.R. Puram, BU 25/11/2021 16:12:00 27/11/2021 11:00:00 20
WIC ,SACS_Karnataka 27/11/2021 11:36:00 - 19

Also, I observed the last deliverShipment (ICTC - General Hospital, K.R. Puram, BU) arrives at 25/11/2021 16:12:00 (2412unit ) but departs at 27/11/2021 11:00:00 (4980 unit) staying there a whole day, even when there is a Time window ([start=3480.0][end=3780.0]) available to service the job. Please let me know if you notice anything that might result in such scenarios.

regards,
Sarita

42

The below implementation seems to work for me.

Constraint:

import com.graphhopper.jsprit.core.algorithm.state.InternalStates;
import com.graphhopper.jsprit.core.algorithm.state.StateManager;
import com.graphhopper.jsprit.core.problem.Capacity;
import com.graphhopper.jsprit.core.problem.constraint.HardActivityConstraint;
import com.graphhopper.jsprit.core.problem.misc.JobInsertionContext;
import com.graphhopper.jsprit.core.problem.solution.route.activity.Start;
import com.graphhopper.jsprit.core.problem.solution.route.activity.DeliverShipment;
import com.graphhopper.jsprit.core.problem.solution.route.activity.PickupShipment;
import com.graphhopper.jsprit.core.problem.solution.route.activity.End;
import com.graphhopper.jsprit.core.problem.solution.route.activity.TourActivity;

/* A Hard Constraint to Prevent Top-Ups
 * 
 * We allow pickups to be inserted into the activity queue when a truck is empty
 * We allow deliveries to be inserted only at the end of the activity queue.
 * 
 * NOTES
 * The constraint is tested with only one depot.
 * The constraint is not tested if a truck has a load at the start
 * Activity types SERVICE, BREAK are not considered.
 * Because we are only aware of the previous and next activity in the activity queue, 
 * therefore we allow deliveries only at the end of the queue, e.g. we prevent the 
 * following sequence: p1p2p3 --> p1p2d2p3--> p1p2d2p3d1 , where p=Pickup and d=Delivery. 
 *  
 * See also: Activity.java, ShipmentInsertionCalculator.java and 
 * https://github.com/graphhopper/jsprit/blob/master/docs/Meta-Heuristic.md
 * 
*/

public class HcNoTopUps implements HardActivityConstraint {
	private StateManager stateManager;

	HcNoTopUps(StateManager stateManager) {
		this.stateManager = stateManager;
	}

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

		// Preparation
		int retVal = 1; // 0 = FULFILLED , 1 = NOT_FULFILLED_BREAK
		Capacity loadAtPrevAct = null;
		Integer loadAtPrevActValue = null;
		loadAtPrevAct = stateManager.getActivityState(prevAct, InternalStates.LOAD, Capacity.class);
		if (loadAtPrevAct != null) {
			loadAtPrevActValue = loadAtPrevAct.get(Globals.WEIGHT_INDEX);
		}

		// Constraint
		if (newAct instanceof PickupShipment && prevAct instanceof Start
		    && (loadAtPrevActValue == null || loadAtPrevActValue == 0)) {
			retVal = 0; // allow pickup as first activity if the truck is empty
		}
		if (newAct instanceof PickupShipment && prevAct instanceof PickupShipment) {
			retVal = 0; // allow truck to load several shipments at once
		}
		if (newAct instanceof PickupShipment && loadAtPrevActValue != null && loadAtPrevActValue == 0) {
			retVal = 0; // allow truck to pickup new shipments if it is empty
		}
		if (newAct instanceof DeliverShipment && nextAct instanceof End) {
			retVal = 0; // allow delivery as last activity
		}
		if (newAct instanceof DeliverShipment && nextAct instanceof DeliverShipment) {
			retVal = 0; // allow multiple deliveries at the end of the activity queue
		}
		// printHcNoTopUps(iFacts, prevAct, newAct, nextAct, loadAtPrevActValue, retval);

		// Result
		if (retVal == 0) {
			return ConstraintsStatus.FULFILLED;
		}
		return ConstraintsStatus.NOT_FULFILLED_BREAK;
	}

	private void printHcNoTopUps(JobInsertionContext iFacts, TourActivity prevAct, TourActivity newAct,
	    TourActivity nextAct, Integer loadAtPrevActValue, int retval) {
		if (retval == 0) {
			Globals.printLog5(String.format("PASS"));
		} else {
			Globals.printLog5(String.format("FAIL"));
		}
		Globals.printLog5(String.format(": loadAtPrevAct: %d , PrevAct %s(%s) %d, newAct %s(%s) %d, nextAct %s(%s) %d\n",
		    loadAtPrevActValue, prevAct.getName(), prevAct.getLocation().getId(),
		    prevAct.getSize().get(Globals.WEIGHT_INDEX), newAct.getName(), newAct.getLocation().getId(),
		    newAct.getSize().get(Globals.WEIGHT_INDEX), nextAct.getName(), nextAct.getLocation().getId(),
		    nextAct.getSize().get(Globals.WEIGHT_INDEX)));
	}
}

In main:

// Add constraints
		StateManager stateManager = new StateManager(problem);
		ConstraintManager constraintManager = new ConstraintManager(problem, stateManager);
		HcNoTopUps hcNoTopUps = new HcNoTopUps(stateManager);
		constraintManager.addConstraint(hcNoTopUps, Priority.HIGH);

		// Create algorithm with new constraints
		VehicleRoutingAlgorithm algorithm = Jsprit.Builder.newInstance(problem)
		    .setStateAndConstraintManager(stateManager, constraintManager).buildAlgorithm();