System and method for estimating a dynamic origin-destination matrix

• US 10,430,736 B2
• Filed: 05/25/2012
• Issued: 10/01/2019
• Est. Priority Date: 05/25/2012
• Status: Active Grant

• Current Assignee: Conduent Business Services, LLC (Conduent, Inc.)
• Original Assignee: Conduent Business Services, LLC (Conduent, Inc.)
• Inventors: Chidlovskii, Boris
• Primary Examiner(s): Brockington, III, William S
• Application Number:
  US13/480,802
• Publication Number:
  US 20130317884A1
• Time in Patent Office: 2,685 Days
• Field of Search: 705 711- 742
• CPC Class Codes: G06Q 10/025 Coordination of plural reservations, e.g. plural trip segments, transportation combined with accommodation
• CPC Class Codes: G06Q 10/047 Optimisation of routes or paths, e.g. travelling salesman problem
• 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 dynamically estimating an origin-destination matrix. An origin-destination matrix is initialized with a set of origin stops and destination stops. Validation sequences are acquired for a set of travelers on a transportation system which include a plurality of the origin stops and respective timestamps. Corresponding destination stops may be known or inferred. For each validation sequence, a set of subsequences is generated, each including a respective one of the origin stops and the associated timestamp. Subsequences which, in combination, constitute a valid transfer trip are identified. For a combination of subsequences constituting a valid transfer trip, the method includes determining whether the valid transfer trip is a multi-goal trip for which there is least a first destination stop with an intermediate goal and a second destination stop with a final goal. The origin-destination matrix is updated, based on the determination.

Claims

1. A method for generating an origin-destination matrix for a transportation system, the method performed by at least one processor in communication with at least one memory, wherein the at least one processor is configured to perform operations including:

initializing, for an entry-only validating transportation system, an origin-destination matrix with a set of origin stops and a set of destination stops;

acquiring, in real-time, via a plurality of automated ticket validation systems of the transportation system, validation sequences for each traveler of a set of travelers on the transportation system, each validation sequence including a plurality of the origin stops, a timestamp associated with each of the plurality of the origin stops, and a ticket identification associated with the validation sequence used at each of the plurality of the origin stops, wherein the ticket identification is distinct for each traveler, wherein the automated ticket validation systems comprise a ticket reading device to acquire validation information to generate the validation sequences;

for each origin stop;

selecting, from the set of destination stops, a set of possible alighting stops associated with the origin stop,

computing a probability for each of the possible alighting stops being a destination stop for the origin stop, and

selecting a most probable alighting stop as a respective destination stop from the set of possible alighting stops;

for each of the validation sequences, generating a set of subsequences, each subsequence including a respective one of the plurality of the origin stops and the associated timestamp;

based on the set of subsequences, identifying subsequences which in combination constitute a valid transfer trip for at least one traveler of the set of travelers;

for a combination of subsequences constituting the valid transfer trip, determining whether the valid transfer trip is a multi-goal trip for the at least one traveler of the set of travelers for which there is at least a first destination stop with an intermediate goal and a second destination stop with a final goal;

updating the origin-destination matrix based on the determination;

refining at least one route of the transportation system in accordance with the updated origin-destination matrix; and

modifying the transportation system using the updated origin-destination matrix, wherein the modification of the transportation system includes a plurality of;

adding or removing a vehicle from the at least one route, adding or subtracting the at least one route, changing a path of the at least one route, adding or removing a station along the at least one route, and adding or subtracting a stop along the at least one route.

2. The method of claim of claim 1, wherein the identifying subsequences which in combination constitute the valid transfer trip comprises:

accessing a set of trip plans from an origin stop for a first of the subsequences to a destination stop for a subsequent one of the subsequences for a time segment which includes the associated timestamp of the origin stop for the first of the subsequences;

where the set of trip plans includes the first and subsequent subsequences, identifying the combination of subsequences as the valid transfer trip.

3. The method of claim of claim 1, wherein the determining comprises:

computing a transfer time between the first destination stop and a subsequent origin stop;

comparing the computed transfer time to a predetermined threshold time; and

wherein the determination is based on the comparison.

4. The method of claim 1, wherein the updating of the origin-destination matrix comprises:

for an identified valid transfer trip, updating the origin-destination matrix to reflect a single origin-destination trip which incorporates the subsequences of the valid transfer trip.

5. The method of claim 1, wherein the updating of the origin-destination matrix comprises:

for the multi-goal trip, updating the origin-destination matrix to reflect a plurality of origin-destination trips for the multi-goal trip.

6. The method of claim 1, wherein the updating of the origin-destination matrix comprises:

providing a weighting schema for weighting each of a predefined set of goals of multi-goal trips; and

associating an intermediate destination with one of the goals; and

updating the origin-destination matrix in accordance with the weighting schema and the one of the goals.

7. The method of claim 6, wherein the weighting schema is one of an equal weighting schema, an importance weighting schema, and an inverted importance weighting schema.

8. The method of claim 1, wherein the acquiring of the validation sequences further comprises:

collecting validation information for at least some of the travelers in the set of travelers on the transportation system, the validation information including a first set of origin stops and corresponding timestamps; and

determining an inferred destination stop for each of the first set of origin stops in accordance with a subsequent origin stop.

9. The method of claim 8, wherein the least one processer is further configured to perform:

retrieving route information and schedule information corresponding to a vehicle boarded by a traveler at a first origin stop;

identifying a set of stops on a route of the first origin stop in relative proximity to the subsequent origin stop; and

selecting the set of possible alighting stops from the set of stops in relative proximity to the subsequent origin stop.

10. The method of claim 9, wherein computing the probability further comprises:

determining a vehicle passage time of the vehicle boarded at the origin stop relative to an identified stop in the set of possible alighting stops on the route in relative proximity to the subsequent origin stop;

determining a walking time from each stop in the set of possible alighting stops to the subsequent origin stop;

computing a wait time at the subsequent origin stop in accordance with the timestamp associated with the subsequent origin stop, the vehicle passage time, and the schedule information;

assigning a zone attribute to each of the possible alighting stops in the set thereof;

determining a station load associated with each stop in the set of possible alighting stops; and

computing the probability for each of the possible alighting stops in accordance with at least one of the vehicle passage time, the determined walking time, the computed wait time, the zone attribute, and the determined station load.

11. The method of claim 10, further comprising assigning a utility weight to each of the possible alighting stops prior to computing the probability thereof.

12. The method of claim 11, wherein computing the probability is performed in accordance with a discrete choice model.

13. A dynamic origin-destination matrix generation system, comprising at least one processor in communication with at least one memory, wherein the at least one processor is configured to:

generate an origin-destination matrix;

define each of a plurality of validation sequences based on validation information in real-time for at least some of a plurality of travelers on an entry-only transportation system, at least some of the validation sequences including a set of origin stops, a set of destination stops, associated timestamps corresponding thereto, and a ticket identification associated with the validation sequence used at each of the set of origin stops, wherein the ticket identification is distinct for each traveler,

wherein the validation information is acquired by an automatic ticketing validation system configured to detect at least an origin stop of a traveler in the plurality of travelers;

generate a set of subsequences for each of the validation sequences, each subsequence including the origin stop, at least one destination stop, and a time segment corresponding to a boarding at the origin stop of for the traveler in the plurality of travelers;

determine a set of trip plans for at the traveler in the plurality of travelers from the origin stop to the at least one destination stop at the time segment;

select a set of possible alighting stops associated with the origin stop in accordance with a subsequent origin stop, compute a probability for each of the possible alighting stops being the at least one destination stop of the origin stop, and select a most probable alighting stop as the at least one destination stop from the set of possible alighting stops;

identify at least one subsequence in the set thereof as a valid transfer trip in accordance with the at least one subsequence in the set of trip plans,

identify at least one multi-goal trip in the identified at least one subsequence in accordance with an intermediate destination stop in the at least one subsequence,

update the origin-destination matrix in accordance with each of the identified subsequences and multi-goal trips, and

modify the transportation system using the updated origin-destination matrix, the transportation system comprising;

a plurality of routes, each route having a path about a geographic area;

at least one vehicle associated with each route;

at least one stop along each route; and

at least one station;

wherein the modification of the transportation system includes at least one of;

adding or removing a vehicle from at least one route, adding or subtracting the at least one route, changing the path of the at least one route, adding or removing a station along the at least one route, and adding or removing a stop along the at least one route.

14. The system of claim 13, wherein at least one processor is further configured to:

compute a transfer time between the intermediate destination stop and the subsequent origin stop;

compare the computed transfer time to a predetermined threshold time; and

identify a trip from the origin stop to the intermediate destination stop as a goal of a multi-goal trip in response to an output of the comparison indicating the computed transfer time is greater than the predetermined threshold time.

15. The system of claim 13, wherein the at least one processor is further configured to:

select a weighting schema for each goal of the multi-goal trip; and

weight each goal in the origin-destination matrix in accordance with the selected weighting schema, and

wherein the weighting schema is an equal weighting schema, an importance weighting schema, or an inverted importance weighting schema.

16. The system of claim 15, wherein the at least one processor is further configured to:

retrieve route information and schedule information from an associated database corresponding to a vehicle boarded by the traveler at the origin stop;

