GraphHopper.com | Forum | GitHub | Maps | Blog

Maximum trip distance constraint


#1

I’m trying to implement maximum trip distance constraint using hardactivityConstraint and State manager as follows:

`/**

  • Created by Bhoumik Shah on 5/30/2016.
    */
    public class maxTripDistanceConstraint {

    static class DistanceUpdater implements StateUpdater, ActivityVisitor {

     private final StateManager stateManager;
    
     private final VehicleRoutingTransportCostsMatrix costsMatrix;
    
     private final GreatCircleCosts greatCircleCosts;
    
     //        private final StateFactory.StateId distanceStateId;    //v1.3.1
     private final StateId distanceStateId; //head of development - upcoming release
    
     private VehicleRoute vehicleRoute;
    
     private double distance = 0.;
    
     private TourActivity prevAct;
    
     //        public DistanceUpdater(StateFactory.StateId distanceStateId, StateManager stateManager, VehicleRoutingTransportCostsMatrix costMatrix) { //v1.3.1
     public DistanceUpdater(StateId distanceStateId, StateManager stateManager, VehicleRoutingTransportCostsMatrix transportCosts) { //head of development - upcoming release (v1.4)
         this.costsMatrix = transportCosts;
         this.greatCircleCosts = null;
         this.stateManager = stateManager;
         this.distanceStateId = distanceStateId;
     }
    
     public DistanceUpdater(StateId distanceStateId, StateManager stateManager, GreatCircleCosts greatCircleCosts) { //head of development - upcoming release (v1.4)
         this.costsMatrix = null;
         this.greatCircleCosts = greatCircleCosts;
         this.stateManager = stateManager;
         this.distanceStateId = distanceStateId;
     }
    
    
     public void begin(VehicleRoute vehicleRoute) {
         distance = 0.;
         prevAct = vehicleRoute.getStart();
         this.vehicleRoute = vehicleRoute;
     }
    
    
     public void visit(TourActivity tourActivity) {
         distance += getDistance(prevAct, tourActivity);
         prevAct = tourActivity;
     }
    
    
     public void finish() {
         distance += getDistance(prevAct, vehicleRoute.getEnd());
    

// stateManager.putTypedRouteState(vehicleRoute,distanceStateId,Double.class,distance); //v1.3.1
stateManager.putRouteState(vehicleRoute, distanceStateId, distance); //head of development - upcoming release (v1.4)
}

    double getDistance(TourActivity from, TourActivity to) {
        if(this.costsMatrix == null)
            return  this.greatCircleCosts.getDistance(from.getLocation(),to.getLocation(),0.,null);
        else
            return this.costsMatrix.getDistance(from.getLocation().getId(), to.getLocation().getId());
    }
}

static class DistanceConstraint implements HardActivityConstraint {

    private final StateManager stateManager;

    private final VehicleRoutingTransportCostsMatrix costsMatrix;

    private final double maxDistance;

    private final GreatCircleCosts greatCircleCosts;

    //        private final StateFactory.StateId distanceStateId; //v1.3.1
    private final StateId distanceStateId; //head of development - upcoming release (v1.4)

    //        DistanceConstraint(double maxDistance, StateFactory.StateId distanceStateId, StateManager stateManager, VehicleRoutingTransportCostsMatrix costsMatrix) { //v1.3.1
    DistanceConstraint(double maxDistance, StateId distanceStateId, StateManager stateManager, VehicleRoutingTransportCostsMatrix transportCosts) { //head of development - upcoming release (v1.4)
        this.costsMatrix = transportCosts;
        this.greatCircleCosts = null;
        this.maxDistance = maxDistance;
        this.stateManager = stateManager;
        this.distanceStateId = distanceStateId;
    }

    DistanceConstraint(double maxDistance, StateId distanceStateId, StateManager stateManager, GreatCircleCosts greatCircleCosts) { //head of development - upcoming release (v1.4)
        this.costsMatrix = null;
        this.greatCircleCosts = greatCircleCosts;
        this.maxDistance = maxDistance;
        this.stateManager = stateManager;
        this.distanceStateId = distanceStateId;
    }


    public ConstraintsStatus fulfilled(JobInsertionContext context, TourActivity prevAct, TourActivity newAct, TourActivity nextAct, double v) {
        double additionalDistance = getDistance(prevAct, newAct) + getDistance(newAct, nextAct) - getDistance(prevAct, nextAct);
        Double routeDistance = stateManager.getRouteState(context.getRoute(), distanceStateId, Double.class);
        if (routeDistance == null) routeDistance = 0.;
        double newRouteDistance = routeDistance + additionalDistance;
        if (newRouteDistance > maxDistance) {
            return ConstraintsStatus.NOT_FULFILLED;
        } else return ConstraintsStatus.FULFILLED;
    }

    double getDistance(TourActivity from, TourActivity to) {
        if(this.costsMatrix == null)
            return  this.greatCircleCosts.getDistance(from.getLocation(),to.getLocation(),0.,null);
        else
            return this.costsMatrix.getDistance(from.getLocation().getId(), to.getLocation().getId());
    }

}

}

But I’m getting length of route greater than maximum allowed maximum distance. Could you please help me where did I go wrong?


#2

Hi @Bhoumik_Shah,

You need to cater for the following case in your constraint (not sure if this is the cause of your issue, though):

if (nextAct instanceof End && !context.getNewVehicle().isReturnToDepot())

Best regards,
He


#3

Hi @jie31best,

Thanks for reply. I added the above case in constraint. But it was not causing the issue.

I found the issue:
Double routeDistance = stateManager.getRouteState(context.getRoute(), distanceStateId, Double.class);

is always giving null distance.
When I ran debugger I found that in context route is always empty, even if there are activities in context.

See the image attached below:


#4

Hi @jie31best ,

Issue here is while adding Delivery activity of a Shipment to the route PickUp activity is not present in the context. Hence the additional distance due to Pickup activity is ignored.

How do we go about solving this issue?


#5

In such case, context.getRelatedActivityContext().getInsertionIndex() will return you the index of the PickupShipment activity insertion. From there, you can retrieve the activities before and after the PickupShipment activity and calculate the additional distance.

Note that you will need to cater for the case where prevAct is the PickupShipment.


#6

@stefan, this state and shipment issue seems haunting us everywhere, lol…


#7

@jie31best Any suggestion to simplify this?


#8

Hi @stefan,

If we make a duplicate of all the states, label them as “shipmentInsertionTempState” or so, and update them (or the related ones) after the pickupShipmentLoop in the ShipmentInsertionCalculator, will it be very time-consuming?

Best regards,
He


#9

Hi @jie31best,

I was thinking of making a duplicate of all the states. .

Anyway, for time being I have implemented the maximum distance using context.getRelatedActivityContext().getInsertionIndex() .as follows:

In the case when route is empty and newAct is instance of DeliveryShipment I make activity previous to Pickup as start activity. As follows
if(context.getRoute().getTourActivities().getActivities().size() == 0){ prevtoPickupActivity = context.getRoute().getStart(); nexttoPickupActivity = nextAct;

but issue here is context.getRoute.getStart() gives activity with null startID.

How do I get start activity from the context?


#10

When the route is empty, you just need to calculate the distance of the route after insertion of the Shipment as d1 + d2 + d3, where:

d1 = the distance from start location to the PickupShipment location, the former of which can be obtained by context.getNewVehicle().getStartLocation(), and the latter by prevAct.getLocation();

d2 = the distance from the PickupShipment location to the DeliverShipment location, which is simply from prevAct.getLocation() to newAct.getLocation();

d3 = 0 if (!context.getNewVehicle().isReturnToDepot()), else the distance from the DeliverShipment location to the vehicle end location, i.e., from newAct.getLocation() to context.getNewVehicle().getEndLocation().


#11

Hi He,

Thanks for your help. I implemented the constraint.

But I am getting weird results in some cases.

If I keep cost per unassigned package very high, is it possible to that a Hard Constraint with Critical priority will be violated just to serve that package?


#12

Hi @jie31best, @stefan,

Please have a look at case:

Problem Sample problem code:

`

