SYSTEM AND METHOD FOR ESTIMATING A DYNAMIC ORIGIN-DESTINATION MATRIX

• US 20130317884A1
• Filed: 05/25/2012
• Published: 11/28/2013
• 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: Chidlovskii, Boris
• Granted Patent: US 10,430,736 B2
• Time in Patent Office: Days
• US Class Current: 705/7.31
• 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/30 Transportation; Communications
• 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, comprising:

initializing an origin-destination matrix with a set of origin stops and destination stops;

acquiring validation sequences for a set of travelers on a transportation system, each validation sequence including a plurality of the origin stops and a timestamp associated with each of the origin stops, and where for each of origin stops there is a respective destination stop selected from the set of destination stops;

for each of the validation sequences, generating a set of subsequences, each subsequence including a respective one 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 a combination of subsequences constituting a valid transfer trip, providing for 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; and

updating the origin-destination matrix based on the determination.

2. The method of claim of claim 1, wherein at least one of the generating, identifying, and computing is performed with a computer processor.

3. The method of claim of claim 1, wherein the identifying subsequences which in combination constitute a 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 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 a valid transfer trip.

4. 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.

5. 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.

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

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

7. 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 the intermediate destination with one of the goals; and

weighting the update to the origin-destination matrix in accordance with the one of the goals.

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

9. The method of claim 1, further comprising refining at least one route of the transportation system in accordance with the updated origin-destination matrix.

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

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

inferring a destination stop for each of the set of origin stops in accordance with a subsequent origin stop.

11. The method of claim 10, wherein inferring the destination stop for each of the set of origin stops further comprises:

selecting a set of possible alighting stops associated with the origin stop in accordance with the subsequent origin stop;

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

selecting a most probable alighting stop as the at least one destination stop from the set of possible alighting stops.

12. The method of claim 11, wherein selecting a set of possible alighting stops further comprises:

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

identifying a set of stops on the route of the 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.

13. The method of claim 12, wherein computing the probability further comprises:

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

determining a walking time from each 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.

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

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

16. 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.

17. 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.

18. A dynamic origin-destination matrix generation system, comprising:

a validation sequence generator configured for defining a validation sequence for at least some of a plurality of travelers on a transportation system at least some of the validation sequences including a set of origin stops, a set of destination stops, and associated timestamps corresponding thereto;

a subsequence generator configured for generating a set of subsequences for each of the validation sequences, each subsequence including an origin stop, at least one destination stop, and a time segment corresponding to a boarding at the origin stop of a traveler;

a trip planning component configured for determining a set of trip plans from the origin stop to the at least one destination stop at the time segment;

memory which stores instructions for;

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

identifying 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, and

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

a processor in communication with the memory which executes the instructions.

19. The system of claim 18, wherein the memory further comprises instructions which are executed by the processor for:

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 to the intermediate destination stop as a goal of a multi-goal trip response to an output of the comparison indicating the computed transfer time is greater than the predetermined threshold time.

20. The system of claim 18, further comprising a weight determination component configured for:

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, and

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

21. The system of claim 20, further comprising a destination stop selector configured for:

selecting a set of possible alighting stops associated with the origin stop in accordance with the subsequent origin stop;

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

selecting a most probable alighting stop as the at least one destination stop from the set of possible alighting stops.

22. The system of claim 20, wherein the destination stop selector is further configured for:

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

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

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

23. The system of claim 21, wherein destination probability generator is further configured for:

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

determining a walking time from each 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.

24. A computer-implemented method for dynamically generating an origin-destination matrix of a transportation system, comprising:

acquiring validation information for a set of travelers of the transportation system over a predetermined time period, the validation information for at least some of the travelers in the set including a plurality of origin stops, and a timestamp for each origin stop, but lacking a corresponding destination stop for at least one of the origin stops;

selecting, with a processor, a set of possible alighting stops for each of the origin stops in the validation information lacking a 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 of 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 of the set of origin stops;

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

segmenting each validation sequence into a set of subsequences, each subsequence including an 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 from the origin stop to the at least one destination stop at the time segment for each subsequence;

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

identifying 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;

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

25. The computer-implemented method of claim 24, 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 to the intermediate destination stop as a goal of a multi-goal trip response to an output of the comparison indicating the computed transfer time is greater than the predetermined threshold time.

26. The computer-implemented method of claim 25, 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.

27. The computer-implemented method of claim 26, 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 each of the identified set of possible alighting stops on the route in relative proximity to the subsequent origin stop;

determining a walking time from each 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.