New feature: maximum time in vehicle

Directions API
1

This feature lets you specify the maximum time your shipments can be in your vehicle (from pickup to delivery). It is an important feature when it comes to transporting passengers and perishable goods. You can specify the max time by adding max_time_in_vehicle tag to your shipments as illustrated in the following example:

{
  "vehicles": [
    {
      "vehicle_id": "v1",
      "start_address": {
        "location_id": "13.391321_52.543129",
        "lon": 13.391321,
        "lat": 52.543129
      },
      "return_to_depot": false
    },
    {
      "vehicle_id": "v2",
      "start_address": {
        "location_id": "13.440102_52.558179",
        "lon": 13.440102,
        "lat": 52.558179
      },
      "return_to_depot": false
    }
  ],
  "shipments": [
    {
      "id": "1",
      "name": "1",
      "pickup": {
        "address": {
          "location_id": "13.420152_52.558897",
          "lon": 13.420152,
          "lat": 52.558897
        }
      },
      "delivery": {
        "address": {
          "location_id": "13.452596_52.522983",
          "lon": 13.452596,
          "lat": 52.522983
        }
      },
      "max_time_in_vehicle": 900
    },
    {
      "id": "2",
      "name": "2",
      "pickup": {
        "address": {
          "location_id": "13.399381_52.564819",
          "lon": 13.399381,
          "lat": 52.564819
        }
      },
      "delivery": {
        "address": {
          "location_id": "13.473367_52.521599",
          "lon": 13.473367,
          "lat": 52.521599
        }
      },
      "max_time_in_vehicle": 1200
    },
    {
      "id": "3",
      "name": "3",
      "pickup": {
        "address": {
          "location_id": "13.411434_52.552021",
          "lon": 13.411434,
          "lat": 52.552021
        }
      },
      "delivery": {
        "address": {
          "location_id": "13.484219_52.530330",
          "lon": 13.484219,
          "lat": 52.53033
        }
      },
      "max_time_in_vehicle": 1200
    }
  ]
}

“max_time_in_vehicle” should be greater than (direct_travel_time(pickup,delivery) + preparation_time(delivery)). Note that this is still a beta feature and might be changed.

1 Like
2

Is this feature within jsprit.core as well? (Apologies if I’ve missed this already). If so, how is the calculation done? Does it setup new temporary ‘practical time windows’ when the shipment pickup insertion is evaluated, for the later shipment deliveries on the route? i.e. is the shipment insertion 100% correct and running in O(n2) where n is route length?

3

Is this feature within jsprit.core as well?

Yes, it is.

If so, how is the calculation done?

Look at this: jsprit/jsprit-core/src/main/java/com/graphhopper/jsprit/core/problem/constraint/MaxTimeInVehicleConstraint.java at master · graphhopper/jsprit · GitHub

Does it setup new temporary ‘practical time windows’

Yes, it does.

4

Thanks Stefan, looking at the implentation I believe it runs on O(n3), where n is route size. For each pickup insertion location you evaluate every later delivery insertion position (which is O(n2) ) and then for each delivery insertion location you run the code:

         List<TourActivity> tourActivities = new ArrayList<>(iFacts.getRoute().getActivities());
            tourActivities.add(iFacts.getRelatedActivityContext().getInsertionIndex(), iFacts.getAssociatedActivities().get(0));
            for (TourActivity act : tourActivities) {
                updateMaxTimeInVehicle.visit(act);

}

Which makes it O(n3).

I’m wondering if this can instead be done in O(n2) by storing some kind of temporary time windows (based on max time in vehicle) for each pickup insertion location. i.e. get the effect of the pickup insertion on the route and then reuse this for testing each delivery insertion. I’m not sure if this would work though. What do you think?

5

Thanks @PGWelch. Good point. My first priority was to make it work in terms of functionality. Therefore, I did not put a lot of effort into thinking about performance deliberately, especially since I do not like it very much to memorize states when checking constraints. However, it seems that there is no way around it here. I am sure your proposal works and I ll let you know once it is implemented.

6

since I do not like it very much to memorize states when checking constraints

Any memorization should just be stored on the JobInsertionContext, yes? Have something like a statemanager stored on this object, so constraints can create a state on their pickup evaluation and re-use it on their delivery? You wouldn’t store the state globally (i.e. not in the main statemanager).

7

Have ‘moved’ the jsprit discussion to here. Please let me know if the title was wrong or similar :slight_smile: