Journey time estimation

• US 9,959,339 B2
• Filed: 07/13/2015
• Issued: 05/01/2018
• Est. Priority Date: 07/13/2015
• Status: Active Grant

• Current Assignee: DoorDash, Inc.
• Original Assignee: International Business Machines Corporation
• Inventors: Ashton, Jean S., Baudel, Thomas, Blandin, Sebastien
• Primary Examiner(s): Cass, Jean Paul
• Application Number:
  US14/797,202
• Publication Number:
  US 20170016732A1
• Time in Patent Office: 1,023 Days
• Field of Search: 701410
• CPC Class Codes: G01C 21/3415 Dynamic re-routing, e.g. recalculating the route when the user deviates from calculated route or after detecting real-time traffic data or accidents
• CPC Class Codes: G01C 21/343 Calculating itineraries, i.e. routes leading from a starting point to a series of categorical destinations using a global route restraint, round trips, touristic trips travelling salesman problem G06Q10/04; optimisation of routes G06Q10/047
• CPC Class Codes: G06F 16/322 Trees

Abstract

Embodiments relate to calculating a journey time for a planned journey between a chosen origin and a chosen destination over a network of roads in a region. A first journey time for the journey is estimated using a route scheduling algorithm and a second journey time for the journey is estimated using selected historical journeys characterized by journey origins and destinations. The historical journeys are selected based on their vicinity to the planned journey. An error in the second journey time is calculated based on the standard deviation in the selected historical journeys. The second journey time is selected as the estimated journey time from the planned journey if this error is below a defined threshold, otherwise the first journey time is selected as the estimated journey time for the planned journey.

Claims

1. A computer-implemented method of calculating a journey time for a journey between a chosen origin and a chosen destination over a network of roads in a region including the chosen origin and chosen destination,

the method comprising:

planning, by a journey time estimation service executing on a processor,

a route for the journey using a route planning algorithm,

the planning comprising calculating a first journey time for the route based at least in part on data from fixed sensors,

the chosen origin and the chosen destination received via a client device;

providing a database of entries of historical journeys in the region,

each journey entry in the database comprising, for a previously completed journey in the region, a journey origin, a journey destination and an actual journey time;

selecting a set of historical journeys from the database,

where the selected historical journeys have a journey origin and a journey destination that are nearest neighbors to the chosen origin and the chosen destination of the journey;

calculating a second journey time for the journey based on the selected set of historical journeys;

estimating an error for the second journey time based on calculating a standard deviation for calculated journey times of the historical journeys in the set,

where the journey time of each of the historical journeys in the set is calculated from the actual journey times of the other historical journeys in the set;

selecting the second journey time for the journey if the estimated error is below a defined threshold, else selecting the first journey time; and

outputting the selected journey time for the journey to the client device, wherein each database entry further comprises an actual time of day when the historical journey was made, and where calculating the standard deviation for calculated journey times of the historical journeys in the set comprises providing an estimated time of day for the journey and weighting the selected historical journeys in the calculation in accordance with a difference between the estimated time of day for the journey and the actual journey time of the selected historical journey.

2. The computer-implemented method of claim 1, wherein each journey origin and journey destination is represented by a pair of geographic coordinates.

3. The computer-implemented method of claim 2, wherein the database comprises a 4-dimensional tree structure, each dimension corresponding to one of the geographic coordinates, and where selecting a set of historical journeys from the database comprises finding a set of nearest neighbors to the planned journey in the tree structure.

4. The computer-implemented method of claim 1, wherein selecting a set of historical journeys from the database comprises selecting a predefined number of nearest neighbors to the planned journey from the database.

5. The computer-implemented method of claim 1, wherein calculating the second journey time for the journey from the selected set of historical journeys comprises calculating the average of the actual journey times of the selected nearest neighbors.

6. The computer-implemented method of claim 1, wherein estimating an error for the second journey time based on calculating a standard deviation for calculated journey times of the historical journeys in the set comprises dividing the calculated standard deviation by a mean journey time for the historical journeys in the set.

7. The computer-implemented method of claim 1, wherein the database is categorized in one or more categories corresponding to vehicle types having made the historical journeys, and where selecting a set of historical journeys from the database comprises selecting historical journeys from a category corresponding to a particular vehicle type.

8. The computer-implemented method of claim 1, further comprising:

receiving journey information of a journey made in the region, the journey information comprising a journey origin, a journey destination and an actual journey time; and

updating the database with the received journey information.

9. The computer-implemented method of claim 1, further comprising filtering the database by:

calculating a possible route for a historical journey;

calculating an average speed over the possible route based on the actual journey time; and

removing historical journeys from the database that have a calculated average speed outside a defined average speed range.

