Dynamic routing of transit vehicles

• US 9,786,173 B2
• Filed: 08/18/2015
• Issued: 10/10/2017
• Est. Priority Date: 08/18/2015
• Status: Active Grant

• Current Assignee: The Florida International University Board of Trustees (State University System of Florida)
• Original Assignee: The Florida International University Board of Trustees (State University System of Florida)
• Inventors: Ullrich, Oliver, Rishe, Naphtali, Luckerath, Daniel
• Primary Examiner(s): Nguyen, Bao Long T
• Application Number:
  US14/829,021
• Publication Number:
  US 20170053531A1
• Time in Patent Office: 784 Days
• Field of Search: 701117, 701410, 701411, 701414, 701415, 701416, 701423, 701465, 700 28, 700 32
• CPC Class Codes: G06Q 10/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 Class Codes: G06Q 10/047 Optimisation of routes or paths, e.g. travelling salesman problem
• CPC Class Codes: G08G 1/0112 from the vehicle, e.g. floating car data [FCD]
• CPC Class Codes: G08G 1/0116 from roadside infrastructure, e.g. beacons
• CPC Class Codes: G08G 1/012 from other sources than vehicle or roadside beacons, e.g. mobile networks
• CPC Class Codes: G08G 1/0145 for active traffic flow control
• CPC Class Codes: G08G 1/096811 where the route is computed offboard
• CPC Class Codes: G08G 1/096822 where the segments of the route are transmitted to the vehicle at different locations and times
• CPC Class Codes: G08G 1/096844 where the complete route is dynamically recomputed based on new data
• CPC Class Codes: G08G 1/127 to a central station ; Indicators in a central station
• CPC Class Codes: G08G 1/133 within the vehicle ; Indicators inside the vehicles or at stops

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.

Claims

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_top 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<sub>i−

1</sub>) 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<sub>i−

1</sub> 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<sub>i−

1</sub> 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<sub>i−

1</sub>) 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<sub>i−

1</sub>) 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<sub>i−

1</sub> 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 traffic condition factors, a route segment option weight; and

b-2c) to calculate a dynamic cost function based on;

b-2c(i)) the route segment option weight for the individual route segment, and

b-2c(ii)) stop option weighting factors for stop options connected by the individual route segment; and

b-2d) selecting the particular transit route, the particular transit route being comprised of an optimized set of individual route segments, the optimized set of individual route segments being optimized with respect to a totality of dynamic cost functions; and

c) returning the particular transit route to the particular transit vehicle.

13. The method of claim 12, 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<sub>i−

1</sub>) 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<sub>i−

1</sub> and s_i+1 multiplied by a selected first skip weighting factor, wherein the selected first skip weighting factor is greater than one, determining the optimized set of individual route segments by skipping the specific stop zone s_i and proceeding directly from s<sub>i−

1</sub> to s_i+1.

14. The method of claim 12, 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<sub>i−

1</sub>) 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<sub>i−

1</sub>) and the next stop zone (s_i+1) multiplied by a selected second skip weighting factor, wherein the selected second skip weighting factor is greater than one, determining the optimized set of individual route segments by skipping the specific stop zone s_i and proceeding directly from s<sub>i−

1</sub> to s_i+1.

15. The method of claim 12, further comprising:

sending one or more notification messages to one or more notification interfaces.

16. The method of claim 15, 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.

17. The method of claim 12, 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.

18. The method of claim 17, 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.

19. The method of claim 12, wherein a stop option weighting factor comprises one or more preference criteria selected from the group consisting 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.

20. The method of claim 12, wherein the route segment option weight is computed from input data, and 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.