public static void main(String[] args) {
    /*
     * some preparation - create output folder
	 */
    File dir = new File("output");
    // if the directory does not exist, create it
    if (!dir.exists()) {
        System.out.println("creating directory ./output");
        boolean result = dir.mkdir();
        if (result) System.out.println("./output created");
    }

    /*
    Create locations and distance matrix
     */
    Location loc_1 = Location.newInstance("loc_1");
    Location loc_2 = Location.newInstance("loc_2");
    Location loc_3 = Location.newInstance("loc_3");

    VehicleRoutingTransportCostsMatrix.Builder costMatrixBuilder = VehicleRoutingTransportCostsMatrix.Builder.newInstance(true);
    costMatrixBuilder.addTransportDistance(loc_1.getId(),loc_2.getId(),2500);
    costMatrixBuilder.addTransportDistance(loc_1.getId(),loc_3.getId(),2500);
    costMatrixBuilder.addTransportDistance(loc_2.getId(),loc_3.getId(),500);

    VehicleRoutingTransportCostsMatrix costsMatrix =costMatrixBuilder.build();

	/*
     * get a vehicle type-builder and build a type with the typeId "vehicleType" and one capacity dimension, i.e. weight, and capacity dimension value of 2
	 */

    VehicleTypeImpl.Builder vehicleTypeBuilder = VehicleTypeImpl.Builder.newInstance("VehicleType").addCapacityDimension(0, 1).setCostPerDistance(1).setFixedCost(10);
    VehicleType vehicleType = vehicleTypeBuilder.build();

	/*
     * get a vehicle-builder and build a vehicle located at (10,10) with type "vehicleType"
	 */
    Builder V1Builder = VehicleImpl.Builder.newInstance("V1");
    V1Builder.setStartLocation(loc_1).setReturnToDepot(true);
    V1Builder.setType(vehicleType);
    VehicleImpl V1 = V1Builder.build();

    Builder V3Builder = VehicleImpl.Builder.newInstance("V3");
    V3Builder.setStartLocation(loc_3).setReturnToDepot(true);
    V3Builder.setType(vehicleType);
    VehicleImpl V3 = V3Builder.build();

	/*
     * build services at the required locations, each with a capacity-demand of 1.
	 */
    Shipment P1 = Shipment.Builder.newInstance("P1").addSizeDimension(0, 1).setPickupLocation(loc_3).setDeliveryLocation(loc_1).build();
    Shipment P2 = Shipment.Builder.newInstance("P2").addSizeDimension(0,1).setPickupLocation(loc_3).setDeliveryLocation(loc_2).build();


    VehicleRoutingProblem.Builder vrpBuilder = VehicleRoutingProblem.Builder.newInstance();
    vrpBuilder.addVehicle(V1).addVehicle(V3);
    vrpBuilder.addJob(P1).addJob(P2);
    VehicleRoutingProblem problem = vrpBuilder.setRoutingCost(costsMatrix).build();

    /*
    Add constraints
     */

    //Add default constraints
    StateManager stateManager = new StateManager(problem);
    stateManager.updateSkillStates();
    ConstraintManager constraintManager = new ConstraintManager(problem, stateManager);
    constraintManager.addSkillsConstraint();
    StateId distanceStateId = stateManager.createStateId("total_distance");
    Double maxDistance = 1500.;
    stateManager.addStateUpdater(new maxTripDistanceConstraint.DistanceUpdater(distanceStateId, stateManager, costsMatrix));
    constraintManager.addConstraint(new maxTripDistanceConstraint.DistanceConstraint(maxDistance, distanceStateId, stateManager, costsMatrix),ConstraintManager.Priority.CRITICAL);



	/*
     * get the algorithm out-of-the-box.
	 */
    VehicleRoutingAlgorithm algorithm = Jsprit.Builder.newInstance(problem).addCoreStateAndConstraintStuff(true).setStateAndConstraintManager(stateManager,constraintManager).buildAlgorithm();
    algorithm.setMaxIterations(3);

	/*
     * and search a solution
	 */
    Collection<VehicleRoutingProblemSolution> solutions = algorithm.searchSolutions();

	/*
     * get the best
	 */
    VehicleRoutingProblemSolution bestSolution = Solutions.bestOf(solutions);

    new VrpXMLWriter(problem, solutions).write("output/problem-with-solution.xml");

    SolutionPrinter.print(problem, bestSolution, SolutionPrinter.Print.VERBOSE);

}

