隨機作業時間之道路災害緊急搶修排程模式與演算法探討

Stochastic Real-Time Emergency Rehabilitation Scheduling Modeling and Algorithm Development

李德全(Te-Chuan Li)

指導教授 ： 張美香

中原大學/工學院/土木工程學系/碩士(2009年)

https://doi.org/10.6840/cycu200900411

摘要

道路系統受到自然災害的重創時，導致民眾的生命財產受到嚴重威脅，然而災害發生時點、災害結束時點是無法預期的，因此工程師往往只能透過實際災害發生狀況進一步去推估道路搶修時間，由上述可知，在緊急搶修排程問題中存在依時性及不確定性的問題特質。本研究利用隨機規劃技巧建構一隨機作業時間之即時緊急搶修排程模式。
本研究將新增的災點視為搶修排程問題裡的即時資訊，因此，我們發展出一多階段規劃模式來決定工作隊的搶修排程。每一階段的問題隨著新災點的產生或隨機作業時間結束而進到下一階段。而新災點的搶修順序和到達時間將隨之被安排。此一排程的動作會一直重覆，直到所有災點均被納入排程計劃中。
本研究並發展出一套利用樣本抽樣的線上演算法來解決上述的排程問題，發現當能掌握的災點資訊比例愈多時，隨機搶修排程模式的災點總到達時間就愈少，表示掌握愈多的災點資訊，愈能規劃出符合最小到達時間的緊急搶修指派路線。此外，本研究利用完全資訊價值(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

並列關鍵字

Sampling-based Approximation Method ； stochastic repair time ； Rehabilitation scheduling

參考文獻

7. 李思漢(2005)，考慮回收機制下再生物料混合比例之最佳生產模式，國立臺灣大學商學研究所碩士班論文。

2. 王福聖(2008)，不精確資訊下震災路網搶修排程與民眾對搶修時間可忍受度之研究，國立中央大學土木工程學系碩士論文。

26. 廖慧凱(2006)，道路災害搶修與緊急物流配送問題之探討，國立中央大學土木工程學系碩士論文。

14. 張家維(2006)，短期道路養護工作隊排程規劃之研究，國立中央大學土木工程學系碩士論文。

19. 湯慶輝(2006)，隨機性擾動下規劃問題求解演算法之研究，國立中央大學土木工程研究所博士論文。