道路災害搶修與緊急物流配送問題之探討

A study on network reconstruction and relief logistics

廖慧凱(Hui-Kai Liao)

指導教授 ： 陳惠國

國立中央大學/工學院/土木工程學系/碩士(2006年)

摘要

每當重大災害發生時，決策者必須在極短時間內將救災人員與救災機具做出適當的調度，以求有效的降低災區人員與財產之損失。本研究根據救災系統高階管理人員與中、低階技術人員對救災項目優先性的不同觀點，將救災問題建構為具主從關係(leader-follower)的雙層規劃模型(bi-level programming model)。上層問題為在黃金72小時內完成初部道路搶通，追求修復道路服務績效最大，以期達到系統最佳化；下層問題為物資配送問題，但不同於傳統含軟時窗限制與揀配貨物的車輛途程問題，本研究為建構在受破壞路網中貨物揀配的路線安排之模式，並以提出之演算法進行求解分析。以期在此階級式架構(hierarchical structure)下達到Stackelberg競局之系統均衡狀態，所獲結果作為執行疏散物流(relief logistics) 需求配送之主要依據。

關鍵字

主從關係 ； 黃金72小時 ； 雙層規劃問題 ； 系統最佳化 ； 階級式結構 ； 疏散物流

並列摘要

Natural disasters and accidents without serious concern often lead to dread consequences. Whereas the scarceness of resources affects the rescue performances largely, appropriate rescue deployment will be a main task to the decision maker. However, the preferred objectives between managing staff and operational staff are often hierarchical and conflicting so that the problem is modeled as a binary integer mathematical bilevel programming problem (BLPP) in accordance with Stackelberg game. Managing staff, as upper level, pursues to rescue most suffered people by recovering affected area with breakage in 72 hours, and operational staff, as lower level, seeks for a way to deliver or pick up the most relief goods and medical supplies as quick as possible. In particular, emergency vehicles and rescue troops are not necessarily required to go back to the depot where they depart. Decision maker attempts to service all the requests in the disaster area by forming efficient routes, at least nominally, subject to vehicle capacity, performance, and soft time window constraints. To deal with the linear 0-1 integer bilevel model, a heuristic algorithm will be developed to solve the hierarchical relief logistics in blocked areas problem through an iteratively intermediate solution which is generated by fixing upper level binary variables in turn from inducible region and then to reach a feasible solution. Finally, the result is applied to provide analytical information to decision maker for decision-making.

並列關鍵字

relief logistics ； Stackelberg game ； bilevel programming problem

參考文獻

16. Feng, C.M. and Wang, T.C., 2005, “Seismic emergency rehabilitation scheduling for rural highways,” Transportation Planning Journal, Vol. 34, No. 2, pp. 177-210.

1. Bard, J. F., 1990, “A branch and bound algorithm for the bilevel programming problem,” SIAM Journal of Scientific and Statistical Computing, Vol. 11, No. 2, pp.281-292.

3. Ben-Ayed, O., 1993, “Bilevel linear programming,” Computers and Operation Research, Vol. 20, pp.485-501.

5. Bräysy, O. and Gendreau, M., 2002, “Tabu search heuristics for the vehicle routing problem with time windows,” TOP, Vol. 10, No. 2, pp.211-237.

6. Bräysy, O. and Gendreau, M., 2005a, “Vehicle routing problem with time windows, part I: route construction and local search algorithms,” Transportation Science, Vol. 39, No. 1, pp.104-118.