Distance Constraint implementation:

`public class maxTripDistanceConstraint {

static class DistanceUpdater implements StateUpdater, ActivityVisitor {

    private final StateManager stateManager;

    private final VehicleRoutingTransportCostsMatrix costsMatrix;


    //        private final StateFactory.StateId distanceStateId;    //v1.3.1
    private final StateId distanceStateId; //head of development - upcoming release

    private VehicleRoute vehicleRoute;

    private double distance = 0.;

    private TourActivity prevAct;

    //        public DistanceUpdater(StateFactory.StateId distanceStateId, StateManager stateManager, VehicleRoutingTransportCostsMatrix costMatrix) { //v1.3.1
    public DistanceUpdater(StateId distanceStateId, StateManager stateManager, VehicleRoutingTransportCostsMatrix transportCosts) { //head of development - upcoming release (v1.4)
        this.costsMatrix = transportCosts;
        this.stateManager = stateManager;
        this.distanceStateId = distanceStateId;
    }



    public void begin(VehicleRoute vehicleRoute) {
        distance = 0.;
        prevAct = vehicleRoute.getStart();
        this.vehicleRoute = vehicleRoute;
    }


    public void visit(TourActivity tourActivity) {
        distance += getDistance(prevAct, tourActivity);
        prevAct = tourActivity;
    }


    public void finish() {
        distance += getDistance(prevAct, vehicleRoute.getEnd());
        stateManager.putRouteState(vehicleRoute, distanceStateId, distance); //head of development - upcoming release (v1.4)
    }

    double getDistance(TourActivity from, TourActivity to) {
            return this.costsMatrix.getDistance(from.getLocation().getId(), to.getLocation().getId());
    }
}


static class DistanceConstraint implements HardActivityConstraint {

    private final StateManager stateManager;

    private final VehicleRoutingTransportCostsMatrix costsMatrix;

    private final double maxDistance;


    //        private final StateFactory.StateId distanceStateId; //v1.3.1
    private final StateId distanceStateId; //head of development - upcoming release (v1.4)

    //        DistanceConstraint(double maxDistance, StateFactory.StateId distanceStateId, StateManager stateManager, VehicleRoutingTransportCostsMatrix costsMatrix) { //v1.3.1
    DistanceConstraint(double maxDistance, StateId distanceStateId, StateManager stateManager, VehicleRoutingTransportCostsMatrix transportCosts) { //head of development - upcoming release (v1.4)
        this.costsMatrix = transportCosts;
        this.maxDistance = maxDistance;
        this.stateManager = stateManager;
        this.distanceStateId = distanceStateId;
    }



    public ConstraintsStatus fulfilled(JobInsertionContext context, TourActivity prevAct, TourActivity newAct, TourActivity nextAct, double v) {
        double additionalDistance = 0.;
        double pickupDistance = 0.;

        if(newAct instanceof DeliverShipment) {
            if(((DeliverShipment) newAct).getJob().getId().equals("P2") && context.getNewVehicle().getId().equals("V1"))
                System.out.print("P2 delivery by V1");
            TourActivity pickupActivity = context.getAssociatedActivities().get(0);
            TourActivity prevtoPickupActivity = null;
            TourActivity nexttoPickupActivity = null;
            int insertionIndex = context.getRelatedActivityContext().getInsertionIndex();
            if(context.getRoute().getTourActivities().getActivities().size() == 0){
                Double routeDistance = getDistance(pickupActivity,newAct);
                    routeDistance += this.costsMatrix.getDistance(context.getNewVehicle().getStartLocation().getId(),pickupActivity.getLocation().getId());
                if(context.getNewVehicle().isReturnToDepot())
                    routeDistance += getDistance(newAct,nextAct);
                if(routeDistance > this.maxDistance )return ConstraintsStatus.NOT_FULFILLED;
                else return ConstraintsStatus.FULFILLED;
            }else if (insertionIndex == 0) {
                prevtoPickupActivity = context.getRoute().getStart();
                nexttoPickupActivity = context.getRoute().getTourActivities().getActivities().get(0);
            } else if (insertionIndex == context.getRoute().getTourActivities().getActivities().size()) {
                prevtoPickupActivity = context.getRoute().getTourActivities().getActivities().get(insertionIndex - 1);
                nexttoPickupActivity = context.getRoute().getEnd();
            } else {
                prevtoPickupActivity = context.getRoute().getTourActivities().getActivities().get(insertionIndex - 1);
                nexttoPickupActivity = context.getRoute().getTourActivities().getActivities().get(insertionIndex);
            }
            if (nexttoPickupActivity instanceof End && !context.getNewVehicle().isReturnToDepot())
                pickupDistance = getDistance(prevtoPickupActivity, pickupActivity);
            else
                pickupDistance = getDistance(prevtoPickupActivity, pickupActivity) + getDistance(pickupActivity, nexttoPickupActivity) - getDistance(prevtoPickupActivity, nexttoPickupActivity);
        }


        if (nextAct instanceof End && !context.getNewVehicle().isReturnToDepot())
            additionalDistance = getDistance(prevAct, newAct);
        else
            additionalDistance = getDistance(prevAct, newAct) + getDistance(newAct, nextAct) - getDistance(prevAct, nextAct);
        Double routeDistance = stateManager.getRouteState(context.getRoute(), distanceStateId, Double.class);
        if (routeDistance == null) routeDistance = 0.;
        double newRouteDistance = routeDistance + additionalDistance + pickupDistance;
        if (newRouteDistance > maxDistance) {
            return ConstraintsStatus.NOT_FULFILLED;
        } else return ConstraintsStatus.FULFILLED;
    }

    double getDistance(TourActivity from, TourActivity to) {
            return this.costsMatrix.getDistance(from.getLocation().getId(), to.getLocation().getId());
    }

}

}`

