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

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

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.