Preventing load "top ups"

jie31best · January 22, 2018, 9:54am

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

grantm009 · May 13, 2018, 10:21pm

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.

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

Srinivasa_Chakravart · January 10, 2019, 11:53am

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

grantm009 · February 4, 2019, 9:40pm

Hi Srini

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

regards
Grant

mrichter · April 29, 2019, 10:22pm

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

grantm009 · June 15, 2019, 6:42am

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

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

briandilley · July 12, 2019, 6:36am

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.

briandilley · July 13, 2019, 8:56pm

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.

grantm009 · July 14, 2019, 10:23pm

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

briandilley · July 15, 2019, 4:43pm

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

sarita_panigrahi · November 1, 2021, 2:38pm

Hi,

Is there any way to restrict the load top up in the middle of a route ? I have been going through all the suggested constraints but none seems to work. Please help. I am stuck. I am using version 4.0

Regards,
Sarita

sarita_panigrahi · November 1, 2021, 7:05pm

Hi

I have one vehicle and eight shipments to deliver and one pickup location. The vehicle has capacity to complete the whole route without going back to depot. But i am getting the solution where the vehicle goes back to the depot without delivering all shipment. We are using this amazing library in a drug distribution system where the vehicle re-loading needs to occur only if capacity constraint violets. But in this particular case we are stuck.

First: If vehicle has capacity it should not pickup multiple times
Second: Even if it does, it should deliver all the shipment before any further pickup

I have tried implementing PendingDeliveriesUpdater , HC_NoMidRunReloads , HC_NoMidRunReloads4EXP but no success.

Here is the solution i am getting.

--------------------- | detailed solution ±--------±--------- | route | vehicle ±--------±--------- | 1 | KA50A7409 | 1 | KA50A7409 | 1 | KA50A7409 | 1 | KA50A7409 | 1 | KA50A7409 | 1 | KA50A7409 | 1 | KA50A7409 | 1 | KA50A7409 | 1 | KA50A7409 | 1 | KA50A7409 | 1 | KA50A7409 | 1 | KA50A7409 | 1 | KA50A7409 | 1 | KA50A7409 | 1 | KA50A7409 | 1 | KA50A7409 | 1 | KA50A7409 | 1 | KA50A7409 ±------------------- ------ -----------------------------------------------------------------------------------------------------------+
|
------------±----------------------±----------------±----------------±----------------±----------------+
| activity | job | arrTime | endTime | costs |
------------±----------------------±----------------±----------------±----------------±----------------+
| start | - | undef | 600 | 0 |
| pickupShipment | ICTC - Vydehi Medical College & Hospital, Vija Nag_7833 | 600 | 610 | 0 |
| pickupShipment | ICTC - General Hospital, K.R. Puram, BU_7396 | 610 | 620 | 0 |
| pickupShipment | ICTC - K.C. General Hospital, Shivajinagar, BU_7402 | 620 | 630 | 0 |
| pickupShipment | ICTC - Unani Medical College(SJIIM), K. R. Market_7415 | 630 | 640 | 0 |
| pickupShipment | ICTC - ESI Hospital, Indiranagar, Okalipuram, BU_7410 | 640 | 650 | 0 |
| deliverShipment | ICTC - ESI Hospital, Indiranagar, Okalipuram, BU_7410 | 656 | 716 | 43 |
| deliverShipment | ICTC - K.C. General Hospital, Shivajinagar, BU_7402 | 725 | 785 | 115 |
| deliverShipment | ICTC - General Hospital, K.R. Puram, BU_7396 | 816 | 876 | 338 |
| deliverShipment | ICTC - Vydehi Medical College & Hospital, Vija Nag_7833 | 899 | 959 | 507 |
| pickupShipment | ICTC - Hosahalli Referal Hospital, Chamaraj Road,_7830 | 1004 | 2050 | 3436 |
| pickupShipment | ICTC - Bowring & Lady Curzon Hospital, City Market_7401 | 2050 | 2060 | 3436 |
| pickupShipment | ICTC - Srirampura Referal Hospital, Goripalya, BU_7831 | 2060 | 2070 | 3436 |
| deliverShipment | ICTC - Srirampura Referal Hospital, Goripalya, BU_7831 | 2074 | 2134 | 3467 |
| deliverShipment | ICTC - Hosahalli Referal Hospital, Chamaraj Road,_7830 | 2135 | 2195 | 3475 |
| deliverShipment | ICTC - Bowring & Lady Curzon Hospital, City Market_7401 | 2199 | 2259 | 3506 |
| deliverShipment | ICTC - Unani Medical College(SJIIM), K. R. Market_7415 | 2262 | 2322 | 3527 |
| end | - | 2328 | undef | 3572 |
------------------------------------------------------------------------------------------------------------+

