結合平行基因演算法與蟻群最佳化應用於具時窗限制之車輛途程問題

A Parallel Platform Combines Genetic Algorithm and Ant Colony Optimization to Solve Vehicle Routing Problem with Time Windows

李孟澤(Meng-Tse Li)

指導教授 ： 張淳智

國立臺中科技大學/商管學群/事業經營研究所/碩士(2008年)

摘要

在求解組合最佳化問題時經常會面臨到求解規模變大時，其求解所花費的時間與計算成本也將隨之大幅地增加。近年來許多學者都透過巨集式啟發法來求解近似解，然而卻面臨到參數設定的問題，參數值的設定優劣將決定演算法求解問題時結果的好壞，而求解不同問題時各種演算法之參數設定皆不盡相同，如何設定參數值便成為實際應用演算法求解現實生活中問題時相當重要且令人惱人的課題，本研究提出了一個平行處理的架構，該架構中係結合了兩種演算法，本研究中所採用的演算法分別為基因演算法與蟻群最佳化演算法，並採用具時窗限制之車輛途程問題作為測試研究成果的標竿例題，透過蟻群最佳化演算法求解該問題，並採用基因演算法來演化求解蟻群最佳化演算法的參數，此外透過平行處理來降低求解所花費的時間，藉由這個架構將可以有效地降低求解時間並簡化參數設定之流程。

關鍵字

平行處理 ； 蟻群最佳化演算法 ； 基因演算法 ； 具時窗限制之車輛途程問題

並列摘要

The combinatorial optimization problem is very important and famous problem in the area of computer science. The feature of this kind of problem is that when the problem scale becomes large, the cost of computing time will be immense. On recent researches, lots of scholars apply the meta-heuristic algorithms to solve the problems. But the related parameters of algorithm are difficult to setting. Parameters will affect the result. However, to solve different problems, the setting of algorithms' parameters will be different. In practice, setting parameters is an important but boring problem to apply heuristic algorithms to solve problems. This research proposes a platform of parallel processing. This platform combines two algorithms, Genetic Algorithm (GA) and Ant Colony Optimization (ACO), and uses Soloman’s VRPTW benchmark problems to test the performance of this platform. ACO is used to solve the VRPTW problems, and GA is used to evolve the parameters of ACO. The empirical results show that our parallel processing platform can reduce the computing time, and simplify the processes of parameters setting.

並列關鍵字

Parallel Processing ； ACO ； GA ； VRPTW

參考文獻

2. 洪光鈞(民94)。分散式基因演算法執行效率最佳化之研究。碩士論文，元智大學資訊管理研究所。

8. Bell, J. E., & McMullen, P. R. (2004). Ant colony optimization techniques for the vehicle routing problem. Advanced Engineering Informatics, 18, 41-48.

10. Chabrier, A. (2006). Vehicle Routing Problem with elementary shortest path based column generation. Computers & Operations Research, 33(10), 2972-2990.

11. Cook, W., & Rich, J. L. (1999). A Parallel Cutting-Plane Algorithm for the Vehicle Routing Problem With Time Windows. Rice University, Houston, TX.

12. Dorigo, M. & Gambardella, L. M. (1997). Ant colonies for the traveling salesman problem, BioSystems, 43, pp. 73-81