臺灣博碩士論文加值系統

節線容量路線問題（Capacitated Arc Routing Problem：簡稱CARP）為車輛路線問題（Vehicle Problem）之一種。CARP屬於NP-hard問題，因此最佳解求取困難。本論文著重在CARP下限值求取方法的研究上，以求取最佳解的下限值。
以往對於CARP問題的研究，不論是啟發解或下限值求取，大多是以節點的觀點來思考，而CARP需求乃是發生在節線上，本研究將針對此特性，首先運用節線觀點為思考方向以求取下限值，發展出來的下限值求法即為節線掃瞄下限值求法（ASLB）。本研究發現，ASLB會比傳統上非運用配對（matching）以求取下限值的方法NSLB，績效表現還要好。
混合式下限值求法（HLB）乃是針對以往研究中，績效表現最好的下限值求法the Benavent Bound（1992）的缺點進行改良。而研究發現，若網路中的節線，有許多其需求大過1/2容量，或是節線彼此成本差異大時，混合式下限值求法可能會比the Benavent Bound的績效表現還要好。

The Capacitated Arc Routing Problem (CARP) is a commonly seen problem in logistic. CARP finds a set of routes that serve each service edge exactly once while satisfying the capacity constraint.CARP was proved to be a NP-Hard problem. Thus, is difficult to find the optimal solution with a reasonable amount of time. Thus, the study focuses in finding a good lower bound which can be used to speed up the B-B process
This paper introduces two lower bounds of CARP:1.the Arc Scanning Lower Bound (ASLB). In steady of considering nodes as most reaches do, ASLB use edge to compute the lower bound. We also prove our ASLB is no worse than the performance of NSLB. 2.the Hybrid Lower Bound (HLB). We also propose a HLB method to find the Lower Bound. This method use the idea From Benavent(1992) and Yasufumi(1992). We observe that HLB perform better who the demand of some edges exceed half of the vehicle capacity and the costs of edges differ significantly.

第一章 緒論 1
1.1研究背景與動機 1
1.2研究目的與範圍 2
1.3研究內容與流程 3
第二章 文獻回顧 6
2.1網路基本性質 6
2.2節線路線問題 6
2.3符號定義 7
2.4 CARP下限值回顧 7
第三章 節線掃瞄下限值 18
3.1 the Node Scanning Lower Bound 18
3.2節線掃瞄下限值求法論述 19
3.3 ASLB績效評估 22
第四章 混和式下限值 27
4.1 the Zaw Win Bound 和the Benavent Bound 27
4.2 the Node Duplication Lower Bound 29
4.3 BB、NDLB之比較 34
4.4混和式下限值求法論述 35
第五章 結論與建議 56

1. Golden, B. L., and R. T. Wong, " Capacitated Arc Routing Problem " Network, Vol. 11, p305-315, 1981.
2. Assad, A. A., W. L. Pearn, and B. L. Golden, " The Capacitated Chinese Postman Problem: Lower Bounds and Solvable Cases. " American Journal of Mathematical and Management Science, Vol. 7, NO. 1?, p63-88, 1987.
3. Pearn, W. L., " New Lower Bounds for the Capacitated Arc Routing Problem. " , Comput. & Opns. Res. Vol 16, p589-600, 1988.
4. Win, Z. 1987. " Contribution to Routing Problem. " Doctoral Dissertation, Universitat Augsburg, Germany.
5. Benavent, E., A. Campos, A. Corbearn, and D. Moya, " The Capacitated Arc Routing Problem: Lower Bound, " Networks, Vol. 22, p669-690, 1992.
6. Saruwatari, Y., R. Hirabayashi, and N. Nishida, " Node Duplication Lower Bounds for Capacitated Arc Routing Problem. " Journal of the Operations Research Society of Japan, Vol. 35, NO. 2, p119-133, 1992.
7. Eiselt, H. A., M. Gendreau, and G. Laporte, "Arc Routing Problem, Part II: the Rural Postman Problem. " Operation Research, Vol. 43 No. 3, May-June, p399-414, 1995.
8. 張有恆, " 民國84年，運輸經濟 "