Method and system for dispatching of vehicles in a public transportation network

• US 10,176,443 B2
• Filed: 08/09/2016
• Issued: 01/08/2019
• Est. Priority Date: 08/09/2016
• Status: Active Grant

• Current Assignee: Conduent Business Services, LLC (Conduent, Inc.)
• Original Assignee: Conduent Business Services, LLC (Conduent, Inc.)
• Inventors: Tulabandhula, Theja, Jayachandran, Prabuchandran Krithivasan, Bodas, Tejas Prakash
• Primary Examiner(s): Mansfield, Thomas L
• Application Number:
  US15/232,182
• Publication Number:
  US 20180046961A1
• Time in Patent Office: 882 Days
• Field of Search: None
• CPC Class Codes: G06F 18/295 Markov models or related models, e.g. semi-Markov models; Markov random fields; Networks embedding Markov models
• CPC Class Codes: G06N 20/00 Machine learning
• CPC Class Codes: G06N 7/01 Probabilistic graphical models, e.g. probabilistic networks
• CPC Class Codes: G06Q 10/06315 Needs-based resource requirements planning or analysis
• CPC Class Codes: G06T 7/97 Determining parameters from multiple pictures depth or shape recovery from multiple images G06T7/55; stereo camera calibration G06T7/85
• CPC Class Codes: G06V 10/85 Markov-related models; Markov random fields
• CPC Class Codes: G06V 20/52 Surveillance or monitoring of activities, e.g. for recognising suspicious objects recognising microscopic objects G06V20/69
• CPC Class Codes: G06V 40/103 Static body considered as a whole, e.g. static pedestrian or occupant recognition
• CPC Class Codes: G06V 40/161 Detection; Localisation; Normalisation
• CPC Class Codes: G08G 1/202 Dispatching vehicles on the basis of a location, e.g. taxi dispatching

Abstract

A system for dispatching vehicles in a public transportation network may include a passenger monitoring system configured to monitor a number of passengers waiting at a stop in the transportation network, a vehicle dispatching system and a processing device. The processing device may apply a Markov Decision Process (MDP) model to determine a score for each of multiple decision rules, in which each score represents a number of passengers waiting at the stop at the end of a time interval, and use the scores to identify a number of waiting passengers at which a reserve vehicle should be dispatched. The system may use information received from the passenger monitoring system to determine a state at an instant of time, and determine whether a reserve vehicle should be dispatched based on the MDP model and cause the vehicle dispatch system to dispatch a reserve vehicle or retain a nominal vehicle.

Claims

1. A system for dispatching vehicles in a public transportation network, comprising:

a monitoring system configured to monitor a number of passengers waiting at a stop in a public transportation network;

a vehicle dispatching system;

a processing device communicatively coupled to the monitoring system; and

a non-transitory computer readable medium in communication with the processing device, the computer readable medium storing one or more programming instructions for causing the processing device to;

apply a Markov Decision Process model by;

identifying a plurality of states of the public transportation network, in which each state comprises a time interval and a number of passengers waiting at the stop in the time interval,

identifying a plurality of decision rules, wherein each decision rule is indicative of whether to dispatch a reserve vehicle or to keep using a nominal vehicle during any of the states,

applying the decision rules to a plurality of states and determining a score for each of the decision rules, in which each score represents a number of passengers waiting at the stop at the end of the time interval for the state to which the decision rule is applied, and

using the scores to identify a number of waiting passengers at which a reserve vehicle should be dispatched during a future time interval;

receive information from the monitoring system and use the received information to determine a state at an instant of time;

determine whether a reserve vehicle should be dispatched after the instant of time by applying the Markov Decision Process model to the determined state; and

cause the vehicle dispatching system to dispatch a reserve vehicle after the instant of time if the Markov Decision Process model for the determined state indicates that a reserve vehicle be dispatched, otherwise cause the vehicle dispatch system to retain a nominal vehicle without dispatching a reserve vehicle.

2. The system of claim 1, wherein:

the monitoring system comprises a camera that is positioned at the stop; and

the one or more programming instructions comprise additional programming instructions that are configured to cause the processing device to;

receive, from the camera, a sequence of video frames of the stop; and

identify the number of passengers waiting at the stop based on the sequence of video frames.

3. The system of claim 1, wherein:

the monitoring system comprises a token reader that is positioned at the stop; and

the one or more programming instructions comprise additional programming instructions that are configured to cause the processing device to receive, from the token reader, a measured indication of a number of passengers who bore tokens and who passed within a detectable communication range of a receiver of the token reader.

4. The system of claim 1, in which the instructions to apply the decision rules to a plurality of states and determine the scores for each of the decision rules comprise instructions to:

identify a transition probability matrix indicative of probabilities between state transitions;

identify a reward matrix indicative of rewards between state transitions; and