any help would be greatly appreciated.

regards,
Sarita

m.essi · November 2, 2021, 8:05am

I think I found a tricky way to prevent top-ups.

There are two kinds of top-ups:
The first, is when the vehicle has pickups from a depot and before delivering all of them, comes back to the same depot to pick up again. And the second, is when it goes to another depot.

The first kind of top-up, could be solved easily just by modifying the output. The point is that there are some pickups that could be postponed. Theses are stuffs which had been picked up in the first run, but delivered in the 2nd or … run. You could postpone these pickups to the run that they will be delivered. Note that this change does not cause any overflow in the capacity of the vehicle and make no changes on solution optimality.

For solving the second kind of top-up, note that every route which has this kind of top-up surely has:
Two consecutive deliveries which have been picked up from different depots.
or
A pickup from depot D followed by a delivery which its depot is not D.

This could be prevented by some modifications in transport costs. Just add a very big constant to the transport cost between every two delivery locations which are from different depots () and to the transport cost of trips from a depot to a demand location which is not from that depot. ()

ifley · November 6, 2021, 6:26pm

Would you please provide a sample of the code?

grantm009 · November 7, 2021, 10:20pm

Hi Sarita

Did you solve that problem? If not, let me know and I will try to help you.

regards
Gmax

sarita_panigrahi · November 9, 2021, 12:03pm

Hi @ifley @grantm009

I have tried to put the hard constraint to prevent pickup if load is there with the following piece of code.

		if (prevIsDepot && !newIsDepot && nextIsDepot && pendingExternalDeliveries > 0) {
			return ConstraintsStatus.NOT_FULFILLED;
		}
		if (!prevIsDepot && !newIsDepot && nextIsDepot && pendingExternalDeliveries > 0) {
			return ConstraintsStatus.NOT_FULFILLED;
		}
		if (!prevIsDepot && newIsDepot && pendingExternalDeliveries > 0) {
			return ConstraintsStatus.NOT_FULFILLED;
		}

But still not getting the expected result. Please let me know how can I solve this problem.

regards,
Sarita

sarita_panigrahi · November 9, 2021, 12:06pm

Hi @m.essi,

I have only one depot and multiple delivery shipment, how to handle in that case.

regards,
Sarita

grantm009 · November 20, 2021, 4:50am

Hi Sarita

I use a hard constraint and it works fine. It considers:

if the activity is a pickup is it at a depot (could be from a supplier or other location)
pickups from depots can only be at the start of the run
pickups from non-depots can be during the run

I hope it helps.

@Override
public ConstraintsStatus fulfilled(JobInsertionContext iFacts, TourActivity prevAct, TourActivity newAct, TourActivity nextAct, double prevActDepTime) {
boolean atDepot = isDepot(newAct.getLocation().getId());
if(iFacts.getRoute().getActivities().size() < 3)
return ConstraintsStatus.FULFILLED;

List tasks = iFacts.getRoute().getActivities();
if(newAct instanceof DeliverShipment && nextAct.getIndex() == -1 )
return ConstraintsStatus.FULFILLED;

if(newAct instanceof DeliverShipment && !atDepot) {
for(TourActivity act: tasks) {
if(act.getIndex() >= prevAct.getIndex() && isDepot(act.getLocation().getId()) ) {
return ConstraintsStatus.NOT_FULFILLED;
}
}
}
if(newAct instanceof PickupShipment && atDepot) {
if(prevAct.getIndex() == -1) // at start of route
return ConstraintsStatus.FULFILLED;
for(TourActivity act: tasks) {
if(act.getIndex() <= prevAct.getIndex() && !isDepot(act.getLocation().getId()) ) {
return ConstraintsStatus.NOT_FULFILLED_BREAK;
}
}
}
return ConstraintsStatus.FULFILLED;

}

