GraphHopper.com | Forum | GitHub | Maps | Blog

Preventing load "top ups"


#1

Hi

Is there a way to prevent a vehicle from coming back to base to top up in the middle of a route ?

Example.

Vehicle has a capacity of 8 and 10 jobs to deliver each of size 1

JSPRIT produces a route that:
Pickups up 8 at depot
Delivers 2 jobs
Comes back to depot and picks up the remaining 2 jobs
continues and delivers the 8 loaded jobs.
returns to base.

This may be efficient for a route but is not possible for a loading dock that uses the route plan to load the vehicle in inverse delivery order.

We need to stop the vehicle coming back to depot to fill up while it still has jobs to deliver.

If there is no really simple way then my thoughts are:

create a hard constraint that says if it is a delivery and if the location is a depot and if the truck still has capacity utilised gt 0 then return no.

Is this possible in a hard constraint or is there an easier way ?

regards
Grant


No pickup should happen if it is not meant to be Delivered
#2

There is no easy way to implement this. You need to do this using hard constraint.
If newAct is pickupShipment and there was a DeliveryShipment activity before newAct and vehicle in not empty,
return ConstraintsStatus.NOT_FULFILLED_BREAK;


#3

Thanks Bhoumik_Shah

I can’t, so far, see how to determine if the vehicle is empty.

So far I have got:

public class HC_NoMidrunReloads implements HardActivityConstraint {
	@Override
	public ConstraintsStatus fulfilled(JobInsertionContext iFacts, TourActivity prevAct, TourActivity newAct,
			TourActivity nextAct, double prevActDepTime) {
		Vehicle v = iFacts.getNewVehicle();
		boolean notEmpty = v.?????
		if(newAct.getName().equalsIgnoreCase("pickupShipment") && prevAct.getName().equalsIgnoreCase("deliverShipment") && notEmpty)
			return ConstraintsStatus.NOT_FULFILLED_BREAK;		
		return ConstraintsStatus.FULFILLED;
	}	
}

Can you help with that ?

regards
Grant


#4

you can use the load state updater.

note that, if newAct is a DeliverShipment, you will need to add the load of the corresponding PickupShipment, because it won’t be part of the load retrieved from the state.


#5

Thanks He

I looked at state manager. After I picked myself up off the floor my first thought was - thats big.

I found an example that you gave to @Bhoumik_Shah for maximum trip duration constraint.
So I have made some progress and currently have the code below as the fundamental structure.
But Im not completely sure on how to calculate the currentLoad. Perhaps you could guide me on that.

public class HC_NoMidrunReloads implements HardActivityConstraint {
	private final StateManager stateManager;
	private final StateId stateId;
	HC_NoMidrunReloads(double maxDuration, StateManager stateManager, VehicleRoutingTransportCostsMatrix transportCosts){
		this.stateManager = stateManager;
		this.stateId = this.stateManager.createStateId("currentVehicleLoad");
	}	
	@Override
	public ConstraintsStatus fulfilled(JobInsertionContext iFacts, TourActivity prevAct, TourActivity newAct, TourActivity nextAct, double prevActDepTime) {
		boolean isEmpty = this.stateManager.getRouteState(iFacts.getRoute(), stateId, Double.class) == 0 ? true : false;
		if((newAct instanceof PickupShipment && prevAct instanceof DeliverShipment) && !isEmpty)
			return ConstraintsStatus.NOT_FULFILLED_BREAK;
		return ConstraintsStatus.FULFILLED;
	}
}

and

public class LoadStatusMonitor implements StateUpdater, RouteVisitor {
	private StateManager stateManager;
	private StateId stateId;
	public LoadStatusMonitor(StateManager stateManager, VehicleRoutingTransportCosts routingCosts){
		super();
		this.stateManager = stateManager;
		this.stateId = this.stateManager.createStateId("currentVehicleLoad");
	}
	@Override
	public void visit(VehicleRoute route) {
		if(!route.isEmpty()) {
			double currentLoadSize = 0.0;

			
			
			this.stateManager.putRouteState(route,  this.stateId, currentLoadSize);
		}
	}
}

