Traffic and time dependent optimization

stefan · September 18, 2017, 8:57am

To consider traffic within the optimization, you need to specify the following:

"configuration":{
      "routing":{
          "consider_traffic": true,
          "network_data_provider": "tomtom"
      }
}

Note that the optimization is daytime-dependent now, i.e. it is important to specify all time-related fields in seconds since Jan 01 1970 (UTC). Along with the coordinates, it is then internally converted into UTC date time with offset (e.g. “2017-09-18T10:12+02:00”). For example, if you want to let your vehicle start today, 18.09., 11am and you are located in Berlin (UTC date time with offset: “2017-09-18T11:00+02:00”) find the according unix timestamp and put it in your vehicle specification like this:

{
      "vehicle_id": "my_vehicle",
      "start_address": {
        "location_id": "berlin",
        "lon": 13.406,
        "lat": 52.537
      },
      "earliest_start": 1505725200
}

If traffic should be considered, GraphHopper uses historical traffic data from TomTom to solve the underlying vehicle routing problem.

In the response you will have two additional fields arr_data_time and end_data_time that display UTC time as date time string (e.g. “2017-09-18T11:00+02:00”), e.g.:

{
          "type": "service",
          "id": "frankfurt",
          "location_id": "13.456055_52.517795",
          "address": {
            "location_id": "13.456055_52.517795",
            "lat": 52.517795,
            "lon": 13.456055
          },
          "arr_time": 1505723036,
          "arr_date_time": "2017-09-18T10:23:56+02:00",
          "end_time": 1505723036,
          "end_date_time": "2017-09-18T10:23:56+02:00",
          "waiting_time": 0,
          "distance": 4910,
          "driving_time": 716,
          "preparation_time": 0,
          "load_before": [
            0
          ],
          "load_after": [
            0
          ]
}

It is important to mention that in the alpha phase we only allow the vehicle profile “car” and we only cover Europe. Also the changed copyright notice has to be considered.

See our official documentation for the latest coverage: https://docs.graphhopper.com/#section/Map-Data-and-Routing-Profiles/TomTom

stefan · September 18, 2017, 9:58am

To illustrate what this actually means, let us assume we have a single driver who needs to deliver 4 items to customers in London. It starts from the airport London Heathrow.

Our current Optimization API calculates that this delivery tour will take 154min no matter whether the driver starts at 3am, 7am, 1pm or 6pm. It is an average value over the entire day. De facto, travel time varies significantly throughout the day so that it actually does matter when the driver starts. Our new time dependent optimization takes this into account and returns the following travel times depending on the vehicle’s departure time:

04:00: 121min
06:00: 139min
08:00: 169min
10:00: 163min
12:00: 163min
14:00: 176min
16:00: 171min
18:00: 135min
20:00: 135min

stefan · October 12, 2017, 9:14am

We slighly changed the configuration and the way one can enable traffic data (original post above was updated accordingly to avoid confusion for first time readers). It can be enabled as follows:

"configuration":{
      "routing":{
          "consider_traffic": true,
          "network_data_provider": "tomtom"
      }
}

We extended it not only because of the options to integrate more data providers, but also to provide users the option to solve their problems with free-flow travel times. For example, if one wants to activate TomTom’s free-flow data, specify it as follows:

"configuration":{
      "routing":{
          "consider_traffic": false,
          "network_data_provider": "tomtom"
      }
}

It then only use travel times that can be achieved in times with very low traffic, i.e. night times. This way one can easily compare how much time is added when considering traffic.

karussell · November 6, 2017, 5:03pm

See this official announcement and let us know if you have interests to try this out!

arielmoraes · November 9, 2017, 1:30pm

Nice work, will this new feature be merged into the public branch?

karussell · November 9, 2017, 2:07pm

I assume you mean open sourcing the changes to jsprit? There are no plans to do so (read here a bit about our open vs. closed ‘strategy’). Still keep in mind that the majority of work was to get the (proprietary) data into the routing engine and handle a very big deployment of the routing engine. So not much that would make sense to open source, there is just too few open traffic data.

MKergall · November 10, 2017, 5:34pm

