Please download the dossier by clicking on the dossier button x
×

Shortest travel path determination using critical start time points

  • US 9,285,218 B2
  • Filed: 08/23/2013
  • Issued: 03/15/2016
  • Est. Priority Date: 08/24/2012
  • Status: Active Grant
First Claim
Patent Images

1. A method comprising:

  • obtaining a set of start times;

    determining a shortest path from a source to a destination for a current start time in the set of start times;

    a processor identifying a critical start time in the set of start times temporally separated from the current start time by at least one intermediate start time in the set of start times wherein identifying a critical start time comprises;

    identifying a shortest path from the source to a current node;

    identifying at least two edges that extend from the current node;

    for each edge that extends from the current node, determining path functions that indicate an earliest arrival time for traveling from the source to an end of the edge opposite the current node for each start time in the set of start times after the current start time;

    comparing each of the path functions for each edge at each start time after the current start time; and

    identifying each start time at which the edge with the earliest path function changes as a critical start time;

    setting the shortest path from the source to the destination for the current start time as the shortest path for the at least one intermediate start time without separately determining the shortest path for the at least one intermediate start time;

    determining a different shortest path from the source to the destination for the critical start time than for the current start time; and

    generating a user interface displaying a plurality of shortest paths from the source to the destination.

View all claims
  • 2 Assignments
Timeline View
Assignment View
    ×
    ×