Here I have 2 Shipments : P1 and P2
P1 has to be picked up from loc_3 and delivered at loc_1
P2 has to be picked up from loc_3 and delivered at loc_2

distance:
loc_1 - loc_2 = 2500
loc_1 - loc_3 = 2500
loc_2 - loc_3 = 500

Two vehicles : starting from loc_1 and loc_3 with Return to depot as True

Expected output is: P2 should be served by V3.

But this is what I’m getting:

When I tried to find out the issue by putting this in code:

if(((DeliverShipment) newAct).getJob().getId().equals("P2") && context.getNewVehicle().getId().equals("V1")) System.out.print("P2 delivery by V1");

I got none such case.
Means at no point does the algorithm checks constraint for a route when P2 is delivered by V1, but I still get in the output route.
Is this a bug?

Notice:
If I run only 2 iteration I get this answer:

But when I run more than 2 I get this:

Notice that total cost in second case is less

Does it violate hard constraint to reduce the cost?

`


#13

In the (newAct instanceof DeliverShipment) clause, you need to cater for the case that prevAct is the associated PickupShipment, i.e., you won’t need the following part in the pickupDistance in that case:

getDistance(pickupActivity, nexttoPickupActivity) - getDistance(prevtoPickupActivity, nexttoPickupActivity)

#14

Hi He,

I don’t think so,
pickupDistance = getDistance(prevtoPickupActivity, pickupActivity) + getDistance(pickupActivity, nexttoPickupActivity) - getDistance(prevtoPickupActivity, nexttoPickupActivity);

with
additionalDistance = getDistance(prevAct, newAct) + getDistance(newAct, nextAct) - getDistance(prevAct, nextAct);

Takes into account where prevAct is the associated PickupShipment.

e.g:
Route : S - P1 - D1 - E
Now newAct = D2
prevAct = P2.
nextAct = E

In this case pickup activity = P2
prevtoPickupActivity = D1
nexttoPickupActivity = E

So,
pickupDistance = D1P2 + P2E - D1E
additionalDistance = P2D2 + D2E - P2E

routeDistance = SP1 + P1D1 + D1E

Hence,
newRouteDistance = routeDistance + additionalDistance + pickupDistance
= SP1 + P1D1 + D1P2 +P2D2 + D2E
which is correct.

I’m certain that this is correct implementation.

Thing that is worrying me is that the constraint was not checked for the case where P2 is delivered by V1. but still such route exist in solution.


#15

Ah, you are right. Oops, I must have confused myself, LOL.


#16

btw, in the following case,

should we set it to 0 or should we use the distance from vehicle start location to its end location (if not open route)?


#17

I think it should be 0.

Consider a case when start location is S and end location is E.

routeDistance == null only in the case when we add first pickUp or first delivery.

First Pickup (P1) :
additionalDistance = SP1 + P1E
hence newRouteDistance = SP1 + P1E

First Delivery (D1) :
it will go inside this loop:
if(context.getRoute().getTourActivities().getActivities().size() == 0)

By the way any idea about why is it not checking this constraint for a case when P2 is delivered by V1 and still we get such route in answer?


#18

Oh,
I just realized it should not be 0.
you are right. It should be distance from vehicle start location to its end location (if not open route).

But as in above case start and end locations are same, it won’t matter.


#19

Hi @Bhoumik_Shah,

I am able to reproduce your case. I will look into it.

Interesting thing is, if you deactivate either one of the two vehicles, you will get expected solution:

  1. if you deactivate v3, both jobs are unassigned;
  2. if you deactivate v1, you will get the solution that you obtained after 2 iterations in your case.

Best regards,
He


#20

Hi @jie31best,

Even I noticed both the above cases.
Also if you add one more vehicle V2 with start and end location as loc_2, it will take 9 iteration, instead of 3 to give an infeasible solution.