System and method for estimating origins and destinations from identified end-point time-location stamps

• US 8,977,496 B2
• Filed: 05/25/2012
• Issued: 03/10/2015
• Est. Priority Date: 05/25/2012
• Status: Active Grant

• Current Assignee: Conduent Business Services, LLC (Conduent, Inc.)
• Original Assignee: Xerox Corporation (Xerox Holdings Corp.)
• Inventors: Ulloa Paredes, Luis Rafael, Bouchard, Guillaume M.
• Primary Examiner(s): Kiswanto, Nicholas
• Application Number:
  US13/481,042
• Publication Number:
  US 20130317742A1
• Time in Patent Office: 1,019 Days
• Field of Search: 701/533
• US Class Current: 701/533
• CPC Class Codes: G06Q 10/063 Operations research, analysis or management
• CPC Class Codes: G06Q 50/40 Business processes related to the transportation industry shipping G06Q10/083

Abstract

A method and system are disclosed for estimating origin and destination locations of users of a transportation system. The origins and destinations of known users are determined during a segment of an analysis period from validation information for all users of the transportation system. The origins and destinations are then mapped to probable locations associated with the transportation network. A destination probability is then computed for each destination location of an individual origin location. A unknown users are then apportioned to each destination, which may be based on the number of unknown users on a vehicle traveling from the origin to the destination, the computed probability, and the validation information, so as to estimate the number of users traveling from an origin location to any corresponding destination location on the transportation system.

Claims

1. A method for estimating origin and destination locations of users of a transportation system, comprising:

acquiring validation information for a set of users of the transportation system, the set of users including a set of unknown users and a set of known users, the transportation system including a set of routes, each route including a set of stops which are selectable by users as origin stops and destination stops;

for each of the set of known users, identifying origin stops from the validation information and predicting destination stops, based on the respective identified origin stops, during a segment of an analysis period;

mapping at least some of the origin stops and predicted destination stops to respective origin and destination locations associated with the transportation system;

based on the origin stops and respective predicted destination stops of the set of known users and the mappings, computing destination probabilities for the destination locations from respective origin locations;

apportioning unknown users of the set of users among the destination locations, based on the computed destination probabilities associated with each destination location and the validation information; and

estimating destinations of the unknown users traveling from an origin location to a corresponding destination location on the transportation system in accordance with the apportionment,

wherein at least one of the identifying, mapping, computing, apportioning or estimating is performed by a processor in communication with associated memory.

2. The method of claim 1, wherein the validation information includes, for each of a plurality of users, a unique ticket identification, at least one timestamp, at least one of a stop location and at least one vehicle identification.

3. The method of claim 2, wherein each segment of the analysis period is a day or part of a day, and wherein the analysis period includes a plurality of days.

4. The method of claim 2, wherein the unique ticket identification is at least one of a persistent identification corresponding to a known user and an anonymous identification corresponding to an unknown user.

5. The method of claim 2, wherein identifying origin stops and destination stops of known users further comprises:

defining a path for each known user of the plurality of users during a segment of the analysis period, the path including a set of ordered stops;

assigning each stop in the set of ordered stops as at least one of an origin stop and a destination stop in accordance with an order of the set of ordered stops.

6. The method of claim 5, further comprising:

identifying a stop in the set thereof as an origin stop when a subsequent stop in the set is present; and

assigning the subsequent stop as a destination stop associated with the identified origin stop.

7. The method of claim 6, further comprising identifying a last stop in the set thereof as an origin stop with a predicted destination stop corresponding to a first stop in the set.

8. The method of claim 2, wherein mapping of the stops to a corresponding probable origin location or a destination location further comprises:

applying an origin assignment function to each identified origin stop so as to map a corresponding origin location; and

applying a destination assignment function to each predicted destination stop so as to map a corresponding destination location.

9. The method of claim 8, wherein each of the origin locations and destination locations are mapped from a set of probable locations associated with the transportation system.

10. The method of claim 9, further comprising defining the set of probable locations in accordance with preselected geographical partitions of a city associated with the transportation network.

11. The method of claim 2, wherein calculating the destination probability further comprises identifying a vehicle associated with the vehicle identification from a set of vehicles, each of the vehicles in the set of vehicles having an associated route, the route including a scheduled origin stop and a scheduled destination stop corresponding to the identified origin stop and predicted destination stop, and

wherein predicting the destination stops further includes predicting the destination stops based on the respective identified origin stops and the identified vehicle.

12. The method of claim 11, wherein calculating the destination probability further comprises:

retrieving, from an associated database, route information and schedule information corresponding to the vehicle associated with the vehicle identification corresponding to the analysis period segment;

determining, from the validation information, a number of times a destination location is a destination from the origin location using the vehicle; and

determining, from the retrieved route and schedule information, a number of times the origin location is an origin stop of the vehicle during the analysis period segment,

wherein the destination probability is computed for each destination location in accordance with the determined number of times the destination location is the destination from the origin location using the vehicle and the determined number of times the origin location is an origin stop in the route of the vehicle.

13. The method of claim 12, wherein apportioning unknown users further comprises:

identifying each origin stop in the validation information including at least one unknown user;

for each identified origin stop, identifying at least one vehicle having a route associated therewith;

determining a number of unknown users of the at least one vehicle during the analysis period segment;

mapping each identified origin stop to a probable location of the transportation system in accordance with the assignment origin function;

identifying each destination location for each identified origin location; and

