以現今物流資訊系統日益進步的情況下，各產業都要求能夠減少派車成本或是派車數量，以達到降低成本，增加效率或精簡人力之目的。而在實際應用上，例如灑水車與掃街車，網路配線車或是油漆車等諸如此類之問題，稱為具車容量限制之節線路徑規劃問題(Capacitated Arc Routing Problem, CARP)，此類問題有兩種以上車種服務，並具有先後順序之問題，對於降低成本與人力以及增加效率等議題，至為重要，故本研究建構一套可適用於兩種車輛之路徑規劃方法，期望能應用於實際問題上，或是其他延伸性之節線路徑規劃問題，對於實務運作之成本考量，具指標意義。
本研究之建構具車容量限制節線路徑規劃問題，方法考慮到兩種車輛之路徑規劃，並將CARP問題轉換成以節點方式求解。在演算法中，本研究採用建構路徑相當有效的方法，蟻群最佳化(Ant Colony Optimization;ACO)法來求解車輛路徑之問題，而兩種車輛分別為先服務之車輛First Servicing Vehicle (FV)車，與後服務之車輛 Secondary Servicing Vehicle (SV)車過程中將兩種類型車輛分為三種類型路徑，分別為型一(FV車路徑)，型二(SV車路徑)與型三(FV車與SV車共同路徑)，在求解過程中則是先規劃FV車路徑，再規劃SV車路徑，FV車會服務在SV車之前。
在測試三種標竿例題中，與貪婪演算法來做比較，結果顯示本研究之路徑規劃法在大部份之例題中之車輛總成本較小，故本研究在求解此類網路範圍之問題時，較貪婪演算法之結果佳。

In light of today''s logistics information system, the industries are required to reduce the fleet size to achieve the purposes of reducing total costs, increase efficiency or streamlining human resource. In practical application, such as watering-cart, sweeper, network wiring, or painting cars, we will encounter the issue of “Capacitated Arc Routing Problem, CARP”. To reducing labor costs and increasing efficiency in such issues is very important. We always refers to two kinds of vehicle services, and the sequence questions. The conceptual specification of research constructs to a vehicle routing plan which expectations can be applied to practical problems, or other extension routing plan.
The capacitated arc routing problem proposed by our research considers the constraints of vehicle capacity . We transformed the capacitated arc routing problems into a node routing problem. The Ant Colony Optimization (ACO) algorithm which executes high efficiency in this problem is chosen in this research to solve the proposed problem. Moreover, there are two types of vehicle i.e. the first service vehicle (FV) car and after the secondary service of vehicles (SV). We defined three types of vehicle path, respectively type I (FV car path), type II (SV vehicle path) and type III (FV and SV vehicle car common path). Last, we discuess three types (type I, type II and type III) in the research conclusion.
Comparing with Greedy Algorithm, the algorithm we use shows better total cost in most of the examples which indicates our method is more suitable for solving the issue of CARP.

中文摘要 I
ABSTRACT II
誌謝 IV
目錄 V
圖目錄 VII
表目錄 VIII
第一章 研究背景與問題定義 1
1.1研究背景與動機 1
1.2研究目的與範圍 2
1.3研究假設 3
1.4研究內容與流程 5
第二章 文獻回顧 7
2.1節線路徑規劃問題(ARC ROUTING PROBLEM) 7
2.2啟發式解法求解車輛途程問題 9
2.3 具時窗限制之車輛途程問題 15
2.4 CARP問題轉換為CVRP問題求解 16
2.5路網之改善階段 18
第三章 研究方法與模型 20
3.1問題定義 20
3.2 路網規劃 21
3.4模式建構 24
3.4.1 CARP數學模式建構： 24
3.4.2路徑之成本與需求量計算 28
第四章 啟發式解法 30
4.1 ACO更新步驟之參數 30
4.2蟻群最佳化法之操作 31
4.2.1 隨機比例法則 31
4.3本研究之蟻群最佳化操作步驟 33
4.3.1標竿例題驗證 33
4.3.2第一種類型之蟻群最佳化操作流程： 35
4.3.3第二種類型之蟻群最佳化操作流程： 37
第五章 例題測試與分析 39
5.1參數設定 39
5.2 例題測試與分析 42
第六章 結論與建議 51
6.1結論 51
6.2建議 52
參考文獻 53
中文文獻 53
英文文獻 54
附錄一 1
附錄二 2
附錄三 7

中文文獻
1.王政嵐（2005）。「類螞蟻族群演算法於求解含凹形節線成本最小成本轉運問題之研究」。國立中央大學土木工程研究所，碩士論文。
2.朱文正（2003）。「考量旅行時間可靠度之車輛途程問題─螞蟻族群演算法之應用」。交通大學交通運輸研究所，碩士論文。
3.林惠民（2002）。「具時窗之多趟次車輛徒程問題」。元智大學資訊管理學研究所，碩士論文。
4.林宗漢（2008）。「應用螞蟻演算法探討卡車與拖車途程問題」。國立高雄第一科技大學運籌管理系，碩士論文。
5.林依潔（2003）。「整合模糊理論與螞蟻演算法於含時間窗限制之車輛途程問題」。國立台北科技大學生產系統工程與管理研究所，碩士論文。
6.周淑蓉 ( 2004 ) 。「以群聚及禁制搜尋法求解含時窗限制之車輛巡迴路線問題」。朝陽科技大學資訊管理系，碩士論文。
7.陳昱廷（2005）。「顧客需求不確定下，即時車輛派遣系統之研究」。國立高雄第一科技大學運籌管理系，碩士論文。
8.盧尚群（2005）。「依時路網車輛路徑規劃系統」。國立高雄第一科技大學運籌管理系，碩士論文。