identify a set of stops on the route of the origin stop in relative proximity to the subsequent origin stop; and

output the selected set of possible alighting stops from the set of stops in relative proximity to the subsequent origin stop to a destination probability generator.

17. The system of claim 15, wherein the at least one processor is further configured to:

determine a vehicle passage time of the vehicle boarded at the origin stop relative to an identified stop in the set of possible alighting stops on the route in relative proximity to the subsequent origin stop;

determine a walking time from each stop in the set of possible alighting stops to the subsequent origin stop;

compute a wait time at the subsequent origin stop in accordance with the timestamp associated with the subsequent origin stop, the vehicle passage time, and the schedule information;

assign a zone attribute to each of the possible alighting stops in the set thereof;

determine a station load associated with each stop in the set of possible alighting stops; and

compute the probability for each of the possible alighting stops in accordance with at least one of the vehicle passage time, the determined walking time, the computed wait time, the zone attribute, and the determined station load.

18. A computer-implemented method for dynamically generating an origin-destination matrix of an entry-only transportation system, comprising:

generating an origin-destination matrix, the origin-destination matrix including information about a spatial and a temporal distribution of activities between different traffic zones in the transportation system;

acquiring validation information for a set of travelers of the transportation system in real-time, the validation information for at least some of the travelers in the set including a set of origin stops, a timestamp for each origin stop, and a ticket identification associated with a validation sequence used at each origin stop, wherein the ticket identification is distinct for each traveler, but lacking a corresponding destination stop for at least one origin stop of the set of origin stops,

wherein the validation information is acquired by an automatic ticketing validation system configured to detect at least an origin stop of a traveler in the set of travelers;

selecting, with a processor, a set of possible alighting stops for each of the origin stops in the validation information lacking the corresponding destination stop, the set of possible alighting stops selected in accordance with at least one of a proximity to a subsequent origin stop, a route associated with the origin stop, and a schedule associated with a vehicle boarded at the origin stop;

computing a probability for each stop in the set of possible alighting stops relative to the origin stop corresponding to the probability that each alighting stop is a destination stop of the origin stop;

selecting a possible alighting stop from the set thereof as the destination stop of the origin stop in accordance with the computed probability associated therewith for each origin stop of the set of origin stops;

generating validation sequences for the at least some of the travelers in the set of travelers in accordance with the acquired validation information and the selected possible alighting stop for each origin stop of the set of origin stops;

segmenting each validation sequence into a set of subsequences, each subsequence including a first origin stop, at least one inferred destination stop, and a time segment associated with the timestamp corresponding to the origin stop;

receiving a set of trip plans for at least one traveler of the set of travelers from the first origin stop to the at least one inferred destination stop at the time segment for each subsequence;

identifying at least one subsequence in the set thereof as a valid transfer trip for the at least one traveler of the set of travelers in accordance with the at least one subsequence in the set of trip plans;

identifying at least one multi-goal trip for the at least one traveler of the set of travelers in the identified at least one subsequence in accordance with an intermediate destination stop in the at least one subsequence;

updating the origin-destination matrix in accordance with each of the identified subsequences and multi-goal trips; and

modifying the transportation system using the updated origin-destination matrix, the modifying representative of adding or removing a vehicle, a route, a station or a number of stops to or from the transportation system.

19. The computer-implemented method of claim 18, wherein identifying at least one multi-goal trip further comprises:

computing a transfer time between the intermediate destination stop and a subsequent origin stop;

comparing the computed transfer time to a predetermined threshold time; and

identifying a trip from the origin stop to the intermediate destination stop as a goal of the multi-goal trip in response to an output of the comparison indicating the computed transfer time is greater than the predetermined threshold time.

20. The computer-implemented method of claim 19, wherein updating the origin-destination matrix further comprises:

selecting a weighting schema for each goal of the multi-goal trip; and

weighting each goal in the origin-destination matrix in accordance with the selected weighting schema.

21. The computer-implemented method of claim 20, wherein computing a probability for each of the set of possible alighting stops further comprises:

determining a vehicle passage time of the vehicle boarded at the origin stop relative to an identified stop in the set of possible alighting stops on the route in relative proximity to the subsequent origin stop;

determining a walking time from each stop of the set of possible alighting stops to the subsequent origin stop;

computing a wait time at the subsequent origin stop in accordance with the timestamp associated with the subsequent origin stop, the vehicle passage time, and the schedule information;

assigning a zone attribute to each of the possible alighting stops in the set thereof;

determining a station load associated with each stop in the set of possible alighting stops; and

computing the probability for each of the possible alighting stops in accordance with at least one of the vehicle passage time, the determined walking time, the computed wait time, the zone attribute, and the determined station load.