Dynamic routing of transit vehicles

Patent metadata

Field	Value
Publication number	US-9786173-B2
Application number	US-201514829021-A
Country	US
Kind code	B2
Filing date	Aug 18, 2015
Priority date	Aug 18, 2015
Publication date	Oct 10, 2017
Grant date	Oct 10, 2017

Abstract

Systems and techniques are described to enable the dynamic selection of a transit route through the stop zones of a transit line. Techniques are disclosed for receiving a current location of a transit vehicle on a transit line and determining a transit route through one or more of the vehicle's remaining stop zones by choosing an optimized combination of stop options and route segment options for that specific transit vehicle. Techniques may be performed in some cases by accessing a real-time traffic information service to obtain one or more traffic condition factors on a route segment, determining a dynamic route segment option weight, calculating a dynamic cost function with respect to the weights, and determining an optimized set of the route segments with respect to the cost functions.

First claim

What is claimed is:

1. A system for dynamic selection of transit routes, the system comprising:
a) one or more non-transitory computer readable storage media;
b) a data store contained on the one or more non-transitory computer readable storage media comprising one or more data structures related to:
b-1) one or more transit lines in a transit system;
b-2) a plurality of stop zones served by each of the one or more transit lines;
b-3) one or more stop options associated with each of the plurality of stop zones;
b-4) a plurality of stop option weighting factors, each stop option weighting factor describing a relative desirability of a particular stop option in accordance with one or more preference criteria; and
b-5) a plurality of route segment options, each route segment option describing a path between a first stop option and a subsequent stop option; and

c) program instructions for a dispatching service stored on the one or more non-transitory computer readable storage media, when executed by a processing system, the program instructions direct the processing system to:
in response to receiving a dynamic route request, the dynamic route request comprising a current location of a particular transit vehicle on a particular transit line and the current location being obtained from a transit vehicle location device, determine a particular transit route from the current location of the particular transit vehicle through one or more remaining s t op zones of the particular transit line by:
c-1) determining one or more remaining route segment options based on the one or more remaining stop zones and the plurality of route segment options in the data store;
c-2) for each individual route segment of the one or more remaining route segment options:
c-2a) to retrieve, from a real-time traffic information service, one or more traffic condition factors related to the individual route segment;
c-2b) to determine, from the one or more traffic condition factors, a route segment option weight; and
c-2c) to calculate a dynamic cost function based on the route segment option weight for the individual route segment, and particular stop option weighting factors for the one or more stop options connected by the individual route segment;

c-3) selecting the particular transit route, the particular transit route being comprised of an optimized set of individual route segments with respect to a totality of dynamic cost functions; and
c-4) returning the particular transit route to the particular transit vehicle.

2. The system of claim 1 , wherein selecting the particular transit route comprises:
determining an estimated traversal time for a best possible set of route segment options from a preceding stop zone (s i−1 ) to a specific stop zone (s i ) and on to a next stop zone (s i+1 ); and
when the estimated traversal time is greater than an originally planned traversal time between s i−1 and s i+1 multiplied by a selected first skip weighting factor, the selected first skip weighting factor being greater than one, determining the optimized set of individual route segments by skipping the specific stop zone s i and proceeding directly from s i−1 to s i+1 .

3. The system of claim 2 , wherein the data store further comprises one or more properties related to a plurality of first skip weighting factors, each of the plurality of first skip weighting factors relating to an associated stop zone, and the selected first skip weighting factor being the one of the plurality of first skip weighting factors associated with the specific stop zone.

4. The system of claim 1 , wherein selecting the particular transit route comprises:
determining a first estimated traversal time for the best possible set of route segment options from a preceding stop zone (s i−1 ) to a specific stop zone (s i ) and on to a next stop zone (s i+1 ); and
when the first estimated traversal time is greater than a second estimated traversal time for the best possible set of route segment options between the preceding stop zone (s i−1 ) and the next stop zone (s i+1 ) multiplied by a selected second skip weighting factor, the selected second skip weighting factor being greater than one, determining the optimized set of individual route segments by skipping the specific stop zone s i and proceeding directly from s i−1 to s i+1 .

5. The system of claim 4 , wherein the data store further comprises one or more properties related to a plurality of second skip weighting factors, each of the plurality of second skip weighting factors relating to an associated stop zone, and the selected second skip weighting factor being the one of the plurality of second skip weighting factors associated with the specific stop zone.

6. The system of claim 1 , further comprising program instructions that, when executed by the processing system, direct the processing system to:
send one or more notification messages to one or more notification interfaces.

7. The system of claim 6 , wherein the one or more notification messages comprise information describing one or more of:
the particular transit route;
a delay in arrival time at a stop zone;
a change in a selected stop option; and
a selected route segment option.

8. The system of claim 1 , wherein a dynamic aspect of a weighting factor comprises one or more of:
a first count of passengers on the particular transit vehicle;
a second count of passengers who are planning to disembark at a given stop zone;
a third count of passengers waiting at a particular stop option for the particular transit vehicle to arrive;
an estimated number of prospective passengers heading for a certain stop zone or stop option; and
an estimated wait time passengers will wait at a certain stop option to be collected by a subsequent transit vehicle.

9. The system of claim 8 , wherein an input to the dynamic aspect is obtained in real-time from the real-time traffic information service, an optional component, or estimated from historical data.

10. The system of claim 1 , wherein the one or more preference criteria of a stop option weighting factor comprise one or more of:
a walking distance from an associated stop option to a normal stop option;
an available pedestrian access from the normal stop option to the associated stop option; and
a quality of facilities at the associated stop option.

11. The system of claim 1 , wherein the route segment option weight is computed from input data, wherein the input data relates to the individual route segment for a projected time of usage, the input data comprising one or more of:
an estimated traversal time;
an estimated susceptibility to disruptions;
a traffic load;
a current or predicted delay;
a special event; and
a weather forecast.

12. A method for dynamic selection of transit routes, the method comprising:
a) receiving a dynamic route request, the dynamic route request comprising a current location of a particular transit vehicle on a particular transit line, the current location being obtained from a transit vehicle location device;
b) determining a particular transit route from the current location of the particular transit vehicle through one or more remaining stop zones of the particular transit line by:
b-1) determining one or more remaining route segment options based on the one or more remaining stop zones and a plurality of route segment options;
b-2) for each individual route segment of the one or more remaining route segment options:
b-2a) to retrieve, from a real-time traffic information service, one or more traffic condition factors related to the individual route segment;
b-2b) to determine, from the one or more tr

Assignees

• Ullrich Oliver
• Rishe Naphtali
• LUCKERATH Daniel
• Univ Florida Int

Inventors

• Ullrich Oliver
• Rishe Naphtali
• LUCKERATH Daniel

Classifications

• G08G1/133 Primary

  within the vehicle {; Indicators inside the vehicles or at stops} · CPC title

• G06Q10/04

  Forecasting or optimisation specially adapted for administrative or management purposes, e.g. linear programming or "cutting stock problem" (market predictions or forecasting for commercial activities G06Q30/0202) · CPC title

• G08G1/096844

  where the complete route is dynamically recomputed based on new data · CPC title

• G08G1/127

  to a central station {; Indicators in a central station} · CPC title

• G08G1/0112

  from the vehicle, e.g. floating car data [FCD] · CPC title