Method and apparatus for assigning vehicles to trips

• US 10,352,720 B2
• Filed: 08/28/2013
• Issued: 07/16/2019
• Est. Priority Date: 08/28/2013
• Status: Active Grant

• Current Assignee: HERE Global B.V. (HERE Holding Corporation)
• Original Assignee: HERE Global B.V. (HERE Holding Corporation)
• Inventors: Stenneth, Leon
• Primary Examiner(s): Ziaeianmehdizadeh, Navid
• Application Number:
  US14/012,329
• Publication Number:
  US 20150066361A1
• Time in Patent Office: 2,148 Days
• Field of Search: None
• CPC Class Codes: G01C 21/3691 Retrieval, searching and output of information related to real-time traffic, weather, or environmental conditions arrangements for giving variable traffic instructions G08G1/09
• CPC Class Codes: G06Q 10/047 Optimisation of routes or paths, e.g. travelling salesman problem
• CPC Class Codes: G06Q 50/40 Business processes related to the transportation industry shipping G06Q10/083
• CPC Class Codes: G08G 1/123 indicating the position of vehicles, e.g. scheduled vehicles; Managing passenger vehicles circulating according to a fixed timetable, e.g. buses, trains, tramstransmission of navigation instructions to vehicles G08G1/0968
• CPC Class Codes: G08G 1/127 to a central station ; Indicators in a central station

Abstract

A method, apparatus and computer program products are provided for matching a transit vehicle to a trip. An example method may comprise receiving probe data, the probe data comprising at least one of identity information, location information, or time information corresponding to the transit vehicle, causing placement of the probe data into a queue, wherein a placement in the queue is dependent on how much of the trip the transit vehicle has completed as indicated by the probe data, and causing assignment of the transit vehicle to a single candidate trip from among a set of candidate trips comprising a scheduled arrival time at a next closest stop closest to a calculated arrival time.

Claims

1. A method for assigning a transit vehicle whose location trace is available to a single candidate trip among a set of candidate trips for a route, the method comprising:

receiving probe data, the probe data comprising at least one of identity information, location information, or time information corresponding to a transit vehicle;

determining a route corresponding to the probe data of the transit vehicle;

causing, using a processor, placement of the probe data into an entry in a priority queue associated with the route in accordance with a priority criterion, each entry in the priority queue representative of a single transit vehicle traveling along the route, the priority queue being one queue of at least two queues and indicative of a direction, wherein a placement of each entry in the priority queue is dependent on how much of the trip the associated transit vehicle has completed as indicated by the probe data for each entry, wherein the priority criterion for the placement in the priority queue includes distance along the route, such that entry data corresponding to probe data indicative of transit vehicles that are further along the route are prioritized within the priority queue;

causing assignment of the transit vehicle to a single candidate trip from among a set of candidate trips for the route comprising a scheduled arrival time at a next closest stop closest to a calculated arrival time;

causing removal of the entry associated with the transit vehicle from the priority queue associated with the route in response to the transit vehicle being assigned to the single candidate trip;

causing storage of information indicating a match between the transit vehicle and the single candidate trip from among the set of candidate trips;

causing monitoring, for a predetermined period of time, of the probe data of the transit vehicle for a change in state, wherein the states of the transit vehicle are one of active at start, new, change in direction, change in route, and silent; and

providing for personalized, real-time transit routing and alerting based on the matched transit vehicle and the single candidate trip.

2. The method of claim 1, further comprising:

determining the next closest stop based on the probe data;

calculating the arrival time of the transit vehicle at the next closest stop,

wherein each candidate trip comprises a plurality of stops, each stop having a scheduled arrival time; and

determining which single candidate trip from one or more unmatched scheduled trips comprises a scheduled arrival time for the next closest stop nearest in time to the calculated arrival time.

3. The method of claim 1, wherein the transit vehicle is a first transit vehicle, the method further comprising:

receiving probe data corresponding to a second transit vehicle;

causing assignment of the second transit vehicle to a second priority in the priority queue lower than the first transit vehicle in response to the second transit vehicle having completed less of a trip than the first transit vehicle, and

causing assignment of the second transit vehicle to a second single candidate trip from among a set of candidate trips comprising a scheduled arrival time at a next closest stop closest to a calculated arrival time.

4. The method of claim 1, further comprising:

causing assignment of a new transit vehicle to a next scheduled trip in an instance in which the priority queue is empty and the new transit vehicle is identified.

5. The method of claim 1, further comprising:

identifying a change in state of at least one transit vehicle; and

causing a purging of one or more assignments from a memory.

6. An apparatus for assigning a transit vehicle whose location trace is available to a single candidate trip among a set of candidate trips for a route, the apparatus comprising at least one processor and at least one memory including computer program code, the at least one memory and the computer program code configured to, with the processor, cause the apparatus to at least:

receive probe data, the probe data comprising at least one of identity information, location information, or time information corresponding to a transit vehicle;

determine a route corresponding to the probe data of the transit vehicle;

cause placement of the probe data into an entry in a priority queue associated with the route in accordance with a priority criterion, each entry in the priority queue representative of a single transit vehicle traveling along the route, the priority queue being one queue of at least two queues and indicative of a direction, wherein a placement of each entry in the priority queue is dependent on how much of the trip the associated transit vehicle has completed as indicated by the probe data for each entry, wherein the priority criterion for the placement in the queue includes distance along the route, such that entry data corresponding to probe data indicative of transit vehicles that are further along the route are prioritized within the priority queue;

