System and method for estimating a dynamic origin-destination matrix

Patent metadata

Field	Value
Publication number	US-10430736-B2
Application number	US-201213480802-A
Country	US
Kind code	B2
Filing date	May 25, 2012
Priority date	May 25, 2012
Publication date	Oct 1, 2019
Grant date	Oct 1, 2019

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.

First claim

What is claimed is:

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 syst

Assignees

• Chidlovskii Boris
• Conduent Business Services Llc

Inventors

• Chidlovskii Boris

Classifications

• G06Q10/063 Primary

  Operations research, analysis or management · CPC title

• G06Q10/025

  Coordination of plural reservations, e.g. plural trip segments, transportation combined with accommodation · CPC title

• G06Q10/047

  Optimisation of routes or paths, e.g. travelling salesman problem · CPC title

• G06Q50/30

  Physics · mapped topic

• G06Q50/40

  Business processes related to the transportation industry (shipping G06Q10/083) · CPC title