Preventing load "top ups"

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,
He

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

Regard
Srini

Hi Srini

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

regards
Grant

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

Hi

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;
}
@Override
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))) ){
		if(isDepot(newAct.getLocation().getId())){
			return ConstraintsStatus.NOT_FULFILLED;
		}
	}
	return ConstraintsStatus.FULFILLED;
}
private boolean isDepot(String name){
	if(depotList != null){
		for(String n: depotList){
			if(n.equalsIgnoreCase(name)){
				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);
constraintManager.addLoadConstraint();
constraintManager.addTimeWindowConstraint();
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.
regards
Grant

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.
regards
Grant

@grantm009 thanks, i’ve also added it to GitHub: https://github.com/graphhopper/jsprit/issues/475