cause assignment of the transit vehicle to a single candidate trip from among a set of candidate trips for the route comprising a scheduled arrival time at a next closest stop closest to a calculated arrival time;

cause removal of the entry associated with the transit vehicle from the priority queue associated with the route in response to the transit vehicle being assigned to the single candidate trip;

cause storage of information indicating a match between the transit vehicle and the single candidate trip from among the set of candidate trips; and

cause monitoring, for a predetermined period of time, of the probe data of the transit vehicle for a change in state, wherein the states of the transit vehicle are one of active at start, new, change in direction, change in route, and silent.

7. The apparatus according to claim 6, wherein the at least one memory and the computer program code are further configured to, with the processor, cause the apparatus to:

determine the next closest stop based on the probe data;

calculate the arrival time of the transit vehicle at the next closest stop, wherein each candidate trip comprises a plurality of stops, each stop having a scheduled arrival time; and

determine which single candidate trip from one or more unmatched scheduled trips comprises a scheduled arrival time for the next closest stop nearest in time to the calculated arrival time.

8. The apparatus according to claim 6, wherein the transit vehicle is a first transit vehicle, and wherein the at least one memory and the computer program code are further configured to, with the processor, cause the apparatus to:

receive probe data corresponding to a second transit vehicle;

cause assignment of the second transit vehicle to a second priority in the priority queue lower than the first transit vehicle in response to the second transit vehicle having completed less of a trip than the first transit vehicle, and

cause assignment of the second transit vehicle to a second single candidate trip from among a set of candidate trips comprising a scheduled arrival time at a next closest stop closest to a calculated arrival time.

9. The apparatus according to claim 6, wherein the at least one memory and the computer program code are further configured to, with the processor, cause the apparatus to:

cause assignment of a new transit vehicle to a next scheduled trip in an instance in which the priority queue is empty and the new transit vehicle is identified.

10. The apparatus according to claim 6, wherein the at least one memory and the computer program code are further configured to, with the processor, cause the apparatus to:

identify a change in state of at least one transit vehicle; and

cause a purging of one or more assignments from memory.

11. A computer program product for assigning a transit vehicle whose location trace is available to a single candidate trip among a set of candidate trips for a route, the computer program product comprising at least one non-transitory computer-readable storage medium having computer-executable program code portions stored therein, the computer-executable program code portions comprising program code instructions for:

receiving probe data, the probe data comprising at least one of identity information, location information, or time information corresponding to a transit vehicle;

determining a route corresponding to the probe data of the transit vehicle;

causing placement of the probe data into an entry in a priority queue associated with the route in accordance with a priority criterion, each entry in the priority queue representative of a single transit vehicle traveling along the route, the priority queue being one queue of at least two queues and indicative of a direction, wherein a placement of each entry in the queue is dependent on how much of the trip the associated transit vehicle has completed as indicated by the probe data for each entry, wherein the priority criterion for the placement in the queue includes distance along the route, such that entry data corresponding to probe data indicative of transit vehicles that are further along the route are prioritized within the priority queue;

causing assignment of the transit vehicle to a single candidate trip from among a set of candidate trips for the route comprising a scheduled arrival time at a next closest stop closest to a calculated arrival time;

causing removal of the entry associated with the transit vehicle from the priority queue associated with the route in response to the transit vehicle being assigned to the single candidate trip;

causing storage of information indicating a match between the transit vehicle and the single candidate trip from among the set of candidate trips; and

causing monitoring, for a predetermined period of time, of the probe data of the transit vehicle for a change in state, wherein the states of the transit vehicle are one of active at start, new, change in direction, change in route, and silent.

12. The computer program product according to claim 11, wherein the computer-executable program code portions further comprise program code instructions for:

determining the next closest stop based on the probe data;

calculating the arrival time of the transit vehicle at the next closest stop,

wherein each candidate trip comprises a plurality of stops, each stop having a scheduled arrival time; and

determining which single candidate trip from one or more unmatched scheduled trips comprises a scheduled arrival time for the next closest stop nearest in time to the calculated arrival time.

13. The computer program product according to claim 11, wherein the transit vehicle is a first transit vehicle, wherein the computer-executable program code portions further comprise program code instructions for:

receiving probe data corresponding to a second transit vehicle;

causing assignment of the second transit vehicle to a second priority in the priority queue lower than the first transit vehicle in response to the second transit vehicle having completed less of a trip than the first transit vehicle, and

causing assignment of the second transit vehicle to a second single candidate trip from among a set of candidate trips comprising a scheduled arrival time at a next closest stop closest to a calculated arrival time.

14. The computer program product according to claim 11, wherein the computer-executable program code portions further comprise program code instructions for:

causing assignment of a new transit vehicle to a next scheduled trip in an instance in which the priority queue is empty and the new transit vehicle is identified.

15. The computer program product according to claim 11, wherein the computer-executable program code portions further comprise program code instructions for:

identifying a change in state of at least one transit vehicle; and

causing a purging of one or more assignments from the at least one memory.