Preventing load "top ups"

jie31best · June 5, 2017, 7:09am

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

    double x = 20;
    VehicleTypeImpl type = VehicleTypeImpl.Builder.newInstance("type")
            .addCapacityDimension(0, 2)
            .build();
    VehicleImpl v1 = VehicleImpl.Builder.newInstance("v1")
            .setType(type)
            .setReturnToDepot(false)
            .setStartLocation(Location.newInstance(0, 0))
            .build();
    Shipment s1 = Shipment.Builder.newInstance("s1")
            .setPickupLocation(Location.newInstance(0, 0))
            .setDeliveryLocation(Location.newInstance(x, 0))
            .addSizeDimension(0, 1)
            .build();
    Shipment s2 = Shipment.Builder.newInstance("s2")
            .setPickupLocation(Location.newInstance(0, 0))
            .setDeliveryLocation(Location.newInstance(x, 0))
            .addSizeDimension(0, 1)
            .build();
    Shipment s3 = Shipment.Builder.newInstance("s3")
            .setPickupLocation(Location.newInstance(0, 0))
            .setDeliveryLocation(Location.newInstance(0, 100))
            .addSizeDimension(0, 1)
            .build();
    VehicleRoutingProblem vrp = VehicleRoutingProblem.Builder.newInstance()
            .addJob(s1)
            .addJob(s2)
            .addJob(s3)
            .addVehicle(v1)
            .setFleetSize(VehicleRoutingProblem.FleetSize.FINITE)
            .build();

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

    constraintManager.addConstraint(
            new HardActivityConstraint() {
                @Override
                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(
                                newAct.getLocation().getCoordinate()))
                            return ConstraintsStatus.NOT_FULFILLED_BREAK;
                    }
                    return ConstraintsStatus.FULFILLED;
                }
            },
            ConstraintManager.Priority.HIGH);

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

grantm009 · June 5, 2017, 9:12am

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.

regards
Grant

jie31best · June 6, 2017, 2:28am

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

grantm009 · June 6, 2017, 2:46am

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.

Denzil_Martin · August 8, 2017, 7:23am

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");
}

@Override
public ConstraintsStatus fulfilled(JobInsertionContext jobInsertionContext, TourActivity prevAct,
		TourActivity newAct, TourActivity nextAct, double departureTimeAtPrevAct) {
      if((newAct instanceof PickupShipment) &&
	         (!(nextAct instanceof End) && 
	          !(nextAct instanceof PickupShipment))){
	    if(isDepot(newAct.getLocation().getId()))
	        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.

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