Its that middle bit in LoadStatusMonitor I don’t get. Would it be to iterate over the activities in the route until the current activity = the currentIterationActivity and add the activity sizes ?

Your guidance would be appreciated

kind regards
Grant


#6

Route State: Are the states associated with entire route. (e.g: Start time, Max load, End time etc):
Activity State: States associated with a particular activity (e.g: Load, Future waiting etc.)

To get load at previous activity from state manager you need to use following line of code:

stateManager.getActivityState(prevAct, InternalStates.LOAD, Capacity.class);

I hope that helps.


#7

OK Making some progress however - although the constructor is called the fulfilled function never seems to be called.
Can anyone pick what I have done wrong ?

thanks

public class HC_NoMidRunReloads implements HardActivityConstraint {
	private  StateManager stateManager;
	private  List<String> depotList;
	HC_NoMidRunReloads(double maxDuration, StateManager stateManager, VehicleRoutingTransportCostsMatrix transportCosts){
		Utils.LOGGER.log(Level.INFO, " HC_NoMidRunReloads multi arg started");
		this.stateManager = stateManager;
	}
	HC_NoMidRunReloads(List<String> depotList){
		Utils.LOGGER.log(Level.INFO, " HC_NoMidRunReloads one arg started");

		this.depotList = depotList;
	}	

	@Override
	public ConstraintsStatus fulfilled(JobInsertionContext iFacts, TourActivity prevAct, TourActivity newAct, TourActivity nextAct, double prevActDepTime) {
		Utils.LOGGER.log(Level.INFO, " LOOKING AT " + newAct.getName() + " for depot status");
		if(isDepot(newAct.getLocation().getName())){
			Utils.LOGGER.log(Level.INFO, " FOUND " + newAct.getName() + " to a depot");
		}
		boolean isEmpty = stateManager.getActivityState(prevAct, InternalStates.LOAD, Capacity.class).get(0) == 0 ? true : false;
		if((newAct instanceof PickupShipment && prevAct instanceof DeliverShipment) && !isEmpty){
			if(isDepot(newAct.getLocation().getName())){
				Utils.LOGGER.log(Level.INFO, " REJECTED  "+ newAct.getName() + " to a depot");
				return ConstraintsStatus.NOT_FULFILLED_BREAK;
			}
		}
		return ConstraintsStatus.FULFILLED;
	}
	private boolean isDepot(String name){
		for(String n: depotList){
			if(n.equalsIgnoreCase(name))
				return true;
		}
		return false;
	}

In Main I call

        ConstraintManager constraintManager = new ConstraintManager(problem, stateManager);
		Map<String, List<String>> HC_NoMidRunReloadsMap = new HashMap<String, List<String>>();
		HC_NoMidRunReloadsMap.put("depots", depotList);
		HC_SpecificVehicleForJob svfj = new HC_SpecificVehicleForJob(jobVehicleMap);
		HC_NoMidRunReloads noMidRunReloads = new HC_NoMidRunReloads(stateManager, depotList);
		constraintManager.addConstraint(svfj);
		constraintManager.addConstraint(noMidRunReloads,Priority.HIGH);

#8

OK I worked it out.

String Lesson = “read the fine print”;


#9

just wondering, how do you handle the case that newAct instanceof DeliverShipment?


#10

There’s a simpler way to do this. Just provide your own implementation of TransportCost and - in addition to the normal transport cost - add an extra really big cost that’s only applied between different locations (i.e. never applied between the same location).

This ‘parkingCost’ (the term I use in the next release of ODL Studio - I implemented this for a client a while back in a pre-release version) should be bigger than any other cost. It’s not applied between consecutive pickups at the depot (because they’re at the same location), so the cheapest solution will be the one where the depot pickups are all bunched together.


#11

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.


#12

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…


#13

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))){
    if(isDepot(newAct.getLocation().getId()))
        return ConstraintsStatus.NOT_FULFILLED_BREAK;
}
return ConstraintStatus.FULFILLED;

#14

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.


#15

I’m glad I could help.


#16

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,
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);

#17

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


#18

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


#19

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.


#20

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.