道路系統受到自然災害的重創時,導致民眾的生命財產受到嚴重威脅,然而災害發生時點、災害結束時點是無法預期的,因此工程師往往只能透過實際災害發生狀況進一步去推估道路搶修時間,由上述可知,在緊急搶修排程問題中存在依時性及不確定性的問題特質。本研究利用隨機規劃技巧建構一隨機作業時間之即時緊急搶修排程模式。 本研究將新增的災點視為搶修排程問題裡的即時資訊,因此,我們發展出一多階段規劃模式來決定工作隊的搶修排程。每一階段的問題隨著新災點的產生或隨機作業時間結束而進到下一階段。而新災點的搶修順序和到達時間將隨之被安排。此一排程的動作會一直重覆,直到所有災點均被納入排程計劃中。 本研究並發展出一套利用樣本抽樣的線上演算法來解決上述的排程問題,發現當能掌握的災點資訊比例愈多時,隨機搶修排程模式的災點總到達時間就愈少,表示掌握愈多的災點資訊,愈能規劃出符合最小到達時間的緊急搶修指派路線。此外,本研究利用完全資訊價值(EVPI)和隨機解價值(VSS)兩項指標探討隨機需求規劃和完全資訊規劃之間的差異。結果呈現EVPI及VSS均為正值,隨機需求的規劃相較於確定性需求規劃有小幅度的改善。
The roadway system is in infrastructure of city lifeline. While the roadway system is broken by natural disasters, people's property and life will be are threatened seriously. Emergency rehabilitation of roadway system is essential to disaster rescue and response. An emergency scheduling tool can help the authority rehabilitate the broken roadway system as soon as possible. However, according to the actual damage situation, the experienced civil engineers estimate the duration times of roadway repair, once the disaster occurs. As all above mentions, time dependence and uncertainties indeed exist in the emergency rehabilitation scheduling problem (ERSP). In this study, we utilize stochastic programming skills to formulate a real-time emergency rehabilitation scheduling model with stochastic duration time. We regard the newly damage points as real-time information in this study. Consequently, a multiple-stage stochastic programming model is proposed to determine the rehabilitation schedules of work teams. If any one newly damaged point occurs or any stochastic duration time is realized, the stage of this stochastic problem is changed to next stage. The rehabilitation order and arrival time of newly damaged points are arranged. This rescheduling job is repeated until all damaged points are restored. In addition, an on-line algorithm integrated with a sampling-based approximation method is developed for solving this problem. Numerical examples are elaborated to demonstrate the characteristics of ERSP and to prove the validness of the developed algorithm. According to test results, we found that the more the proportion of given damaged points is, the more total arrival time of all damaged points is. Furthermore, two indices, Expected Value of Perfect Information (EVPI) and Value of the Stochastic Solution (VSS), are adopted to discuss the difference of the stochastic programming model and deterministic programming model. The values of the EVPI and VSS are all positive in our testing examples. It is shown that the stochastic programming approach to the ERSP is better than the deterministic programming one. Keywords: Rehabilitation scheduling, stochastic repair time, Sampling-based Approximation Method