節線容量路線問題下限值求法之研究

Abstract

節線容量路線問題（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.