apportioning the determined number of unknown users to each identified destination location in accordance with the computed destination probability corresponding thereto.

14. The method of claim 1, further comprising;

outputting the estimated destinations of a set of users including known users and unknown users; and

refining at least one route of the transportation system based on the output estimated destinations.

15. The method of claim 5, wherein the path includes a single stop, further comprising:

identifying the single stop as an origin stop for the known user; and

designating a destination stop corresponding to the single stop as an unknown destination stop.

16. The method of claim 2, wherein the apportionment of the unknown users comprises identifying a number of the unknown users traveling on a vehicle with a route that extends from the origin location to the destination location.

17. A computer program product comprising a non-transitory recording medium storing instructions, which when executed on a computer causes the computer to perform the method of claim 1.

18. A system comprising memory storing instructions for performing the method of claim 1, and a processor in communication with the memory which implements the instructions.

19. An origin and destination estimation system, comprising:

a path generator component configured for defining a set of ordered stops from validation information for each known user of a transportation system during a segment of an analysis period, the validation information comprising a unique ticket identification, at least one vehicle identification, at least one stop location, and at least one timestamp;

memory which stores;

instructions for identifying origin stops and predicting destination stops of each known user during the analysis period segment from validation information for a plurality of users of the transportation system;

a mapping component configured for mapping each identified origin stop to a corresponding probable origin location associated with the transportation network with an origin assignment function and mapping each predicted destination stop to a corresponding probable destination location associated with the transportation system with a destination assignment function; and

a destination probability generator configured for computing a destination probability for each destination location of an individual origin location,

instructions for;

apportioning unknown users to each destination location in accordance with a number of unknown users on a vehicle associated with the vehicle identification and traveling from the origin location to the destination location, the computed destination probability associated with each destination location, and the validation information, and

estimating a destination of each unknown user traveling from an origin location to a corresponding destination location on the transportation system in accordance with the apportionment; and

a processor in communication with the memory which implements at least one of the path generator, the mapping component, and the destination probability generator.

20. The system of claim 19, wherein the destination probability generator is further configured for:

retrieving, from an associated database, route information and schedule information corresponding to the vehicle associated with the vehicle identification corresponding to the analysis period segment;

determining, from the validation information, a number of times a destination location is predicted to be a destination from the origin location using the vehicle;

determining, from the retrieved route and schedule information, a number of times the origin location is an origin stop of the vehicle during the analysis period segment; and

computing the destination probability for each destination location in accordance with the determined number of times the destination location is the predicted destination from the origin location using the vehicle and the determined number of times the origin location is an origin stop in the route of the vehicle.

21. The system of claim 20, wherein the memory further stores instructions which are executed by the processor for:

identifying each origin stop in the validation information including at least one unknown user and at least one vehicle having a route associated with the identified origin stop;

determining a number of unknown users of the at least one vehicle during the analysis period segment;

mapping each identified origin stop to a probable location of the transportation system in accordance with the assignment origin function;

retrieving each destination location corresponding to each identified origin location; and

apportioning the determined number of unknown users to each retrieved destination location in accordance with the computed destination probability corresponding thereto.

22. A computer-implemented method for estimating origin and destination locations of users of a transportation system, comprising:

acquiring validation information for each of a plurality of users of a transportation system for a selected analysis period, the validation information including a unique ticket identification, at least one vehicle identification, at least one stop location, and at least one timestamp;

defining a path for each known user of the plurality of users during a segment of the analysis period, the path including a set of ordered stops;

assigning each stop in the set of ordered stops as at least one of an origin stop and a destination stop in accordance with the order of the stops;

mapping each assigned stop to a corresponding origin location or a destination location;

computing a destination probability of known users for each of a set of destination locations associated with each origin location;

apportioning unknown users of the plurality of users to each destination location in accordance with the computed destination probability; and

estimating destination locations for each of the plurality of users during the analysis period segment;

wherein at least one of the defining, assigning, mapping, computing, apportioning, and estimating is performed with a computer processor.

23. The computer-implemented method of claim 22, wherein mapping each stop to a corresponding origin location or a destination location further comprises:

applying an origin assignment function to each origin stop so as to map the corresponding origin location; and

applying a destination assignment function to each destination stop so as to map the corresponding destination location.

24. The computer-implemented method of claim 23, wherein computing the destination probability further comprises:

retrieving, from an associated database, route information and schedule information corresponding to a vehicle associated with the vehicle identification corresponding to the analysis period segment;

determining, from the validation information, a number of times a destination location is predicted as a destination from the origin location using the vehicle; and

determining, from the retrieved route and schedule information, a number of times the origin location is an origin stop of the vehicle during the analysis period segment,

wherein the destination probability is computed for each destination location in accordance with the determined number of times the destination location is predicted to be the destination from the origin location using the vehicle and the determined number of times the origin location is an origin stop in the route of the vehicle.

25. The computer-implemented method of claim 24, wherein apportioning unknown users further comprises:

identifying each origin stop in the validation information including at least one unknown user;

for each identified origin stop, identifying at least one vehicle having a route associated therewith;

determining a number of unknown users of the at least one vehicle during the analysis period segment;

mapping each identified origin stop to a probable location of the transportation system in accordance with the assignment origin function;

predicting each destination location corresponding to each identified origin location; and

apportioning the determined number of unknown users to each predicted destination location in accordance with the computed destination probability corresponding thereto.