Preventing load "top ups"

Hi @PGWelch,

I do not understand this. As per my understanding the constraint here is once a vehicle leaves depot with shipment it should not come back until it is empty. I.e It can only come back once it has delivered all the shipment it left with.

How adding an additional cost (parking cost) will help the purpose? I understand that it will try to minimize number of nodes visited. We can have solution as below
Solution 1:

  1. start from depot with shipments A,B,C
  2. deliver only A and B
  3. come back to depot to pickup D
  4. deliver C,D

While desired solution is:
Solution 2

  1. start with shipment A and B
  2. deliver both,
  3. come back to depot,
  4. pickup C and D
  5. deliver both.

The cost of both the solutions are same even after adding parking cost.

If the quantity constraints mean that two separate pickup visits at the depot cannot be avoided, then parkingCost will have no effect. However I have seen scenarios where jsprit will assign two different separate pickup visits to the depot, where only one is needed. Here, parkingCost will prevent the additional depot visit…

Thanks for the input @PGWelch.

In this case @Bhoumik_Shah was correct in his description of the problem.

I think I have solved the problem with the following snippet in a hard activity constraint - after a lot of help by people here. - Thanks folks.

if((newAct instance PickupShipment) &&
         (!(nextAct instanceof End) && 
          !(nextAct instanceof PickupShipment))){
        return ConstraintsStatus.NOT_FULFILLED_BREAK;
return ConstraintStatus.FULFILLED;
1 Like

My thanks to @Bhoumik_Shah.

His statement of the problem provoked an idea with me resulting the snippet above. Our previous approach involved truck capacity utilisation etc. All that proved un-necessary when simply put “the vehicle should not do pickups at a depot until the end of the run”. The code above did the job and worked well.

The customer signed off on it today.
Thanks for the help.

1 Like

I’m glad I could help.

hi @grantm009 and @Bhoumik_Shah,

it seems to me that the implemented constraint lacks handling of the case that newAct instanceof DeliverShipment, as I’ve asked earlier.

please find at the end of the post an example where the solution does not fulfill the constraint (and also is not the optimal solution).

an interesting thing is that, in the example, if x is changed from 20 to 10 or 30, the solution will fulfill the constraint, but it is still not the optimal solution.

Best regards,

    double x = 20;
    VehicleTypeImpl type = VehicleTypeImpl.Builder.newInstance("type")
            .addCapacityDimension(0, 2)
    VehicleImpl v1 = VehicleImpl.Builder.newInstance("v1")
            .setStartLocation(Location.newInstance(0, 0))
    Shipment s1 = Shipment.Builder.newInstance("s1")
            .setPickupLocation(Location.newInstance(0, 0))
            .setDeliveryLocation(Location.newInstance(x, 0))
            .addSizeDimension(0, 1)
    Shipment s2 = Shipment.Builder.newInstance("s2")
            .setPickupLocation(Location.newInstance(0, 0))
            .setDeliveryLocation(Location.newInstance(x, 0))
            .addSizeDimension(0, 1)
    Shipment s3 = Shipment.Builder.newInstance("s3")
            .setPickupLocation(Location.newInstance(0, 0))
            .setDeliveryLocation(Location.newInstance(0, 100))
            .addSizeDimension(0, 1)
    VehicleRoutingProblem vrp = VehicleRoutingProblem.Builder.newInstance()

    Jsprit.Builder algorithmBuilder = Jsprit.Builder.newInstance(vrp);
    StateManager stateManager = new StateManager(vrp);
    ConstraintManager constraintManager = new ConstraintManager(vrp, stateManager);

            new HardActivityConstraint() {
                public ConstraintsStatus fulfilled(
                        JobInsertionContext iFacts,
                        TourActivity prevAct,
                        TourActivity newAct,
                        TourActivity nextAct,
                        double prevActDepTime
                ) {
                    if ((newAct instanceof PickupShipment) &&
                            (!(nextAct instanceof End) && !(nextAct instanceof PickupShipment))) {
                        if (iFacts.getNewVehicle().getStartLocation().getCoordinate().equals(
                            return ConstraintsStatus.NOT_FULFILLED_BREAK;
                    return ConstraintsStatus.FULFILLED;

    algorithmBuilder.setStateAndConstraintManager(stateManager, constraintManager);
    VehicleRoutingAlgorithm algorithm = algorithmBuilder.buildAlgorithm();
    VehicleRoutingProblemSolution s = Solutions.bestOf(algorithm.searchSolutions());
    SolutionPrinter.print(vrp, s, SolutionPrinter.Print.VERBOSE);

Hi @jie31best

Unless I’m missing something I don’t see the problem with the ShipmentDeliver case. The constraint is only designed to work on ShipmentPickup and so the first “if” statement locks that in. At the end of that if statement it returns FULFILLED which it should always do with deliveries.

Sorry If Im missing something.


the insertion of a DeliverShipment, if you don’t use a constraint to guide it, could lead to a solution that does not fulfill the constraint.

for example, suppose you have 3 shipments (1, 2 and 3) and two of them are already inserted in a route and respect the constraint, with a sequence of, say, p1p2d1d2. now you are trying to insert the third shipment. with the implemented constraint, suppose p3 is inserted before p2, so the sequence becomes p1p3p2d1d2. when inserting d3, since there is no constraint to guide the insertion, it could be inserted between p3 and p2, and thus lead to a sequence of p1p3d3p2d1d2, which does not fulfill the constraint. but the implemented constraint would not detect this.

this is what happens with the example I gave in the previous reply.

Best regards,

Well thats a brain breaker. I will sit down with pencil and paper and work it through. However for your amusement it reminded me of a brief digital poem that goes like this:

11 was 1 racehorse 22 was 12. 1111 race and 22112.

Good luck with that one. It does make sense if said right.

Hi grantm009 , I am facing the same issue as you mentioned in this thread. I have added the following Hard constraint snippet which solved yours. Please go through the following snippet and response and let me know where i am going wrong.

My Code snippets for hard type constraint are as follows.

static class NoPickupWhenDeliveryInTruck implements HardActivityConstraint {

private StateManager stateManager;
private StateId  stateId;

NoPickupWhenDeliveryInTruck(StateManager stateManager) {
	this.stateManager = stateManager;
	this.stateId = this.stateManager.createStateId("currentVehicleLoad");

public ConstraintsStatus fulfilled(JobInsertionContext jobInsertionContext, TourActivity prevAct,
		TourActivity newAct, TourActivity nextAct, double departureTimeAtPrevAct) {
      if((newAct instanceof PickupShipment) &&
	         (!(nextAct instanceof End) && 
	          !(nextAct instanceof PickupShipment))){
	        return ConstraintsStatus.NOT_FULFILLED_BREAK;
	return ConstraintsStatus.FULFILLED;


The solution that i still get is as follows
route | vehicle | activity | job | arrTime | endTime | costs |
| 1 | 10427333 | start | - | undef | 300 | 0 |
| 1 | 10427333 | pickupShipment | 18 | 300 | 300 | 0 |
| 1 | 10427333 | pickupShipment | 15 | 300 | 300 | 0 |
| 1 | 10427333 | pickupShipment | 20 | 300 | 300 | 0 |
| 1 | 10427333 | pickupShipment | 12 | 300 | 300 | 0 |
| 1 | 10427333 | deliverShipment | 12 | 321 | 351 | 21 |
| 1 | 10427333 | deliverShipment | 15 | 374 | 404 | 44 |
| 1 | 10427333 | deliverShipment | 20 | 421 | 451 | 61 |
| 1 | 10427333 | pickupShipment | 32 | 470 | 500 | 80 |
| 1 | 10427333 | deliverShipment | 32 | 521 | 521 | 101 |
| 1 | 10427333 | pickupShipment | 17 | 521 | 521 | 101 |
| 1 | 10427333 | pickupShipment | 27 | 533 | 563 | 113 |
| 1 | 10427333 | pickupShipment | 4 | 574 | 574 | 124 |

If the arrTime & endTime is same, it means the vehicle is at depot as per the logic i have put.

As you can see above, after 4 pickup (18,15,20,12) at depot, It only delivered (12,15,20) and picked up (32 - on the way pickup -Not depot) and returned to the depot to deliver (32) with (18) still inside truck(Vehicle). Any Help would be appreciated.

Hi all,

I’m looking into this issue recently. It seems to me such constraint could lead to sub-optimal solutions. Let me use a small example to illustrate:

Assume there are three locations:

O: (0, 0)
A: (0, 1)
B: (1, 0)

Two shipments from A to O, and two more shipments from B to O, each with size 1.

There is only one vehicle, with capacity 3, starting and ending at O. There is no time window or any other constraint except for the desired “preventing load top ups” constraint.

Obviously the optimal solution would be AAOOBBOO, where A and B represent associated pickups and each O is a delivery, and the cost is 4.

Let’s see what happens when the algo builds initial solution:

  • When it tries to insert the first shipment into an empty route, all four shipments lead to the same marginal cost, so let’s assume it inserts a BO into the route;

  • Then when it tries to insert the second shipment, obviously it will insert another BO into the route without starting a new trip, so the route becomes BBOO and the marginal cost is 0;

  • When it tries to insert the third shipment, it has two choices: 1) starting a new trip, i.e., making the route AOBBOO, and the marginal cost is 2; and 2) going to two different pickup locations in one trip, i.e., making the route ABBOOO, and the marginal cost is 1.414. Thus the algo will choose the second option;

  • Then when it tries to insert the last shipment, due to the capacity, it has to start a new trip, and due to the desired constraint, the route will become AOABBOOO, and total cost is 5.414.

What will happen if we don’t have the desired constraint in the problem? The first three steps will be the same, and in the last insertion, the route will become AAOBBOOO, and total cost is 4.

Note that for this small example, the iterative ruin and recreate process that follows will be able to find the optimal solution, but, for some larger problems, it is possible that it cannot.

Best regards,

Hi He

Sorry I did not see your post previously. I hope my response is still relevant.
I think you are right in your scenario however two operational factors make it work for us.

  1. Ours is a star config for the start of the day. So the trucks all come to one depot to load up. Other depot pickups are “end of day” activities to move stock to and from the main depot.
  2. The order of loading the jobs for delivery order is important so we can’t load additional jobs mid-run without screwing up the delivery order access to the product in the vehicle.

Hi ,
Please share isDepot method .

We have multiple vehicles and every vehicle have different depot location.

I want know isDepot condition , please share this method deatils


Hi Srini

Sorry for the delay in reply. I have been travelling. Do you still want this ?


Hi, I posted a possible solution to this in this thread:


I have had the same requirement. Please ignore the references to stateManager. It is not used and I have not gotten around to remove it :frowning:

Please note that a key aspect of this solution is that not ALL pickup locations are depots. Sometimes it is necessary to do a pickup from somewhere on the route. If this is not the case in your situation there would be a much simpler approach.

public class HC_NoMidRunReloads implements HardActivityConstraint {
private  StateManager stateManager;
private  Set<String> depotList;
HC_NoMidRunReloads( StateManager stateManager, Set<String> depotList){
	int count = depotList == null ? 0 : depotList.size();
	this.stateManager = stateManager;
	this.depotList = depotList;
public ConstraintsStatus fulfilled(JobInsertionContext iFacts, TourActivity prevAct, TourActivity newAct, TourActivity nextAct, double prevActDepTime) {
	if((newAct instanceof PickupShipment) && isDepot(newAct.getLocation().getId()) == false)
		return ConstraintsStatus.FULFILLED;
	if((newAct instanceof PickupShipment && isDepot(newAct.getLocation().getId()))
			&& (isDepot(prevAct.getLocation().getId()) 
					||  isDepot(nextAct.getLocation().getId())
					|| nextAct instanceof End
					|| prevAct instanceof Start))
		return ConstraintsStatus.FULFILLED;
	if((newAct instanceof PickupShipment) && 
			(!( nextAct instanceof End)  && 
					(!(nextAct instanceof PickupShipment))) ){
			return ConstraintsStatus.NOT_FULFILLED;
	return ConstraintsStatus.FULFILLED;
private boolean isDepot(String name){
	if(depotList != null){
		for(String n: depotList){
				return true;
	return false;


In the main:
You will notice references to depotList. This is a simple hash list of depot location names. While reading in the job list we lookup the location name to see if it is a depot and add it to the depotList as:
if(isDepot) depotList.add(pickupName);

Set<String> depotList = **new** HashSet<String>();
ConstraintManager constraintManager = **new** ConstraintManager(problem, stateManager);
HC_NoMidRunReloads noMidRunReloads = **new** HC_NoMidRunReloads(stateManager, depotList);
constraintManager.addConstraint(noMidRunReloads,Priority. **HIGH** );

Please note I’m not saying this is the best or only way to handle “no topups” but it works for me.
If you have questions or suggestions please let me know.

I still have this problem and I’ve realized that it’s impossible to implement this as an activity constraint because you need to have access to the entire route to know if inserting a pickup somewhere invalidates the rest of the route. For instance:

  • 3 pickups with a delivery each: A, B, C

route starts as:
pickup A
deliver A

then it becomes:
pickup A
deliver A
pickup B
deliver B

then it tries to add the pickup for C and inserts it as such (passing constraints):
pickup C <- newly inserted because it passes the constraint
pickup A
deliver A
pickup B <- this pickup is now invalid because there are two pickups on board
deliver B

The problem is that when adding the pickup for C the only context we’re given is the prevAct and nextAct which isn’t enough context to accurately determine if the constraint was fulfilled or not. In my tests my constraint (and the ones outlined in this thread) produce an invalid route about 20% of the time.

So I think I need to use a ReverseActivityVisitor to add state to the activities so that at each activity i know how many other pickups there will be or something. Having trouble wrapping my head around it.

Hi Brian
I’ll think about this. It is interesting to me also.

@grantm009 thanks, i’ve also added it to GitHub: