Disruption forecasting in complex schedules

Patent metadata

Field	Value
Publication number	US-11074513-B2
Application number	US-201514657378-A
Country	US
Kind code	B2
Filing date	Mar 13, 2015
Priority date	Mar 13, 2015
Publication date	Jul 27, 2021
Grant date	Jul 27, 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 system 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 system comprising:
a transport apparatus implementing the physical transportation task;
a processor configured to:
generate a stochastic model of the physical transportation task and the transport apparatus implementing the physical transportation task, the stochastic model comprising a reactionary delay component and a root cause delay component, the reactionary component being a function of previous task end times and the root cause delay component being an independent random process at a specific time;
calculate 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;
calculate 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;
transmit a signal comprising the probability distribution of start times and the probability distribution of end times to a signal receiving device;
wherein the stochastic model comprises a hidden Markov model (HMM);

wherein the HMM 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;
a signal receiving device configured to receive the signal comprising the probability distribution of start times and the probability distribution of end times;
wherein the physical transportation task is transformed by replacing the transport apparatus implementing the physical transportation task by a computer implemented process in which a computer system is configured to transmit a signal in response to the probability distribution of start times and the probability distribution of end times.

2. The system according to claim 1 , wherein the signal receiving device comprises at least one of a display and a printer.

3. The system according to claim 1 , wherein the signal receiving device comprises at least one of a non-transitory storage medium and memory.

4. The system according to claim 1 , wherein the processor is further configured to train the HMM using historical schedule and delay data.

5. The system according to claim 1 , wherein the physical transportation task comprises a plurality of sub-tasks and the processor is further configured to:
generate 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;
calculate 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
calculate 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.

6. The system according to claim 1 , wherein the processor is further configured to implement the computer implemented process 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.

7. The system according to claim 1 , wherein the processor is further configured to update in real time a published 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.

8. The system according to claim 7 , wherein the processor is further configured to implement a second physical transportation task according to the updated published schedule.

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

10. A system 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 comprising:
a transport apparatus implementing the physical transportation task;
a processor configured to:
generate a stochastic model of the physical transportation task and the resources implementing the physical transportation task, the stochastic model comprising a reactionary delay component and a root cause delay component, the reactionary 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;
calculate 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;
calculate 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; and
transmit a signal comprising the probability distribution of start times and the probability distribution of end times to a signal receiving device;
wherein the physical transportation task comprises a transport stopping at a station and the scheduled start time is a scheduled arrival time of the transport at the station and the scheduled end time is a scheduled departure time of the transport at the station; and
wherein calculating a probability distribution of time delays added to the scheduled end time comprises performing a convolution of Y α i ,i , the scheduled departure time s i and a function of the maximum of arrival times {A j } of predecessor transports;

a signal receiving device configured to receive the signal comprising the probability distribution of start times and the probability distribution of end times;
wherein the physical transportation task is transformed by replacing the transport apparatus implementing the physical transportation task by a computer implemented process in which a computer system is configured to transmit a signal in response to the probability distribution of start times and the probability distribution of end times.

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