GraphHopper.com | Forum | GitHub | Maps | Blog

Maximum trip distance constraint


#41

Hi @stefan,

I have taken a look at your implementation of the max distance constraint, and I have a few questions:

  1. You assumed a static travel distance, which might be fine for now, but I suppose a constraint here should be able to handle general cases. I guess it will require to add more states: activity vehicle-dependent arrival times, yet it might be a bit tricky due to the pickup shipment issue;

  2. Do you think we need to handle the case when actAfterPickup is End?

  3. When actBeforePickup is Start, I don’t think we should set it to iFacts.getRoute().getStart(), because the new vehicle start location and departure time could be different from those of the route start;

  4. Do you think we need to handle if(newAct instanceof DeliverShipment) in some other constraints or cost calculators, e.g., AdditionalTransportationCosts, LocalActivityInsertionCostsCalculator, etc.?

  5. Have you considered Phil’s suggestion and mine regarding the pickup shipment issue?

  6. When it comes to the generalized/extended job definition (a job is a list of activities), I suppose we cannot handle the pickup shipment issue in this way if(newAct instanceof DeliverShipment){} any more?

Best regards,
He


#42

Hi @He,
Thanks for analysing this. Please find my answers below:

  1. this is correct. for now I assumed static distances. we should adjust this. I just opened an issue for this. (see https://github.com/graphhopper/jsprit/issues/292)
  2. thats correct. if the vehicle does not need to return to depot then additional distance of pickup act is not calculated correctly
  3. also correct
  4. What do you mean here?
  5. I do not think that this is an issue here. It is not maxTimeOrDistance of job i InVehicle but related to overall distance. Why do you think it is an issue?
  6. Does that mean we still need to differentiate between Pickup and ShipmentPickup? Or what is your suggestion here?

Thanks a lot for your input. Really nice :).
Best,
Stefan


#43

@jie31best: Would you mind that we further discuss this feature here?


#44

Hi @stefan,

Please find below clarifications of my questions 4-6, but let me try to define what I have been calling the pickup shipment issue first:

When a job is a list of N activities, and when you are evaluating the insertion of the i-th activity. What you have in the states are what the world is like before the insertion of the whole job, and thus you will need to calculate the impact of the insertion of all the preceding i-1 activities in the job. Put it in the context of Shipment, when you are evaluating the insertion of the DeliverShipment, you need to calculate the impact of the insertion of the corresponding PickupShipment. Thus I call it the pickup shipment issue.

What I was saying is that, in some other constraints or cost calculators, when newAct is a DeliverShipment, we might also need to consider the impact of the insertion of the corresponding PickupShipment. Not sure if the two classes I put there as examples require that, though.

Meanwhile, I wonder if those two classes will need to consider the different vehicle issue? For example, in both classes, there is calculation of tp_costs_prevAct_nextAct when the route is not empty, in which you used prevAct.getLocation(), nextAct.getLocation() and iFacts.getRoute().getVehicle(). Not sure if that could be problematic, because, for example, prevAct could be Start and its location would be the start location of the new vehicle rather than that of the route?

I think what we were suggesting is that, for each state you have in the state manager (which could include the states in VehicleDependentTraveledDistance for this max distance constraint, and those in UpdateMaxTimeInVehicle for the max time in vechile constraint), you make a corresponding new one, and then, in the ShipmentInsertionCalculator, before the deliverShipmentLoop, update it taking into account the “insertion” of the pickupShipment, and then use it in the evaluation of the deliverShipment insertion. The update part will need to loop through all the activities in the route, but will keep the same complexity as current.

In this way, the impact of the insertion of the PickupShipment is already considered in the state, and thus will not require calculating it in the constraint (e.g., additionalDistanceOfPickup).

I think this is not only about Pickup or PickupShipment, but about the general case. When you are evaluating the insertion of the i-th activity, you will need to calculate the impact of the insertion of all the preceding i-1 activities in the job. It seems to me that it will be overwhelming.

What I have in mind is to go with the way as suggested in 5). For each state, you make an array, the length of which is the maximum number of activities in a job. Then in the JobInsertionCaculator (which I suppose would be a generalization of ServiceInsertionCalculator and ShipmentInsertionCalculator), you have a N-layer loop to evaluate the insertion of the whole job, where N is the number of activities in the job. In the i-th layer you evaluate the insertion of the i-th activity in the job, and, before that layer, you update the i-th element in the array for each state and use it in the i-th layer loop. Note that the 1st element in the array for each state is what we already have and updated in the state updaters and thus is not updated in the JobInsertionCaculator.