英文文獻
1.Amaya, A., Langevin, A. and Trepanier, M. (2007). "The capacitated arc routing problem with refill points." Operations Research Letters 35(1): 45-53.

2.Aminu, U. F. and R. W. Eglese (2006). "A constraint programming approach to the Chinese postman problem with time windows." Computers & Operations Research 33(12): 3423-3431.

3.Corberàn, A. I. Plana and J. Sanchis, M. (2007). "A branch & cut algorithm for the windy general routing problem and special cases." Netw. 49(4): 245-257.

4.Baldacci, R. and Maniezzo, V. (2006). "Exact methods based on node-routing formulations for undirected arc-routing problems." Networks 47(1): 52-60.

5.B. Bullnheimer, R.F. Hartl, and C. Strauss(1997). " An improved ant system algorithm for the vehicle routing problem. " Technical Report POM-10/97, Institute of Management Science, University of Vienna.

6.Bruce L. Golden, R. T. W. (1981). "Capacitated arc routing problems." Networks 11(3): 305-315.

7.Baldacci, R. and Maniezzo, V. (2006). Exact methods based on node-routing formulations for undirected arc-routing problems. Networks, 47(1), 52-60.

8.Doerner, K.F., Hartl, R.F., Maniezzo, V. and Reimann, M. (2003). "An ant system metaheuristic for the capacitated arc routing problem." MIC2003: The Fifth Metaheuristics International Conference.

9.Dorigo, M., Maniezzo, V. and Colorni, A. (1996). "Ant system: optimization by a colony of cooperating agents." Systems, Man, and Cybernetics, Part B, IEEE TranSVctions on 26(1): 29-41.

10.Dorigo, M., Caro, G.D. and Gambardella, L.M. (1999). "Ant algorithms for discrete optimization." Artif. Life 5(2): 137-172.
11.Feng Chu , N. L. a. C. P. (2005). "Heuristics for the periodic capacitated arc routing problem " Intelligent Manufacturing, 243-251

12.Greistorfer, P. (2003). "A Tabu Scatter Search Metaheuristic for the Arc Routing Problem." Computers & Industrial Engineering 44(2): 249-266.

13.Ghiani, G. Musmanno, R. Paletta, G. and Triki, C. (2005). "A heuristic for the periodic rural postman problem." Computers & Operations Research 32(2): 219-228.

14.Gianpaolo, G., Gennaro, I., Gilbert, L. (2001). "The capacitated arc routing problem with intermediate facilities." Networks 37(3): 134-143.

15.Gilbert, L. (1997). "Modeling and solving several classes of arc routing problems as traveling salesman problems." Comput. Oper. Res. 24(11): 1057-1061.

16.Guan, M.(1962) "Graphic programming using odd and even points. " Chinese Mathematics. 1:273-7.

17.Grotschel, M. Junger, M. Reinelt, G.(1991) "Optimal control of plotting and drilling machines: A case study. "Mathematical Methods of Operations Research. 35:61-84.

18.Fleury, G. Lacomme, P. Prins C. and W.(2005) "Improving Robustness of Solutions to Arc Routing Problems." Journal of the Operational Research Society.56:526–538.

19.Herminia, I. C. (2004). "The quickest path problem with interval lead times." Comput. Oper. Res. 31(3): 383-395.

20.Jos, B.,. (2008). "A deterministic tabu search algorithm for the capacitated arc routing problem." Comput. Oper. Res. 35(4): 1112-1126.

21.Lacomme, P., Prins, C. and Tanguy, A. (2004). " First Competitive Ant Colony Scheme for the CARP. "Ant Colony, Optimization and Swarm Intelligence, Springer Berlin / Heidelberg. 3172/2004: 426-427.
22.Lacomme, P., Prins, C. and Ramdane-Cherif, W. (2004). "Competitive Memetic Algorithms for Arc Routing Problems." Annals of Operations Research 131(1): 159-185.
23.Marco Dorigo, a. L. M. G. (1997). "Ant colonies for the travelling salesman problem."BioSystems, 43:73-81.

24.Tagmouti, M., Gendreau, M. and Potvin, J.-Y. (2007). “Arc routing problems with time-dependent service costs.” European Journal of Operational Research, 181(1), 30-39.

25.Vittorio, M. and Alberto, C. (1999). "The Ant System Applied to the Quadratic Assignment Problem." IEEE Trans. on Knowl. and Data Eng. 11(5): 769-778.

26.Willard, J.A.G. (1989). "Vehicle routing using r-optimal tabu search. " M.
Sc. Dissertation. The management school, Imperial College.

27.Zhu, Z., Li, X., Yang, Y., Deng, X., Xia, M., Xie, Z. and Liu, J.. (2007). "A Hybrid Genetic Algorithm for the Multiple Depot Capacitated Arc Routing Problem." Automation and Logistics, 2007 IEEE International Conference on.