以基因演算法探討多旅行銷售員問題

A comparison of selection schemes in genetic algorithm for the multiple traveling salesman problem

范雯婷(Wen-Ting Fan)

指導教授 ： 龐金宗

元智大學/資訊學院/資訊管理學系/碩士(2008年)

https://doi.org/10.6838/YZU.2008.00011

摘要

多旅行銷售員問題比旅行銷售員問題複雜但卻更能貼近實際狀況，除此之外，也能將其延伸至車輛排程問題，因此多旅行銷售員問題在運輸和排程上扮演著重要的角色。
有許多相關文獻使用基因演算法來解決多旅行銷售員問題，在這些研究中，學者們在基因演算法之選擇方法的採用，並沒有一定的方法，故無法知道不同選擇方法對多旅行銷售員問題的影響。
本研究除了針對較小型的多旅行銷售員問題，也會將問題的複雜度提高，試著找到最佳的選擇方法，能使多旅行銷售員問題產生最佳的路徑。

關鍵字

基因演算法, 多旅行銷售員問題, 選擇

並列摘要

The multiple traveling salesman problem（mTSP）is more complex than the traveling salesman problem（TSP）but is more suitable to model real life situations. Moreover, The mTSP can be considered as a relaxation of the vehicle routing problem（VRP）. Hence, the mTSP itself plays an important role in practical distribution and routing. Many studies use genetic algorithm（GA）to solve the mTSP and different selection schemes are used. At the moment, it is unknown which scheme is the best to solve the mTSP. This study will increase the complexity of the problem and attempt to identify the optimum scheme to prove its capability.

並列關鍵字

GA, MTSP, Selection

參考文獻

1. Tolga, B.（2006）.The multiple traveling salesman problem：an

3. Lixin, T.＆Jiyin, L.＆Aiying, R.＆Zihou, Y.（2000）.A multiple traveling salesman problem model for hot rolling scheduling in Shanghai Baoshan Iron & Steel Complex. European Journal of Operational Research, 124, 267-282.

4. Donald, S.＆Alan, S.＆Kenneth, D. J.（2002）. Evolutionary computation approaches to solving the multiple traveling salesman problem using a neighborhood attractor schema. EvoWorkshops, LNCS 2279,（pp. 153-162）. S. Cagnoni et al.（Eds.）

5. Zhong, Y.＆Liang J.＆Gu, G., Zhang, R.＆Yang H.（2002）.An implementation of evolutionary computation for path planning of cooperative. IEEE Intelligent Control and Automation, 3, 1798-1802.

8. Holland, J. H.（1975）.Adaptation in natural and artificial systems. University of Michigan press.