結合區域搜尋之遺傳演算法求解多車種之車輛途程問題

A Genetic Local Search Algorithm for the Heterogeneous Fleet Vehicle Routing Problem

馬凱賢(Kai-Shian Ma)

指導教授 ： 劉祐興

共同指導教授 ： 周榮昌(Rong-Chang Jou)

國立暨南國際大學/科技學院/土木工程學系/碩士(2006年)

https://doi.org/10.6837/NCNU.2006.00030

摘要

多車種之車輛途程問題在理論及實務研究領域皆為十分重要之課題。本研究嘗試以遺傳演算法為基本架構，結合區域搜尋，針對文獻既有之測試案例進行測試。探討不同區域搜尋之策略，以及區域搜尋後，取代解之不同門檻值設定，與各案例之車隊配置、節點空間分佈是否有相關性。結果顯示，在車隊配置方面，並無明顯相關性；在節點空間分佈方面，求解之區域搜尋策略，與其路線成本佔總成本之比例有相關性。所佔比例以15%為一區隔，比例越高，搜尋策略越重單途程（排程）；反之，較重多途程（分群）之區域搜尋策略。門檻值的部份，當解的值偏高時，線性遞減之門檻值設定優於定值設定；反之，定值設定優於線性遞減設定。而本研究發展出四種區域搜尋方法，與文獻中的五種區域搜尋方法合併使用，結果發現，加上本研究所提出之四種區域搜尋方法之求解績效，較原有僅使用文獻中的五種區域搜尋方法所獲得之平均目標函數值改善1.19%~11.79%。在目前最佳解求解績效方面，12個測試案例中，6個案例與現有文獻之最佳解相同；2個案例比現有文獻所獲得之最佳解更佳；4個案例與文獻相近，誤差率介於0.01%~2.1%。就區域搜尋策略與門檻值設定整體而言，區域搜尋之策略以先單途程後多途程且門檻值以0.0之設定，求解績效最佳。

關鍵字

遺傳演算法 ； 多車種之車輛途程問題 ； 區域搜尋策略 ； 門檻值設定

並列摘要

The Heterogeneous Fleet Vehicle Routing Problem（HVRP） is an important theoretical and practical topic in the study of routing problem. This study incorporates various local search methods and threshold values into genetic algorithm for solving a set of test instances adopted in the past studies. The performance of different local search methods and threshold values was investigated. The results showed that the single routing local search strategy perform well when the ratio between variable cost (i.e., cost of routing) and total cost gets higher. With high objective function value, the linear decreasing threshold value performs better than the fixed threshold value strategy. Moreover, the average obtained objective values can be improved 1.19% to 11.79% by adding four local search methods, which was developed in this thesis. Based on the best known solutions associated with different instances from the previous studies, the genetic local search method proposed in this study can obtain better objective function values in two instances and the same values in six instances among 12 testing instances.

並列關鍵字

genetic algorithm ； the heterogeneous fleet vehicle routine problem ； local search ； threshold value

參考文獻

1. 劉祐興、周榮昌、王正傑，「運用遺傳演算法求解機率旅行推銷員問題」，物流產業電子化學術與實務研討會 （2004a）.

2. 劉祐興、周榮昌、馬凱賢，「機率旅行推銷員問題」，收錄於「運籌管理：二十一世紀新經營典範」 （2004b）.

3. Baker, B. M. and Ayechew, M. A., “A Genetic Algorithm for the Vehicle Routing Problem,” Computers & Operations Research, Vol. 30, pp. 787-800, （2003）.

4. Cheng, V.H.L., Crawford, L.S. and Menon, P.K., “Air Traffic Control Using Genetic Search Techniques,” IEEE International Conference on Control Applications, Vol. 1, pp. 249-254, （1999）.

5. Choi, E. and Tcha, D.-W., “A Column Generation Approach to the Heterogeneous Fleet Vehicle Routing Problem,” Computers & Operations Research, Vol. 34, Issue 7, pp. 2080-2095, （2007）.