private boolean isDepot(String name){
if(depotList != null){
for(String n: depotList){

if(n.equalsIgnoreCase(name)){
return true;
}
}
}
return false;
}

sarita_panigrahi · November 22, 2021, 7:51am

Hi @grantm009

Thank you so much for your time. I have implemented the hard constraint, the in between pickup during delivery of shipments issue is fixed. However, the vehicle goes to depot multiple times, where it can pickup all the shipments at once at the start of the route (as the capacity constraint is not getting violated).
Additionally, the shipments have pickupTimeWindows and deliveryTimeWindows. I have also implemented AbeProblemMinMax to minimize the overall transport time. But, the current solution takes more time as it again goes to depot for pickup. Please let me know if I am missing anything.

Please find below the detailed solution:

±--------±---------------------±----------------------±----------------±----------------±----------------±----------------+
| route | vehicle | activity | job | arrTime | endTime | costs |
±--------±---------------------±----------------------±----------------±----------------±----------------±----------------+
| 1 | KA50A7409 | start | - | undef | 600 | 0 |
| 1 | KA50A7409 | pickupShipment | ICTC - Vydehi Medical College & Hospital, Vija Nag_7833 | 600 | 610 | 0 |
| 1 | KA50A7409 | deliverShipment | ICTC - Vydehi Medical College & Hospital, Vija Nag_7833 | 655 | 715 | 339 |
| 1 | KA50A7409 | pickupShipment | ICTC - K.C. General Hospital, Shivajinagar, BU_7402 | 760 | 770 | 679 |
| 1 | KA50A7409 | pickupShipment | ICTC - Bowring & Lady Curzon Hospital, City Market_7401 | 770 | 780 | 679 |
| 1 | KA50A7409 | pickupShipment | ICTC - ESI Hospital, Indiranagar, Okalipuram, BU_7410 | 780 | 790 | 679 |
| 1 | KA50A7409 | pickupShipment | ICTC - Hosahalli Referal Hospital, Chamaraj Road,_7830 | 790 | 800 | 679 |
| 1 | KA50A7409 | pickupShipment | ICTC - Unani Medical College(SJIIM), K. R. Market_7415 | 800 | 810 | 679 |
| 1 | KA50A7409 | pickupShipment | ICTC - General Hospital, K.R. Puram, BU_7396 | 810 | 820 | 679 |
| 1 | KA50A7409 | pickupShipment | ICTC - Srirampura Referal Hospital, Goripalya, BU_7831 | 820 | 830 | 679 |
| 1 | KA50A7409 | deliverShipment | ICTC - Srirampura Referal Hospital, Goripalya, BU_7831 | 834 | 894 | 710 |
| 1 | KA50A7409 | deliverShipment | ICTC - Unani Medical College(SJIIM), K. R. Market_7415 | 901 | 2100 | 3606 |
| 1 | KA50A7409 | deliverShipment | ICTC - K.C. General Hospital, Shivajinagar, BU_7402 | 2108 | 2168 | 3668 |
| 1 | KA50A7409 | deliverShipment | ICTC - Bowring & Lady Curzon Hospital, City Market_7401 | 2177 | 2237 | 3737 |
| 1 | KA50A7409 | deliverShipment | ICTC - ESI Hospital, Indiranagar, Okalipuram, BU_7410 | 2247 | 2307 | 3804 |
| 1 | KA50A7409 | deliverShipment | ICTC - Hosahalli Referal Hospital, Chamaraj Road,_7830 | 2312 | 2372 | 3845 |
| 1 | KA50A7409 | deliverShipment | ICTC - General Hospital, K.R. Puram, BU_7396 | 2412 | 4980 | 10411 |
| 1 | KA50A7409 | end | - | 5016 | undef | 10688 |
±-------------------------------------------------------------------------------------------------------------------------------+
------

regards,
Sarita

grantm009 · November 22, 2021, 10:14am

Hi Sarita

Thats an interesting problem. I suggest you look at the service times during pickups. The accumulated time might be forcing the truck to leave before fully loading in order to satisfy time windows ?