臺灣博碩士論文加值系統

本研究是提出族類競爭演算法來解決物流中心車輛分派問題（車輛途程問題），特別是針對電子商務環境下蓬勃發展的快遞問題。其中，族類競爭演算法是由傳統基因演算法改良而成，改良之處，在於加入了族類競爭模組以及緊密關係的多層次編碼結構。編碼結構由四層次資料所組成，分別是族類、群落、個體、基因，因此可以包含更多的資訊解。族類競爭模組則是依據各族類的最佳適應值來彼此競爭，消長各族類的群落數。研究中並以族類競爭演算法測試各式題庫，包括：隨機題庫、固定題庫，最後測試各參數對成本解的敏感度以分析族類競爭演算法的績效。最後結果，族類演算法確實比傳統基因演算法來的有績效，原因在於族類競爭模組對演算法的改良。

In this research we propose a new algoritjm that was named Race Algorithm (RA) to solve the Vehicle Routing Problem. RA is improved from traditional Gene Algorithm. RA has two revolutionary functions in program that are the tense multi-layer coded structure and the complete race module. The tense multi-layer coded structure which included race, community, body and gene. The structure has rich information that can evolve to complex solution. The complete race module can select better race and make it grow its community’s number by fitness value. The module can also select worse race and make it decrease its community’s number by fitness value. The result of this research shows that RA’s effitness is better than GA.

表次 vi
圖次 vii
第壹章 緒 論 1
第一節 研究背景與動機 1
第二節 研究目的 2
第三節 研究範圍與限制 2
第四節 研究步驟 4
第貳章 文獻探討 7
第一節 電子商務與物流 7
第二節 車輛繞徑問題 8
第三節 基因演算法 18
第參章 研究方法 23
第一節 問題情境分析 23
第二節 數學模式建構 26
第三節 族類競爭演算法 32
第四章 族類競爭演算法在物流中心車輛分派問題的應用與測試結果分析 47
第一節 族類競爭演算法在快遞問題的應用模式設計 47
第二節 族類競爭演算法之電腦求解程式設計 53
第三節 檢測結果與分析 58
第五章 結論與建議 81
第一節 結論 81
第二節 建議 82
參考文獻 85
附錄 89
一、　RA之固定均勻題庫繞徑圖(20 missions) 89
二、　RA之固定叢集題庫繞徑圖(20 missions) 90
三、　RA之固定集散地題庫繞徑圖(20 missions) 91

