橋樑定期檢測作業排程最佳化模式之研究

AN OPTIMAL ROUTING AND SCHEDULING MODEL FOR REGULAR BRIDGE INSPECTIONS

顏上堯(Shang-Yao Yan)；范琇綾(Hsiu-Ling Fan)；陳怡君(Yi-Chun Chen)

橋樑定期檢測作業 ； 排程 ； 含額外限制之整數網路流動問題 ； 啟發解法 ； Regular bridge inspection ； Routing and scheduling ； Network flow problem with side constraints ； Heuristic algorithm

運輸計劃季刊

45卷1期（2016 / 03 / 30）

63 - 79

繁體中文

臺灣地區的橋樑必須每年進行所有構件的全面性定期檢測。實務上橋樑定期檢測作業排程主要由人力指派方式決定，缺乏系統性分析與整體考量，當面臨龐大的檢測作業排程時，將造成人力、經費與時間等成本之浪費。緣此，本研究建構一橋樑定期檢測作業排程最佳化模式，期能使執行橋樑定期檢測作業的總成本最小化。此外，本研究模式為一大型含額外限制之整數網路流動問題，屬NP-Hard 問題，難以現有最佳化軟體直接求最佳解，故本研究發展一啟發解演算法。最後，本研究以國內某地區之橋樑定期檢測作業為測試範例，其結果良好，顯示本研究模式與演算法可供實務界應用之參考。

The bridges in Taiwan have to be inspected regularly in every year. In practice, the routing and scheduling for bridge inspections depend on the experience of the decision maker, which is neither efficient nor effective. Therefore, in this study we propose an optimal routing and scheduling model with the objective of minimizing the total cost for bridge regular inspection. In addition, the model is formulated as an integer network flow problem with side constraints, which is characterized as NP-hard. To efficiently solve the realistically large problems occurring in pracitce, a heuristic algorithm is developed. Finally, we perform a case study using real data of bridge inspections from a Taiwan city to demonstrate and to elvaute the model and the solution algorithm. The results are good, showing that the model and the solution algorithm could be useful references for practices.

1. Barnhart, C.,Johnson, E. L.,Nemhauser, G. L.,Savelsbergh, M. W. P.,Vance, P. H.(1998).Branch-and-Price: Column Generation for Solving Huge Integer Programs.Operations Research,46(3),316-329.
2. Dai, K.,Smith, H. B.,Chen, S. E.,Sun, L.,(2014).Comparative Study of Bridge Management Programmes and Practices in the USA and China.Structure and Infrastructure Engineering,10(5),577-588.
3. Lu, H. A.,Chen, C. Y.(2011).A Time-Space Network Model for Unit Load Device Stock Planning in International Airline Services.Journal of Air Transport Management,17(2),94-100.
4. Matos, A. C.,Oliveira R. C.(2004).An Experimental Study of the Ant Colony System for the Period Vehicle Routing Problem.Lecture Notes in Computer Science,3172,286-293.
5. Wen, M.,Cordeau, J. F.,Laporte, G.,Larsen, J.(2010).The Dynamic Multi-Period Vehicle Routing Problem.Computers and Operations Research,37(9),1615-1623.
6. Yan, S.,Chen, C. Y.,Chang, S. C.(2014).A Carpooling Model and Solution Method with Stochastic Vehicle Travel Times.IEEE Transactions on Intelligent Transportation Systems,15(1),47-61.
7. Yan, S.,Chen, S. C.,Chen, C. H.(2006).Air Cargo Fleet Routing and Timetable Setting with Multiple On-Time Demands.Transportation Research Part E,42(5),409-430.
8. Yan, S.,Hsiao, F. Y.,Guo, J. J.,Chen, Y. C.(2011).Effective Aircraft Maintenance Schedule Adjustment Following Incidents.Transportation Planning and Technology,34(8),727-745.
9. Yan, S.,Shih, Y. L.(2007).A Time-Space Network Model for Work Team Scheduling after a Major Disaster.Journal of the Chinese Institute of Engineers,30(1),63-75.
10. Yan, S.,Tang, C. H.,Fu, T. C.(2008).An Airline Scheduling Model and Solution Algorithms under Stochastic Demands.European Journal of Operational Research,190(1),22-39.
11. Yan, S.,Wang, S. S.,Chang, Y. H.(2014).Cash Transportation Vehicle Routing and Scheduling under Stochastic Travel Times.Engineering Optimization,46(3),289-307.
12. Yan, S.,Wang, S. S.,Wu, M. W.(2012).A Model with a Solution Algorithm for the Cash Transportation Vehicle Routing and Scheduling Problem.Computers and Industrial Engineering,63(2),464-473.
13. Yu, B.,Yang, Z. Z.(2011).An Ant Colony Optimization Model: The Period Vehicle Routing Problem with Time Windows.Transportation Research Part E,47(2),166-181.
14. 交通部公路總局(2012)。公路養護手冊。
15. 吳秋木(2006)。碩士論文(碩士論文)。國立嘉義大學土木與水資源工程研究所。
16. 延允中(2004)。碩士論文(碩士論文)。國立中央大學土木工程研究所。
17. 柴志傑(2009)。碩士論文(碩士論文)。國立中央大學營建管理研究所。
18. 顏上堯、姜蔚宗(2013)。公路橋樑檢測最佳化模式分析。臺灣公路工程，39(9)，2-42。