以網路模式求解考慮預算限制之風險最小化鋪面養護規劃問題

Abstract

公路是國家發展的重要命脈，高品質的公路不僅可提升人民的生活水準，還帶動了國家的交通運輸、經濟、政治等各領域的發展。因此，如何而能不間斷地持續維護與改善公路品質，以求更安全舒適的行車環境至為重要。隨著公路的使用率增加，各路段不一之鋪面毀損程度亦將日益惡化，然而其鋪面養護預算卻經常不足以全面修復所有路段。因此，政府常必須選擇性地將有限的鋪面養護經費花在修復部分路段，以極小化公路的整體風險程度。 本研究針對鋪面毀損狀況不同的一維連續路段，在有限的養護維修預算下，探討如何將路段分組維修以達成整體風險程度最小之路段集群維修問題。此一路段集群維修問題必須遵守一些行之有年的特殊業界修復規範與習慣，譬如目前之鋪面風險程度高於門檻值的路段一定要被修復；被劃分於同一修復分組的待修路段總數必須足夠多，且這些路段必須為連續相鄰；此外，同一分組中的所有路段一定要採取其分組中修復花費最昂貴路段的修復方式來全面修復之。雖然被修復的路段其風險程度將被歸零，但不同的修復分組方式亦將引發不同的維修成本，因此求解最佳的修復分組方式為一個複雜的組合最佳化問題。 本研究首先將各路段與分組分別視為顧客與廠商，即可將本問題轉換成一個特殊的無容量限制之設施區位問題，並建構一整數規劃模式求解之。然而該整數規劃模式必須使用?多限制式來處理分組的規範與習慣，因而導致求解過程極為耗時。因此，本研究再將各路段視為節點，各種合乎風險門檻與分組路段總數限制的分組方式視為「分組節線」，並針對可以不用修復的路段建立「原狀節線」，藉以建構一個特殊的網路圖；其中每條節線代表路段的分組，分別具有其維修成本與風險等兩種權重，而該網路圖上自路段一的起始節點連通至最終路段節點的任一路徑即代表一種修復分組方式，其路徑上所有節線的兩種權重分別加總即代表該種修復方式的總維修花費與總風險，而求取滿足預算限制之最佳的修復分組方式即可對應成於該網路圖上計算一條滿足額外預算限制的最短路徑問題（Constrained Shortest Path CSP）。 為測試解法之求解效能，我們利用最佳化軟體Gurobi求解本研究所發展之特殊設施區位問題以及CSP等兩種整數規劃模式，再依據CSP文獻設計拉氏鬆弛法(Lagrangian Relaxation LR)與第K短路徑演算法(KSP)等兩種常見的CSP求解方法。數值測試結果顯示，以Gurobi求解設施區位與CSP等兩種整數規劃模式，以及KSP之求解時間經常會隨著問題規模擴大而急遽增加；LR雖可以在較短時間快速求得一個好的解，但偶爾會因對偶間隙(Duality Gap)而難以收斂。因此，本研究最後以LR之可行解為基礎，再運用模擬退火法(Simulated Annealing SA)加以改善收歛效率，以更有效地求解路段集群維修問題。

Date of Award	2014 Aug 28
Original language	Chinese
Supervisor	I-Lin Wang (Supervisor)