1、 李軍、郭耀煌，物流配送車輛優化調度理論與方法，中國物資出版社，2001年。
2、 徐吉田，單一物流中心配送車輛途程問題之研究，國立台灣工業技術學院管理技術研究所碩士論文，1993年。
3、 吳亮瑩，單一物流中心配送車輛途程問題之研究，國立成功大學工業管理研究所碩士論文，1999年。
4、 敖君瑋，禁忌搜尋法於軟性時窗限制之車輛途程問題研究，元智大學工業工程研究所碩士論文，1999年。
5、 陳致元，單一物流中心車輛途程問題求解模式之空間分析研究，國立台灣大學地理環境資源研究所碩士論文，2001年。
6、 陳契伸，硬性/軟性時窗限制之車輛途程問題研究，中原大學工業工程系
碩士論文，2001年。
7、 葉心蘋，應用禁制搜尋法求解優先順序旅行推銷員問題之研究，元智大學工業工程研究所碩士論文，1999年。
8、 弗列佐.愛德華，林宜萱譯，供應鏈高績效管理，台北市，麥格羅希爾，2002年。
9、 蘇雄義，物流與運籌管理─觀念、機能與整合，華泰書局，2000年。
10、 廖亮富，含時窗限制多部車輛途程問題解算之研究，元智大學工業工程研究所碩士論文，1998 年。
11、 Bagchi, S., Uckun, S., Miyabe, Y., and Kawamura, K., "Exploring Problem-SpecificRecombination Operators for Job Shop Scheduling", Proceedings of the FourthInternational Conference on Genetic Algorithms, 1991, pp.10-17.
12、 Barrie, M. Baker and Ayechew, M.A., "A genetic algorithm for the vehicle routing problem", Computers & Operations Research, (30), 2003, pp.787-800.
13、 Blanton, Jr. J. L. B. and Wainwright, R. L., "Multiple Vehicle Routing with Timeand Capacity Constraints using Genetic Algorithms", Proceedings of The FifthInternational Conference on Genetic Algorithms, 1993, pp.452-459.
14、 Bodin, L., Golden B., Assad A. and Ball M., "Routing and Scheduling of Vehiclesand Crews", Computers and Operations Research, (10-2), 1983, pp.63-211.
15、 Chin, A. J., Kit, H. W. and Lim, A., "A New GA Approach for the Vehicle Routing Problem", Proceedings. 11th IEEE International Conference on, Tools with Artificial Intelligence, 1999, pp.307—310.
16、 Clarke, G. and Wright, J., "Scheduling of Vehicles from a Central Depot to a Number of Delivery Points", Operations Research, (12), 1964, pp.568-581.
17、 Dantzig, G. B. and Ramser, J. H., "The Truck Dispatching Problem", Management Science, (6), 1985, pp.80-91.
18、 Drucker, P., "Economy''s Dark Continent", Fortune, April, 1962.
19、 Drummond, L. M. A., Ochi, L. S. and Vianna, D. S., "An asynchronous parallel metaheuristic for the period vehicle routing problem", Future Generation Computer Systems, (17), 2001, pp.379-386.
20、 Fisher, M. L., Operations Research and Management Science, (8), 1995, pp.1-33.
21、 Fisher, M. L. and Jaikumar, R., "A Generalized Assignment Heuristic for Vehicle Routing Problems", Network, (11), 1981, pp.109-124.
22、 Gillett, B. and Miller, L., "A Heuristic Algorithm for the Vehicle Dispatch Problem", Operations Research, (22), 1074, pp.340-349.
23、 Glover, F., "Tabu search - part I", ORSA Journal on Computing, (1-3), 1989, 190-260.
24、 Golden, B. L., Magnanti, T. L. and Nguyen, H. Q., " Implementing Vehicle Routing Algorithms", Networks, (7), 1977, pp.113-148.
25、 Goldberg, D. E., "Genetic Algorithms in Search", Optimization and Machine Learning, Addison-Wesley, New York, 1989.
26、 Herron, P. D. and Novak, T.P., "A New Marketing Paradigm for Electronic Commerce", The Information Society, (13), 1997, pp.43-54.
27、 Holland, J. H., Adaptation in Natural and Artificial Systems, The University of Michigan Press, Ann Arbor, 1975.
28、 Juliff, K., "A Multi-chromosome Genetic Algorithm for Pallet Loading", Proceedings of the Fifth International Conference on Genetic Algorithms, 1993, pp.467-473.
29、 Lin, S. and Kernighan, B., "An Efficient Heuristic Algorithm for the Traveling Salesman Problem", Operations Research, (21), 1973, pp.498-516.
30、 Lotka, A., "The stability of the normal age distribution", Proceedings of the National Academy of Science, (8), 1925, p.39-345.
31、 Poon, P. W. and Carter, J. N., "Genetic Algorithm Crossover Operations for Ordering Applications", Computers and Operations Research, (22-1), 1995, pp.135-147.
32、 Solomon, M. M., "Algorithms for the Vehicle Routing and Scheduling Problems with Time Window Constraints", Operation Researsch, (35-2), 1987, pp. 254-265.
33、 Taillard, E., Badeau, P., Gendreau, M., Guertin, F. and Potvin, J. Y., " A Tabu Search Heuristic for the Vehicle Routing Problem with Soft Time Windows", Transportation Science, (31-2), 1997, pp. 170-186.
34、 Volterra, V., "Variations and fluctuations of the numbers of individuals in animal species living together", Reprinted in 1931 in R. N. Chapman, Animal ecology, New York; McFraw-Hill, 1926.