以蟻拓優化演算法及遺傳演算法求解價選式多車場車輛途程問題

Ant Colony Optimization and Genetic Algorithm for Solving Selective Multi Depot Vehicle Routing Problem with Pricing

陳暉陵(Hui-Ling Chen)

指導教授 ： 楊烽正

國立臺灣大學/工學院/工業工程學研究所/碩士(2013年)

https://doi.org/10.6342/NTU.2013.02013

摘要

價選式多車場車輛途程問題是車輛途程問題中衍生問題，其問題源自於資源再生企業派車於販售商回收貨品流程。過往學者將此問題定義為一標竿問題，且嘗試以整數規劃模式，以及禁忌搜尋法求解。遺傳演算法為一萬用啟發式演算法，其透過生物演化中，物競天擇的演化概念，代次淘汰適應性欠佳的解。而蟻拓優化演算法也屬於萬用啟發式演算法，其設計概念源自於螞蟻覓食過程中參照費洛蒙方式，代次演化螞蟻解。本研究承襲此概念提出用於求解價選式多車場車輛途程問題下的蟻拓以及遺傳演算法，於遺傳演算法中更提出一較適於本問題下的初始解產生模式、染色體編碼以及解碼方式。此外為了驗證本研究演算機制的效能，與學者取得問題大小不同的40個標竿問題進行比較。本研究遺傳演算初始解產生法將針對此40個不同問題與本研究所應用於求解價選式多車場車輛問題的啟發式演算法做比較，結果可發現本研究初始解產生方式優於兩啟發式演算法。且對於學者所提出的整數規劃以及禁忌演算法，本研究已遺傳演算法以及蟻拓優化演算法進行比較，結果在大部分問題下，蟻拓優化演算法可於一定時間內求得解品質較佳的解，遺傳演算法雖略遜於禁忌演算法，但其求解速度較快。

關鍵字

遺傳演算法 ； 蟻拓優化演算法 ； 車輛途程問題 ； 反向供應鏈

並列摘要

Selective Mulit Depot Vehicle Routing Problem with Pricing, SMDVRPP, is a derived problem of Classic Vehicle Routing Problem. This problem origin from the process of recycle enterprise setting fleet to buy recyclable product owned by the dealer. It is defined as a benchmark problem by theacademic and use integer programming and Tabu Search, TS, to solve this problem, because the quality of solution is still not enough. Our research propose two kind of meta heurisitc algorithm which are genetic algorithm, GA, and ant colony optimization, ACO, algorithm try to find the so far best solution better than ever. The concept of GA is through the evolution of chromosome. It will eliminate the chromosomes which have lower fitness value to get the best chromosome. The concept of ACO is by imitating ant foraging behavior and leaving pheromone at the road, through the pheromone value to find the best solution. Besides, our research are also propose chromosome encoding and decoding way which is suitable of SMDVRPP problem. For verify quality, we connectedacademic to obtain 40 different size benchmark problems for comparison. In this study, the genetic algorithm initialize solution for this problem to compare the results of the two heuristic algorithms, the evidence shows it is effective. And compare the result among the integer programming, Tabu Search, GA , ACO, finally we found the ACO algorithm can obtain a best solution within a certain period of time.GA although the quality is slightly lower thanTabu Search, but it can get solution faster.

並列關鍵字

Genetic Algorithm ； Ant Colony Optimization ； Vehicle Routing Problem ； Reverse Supply Chain

參考文獻

Aras, Necati, Aksen, Deniz, & Tuğrul Tekin, Mehmet. (2011). Selective multi-depot vehicle routing problem with pricing. Transportation Research Part C: Emerging Technologies, 19(5), 866-884. doi: 10.1016/j.trc.2010.08.003

Dorigo, M., Maniezzo, V., & Colorni, A. (1996). Ant system: optimization by a colony of cooperating agents. Systems, Man, and Cybernetics, Part B: Cybernetics, IEEE Transactions on, 26(1), 29-41. doi: 10.1109/3477.484436

Feillet, Dominique, Dejax, Pierre, & Gendreau, Michel. (2005). Traveling Salesman Problems with Profits. Transportation Science, 39(2), 188-205. doi: 10.1287/trsc.1030.0079

Fisher, Marshall L., & Jaikumar, Ramchandran. (1981). A generalized assignment heuristic for vehicle routing. Networks, 11(2), 109-124. doi: 10.1002/net.3230110205

Gendreau, Michel, Hertz, Alain, & Laporte, Gilbert. (1996). The Traveling Salesman Problem with Backhauls. Computers & Operations Research, 23(5), 501-508. doi: http://dx.doi.org/10.1016/0305-0548(95)00036-4