update the Markov Decision Process model using the monitored number of passengers waiting at the stop during a plurality of time intervals to maximize an average reward over that time interval.

5. The system of claim 4, in which the instructions to determine a score for each of the decision rules comprise instructions to determine a running sum of a group of rewards for each decision rule over a plurality of time periods.

6. The system of claim 5, wherein each reward of the group of rewards is indicative of a reduction in the number of passengers waiting at the stop when each decision rule is applied.

7. The system of claim 4, wherein the instructions to determine the running sum of a group of rewards for each decision rule over the plurality of time periods comprises instructions to:

identify one or more time periods for which the decision rule achieves a maximum performance among all of the plurality of decision rules, wherein the performance indicates that an average number of passengers waiting at the stop was reduced when the decision rule is applied; and

determine the plurality of time intervals based on the identified one or more time periods.

8. The system of claim 1, in which the instructions to determine the score for each of the decision rules comprise instructions to determine a cumulative reward over a plurality of time intervals.

9. The system of claim 8, wherein the cumulative reward is indicative of a reduction in the number of passengers waiting when each decision rule is applied.

10. The system of claim 8, in which the instructions to determine the cumulative reward comprise instructions to:

identify one or more time periods for which the decision rule achieves a maximum performance among all of the plurality of decision rules, wherein the performance is based on a belief on an average cost reward under the decision rule; and

determine the plurality of time periods based on the identified one or more time periods.

11. A method of dispatching vehicles in a public transportation network, comprising:

monitoring, by a monitoring system, a number of passengers waiting at a stop in a public transportation network;

applying, by a processing device, a Markov Decision Process model by;

identifying a plurality of states of the public transportation network, in which each state comprises a time interval and a number of passengers waiting at the stop in the time interval,

identifying a plurality of decision rules, wherein each decision rule is indicative of whether to dispatch a reserve vehicle or to keep using a nominal vehicle during any of the states,

applying the decision rules to a plurality of states and determining a score for each of the decision rules, in which each score represents a number of passengers waiting at the stop at the end of the time interval for the state to which the decision rule is applied, and

using the scores to identify a number of waiting passengers at which a reserve vehicle should be dispatched during a future time interval;

receiving, by the processing device, information from the monitoring system and using the received information to determine a state at an instant of time;

determining, by the processing device, whether a reserve vehicle should be dispatched after the instant of time by applying the Markov Decision Process model to the determined state; and

dispatching, by a vehicle dispatching system, a reserve vehicle after the instant of time if the Markov Decision Process model for the determined state indicates that a reserve vehicle be dispatched, otherwise retaining a nominal vehicle without dispatching a reserve vehicle.

12. The method of claim 11, wherein:

the monitoring system comprises a camera; and

monitoring the number of passengers at the stop comprises;

receiving, by the processing device from the camera, a sequence of video frames of the stop, and

identifying the number of passengers waiting at the stop based on the sequence of video frames.

13. The method of claim 11, wherein:

the monitoring system comprises a token reader positioned at the stop; and

monitoring the number of passengers at the stop comprises;

receiving, by the processing device from the token reader, a measured indication of a number of passengers who bore tokens and who passed within a detectable communication range of a receiver of the token reader.

14. The method of claim 11, wherein applying the decision rules to a plurality of states and determining the scores for each of the decision rules comprise:

identifying, by the processing device, a transition probability matrix indicative of probabilities between state transitions;

identifying, by the processing device, a reward matrix indicative of rewards between state transitions; and

updating, by the processing device, the Markov Decision Process model using the monitored number of passengers waiting at the stop during a plurality of time intervals to maximize an average reward over that time interval.

15. The method of claim 14, in which determining the scores for each of the decision rules comprises determining a running sum of a group of rewards for each decision rule over a plurality of time periods.

16. The method of claim 15, wherein each reward of the group of rewards is indicative of a reduction in the number of passengers waiting at the stop when each decision rule is applied.

17. The method of claim 14, wherein determining the running sum of a group of rewards for each decision rule over the plurality of time periods comprises:

identifying, by the processing device, one or more time periods for which the decision rule achieves a maximum performance among all of the plurality of decision rules, wherein the performance indicates that an average number of passengers waiting at the stop was reduced when the decision rule is applied; and

determining the plurality of time periods based on the identified one or more time periods.

18. The method of claim 11, in which determining the score for each of the decision rules comprises determining a cumulative reward over a plurality of time intervals.

19. The method of claim 18, wherein the cumulative reward is indicative of a reduction in the number of passengers waiting when each decision rule is applied.

20. The method of claim 18, in which determining the cumulative reward comprises:

identifying one or more time periods for which the decision rule achieves a maximum performance among all of the plurality of decision rules, wherein the performance is based on a belief on an average cost reward under the decision rule; and

determining the plurality of time periods based on the identified one or more time periods.