Best regards,
He


Job/Activity refactor (general discussion)
#45

Hi He,
Thanks for your answers. Let me read this carefully over the weekend and then I ll come back with some question regarding your proposal of memorizing states.
Thanks again for your input.
Have nice weekend,
Stefan


#46

Hi @jie31best,

I have taken a look at your implementation of the max distance constraint, and I have couple of doubts.

  1. If prevAct is Start shouldn’t we use
    double distancePrevAct2NewAct = distanceCalculator.getDistance(iFacts.getNewVehicle().getStartLocation(), newAct.getLocation(), iFacts.getNewDepTime(), iFacts.getNewVehicle());

Similarly if nextAct is end.

  1. What if in case of shipment delivery prevAct is not actual previous activity?
    To give an example, Let’s say initial route is
    Start-A-B-C-End
    In this route we first insert pickUpShipment§ with insertion index 1,
    hence actual route will be
    Start-A-P-B-C-End
    Now if while inserting dropShipment(D) we have prevAct = A and nextAct=B.
    In this case prevAct is A but actual previous activity is P.

Hence we need to consider effect of insertion of related activities on route as well.


#47

Hi @Bhoumik_Shah, Thanks for your ideas/doubts. The easiest way here would be to find concrete examples where the constraint fails. Even better if you could do it in a unit test. If not, your example would also be fine for us.
Best,
Stefan


#48

Hi @stefan,

I recreated the error that I was getting. After analyzing I realized issue is not due to point 2 above.
But it is due to this line.

It makes distancePrevAct2NextAct = 0; in case of nextAct is deliveryShipment even if pickUp activity has been added to route.

See the attached example.

SimpleMaxDistanceTest.java (6.7 KB)


#49

I have a question about the implementation of the VehicleDependentTraveledDistance class.

Why is it classifying two vehicles with the same vehicleTypeIdentifier as equals?

Since it doesn’t take into account the vehicle’s id, wouldn’t two vehicles that are similar sans the id would be evaluated as equal, taking one into account and tossing the other? What is the benefit of this approach?

Just curious

Thanks


#50

Hi @Bhoumik_Shah,

  1. In the ServiceInsertionCalculator or the ShipmentInsertionCalculator, when prevAct is Start, it is set to the following:

     Start start = new Start(newVehicle.getStartLocation(), newVehicle.getEarliestDeparture(), Double.MAX_VALUE);
    

Therefore we have prevAct.getLocation() = iFacts.getNewVehicle().getStartLocation() by default.

Similarly, when nextAct is End, it is set to:

    End end = new End(newVehicle.getEndLocation(), 0.0, newVehicle.getLatestArrival());

Thus we have nextAct.getLocation() = iFacts.getNewVehicle().getEndLocation() by default.

So I think your concern should have been taken care of.

  1. In the ShipmentInsertionCalculator, when D is to be inserted right after P, then prevAct is set to P by this line:

     TourActivity prevAct_deliveryLoop = pickupShipment;
    

So I suppose it covers your concern?

  1. Regarding your test case, I will take a look asap and will get back to you later.

Best regards,
He


#51

Ok, I think we should change

if(routeIsEmpty)

to

if(prevAct instanceof Start && nextAct instanceof End)

@stefan what do you think?

Best regards,
He

EDIT: added changes and unit tests to #301.


#52

Hi He,

Thanks for clarification.

Why do we need Map<Vehicle,Double> maxDistancePerVehicleMap?

Can’t we keep maxDistance a parameter of Vehicle Class just like Id, StartLocation etc.?


#53

I guess you can, but that part was written by @stefan, not me, lol.


#54

Thanks for the good ideas to bring it. I know a lot more. :slight_smile: สมัครเอเย่นต์,ทางเข้าเอเย่นต์

[


#55

Hi @Bhoumik_Shah,

To achieve this in minimal changes, You can use “userData” variable from “Vehicle” to store the max distance and make the constraint to use the max distance value from userData instead of the Map.

Or you can always write your own implementation of Vehicle and Constraint. :slight_smile: