在繁忙的市區道路上，為維持車流順暢與避免事故產生，交通號誌扮演了極重要的角色；因此當颱風、地震等重大災害後所產生大量的號誌損壞，將嚴重影響路網效率與交通安全。為降低其影響交通的嚴重程度，考慮當時路網交通狀況，安排適當的號誌維修順序與路徑，即成為一重要的課題。

旅行維修員問題 (Traveling Repairman Problem, TRP) 之定義如下，維修員以相同的速度拜訪已知一區域上的n個需求點，設各需求點的完成時間Cj (j =1…n) 為其距離原點的路徑成本；給定各需求點的權重因子wj，求解其加權完成時間或平均加權完成時間的最小值。而動態型旅行維修員問題 (Dynamic traveling repairman problem, DTRP) 則考慮各需求點的資料非出發前全部已知，而是隨著時間出現，且維修員必須對新增的需求點產生即時的策略。

本研究使用一整合模式求解動態旅行維修員問題，首先根據已知的需求資訊，使用依時性動態數學模式，求解離線型最佳初始路徑；對於即時新增需求，則以線上型 (On-line) 路線更新演算法，藉由INTERVAL策略更新即時資訊，考慮即時新增需求點的出現時間、權重與維修員的目前位置，並以模擬退火法產生可能路徑，更新維修路線；並使用交通模擬指派模式DynaTAIWAN產生依時性旅行成本且模擬車輛移動，最後依數值實驗結果修正演算法參數，使其具有更好的運算效率與品質。

為考慮現實交通狀況，相關數值實驗於高雄市真實路網中進行，並將實驗結果與實際維修資料做比較，並使用競爭分析 (Competitive analysis)，將數值實驗產生的求解上界與相對應之離線最佳解相比，評估線上型演算法的求解績效。

Traffic signals play an important role of keeping the traffic flow smooth and avoiding traffic accidents. Signal malfunctions after natural disasters, such as typhoons and earthquakes, usually cause great impact on traffic systems in terms of efficiency and safety. Therefore, how to design an efficient repairing plan with considering new requests and traffic conditions is a critical issue to ensure traffic safety and efficiency.

The traveling repairman problem (TRP) is defined as follows: given a set of n request points and associated weights, and a repairman should visit the requests, defining the completion time Cj (j =1…n) of a point pj to be the cost of the tour from origin to pj. Given a weight wj (j =1…n) for the point, the goal of the TRP is minimize the average weighted completion time or the total weighted completion time. The dynamic traveling repairman problem (DTRP) considers requests appeared over time, and the repairman should have the real time policy for these new demands.

This research proposes an integrated framework to solve DTRP. For known requests, a time-dependent formulation is formulated to compute an optimal initial route. For on-line requests, an on-line algorithm is developed to reschedule the repair plan to consider on-line requests based on weights of new requests. The on-line algorithm uses the INTERVAL strategies to consider new requests and uses the Simulated Annealing algorithm to evaluate possible arrangements. The simulation-assignment model, DynaTAIWAN, is used as a test bed to generate time-dependent travel time matrices and to simulate vehicular movements. Parameters of the algorithms are determined through numerical tests to achieve better computing efficiency and quality.

Numerical experiments for illustrating the proposed algorithms are conducted in a real city network, the Kaohsiung network. The numerical results are compared with empirical data. In order to measure the performance of the on-line algorithm, the upper bounds are solved numerically and compared with the off-line optimal solutions by Competitive Analysis.

胡大瀛等人 (2004)，區域級智慧型運輸系統示範計畫－核心交通分析與預測系統(第二年期)，交通部運輸研究所。

胡大瀛等人 (2008)，即時動態交通分析與預測模型 (DynaTAIWAN) 之實證分析與推廣(2/3) ，交通部運輸研究所。

高雄市政府交通局 (2009)，交通設施委外維修與管理服務企劃書。

張清濱 (2008)，動態車輛巡迴路線問題之數學模式建構與分析，成功大學交通管理科學系碩士論文。

梅明德 (1998)，線上型時窗限制車輛路線問題之模式與求解演算法，中央大學土木工程研究所博士論文。

Ausiello, G., Feuerstein, E., Leonardi, S., Stougie, L. and Talamo, M. (2001), “Algorithms for the on-line travelling salesman,” Algorithmica, Vol. 29, No. 4, pp. 560-581.

Bertsimas, D. and Ryzin G. V. (1989), The dynamic traveling repairman problem, Sloan School of Management, Massachusetts Institute of Technology, HD28. M414 No. 3036-89.

Blom, M., Krumke, S. O. and de Paepe, W. E. (2001), “The online-TSP against fair adversaries,” INFORMS Journal on Computing, Vol. 13, No. 2, pp. 138-148.

Blum, A., Chalasani, P., Coppersmith, D., Pulleyblank, B., Raghavan, P. and Sudan, M. (1994), “The minimum latency problem,” Proceeding of the 26th Annual ACM Symposium on the Theory of Computing, pp. 163-171.

Borodin, A. and El-Yaniv, R. (1998), Online computation and competitive analysis, New York: Cambridge University Press.

