Disruption forecasting in complex schedules

Patent metadata

Field	Value
Publication number	US-11023816-B2
Application number	US-201514746282-A
Country	US
Kind code	B2
Filing date	Jun 22, 2015
Priority date	Mar 13, 2015
Publication date	Jun 1, 2021
Grant date	Jun 1, 2021

Abstract

A method for forecasting time delays added to a scheduled start time and a scheduled end time of a task includes generating a stochastic model of the task and resources affecting the task, the stochastic model includes a reactionary delay component that is a function of previous task end times and a root cause delay component that is an independent random process at a specific time. The method further includes: calculating a probability distribution of time delays added to the scheduled start time as a combination of the reactionary delay component and the root cause delay component using the stochastic model to provide a probability distribution of start times; and calculating a probability distribution of time delays added to the scheduled end time as a combination of the reactionary delay component and the root cause delay component using the stochastic model to provide a probability distribution of end times.

First claim

What is claimed is:

1. A method for transforming a physical transportation task having a scheduled start time and a scheduled end time based on forecasting time delays added to the scheduled start time and the scheduled end time of the physical transportation task, the method comprising:
generating a stochastic model of the physical transportation task and a transport apparatus implementing the physical transportation task, the stochastic model comprising a reactionary delay component and a root-cause delay component, the reactionary delay component being a function of previous physical transportation task end times and the root-cause delay component being an independent random process at a specific time;
calculating a probability distribution of time delays added to the scheduled start time as a combination of the reactionary delay component and the root cause delay component using the stochastic model to provide a probability distribution of start times; and
calculating a probability distribution of time delays added to the scheduled end time as a combination of the reactionary delay component and the root cause delay component using the stochastic model to provide a probability distribution of end times;
wherein the generating, the calculating a probability distribution of time delays added to the scheduled start time, and the calculating a probability distribution of time delays added to the scheduled end time are implemented by a processor;
wherein the stochastic model comprises a hidden Markov model (HMM);
wherein the HMI comprises:
(a) an initial state distribution ρ 0 (x) to estimate a previous state x t-1 for each resource;
(b) a current state x t conditioned on x t-1 obtained using conditional probability distribution p(x t |x t-1 ) for each resource;
(c) additional details c i conditioned on x t-1 obtained using conditional probability distribution q(c t |x t ) for each resource; and
(d) a departure-related noise-term Y α i ,i conditioned on x t and c t obtained using conditional probability distribution r(y t |c t ,x t ) for each resource;
transforming the physical transportation task by replacing the transport apparatus implementing the physical transportation task by a computer implemented process that transmits a signal in response to the probability distribution of start times and the probability distribution of end times.

2. The method according to claim 1 , further comprising training the HMM using historical schedule and delay data.

3. The method according to claim 1 , wherein the physical transportation task is the transport apparatus stopping at a station and the scheduled start time is a scheduled arrival time of the transport apparatus at the station and the scheduled end time is a scheduled departure time of the transport apparatus at the station.

4. The method according to claim 3 , wherein the transport apparatus is a train.

5. The method according to claim 1 , further comprising displaying the probability distribution of start times and the probability distribution of end times to a user using a user interface.

6. The method according to claim 1 , further comprising storing the probability distribution of start times and the probability distribution of end times in memory or a storage medium.

7. The method according to claim 1 , further comprising identifying a mode or an expectation or another risk measure of the probability distribution of start times as a most likely start time and identifying a mode or an expectation or another risk measure of the probability distribution of end times as a most likely end time.

8. The method according to claim 7 , further comprising updating a schedule to include the most likely start time and the most likely end time.

9. The method according to claim 1 , wherein the physical transportation task comprises a plurality of sub-tasks and the method further comprises:
generating a stochastic model of each of the sub-tasks and resources implementing the sub-tasks, the stochastic model comprising a reactionary delay component and a root-cause delay component, the reactionary delay component being a function of previous sub-task end times and the root-cause delay component being an independent random process at a specific time;
calculating a probability distribution of time delays added to a scheduled start time of each sub-task as a combination of the reactionary delay component and the root cause delay component of each sub-task using the stochastic model of each of the sub-tasks and resources implementing the sub-tasks to provide a probability distribution of start times of the sub-tasks; and
calculating a probability distribution of time delays added to a scheduled end time of each sub-task as a combination of the reactionary delay component and the root cause delay component of each sub-task using the stochastic model of each of the sub-tasks and resources implementing the sub-tasks to provide a probability distribution of end times of the sub-tasks.

10. The method according to claim 1 , further comprising taking action to prevent a first delay of the physical transportation task from causing a second delay of a second physical transportation task in response to the probability distribution of start times and the probability distribution of end times.

11. The method according to claim 1 , further comprising updating in real time a schedule comprising at least one of a start time and an end time in response to at least one of the probability distribution of start times and the probability distribution of end times.

12. The method according to claim 11 , further comprising implementing a second physical transportation task according to the updated schedule.

13. The method according to claim 1 , wherein the physical transportation task is further transformed to incorporate at least one of a new scheduled start time, a new scheduled end time.

14. A method for transforming a physical transportation task having a scheduled start time and a scheduled end time based on forecasting time delays added to the scheduled start time and the scheduled end time of the physical transportation task, the method comprising:
generating a stochastic model of the physical transportation task and a transport apparatus implementing the physical transportation task, the stochastic model comprising a reactionary delay component and a root-cause delay component, the reactionary delay component being a function of previous physical transportation task end times and the root-cause delay component being an independent random process at a specific time;
calculating a probability distribution of time delays added to the scheduled start time as a combination of the reactionary delay component and the root cause delay component using the stochastic model to provide a probability distribution of start times; and
calculating a probability distribution of time delays added to the scheduled end time as a combination of the reactionary delay component and the root cause delay component using the stochastic model to provide a probability distribution of end times;
wherein the generating, the calculating a probability distribution of time delays added to the scheduled start time, and the calculating a probability distribution of time delays added to the scheduled end time are implemented by a processor;
wherein the physical transportation task is the transport apparatus stopping at a station and the scheduled start time is a scheduled arrival time of the transport apparatus at the station and the scheduled end time is a scheduled departure time of the transport apparatus at the station; and
wh

Assignees

• IBM

Inventors

• Cogill Randall L
• Marecek Jakub
• Mevissen Martin
• Palmes Paulito
• Shorten Robert
• Wirth Fabian R

Classifications

• G06N7/01 Primary

  Probabilistic graphical models, e.g. probabilistic networks · CPC title

• G06Q10/0635 Primary

  Risk analysis of enterprise or organisation activities · CPC title

• B61L27/14

  Following schedules · CPC title

• B61L27/12

  Preparing schedules · CPC title

• G06Q10/06311

  Scheduling, planning or task assignment for a person or group · CPC title