DYNAMIC CITY ZONING FOR UNDERSTANDING PASSENGER TRAVEL DEMAND

• US 20140089036A1
• Filed: 09/26/2012
• Published: 03/27/2014
• Est. Priority Date: 09/26/2012
• Status: Abandoned Application

• Current Assignee: Xerox Corporation (Xerox Holdings Corp.)
• Original Assignee: Xerox Corporation (Xerox Holdings Corp.)
• Inventors: Chidlovskii, Boris
• Application Number:
  US13/627,371
• Publication Number:
  US 20140089036A1
• Time in Patent Office: Days
• US Class Current: 705/7.27
• CPC Class Codes: G06Q 10/047 Optimisation of routes or paths, e.g. travelling salesman problem
• CPC Class Codes: G06Q 10/06 Resources, workflows, human or project management; Enterprise or organisation planning; Enterprise or organisation modelling
• CPC Class Codes: G06Q 10/06315 Needs-based resource requirements planning or analysis
• CPC Class Codes: G06Q 50/40 Business processes related to the transportation industry shipping G06Q10/083

Abstract

A system and method for dynamic zoning are provided. Travel demand data is received for a network which includes a set of points. The travel demand data includes values representing demand from each point to each of other point. Destination-distance values are computed which reflect the similarity between points in a respective pair, based on the travel demand data. For each pair of the points, a geo-distance value is generated which reflects the distance between locations of the points in the pair. An aggregated affinity matrix is formed by aggregating the computed geo-distance values and destination-distance values. The aggregated affinity matrix is used by a clustering algorithm to assign each of the points in the set to a respective one of a set of clusters. A representation of the clusters can be generated in which each of a set of zones encompasses the points assigned to its respective cluster.

Claims

1. A method for dynamic zoning, comprising:

receiving travel demand data for a set of geographically-spaced points that are interconnected by routes of a transportation network, the travel demand data comprising, for each of the points, values representing travel demand to each of the other points in the set;

for each pair of the points, computing a destination-distance function based on the travel demand data of the points in the pair, to provide a respective destination-distance value;

for each pair of the points, generating a geo-distance value based on locations of the points in the pair;

forming an aggregated affinity matrix by aggregating the computed geo-distance values and destination-distance values;

based on the aggregated affinity matrix, clustering points in the set among a set of clusters; and

generating a representation of the clusters in which each of a set of zones encompasses the points assigned to a respective cluster.

2. The method of claim 1, wherein at least one of the computing of the geo-distance function, computing of the destination-distance function, forming of the aggregated affinity matrix, clustering points in the set among the set of clusters, and generating of the representation of the clusters is performed with a computer processor.

3. The method of claim 1, further comprising outputting the representation to an output device.

4. The method of claim 1, wherein the geographically-spaced points comprise locations of stations in the transportation network that are connected by a set of predefined routes.

5. The method of claim 1, wherein the travel demand data comprises at least one origin-destination matrix inferred from time stamp data acquired for tickets of travelers boarding transportation vehicles at the points of the network.

6. The method of claim 1, wherein the generating of the geo-distance value comprises computing a Euclidian distance between the points in the pair.

7. The method of claim 1, wherein the computing of the destination-distance function comprises computing a Euclidian distance between vectors representing the travel demands of the points in the pair.

8. The method of claim 1, wherein the aggregating of the computed geo-distance values and destination-distance values comprises forming a geo-distance affinity matrix based on the computed geo-distance values and forming a destination-distance affinity matrix based on the computed destination-distance values.

9. The method of claim 8, further comprising multiplying the geo-distance affinity matrix and destination-distance affinity matrix to form the aggregated affinity matrix.

10. The method of claim 1, further comprising providing for a user to select a number of clusters to be generated in the clustering.

11. The method of claim 1, wherein the clustering comprises:

clustering the points in the set among a first set of clusters;

clustering the points among a second set of clusters having a different number of clusters from the first set of clusters; and

generating first and second representations which differ in the number of zones, based on the number of clusters in the first and second sets.

12. The method of claim 1, wherein the clustering comprises multi-view spectral clustering.

13. The method of claim 1, wherein the clustering comprises:

deriving a set of eigenvectors from a Laplacian matrix derived from the aggregated affinity matrix;

forming an eigenvector matrix from eigenvectors of the Laplacian matrix in which the eigenvectors form columns and have a value in each of a set of rows of the matrix, each row corresponding to one of the points, and optionally normalizing the eigenvector matrix;

clustering the rows among the clusters in the set of clusters; and

assigning the point to the cluster to which the row is assigned.

14. The method of claim 13, wherein the clustering of the rows is performed by k-means clustering.

15. The method of claim 1, wherein the representation of the clusters comprises a map of the network which illustrates the zones that encompass the points assigned to the respective clusters.

16. The method of claim 1, wherein the travel demand data comprises travel demand data for a first time period and travel demand data for second time period and the method comprises generating a first representation of clusters generated for the first time period in which zones encompass the points assigned to the respective clusters and generating a second representation of clusters generated for the second time period in which zones encompass the points assigned to the respective clusters.

17. The method of claim 1, further comprising modifying the representation to represent travel demand from a selected one of the zones to others of the zones.

18. The method of claim 1, further comprising providing for a user to select a portion of the network and generating the representation of the clusters for only those points that are in the selected portion of the network.

19. A system for dynamic zoning, comprising memory which stores instructions for performing the method of claim 1 and a processor in communication with the memory for executing the instructions.

20. A computer program product comprising a non-transitory recording medium which stores instructions, which when executed by a computer, perform the method of claim 1.

21. A system for dynamic zoning, comprising:

a destination-distance component which receives travel demand data for a set of geographically-spaced points that are interconnected by routes of a transportation network, the travel demand data comprising, for each of the points, a vector of values representing travel demand to each of the other points in the set, and for each pair of the points, computes a destination-distance value based on the vectors for the points in the pair;

a geo-distance component which, for each pair of the points, generates a geo-distance value based on locations of the points in the pair;

an aggregation component which forms an aggregated affinity matrix by aggregating the computed geo-distance values and destination-distance values;

a clustering component which clusters points in the set into a set of clusters, based on the aggregated affinity matrix;

a representation component which generates a representation of the clusters in which zones encompass the points assigned to respective clusters; and

a processor which implements the destination-distance component, geo-distance component, aggregation component, clustering component, and representation component.

22. A method for clustering stations based on travel demand and location, comprising:

providing an origin-destination matrix for stations in a transportation network, where each row of the matrix represents a respective one of the stations, each row constituting a vector of values, each value representing travel demand from the respective station to each of the stations;

with a processor, generating a destination-distance matrix by computing a destination-distance value for pairs of the stations by computing a distance between their respective vectors;

generating a geo-distance matrix by computing a geo-distance value for the pairs of the stations based on their locations;

forming an aggregated affinity matrix by matrix multiplication involving the destination-distance matrix and the geo-distance matrix;

using eigenvectors, reducing the dimensionality of the aggregated affinity matrix to generate a matrix which includes a row corresponding to each of the stations;

clustering the rows into a number of clusters and assigning the stations to the clusters to which the corresponding rows are assigned; and

outputting the cluster assignments.