Busetti, F. (2009), “Simulated Annealing Overview,” Retrieved April 24, 2009, website: http://www.geocities.com/ francorbusetti/saweb.pdf.

Chiang, W. C. and Russell, R. A. (1996), “Simulated Annealing Metaheuristics for the Vehicle Routing Problem with Time Windows,” Annals of Operations Research, Vol. 63, No.1, pp.3-27.

Czech, Z. J. and Czarnas, P. (2002), “Parallel Simulated Annealing for the Vehicle Routing Problem with Time Windows,” 10th Euromicro Workshop on Parallel, Distributed and Network-based Processing, Canary Islands–Spain

Dantzig, G. B. and Ramser, J. M. (1959), “The truck dispatching problem,” Management Science, Vol. 6, No. 1, pp. 81-91.

Feuerstein, E. and Stougie, L. (2001),” On-line single server dial-a-ride problems,” Theoretical Computer Science, Vol. 268, No. 1, pp. 91-105.

Garcia, A., Jodr'a, P. and Tejel, J. (2002), “A note on the traveling repairman problem,” Networks, Vol. 40, No. 1, pp. 27-31.

Ghiani, G., Guerriero, F., Laporte, G. and Musmanno, R. (2003), “Real-time vehicle routing: Solution concepts, algorithms and parallel computing strategies,” European Journal of Operational Research, Vol. 151, No. 1, pp. 1-11.

Haghani, A. and Jung, S. (2005), “A dynamic vehicle routing problem with time-dependent travel times,” Computer & Operations Research, Vol. 32, No. 11, pp. 2959-2986.

Hall, L. A., Schulz, A. S., Shmoys, D. B. and Wein, J. (1997),” Scheduling to minimize average completion time: off-line and on-line approximation algorithms,” Mathematics of Operations Research, Vol. 22, No. 3, pp. 513-544.

Herault, L. (2000), “Rescaled Simulated Annealing-Accelerating Convergence of Simulated Annealing by Rescaling the States Energies,” Journal of Heuristics, Vol. 6, No. 2, pp. 215-252.

Jaillet, P. and Wagner, M. R. (2006), “Online routing problems: value of advanced information as improved competitive ratios,” Transportation Science, Vol. 40, No. 2, pp. 200-210.

Karlin, A., Manasse, M., Rudolph, L. and Sleator, D. (1988), ”Competitive snoopy catching,” Algorithmica, Vol. 3, No. 1, pp. 79-119.

Kirkpatrick, S., Gelatt, C. D., Jr. and Vecchi, M. P. (1983), “Optimization by simulated annealing,” Science, Vol. 220, No. 4598, pp. 671-680.

Kirkpatrick, S. (1984), “Optimization by Simulated Annealing: Quantitative Studies,” Journal of Statistical Physics, Vol. 34, No 5/6, pp. 975-986.

Krumke, S. O. (2000), News from the online traveling repairman, Technical Report ZIB-report 00-08, Konrad-Zuze-Zentrum für Informationstechnik, Berlin.

Krumke, S. O., Paepe, W. E., Poensgen, D. and Stougie, L. (2003), “News from the online traveling repairman,” Theoretical Computer Science, Vol. 295, No. 1-3, pp. 279-294.

Larsen, A. (2001), The dynamic vehicle routing problem, Ph.D. Thesis, Institute of Mathematical Modelling, Technical University of Denmark, Denmark.

Lin, S. (1965), “Computer Solution of the Traveling Salesman Problem,” The Bell System Technical Journal, Vol. 44, No. 10, pp. 2245-2269.

Malandraki, C. and Daskin, M. S. (1992), “Time dependent vehicle routing problems: formulations, properties and heuristic algorithms,” Transportation Science, Vol. 26, No. 3, pp. 185-199.

Méndez-Díaz, I., Zabala, P. and Lucena, A. (2008), “A new formulation for the traveling deliveryman problem,” Discrete Applied Mathematics, Vol. 156, No. 17, pp. 3223-3237.

Rocha, A. M., Soares, J. and Fernandes, E. M. G. P. (2005), “Solving the traveling repairman problem with differentiated waiting times through Lagrangian relaxation,” I Congresso de Estatística e Investigação Operacional da Galiza e Norte de Portugal/VII Congreso Galego de Estatística e Investigacíon de Operacións, ISBN 972-99841-0-7, CD-ROM, 6 pages, Guimarães.

Sarubbi, J. F. M. and Luna, H. P. I. (2007), “A new flow formulation for the minimum latency problem,” Proceeding of the 3rd International Network Optimization Conference, Retrieved March 27, 2009, website: http://www.euro-online.org /enog/inoc2007/Papers/author.31/paper/paper.31.pdf.

Schneider, J. (2002), “The Time-Dependent Traveling Salesman Problem,” Physica A, Vol. 314, No.1, pp. 151-155.

Sleator, D. D. and Tarjan, R. E. (1985), “Amortized efficiency of list update and paging rules,” Communications of the ACM, Vol. 28, No. 2, pp. 202-208.

YarKhan, A. and Dongarra, J. J. (2002), “Experiments with Scheduling Using Simulated Annealing in a Grid Environment,” Computer Science, Vol. 2536, pp. 232-242.