具記憶機制之適應性單性生殖基因演算法應用於VRPTW

An Adaptive Parthenogenesis Genetic Algorithm with Memory Base Crossover for VRPTW

葉泰熏(Taihsun Yeh)

指導教授 ： 張淳智

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

摘要

時窗限制下車輛途程問題已被證實為NP-Hard，學者於此類問題上多採用可跳脫局部最佳解的巨集啟發式演算法求解。基因演算法為以族群基礎之演算法，相較於禁忌搜尋法和蟻群演算法不具記憶機制，且需針對不同問題集設定不同之參數。於本研究中結合導引區域搜尋法之記憶機制概念於基因演算法交配階段中，藉由選取較少變動之基因段進行交配，增加搜尋之廣度。此外於突變率之設定上改以適應性設定，於族群的變異降低時，自動增加突變率以加大族群之變異性，使其能有效地跳脫局部最佳解。本研究之基因演算法架構於Chang and Yeh (2007)所提出之單性生殖基因演算法之上，與未加入記憶機制與適應性參數之單性生殖基因演算法所得結果比較，本研究模式之求解績效較佳，能以較小的族群規模求得更精確的解。進一步之測試結果顯示，加入記憶機制後於限制較寬鬆之2型問題中有較佳的表現，加入適應性機制後則較未加入前，於限制較嚴格之1型問題中有較佳表現，顯示記憶機制確實可有效增加求解搜尋之廣度，適應機制亦可增加族群之變異性跳脫局部最佳解。

關鍵字

單性生殖演算法 ； 時窗限制下車輛途程問題 ； 記憶機制 ； 適應性參數設定

並列摘要

Vehicle routing problem with time windows is one of the NP-hard problems. Most researches apply the metaheuristics to solve this kind of problems. Genetic algorithm is one of them. It is a population based algorithm, and doesn’t have the memory structure like Tabu Search and Ant Colony Algorithm. Usually we need to pretest the parameters for different types of problems in order to get better solutions. In this research, we try to combine the memory technique of guided local search and uses adopt parameter in mutation setting. The structure of our genetic algorithm is based on parthenogenesis genetic algorithm (Chang and Yeh, 2007). The results show our research has efficient solution space exploration. It can use less population size to get better results. Small size of population means can reduce the computation time. By the results show memory technique have better outcome in type 2 problems which have lighter restriction. Furthermore, by adding the adopt parameter setting technique have better outcome in type 1 problems which have harder restriction. In a conclusion, memory technique can help wide local search and adopt parameter setting technique can useful drop out the local optimal.

並列關鍵字

VRPTW ； parthenogenesis genetic algorithm ； memory based crossover ； adapted parameter setting

參考文獻

Alvarenga, G.B., Mateus, G. R., & Tomi, G. (2007). A Genetic and Set Partitioning Two-phase Approach for the Vehicle Routing Problem with Time Windows. Computers & Operations Research, 34, 1561-1584.

Bent, R. & VanHentenryck, P. (2001). Atwo-stage hybrid local search for the vehicle routing problem with time windows (Technical Report CS-01–06). Brown University, Computer Science Department.

Berger, J., Barkaoui, M., & Br?ysy, O. (2001). A Parallel Hybrid Genetic Algorithm for the Vehicle Routing Problem with Time Windows. INFOR, 41, 179-194.

Br?ysy, O. (2003). A reactive variable neighborhood search algorithm for the vehicle routing problem with time windows. INFORMS Journal on Computing, 15(4), 347-368.

Chen, C.H., & Ting, C.J. (2005). A Hybrid Ant Colony System for Vehicle Routing Problem with Time Windows. Journal of the Eastern Asia Society for Transportation Studies, 6, 2822-2836.