Sounds really great!
I understand from the anouncement and examples that it applies to route optimization.
Is it - or is it going to be - available to the Routing API? This would be a tremendous improvement.

karussell · November 10, 2017, 8:32pm

This applies currently only to the Route Optimization API.

Update: as beta we also offer this for the Routing, Matrix and Isochrone API.

myominlin · January 3, 2018, 2:34am

Hi @karussell

When I add this configuration to my current optimization input, I get ‘Bad Request’ exception with ‘cannot find the following locations’ message.
When I remove this configuration from optimization input, it’s working fine.
Is there anything to enable to use this routing configuration?

karussell · January 3, 2018, 9:11am

We have to enable this per customer. Will do for you and let you know via Email.

myominlin · February 14, 2018, 2:37am

Hi @stefan

The values of ‘arr_time’ and ‘end_time’ are UTC date time unix values?
‘arr_date_time’ and ‘end_date_time’ return 0 when I tried.
I passed UTC unix values for all earliest and latest of vehicles and job time windows.
I would like to know what is the issue of not returning values in ‘arr_date_time’ and ‘end_date_time’.

Thanks,
Lin

stefan · February 14, 2018, 7:39am

Hi @myominlin,

It will have date time only if you do time dependent optimization. Currently, it means that if you use TomTom data.

Best,
Stefan

Russell_Brown · February 27, 2018, 9:53am

Any idea when this will be available for other vehicle types (particularly small_truck)?

karussell · February 27, 2018, 10:56am

This is available for car and small_truck already, although the tricky thing is to combine heuristics with the speed data to adapt it for small_truck and get differences to car or make it more realistic. Here we appreciate your feedback

jsprout · March 15, 2018, 1:21pm

Is the order of the route determined using the time sensitivity, or is the order of the route determined with the free flow data and then the travel times calculated based on the time of day?

Also, is the travel time based on the TomTom data for each segment of the route at the time the vehicle arrives at the segment? In other words, if the vehicle leaves the first location at 10:00 am, is the travel time based on traveling to the next location at 10:00 or using the time the vehicle started the route?

stefan · March 15, 2018, 2:12pm

If you specify, "consider_traffic": true routes and route orders are determined using traffic data. If
"consider_traffic": false free flow speed is used.

Also, is the travel time based on the TomTom data for each segment of the route at the time the vehicle arrives at the segment?

We split the day into time slices to account for typical variations of travel time during the day, e.g. caused by the rush hours of private traffic. Based on these time slices, we determine travel times from location i to j. It also considers that travelling from i to j might cross more than one time slice. In other words, travel times are dependent on the departure time of the vehicle as well as on the location.

Does this answer your question?

jsprout · March 15, 2018, 2:39pm

this answers part 2

For part 1 here is an example of my question:

In your example route leaving Heathrow airport at different times, you show the total travel time for each departure time. Is the route the same for each departure time? If the traffic to the location labeled 2 is an hour longer at noon than at 4:00 am and location 5 is an hour shorter at noon, the route sequence could be 1,5,4,3,2,1. Is that what happens?

Our delivery trucks will normally leave around 7:00 am. If heading North at 7:00 is with the heavy traffic and South is with light traffic, then it may be better to start the route heading South and finish from the North. The free-flow route has the driver heading North and finishing from the South. I am trying to determine if the time-sensitive routing takes this into consideration, or am I always going to get the same route sequence no matter when I depart.

I guess another way to ask, is the time-sensitive routing only affecting the travel times?

stefan · March 15, 2018, 2:45pm

No, it is not. It should be influenced by the driver’s departure time such that for example it is avoided to drive into a city center in peak hours - if the majority of private traffic flows into the city center - if it can be postponed to off-peak hours.
If you have an example where you would have expected a different sequence than what GraphHopper calculates, please send it over and we will analyse it.

jsprout · March 15, 2018, 3:30pm

We are still writing this so I do not have any examples. I was just over analyzing your example and got worried that the stops were always in the same sequence regardless of the departure time from Heathrow.

Thanks for the clarification

shanness · November 2, 2018, 4:46pm

Is there any update on this? Google has started charging exorbitant prices for travel time with traffic calls. We need this for Australia mainly, but also the US.