Route computation based on route-oriented vehicle trajectories

Patent metadata

Field	Value
Publication number	US-9261376-B2
Application number	US-71205310-A
Country	US
Kind code	B2
Filing date	Feb 24, 2010
Priority date	Feb 24, 2010
Publication date	Feb 16, 2016
Grant date	Feb 16, 2016

Abstract

Techniques for providing a route based on route-oriented vehicle trajectories are described. This disclosure describes receiving GPS logs and extracting route-oriented vehicle trajectory content from the GPS log data to pertain to a single trip. Next, the process maps each route-oriented vehicle trajectory to a corresponding road segment to construct a landmark graph. A landmark is a road segment frequently visited by route-oriented vehicles. The process includes receiving a user query with a starting point and a destination point; searching the landmark graph for a sequence of landmarks with corresponding transition times and a least amount of travel time. Then the process identifies and connects sets of road segments between each pair of consecutive landmarks, and displays a route to a user with a nearest landmark to the starting point, other landmarks along the route, and another nearest landmark to the destination point.

First claim

What is claimed is:

1. A method implemented at least partially by a processor, the method comprising:
collecting a sequence of global positioning system (GPS) points from route-oriented vehicle logs;
identifying geographical locations from the route-oriented vehicle logs, the geographical locations representing locations where route-oriented vehicles travelled as recorded in the vehicle logs;
extracting route-oriented vehicle trajectories from the route-oriented vehicle logs, the route-oriented vehicle trajectories representing individual trips; and
constructing a landmark graph based at least in part on the route-oriented vehicle trajectories by:
associating each route-oriented vehicle trajectory to a corresponding road segment;
determining a first frequency that a first road segment is visited by the route-oriented vehicles and at least a second frequency that other road segments are visited by the route-oriented vehicles, the first frequency being determined based on a number of the route-oriented vehicle trajectories that are associated with the first road segment, and the second frequency being determined based on a number of the route-oriented vehicle trajectories that are associated with the other road segments;
comparing the first frequency to the second frequency; and
identifying a landmark, the landmark being the first road segment when the first frequency is greater than the second frequency.

2. The method of claim 1 , wherein the first road segment is a directed edge that is associated with a direction symbol, two terminal points, and a list of intermediate points describing the road segment with a polyline.

3. The method of claim 1 , further comprising:
determining whether a time interval between two consecutive GPS points meets or exceeds a predetermined threshold; and
partitioning the two consecutive GPS points into two different trajectories based on whether the time interval between the two consecutive GPS points meets or exceeds the threshold.

4. The method of claim 1 , further comprising dividing the route-oriented vehicle trajectories into separate trajectories when a stay point is identified, the stay point representing a geographical region in which a route-oriented vehicle remained within a threshold distance for a threshold time period.

5. The method of claim 1 , wherein the associating each route-oriented vehicle trajectory to a corresponding road segment comprises:
identifying candidate road segments and correlating the candidate road segments to candidate projection points;
detecting the candidate projection points on candidate edges;
identifying a probability that a GPS point matches a candidate point computed based on a distance between two points;
identifying a list of road segments based on determining a shortest path from a first candidate projection point to a second candidate projection point;
generating a candidate graph for the route-oriented vehicle trajectory with a set of candidate projection points and a set of edges to represent the shortest paths between neighboring candidate points; and
determining a road segment that matches the trajectory.

6. The method of claim 1 , wherein the constructing the landmark graph further comprises:
computing a number of route-oriented vehicle trajectories that connect any of the landmarks; and
connecting the landmarks with a landmark edge when there is at least a subset of the route-oriented vehicle trajectories passing through the landmarks, the landmark edge to represent travels between the landmarks by the route-oriented vehicles.

7. The method of claim 1 , further comprising:
determining a median time cost for travelling on a landmark edge, the landmark edge to connect one landmark to another landmark.

8. The method of claim 1 , further comprising:
receiving a user query with a starting point and a destination point for directions;
searching the landmark graph for an initial route that is represented by a sequence of landmarks with corresponding transition times and a least amount of travel time;
computing a set of connected road segments between each pair of consecutive landmarks of an initial route; and
providing data indicating a route including the directions with landmarks from the starting point to the destination point.

9. One or more computer-readable media encoded with instructions that, when executed by a processor, perform acts comprising:
presenting a user interface on a display of a portable electronic device, the user interface to access a service application that provides map-based services;
receiving user input to the user interface indicating a starting location and a destination location;
accessing a landmark graph constructed from route-oriented vehicle trajectories, a landmark being identified when a first frequency of route-oriented vehicles visiting a road segment is compared to a second frequency of route-oriented vehicles visiting a second or subsequent road segment and the first frequency is greater than the second frequency;
computing an initial path, based on the starting location and the destination location, between each pair of consecutive landmarks of the initial path; and
refining the initial path by finding a route that sequentially connects the landmarks, from the starting location to the destination location.

10. The computer-readable media of claim 9 , in response to the initial path, further comprising:
calculating additional paths from the starting location to each terminal point of the landmarks on the initial path; and
determining the additional paths for unidirectional and bidirectional road segments.

11. The computer-readable media of claim 9 , further comprising:
searching the landmark graph for the initial path based on a sequence of landmarks with corresponding transition times between the landmarks and a least amount of travel time; and
visually presenting the route to a user, the route illustrating a nearest landmark to the starting location, any landmarks along the route, and another nearest landmark to the destination location.

12. The computer-readable media of claim 9 , further comprising:
collecting the route-oriented vehicle logs that include a sequence of global positioning system (GPS) points from the variety of route-oriented vehicles;
determining geographical locations from the route-oriented vehicle logs, the geographical locations to represent regions where the variety of route-oriented vehicles have travelled as recorded in the vehicle logs; and
segmenting the geographical locations into the road segments, a road segment including a directed edge that is associated with a direction symbol, two terminal points, and a list of intermediate points describing the road segment with a polyline.

13. The computer-readable media of claim 9 , further comprising:
extracting route-oriented vehicle trajectories from route-oriented vehicle logs, the route-oriented vehicle logs are represented with a sequence of global positioning system (GPS) points from the variety of route-oriented vehicles engaged in business related transportation;
representing individual trips based on a sequence of road segments with transition times with route-oriented vehicle trajectories;
determining when a time interval between two consecutive GPS points is greater than or less than a predetermined threshold:
in an event that the time interval between two consecutive GPS points is greater the predetermined threshold, partition the two consecutive GPS points into two different trajectories; or
in an event that the time interval between the two consecutive GPS points is less than the predetermined thresho

Assignees

• Zheng Yu
• Lou Yin
• Zhang Chengyang
• Xie Xing
• Microsoft Technology Licensing Llc

Inventors

• Zheng Yu
• Lou Yin
• Zhang Chengyang
• Xie Xing

Classifications

• G01C21/10

  by using measurements of speed or acceleration (G01C21/24, G01C21/26 take precedence) · CPC title

• G01C21/3484 Primary

  Personalized, e.g. from learned user behaviour or user-defined profiles · CPC title

• G01S19/42

  Determining position · CPC title

• G01C21/16

  by integrating acceleration or speed, i.e. inertial navigation · CPC title