Urban computing of route-oriented vehicles

Patent metadata

Field	Value
Publication number	US-9754226-B2
Application number	US-201113324758-A
Country	US
Kind code	B2
Filing date	Dec 13, 2011
Priority date	Dec 13, 2011
Publication date	Sep 5, 2017
Grant date	Sep 5, 2017

Abstract

Techniques for analyzing effectiveness of an urban area based on traffic patterns collected from route-oriented vehicles. A process collects sequences of global positioning system (GPS) points in logs and identifies geographical locations to represent the urban area where the route-oriented vehicles traveled. The process models traffic patterns by: partitioning the urban area into regions based at least in part on major roads, segmenting the GPS points from the logs into time slots, and identifying the GPS points associated with transporting a passenger in the route-oriented vehicles. The process models traffic patterns by projecting the identified GPS points onto the regions to construct transitions of the identified GPS points travelling between the regions. Then the process builds a matrix of the regions for each time slot in each day based on a number of the transitions. Each item in the matrix represents an effectiveness of a connection between two regions.

First claim

What is claimed is:

1. A computer-implemented method comprising:
enabling a wireless coupling between a computing device including a processor and global positioning system (GPS) receiving devices of route-oriented vehicles through a wireless communication network;
receiving through the wireless communication network, by the processor, sequences of GPS points of the route-oriented vehicles, the GPS points being obtained by the GPS receiving devices of the route-oriented vehicles;
identifying, by the processor, geographical locations from the sequences of GPS points in which the geographical locations represent on urban area where the route-oriented vehicles travelled as recorded in the sequences GPS points;
modeling, by the processor, traffic patterns in the urban area by:
partitioning the urban area into regions based at least in part on roads that form borders between regions;
segmenting the GPS points into time slots and identifying two or more of the GPS points that each include a status of vehicle occupancy indicating that each of the two or more GPS points is associated with transporting a passenger in one or more of the route-oriented vehicles has at least on a sensor that detects the passenger;
projecting the two or more GPS points associated with transporting the passenger onto the regions to construct transitions associated with transporting the passenger between one or more pairs of the regions; and
building a matrix of the regions for each time slot in each day based on a number of the transitions; and

providing, by the processor, one or more recommendations using the modeled traffic patterns creating at least one new traffic route, the new traffic route replacing a previous area unavailable for travel by the route-oriented vehicles.

2. The computer-implemented method of claim 1 , wherein the GPS points are analyzed from similar time spans in a year.

3. The computer-implemented method of claim 1 , wherein the time slots comprise:
separating the GPS points into (a) weekdays and (b) weekends and/or holidays of a year; and
dividing a time of a day into multiple time slots based on the traffic patterns in the urban area.

4. The computer-implemented method of claim 1 , wherein the transitions are associated with an arrival time, a departure time, a travel distance, and a travel speed between one or more pairs of the two or more GPS points.

5. The computer-implemented method of claim 1 , wherein the matrix includes items to represent effectiveness of connections between each of the one or more pairs of the regions.

6. The computer-implemented method of claim 1 , further comprising:
identifying a pair of regions having a set of transitions between the pair of regions; and
aggregating the transitions to associate the pair of regions with a volume of traffic between the pair of regions, expected travel speeds of the transitions, and a ratio between an actual travel distance for transitions between the pair of regions and a Euclidean distance between a first centroid of a first region of the pair of regions and a second centroid of a second region the pair of regions.

7. The computer-implemented method of claim 1 , further comprising identifying a set of skylines from the matrix of the regions to represent flaws in planning of the urban area, the set of skylines representing GPS points with travel speeds and ratios of actual travel distance and to Euclidean distance between centroids of regions of each of the one or more pairs of the regions that are less efficient than other GPS points.

8. The computer-implemented method of claim 1 , further comprising:
identifying a plurality of pairs of regions, each pair of regions of the plurality of the pairs of regions having a set of transitions between the pair of regions, each pair of regions of the plurality of the pairs of regions in a set of skylines having properties of:
a small travel speed between the set of transitions and a small ratio between an actual travel distance of the set of transitions and a Euclidean distance between centroids of regions of the pair of regions;
a small travel speed between the set of transitions and a large ratio between an actual travel distance of the set of transitions and a Euclidean distance between centroids of regions of the pair of regions; and
a large travel speed between the set of transitions and a large ratio between an actual travel distance of the set of transitions and a Euclidean distance between centroids of regions of the pair of regions; and
identifying from the plurality of the pairs of regions, an identified pair of regions having the small travel speed and the large ratio as requiring the route-oriented vehicles to take detours based on congested traffic for travelling between the identified pair of regions.

9. The computer-implemented method of claim 8 , further comprising:
building skyline graphs for each day b connecting the plurality of the pairs of regions in the skylines with consecutive time slots in which the plurality of the pairs of regions are spatially close to each other;
detecting sub-graph patterns from the skyline graphs to identify the plurality of the pairs of regions with traffic problems and to determine a casualty and a relationship among the plurality of the pairs of regions; and
providing the one or more recommendations based on an analysis of a planning of the urban area based on at least on the sub graph patterns being detected, the recommendations include building roads, suggesting a bus route; or suggesting a subway line.

10. One or more computer storage media encoded with instructions that, when executed by a processor, perform acts comprising:
enabling a wireless coupling between a computing device including the processor and global positioning system (GPS) receiving devices route-oriented vehicles over a wireless communication network;
receiving, in the wireless communication network, sequences of GPS points obtained tot the GPS receiving devices of the route-oriented vehicles, individual of the GPS points comprising a status of vehicle occupancy associated with transporting a passenger based at least on a sensor that detects the passenger;
creating a traffic and connectivity model that models a relationship of traffic of the route oriented vehicles travelling through regions in an urban area;
generating a matrix of the regions from the model to identify a connectivity between the regions, the identifying the connectivity between the regions comprising:
identifying a pair of the regions having a set of transitions between the pair the regions;
aggregating the set of transitions to associate the pair of regions with a volume of traffic between each of the pair regions, expected travel speeds of transitions between the pair of regions, and a ratio between an actual travel distance for transitions between the pair of regions and a Euclidean distance between a first centroid of a first region of the pair of the regions and a second centroid of a second region of the pair of the regions; and
mining information from the aggregated set of transitions for effectiveness of connectivity in the regions with reference to the matrix; and

providing, by the processor, one or more recommendations using output of the identified, connectivity between the regions identifying at least one new traffic route, the new traffic route replacing a previous area unavailable for travel by the route-oriented vehicles.

11. The computer storage media of claim 10 , further comprising:
presenting a user interface to receive a user query for the urban area;
searching the traffic and connectivity model for the urban area being queried, which is represented by a map o

Assignees

• Zheng Yu
• Xie Xing
• Microsoft Technology Licensing Llc

Inventors

• Zheng Yu
• Xie Xing

Classifications

• G08G1/0129

  for creating historical data or processing based on historical data · CPC title

• G08G1/0112

  from the vehicle, e.g. floating car data [FCD] · CPC title

• G06Q10/06 Primary

  Resources, workflows, human or project management; Enterprise or organisation planning; Enterprise or organisation modelling · CPC title