10. The computer-implemented method of claim 1, wherein the route planning algorithm includes a graph representation of the network of roads including graph edges corresponding to road segments and graph nodes interconnecting graph edges, where each graph edge comprises a set of parameters from which a partial journey time over the road segment can be estimated and where calculating the first journey time for the route comprises calculating the partial journey times for the road segments defining the planned route and summing the calculated partial journey times.

11. A computer program product for calculating a journey time for a journey between a chosen origin and a chosen destination over a network of roads in a region, the computer program product comprising a non-transitory computer readable storage medium having program code embodied therewith, the program code executable by a processor to:

plan, by a journey time estimation service, a route for the journey using a route planning algorithm,

the planning comprising calculating a first journey time for the route based at least in part on data from fixed sensors,

the chosen origin and the chosen destination received via a client device;

select a set of historical journeys from a database of entries of historical journeys in the region,

each journey entry in the database comprising, for a previously completed journey in the region, a journey origin, a journey destination and an actual journey time, where the selected historical journeys have a journey origin and a journey destination that are nearest neighbors to the chosen origin and the chosen destination of the journey;

calculate a second journey time for the journey based on the selected set of historical journeys;

estimate an error for the second journey time based on calculating a standard deviation for calculated journey times of the historical journeys in the set, where the journey time of each of the historical journeys in the set is calculated from the actual journey times of the other historical journeys in the set;

select the second journey time for the journey if the estimated error is below a defined threshold, else selecting the first journey time; and

output the selected journey time for the journey to the client device, wherein each database entry further comprises an actual time of day when the historical journey was made, and where calculating the standard deviation for calculated journey times of the historical journeys in the set comprises providing an estimated time of day for the journey and weighting the selected historical journeys in the calculation in accordance with a difference between the estimated time of day for the journey and the actual journey time of the selected historical journey.

12. The computer program product of claim 11, wherein each journey origin and a journey destination is represented by a pair of geographic coordinates.

13. The computer program product of claim 12, wherein the database comprises a 4-dimensional tree structure, each dimension corresponding to one of the geographic coordinates, and where selecting a set of historical journeys from the database comprises finding a set of nearest neighbors to the planned journey in the tree structure.

14. The computer program product of claim 11, wherein selecting a set of historical journeys from the database comprises selecting a predefined number of nearest neighbors to the planned journey from the database.

15. The computer program product of claim 11, wherein the program code is further executable by the processor to:

schedule a round trip from an origin via a plurality of chosen destinations over a network of roads in a region including the origin and the chosen destinations by;

applying a travelling salesman algorithm to a set of data points including the origin and the plurality of chosen destinations.

16. A computer system for calculating a journey time for a journey between a chosen origin and a chosen destination over a network of roads in a region including the chosen origin and chosen destination, the computer system comprising:

a memory having computer readable instructions; and

a processor for executing the computer readable instructions, the computer readable instructions including;

planning, by a journey time estimation service, a route for the journey using a route planning algorithm, the planning comprising calculating a first journey time for the route based at least in part on data from fixed sensors, the chosen origin and the chosen destination received via a client device;

providing a database of entries of historical journeys in the region, each journey entry in the database comprising, for a previously completed journey in the region, a journey origin, a journey destination and an actual journey time;

selecting a set of historical journeys from the database, where the selected historical journeys have a journey origin and a journey destination that are nearest neighbors to the chosen origin and the chosen destination of the journey;

calculating a second journey time for the journey based on the selected set of historical journeys;

estimating an error for the second journey time based on calculating a standard deviation for calculated journey times of the historical journeys in the set,

where the journey time of each of the historical journeys in the set is calculated from the actual journey times of the other historical journeys in the set;

selecting the second journey time for the journey if the estimated error is below a defined threshold, else selecting the first journey time; and

outputting the selected journey time for the journey to the client device, wherein each database entry further comprises an actual time of day when the historical journey was made, and where calculating the standard deviation for calculated journey times of the historical journeys in the set comprises providing an estimated time of day for the journey and weighting the selected historical journeys in the calculation in accordance with a difference between the estimated time of day for the journey and the actual journey time of the selected historical journey.

17. The computer system of claim 16, wherein each journey origin and a journey destination is represented by a pair of geographic coordinates.

18. The computer system of claim 17, wherein the database comprises a 4-dimensional tree structure, each dimension corresponding to one of the geographic coordinates, and where selecting a set of historical journeys from the database comprises finding a set of nearest neighbors to the planned journey in the tree structure.

19. The computer system of claim 16, wherein selecting a set of historical journeys from the database comprises selecting a predefined number of nearest neighbors to the planned journey from the database.