臺灣博碩士論文加值系統

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

SUMMARY

The regular road maintenance and rehabilitation (M＆R) plan is important to keep the surface in a good shape. In practice, a road is divided into a set of contiguous segments, where each set is a pavement project treated by the same M＆R plan. With limited budget, we investigate an optimal pavement rehabilitation plan that seeks an optimal combination of road segments and their rehabilitation plan such that the total risks are minimized with limited budget.

By treating each segment as a customer and a pavement project as a warehouse, this problem can be formulated as a difficult uncapacitated facility location problem (UFLP) by integer program (IP). Then, we formulate this problem as a network flow model where a segment and a project is represented by a node and an arc, respectively. Thus, solving for the optimal M＆R plan equals to seeking a constrained shortest path (CSP). In particular, an optimal M＆R plan corresponds to a path of minimum risks that obeys additional feasibility constraints associated with arcs and path lengths. Finally, we proposed three solution methods for solving the CSP: Lagrangian relaxation (LR), the K shortest path (KSP), and a hybrid algorithm exploiting the simulated annealing (SA) framework to select segments to be treated and then solve for their M＆R plans by LR. Results of our computational experiments indicate some of our proposed heuristic solution methods are both effective and efficient.

Key words: Pavement rehabilitation, Integer program, Constrained shortest path, Lagrangian relaxation, K shortest path.

摘要 I
Extended Abstract III
誌謝 VI
目錄 VII
表目錄 X
圖目錄 XI
第一章 緒論 1
1.1 研究背景 1
1.2 研究動機與目的 1
1.3 研究問題與範圍 3
1.4 論文架構 4
第二章 文獻探討 5
2.1 無容量限制的設施區位問題 5
2.1.1 無容量限制的設施區位問題之簡介 5
2.1.2 無容量限制的設施區位問題之求解技術 6
2.2 集群問題 7
2.2.1 整數規劃在集群分析之應用 7
2.2.2 成串性質 8
2.2.3 一維的集群問題 9
2.3 鋪面養護規劃最佳化問題之相關研究 10
2.4 含額外限制式的最短路徑問題 12
2.4.1. 拉氏鬆弛法 13
2.4.2. 第K短路徑演算法 14
2.5 模擬退火法 15
2.6 小結 16
第三章 路段集群維修問題之數學模式及解法 17
3.1 問題描述與假設 17
3.1.1. 問題描述 17
3.1.2. 問題假設 19
3.2 整數規劃模式 19
3.2.1. 參數與變數定義 19
3.2.2. 模式說明 20
3.3 網路模式 23
3.3.1. 建立網路圖 23
3.3.2. 含額外限制式的最短路徑(CSP)模型 26
3.4 以拉氏鬆弛法求解CSP問題 27
3.4.1 模式轉換 27
3.4.2 次梯度法之介紹 28
3.5 以第K短路徑求解CSP問題 30
3.6 以模擬退火法求解修復路段最佳組合 32
3.7 結合拓樸排序之最短路徑演算法 36
3.8 小結 37
第四章 數值分析 38
4.1 參數設定 38
4.2 數值分析與結果 41
4.2.1 小型的資料集 41
4.2.2 中型資料集 43
4.2.3 大型資料集 46
4.3 小結 49
第五章 結論與未來研究方向 50
5.1 結論與貢獻 50
5.2 未來研究方向 51
參考文獻 53
附錄A、GRB1 求解數值 57
附錄B、GRB2 求解數值 58
附錄C、KSP 求解數值 61
附錄D、LR 求解數值 62
附錄E、SA 求解數值 65

張志強(1987)，「整數規劃在集群分析上之應用研究」，國立政治大學統計學研究所碩士論文

Ahuja, R.K., Magnanti, T.L., ＆ Orlin, J.B. (1993). Network flows: Theory, algorithms, and applications.
Al‐Sultan, K., ＆ Al‐Fawzan, M. (1999). A tabu search approach to the uncapacitated facility location problem. Annals of Operations Research, 86, 91-103.
Allwright, J. R., ＆ Carpenter, D. B. (1989). A distributed implementation of simulated annealing for the travelling salesman problem. Parallel Computing, 10(3), 335-338.
Álvarez, P., López-Rodríguez, F., Canito, J.L., Moral, F.J., ＆ Camacho, A. (2007). Development of a measure model for optimal planning of maintenance and improvement of roads. Computers ＆ Industrial Engineering, 52(3), 327-335.
Bellman, R. (1973). A note on cluster analysis and dynamic programming. Mathematical Biosciences, 18(3), 311-312.
Bilde, O., ＆ Krarup, J. (1977). Sharp lower bounds and efficient algorithms for the simple plant location problem. Annals of Discrete Mathematics. v1, 79-88.
Carlyle, W.M., Royset, J.O., ＆ Kevin Wood, R. (2008). Lagrangian relaxation and enumeration for solving constrained shortest‐path problems. Networks, 52(4), 256-270.
Cornuéjols, G., Fisher, M., ＆ Nemhauser, G.L. (1977). On the uncapacitated location problem. Annals of Discrete Mathematics, 1, 163-177.
Cornuejols, G., Nemhauser, G. L., ＆ Wolsey, L. A. (1990). The uncapacitated facility location problem. In R. L. Francis ＆ P. B. Mirchandani (Eds.), Discrete location theory (pp. 119–171). New York: Wiley
Drexl, A. (1988). A simulated annealing approach to the multiconstraint zero-one knapsack problem. Computing, 40(1), 1-8.
Erlenkotter, D. (1978). A dual-based procedure for uncapacitated facility location. Operations Research, 26(6), 992-1009.
Fisher, W.D. (1958). On grouping for maximum homogeneity. Journal of the American Statistical Association, 53(284), 789-798.
Fox, B. L.(1975). Kth shortest paths and applications to the probabilistic networks, in ORSA/TIMS Joint National Mtg., Vol. 23, p. B263
Frank, C., ＆ Römer, K. (2007). Distributed facility location algorithms for flexible configuration of wireless sensor networks Distributed computing in sensor systems (pp. 124-141): Springer.
Gao, L.L., ＆ Robinson, E.P. (1992). A dual‐based optimization procedure for the two‐echelon uncapacitated facility location problem. Naval Research Logistics (NRL), 39(2), 191-212.
Ghosh, D. (2003). Neighborhood search heuristics for the uncapacitated facility location problem. European Journal of Operational Research, 150(1), 150-162.
Guha, S., ＆ Khuller, S. (1998). Greedy strikes back: Improved facility location algorithms. Paper presented at the Proceedings of the ninth annual ACM-SIAM symposium on Discrete algorithms.
Handler, G.Y., ＆ Zang, I. (1980). A dual algorithm for the constrained shortest path problem. Networks, 10(4), 293-309.
Hansen, P., ＆ Jaumard, B. (1997). Cluster analysis and mathematical programming. Mathematical programming, 79(1-3), 191-215.
Jensen, R.E. (1969). A dynamic programming algorithm for cluster analysis. Operations Research, 1034-1057.
Klose, A., ＆ Drexl, A. (2005). Facility location models for distribution system design. European Journal of Operational Research, 162(1), 4-29.
Körkel, M. (1989). On the exact solution of large-scale simple plant location problems. European Journal of Operational Research, 39(2), 157-173.
Lawler, E.L. Combinatorial optimization: Networks and matroids. 1976. Holt, Rinehart and Winston, New York, 3.
Lawler, E.L. (1972). A procedure for computing the k best solutions to discrete optimization problems and its application to the shortest path problem. Management Science, 18(7), 401-405.
Lazic, N., Frey, B.J., ＆ Aarabi, P. (2010). Solving the uncapacitated facility location problem using message passing algorithms. Paper presented at the International Conference on Artificial Intelligence and Statistics.
Lazic, N., Givoni, I., Frey, B., ＆ Aarabi, P. (2009). Floss: Facility location for subspace segmentation. Paper presented at the Computer Vision, 2009 IEEE 12th International Conference on.
Maffioli, F. (1987). Randomized heuristics for NP-hard problems. Advanced School on Stochastics in Combinatorial Optimization, World Scientific, Dordrecht, 76-93.
Mirzaian, A. (1985). Lagrangian relaxation for the star‐star concentrator location problem: Approximation algorithm and bounds. Networks, 15(1), 1-20.
Mulvey, J.M., ＆ Crowder, H.P. (1979). Cluster analysis: An application of lagrangian relaxation. Management Science, 25(4), 329-340.
Nemhauser, G.L., Wolsey, L.A., ＆ Fisher, M.L. (1978). An analysis of approximations for maximizing submodular set functions—I. Mathematical Programming, 14(1), 265-294.
Novick, B. (2009). Norm statistics and the complexity of clustering problems. Discrete Applied Mathematics, 157(8), 1831-1839.
Ouyang, Y., ＆ Madanat, S. (2006). An analytical solution for the finite-horizon pavement resurfacing planning problem. Transportation Research Part B: Methodological, 40(9), 767-778. doi: 10.1016/j.trb.2005.11.001
Rao, M. (1971). Cluster analysis and mathematical programming. Journal of the American statistical association, 66(335), 622-626.
Shier, D.R. (1979). On algorithms for finding the k shortest paths in a network. Networks, 9(3), 195-214.
Shmoys, D.B., Tardos, É., ＆ Aardal, K. (1997). Approximation algorithms for facility location problems. Paper presented at the Proceedings of the twenty-ninth annual ACM symposium on Theory of computing.
Sun, M. (2006). Solving the uncapacitated facility location problem using tabu search. Computers ＆ Operations Research, 33(9), 2563-2589.
Tsai, Y., Yang, C., ＆ Wang, Z. (2006). Spatial clustering for determining economical highway pavement let projects. Proceedings of Geo Congress, 1-6.
Van der Zijpp, N.J., ＆ Fiorenzo Catalano, S. (2005). Path enumeration by finding the constrained k-shortest paths. Transportation Research Part B: Methodological, 39(6), 545-563. doi: 10.1016/j.trb.2004.07.004
Verter, V. (2011). Uncapacitated and capacitated facility location problems Foundations of location analysis (pp. 25-37): Springer.
Vinod, H.D. (1969). Integer programming and the theory of grouping. Journal of the American Statistical Association, 64(326), 506-519.
Wang, I.L., Tsai, Y.-C.J., ＆ Li, F. (2011). A network flow model for clustering segments and minimizing total maintenance and rehabilitation cost. Computers ＆ Industrial Engineering, 60(4), 593-601.
Xiao, Y., Thulasiraman, K., Xue, G., ＆ Jüttner, A. (2005). The constrained shortest path problem: Algorithmic approaches and an algebraic study with generalization. submitted for publication.
Yang, C., Tsai, Y.J., ＆ Wang, Z. (2009). Algorithm for spatial clustering of pavement segments. Computer‐Aided Civil and Infrastructure Engineering, 24(2), 93-108.
Yen, J.Y. (1971). Finding the k shortest loopless paths in a network. management Science, 17(11), 712-716.