臺灣博碩士論文加值系統

本研究探討週期性車輛派遣問題，除了要最小化派遣車輛的總數外，亦加入切合實際情形的運送量平衡限制式。不含平衡限制式之週期性車輛派遣問題已被証明屬於NP-hard問題，因此，本研究探討的具平衡之週期性車輛派遣問題亦屬於NP-hard問題。本研究應用免疫演算法、基因演算法與粒子群演算法來求解此具平衡之週期性車輛派遣問題，此問題的目標為最小化(i)派遣車輛的總數、(ii)各車輛運送總量差異與(iii)每日車輛運送總量差異。

本研究提出一個新的兩階段來求解此問題，第一階段為最小化派遣車輛的總數、各車輛運送總量差異與每日車輛運送總量差異，第二階段為微調各車輛運送總量。本研究試驗三種演算法於不同參數組合的求解表現，數值結果顯示，本文之兩階段可有效的求解此具平衡之週期性車輛派遣問題，尤其當問題複雜度較高時，免疫演算法表現優於基因演算法與粒子群演算法。

This thesis studies the problem of vehicle minimization for periodic deliveries (VMPD). The problem aims to minimize the total number of vehicles with balance consideration. As known, vehicle periodic delivery problem is an NP-hard. Therefore, the studied vehicle periodic delivery problem with balance consideration is also NP-hard. In this thesis, we will apply three artificial intelligence algorithms, namely, immune algorithm, genetic algorithm and partical swarm optimization, for solveing the problem. The objective of the problem is to minimize (i) the summation of total number of vehicles, (ii) the deviation of total delivery quantities for each vehicle, (iii)the deviation of total delivery quantities for each day.

In this thesis, a new two-phase approach is proposed to solve for the vehicle periodic delivery problem with balance consideration. In the first phase, we aim to minimize the (i) the summation of total number of vehicles, (ii) the deviation of total delivery quantities for each vehicle, (iii) the deviation of total delivery quantities for each day. In the second, we aim to adjust the deviation of total delivery quantities for each day. In this thesis, we apply the three algorithms for solving the problem under various combinations of parameters. Numerical results show that the immune algorithm performs better than the other two approaches, especially when the problem size is larger.

中文摘要...................................................i
ABSTRACT..................................................ii
誌謝.....................................................iii
目錄......................................................iv
表目錄....................................................vi
圖目錄..................................................viii
符號說明..................................................ix
第一章 緒論................................................1
1.1 研究背景與動機.........................................1
1.2 研究目的...............................................2
1.3 研究範圍與限制.........................................2
1.4 研究方法與步驟.........................................3
1.5 論文架構...............................................5
第二章 文獻探討............................................6
2.1 週期性車輛路線問題.....................................6
2.2 週期性車輛派遣最小化問.................................7
2.2.1問題描述..............................................7
2.2.2數學模式..............................................8
2.2.3例題 .................................................9
2.3 基因演算法求解原理與運作機制.........................10
2.3.1 基因與染色體........................................10
2.3.2 基因演算法之組成架構與演算步驟......................11
2.4 免疫演算法求解原理與運作機制.........................16
2.4.1 生物免疫系統........................................16
2.4.2 免疫演算法之組成架構與演算步驟......................19
2.5 粒子群演算法求解原理與運作機制.......................21
2.5.1 群體行為理論........................................21
2.5.2 粒子群演算法之組成架構與演算步驟....................22
第三章 研究方法...........................................25
3.1 具平衡之週期性車輛派遣問題............................25
3.1.1 問題描述............................................25
3.1.2 例題................................................26
3.1.3 數學模式............................................27
3.1.4 編碼方式............................................29
3.2演算法參數設定.........................................30
3.2.1 測試例題描述........................................30
3.2.2 免疫演算法與基因演算法參數設定......................31
3.2.3 粒子群演算法參數設定................................32
第四章 測試實驗與結果分析.................................34
4.1 測試問題之軟硬體設備..................................34
4.2 測試例題一結果與分析..................................34
4.2.1 運送量平衡狀態判別標準選擇..........................34
4.2.2 三種演算法實驗結果分析..............................37
4.2.3 平衡狀態改善方法....................................40
4.3 測試例題二結果與分析..................................42
4.3.1 實驗設計............................................43
4.3.2 結果與分析..........................................50
第五章 結論...............................................52
5.1 結論..................................................52
5.2 未來研究方向..........................................53
參考文獻..................................................54
附錄A 測試例題二求解數據(IA)..............................57
附錄B 測試例題二求解數據(GA)..............................66
附錄C 測試例題二求解數據(PSO).............................75
附錄D p-value檢定.........................................84
Extended Abstract
簡歷

1.王俊偉與汪定偉(2005)，「粒子群演算法中慣性權重的實驗與分析」，東北大學資訊科學與工程學院系統工程學報，20卷，2期，頁197-198。
2.任鳳鳴與李麗娟(2008)，「改進的PSO演算法中學習因數(c1 , c2)取值的實驗與分析」，廣東工業大學學報，25卷，1期，頁86-89。
3.吳俊炘，王秀鑾與陳大正(2004)，「利用免疫演算法於多重貿易商周律性市集問題之研究」，第一屆 台灣作業研究學會學術研討會暨2004年科技與管理學術研討會，台北，中華民國，11月12日。
4.呂英志(2002)，即時資訊下車輛路線問題之研究，逢甲大學交通工程與管理研究所，碩士論文。
5.卓裕仁(2001)，以巨集啟發式方法求解多車種與週期性車輛路線問題之研究，交通大學運輸工程與管理研究所，博士論文。
6.林信宏(2002)，應用基因演算法於結構動力參數識別，朝陽科技大學營建工程研究所，碩士論文。
7.林豐澤(2005)，「演化式計算下篇: 基因演算法以及三種應用實例」，東北大學資訊科學與工程學院系統工程學報，3卷，2期，頁29-56。
8.張文修與梁怡(1999)，遺傳算法的數學基礎，西安交通大學出版社。
9.張奕謙(2008)，具衰退性產品之不定點銷售問題的探討，虎尾科技大學工業工程與管理研究所，碩士論文。
10.黃若蘋(2007)，啟發式演算法於資料分群問題之比較，大同大學資訊經營研究所，碩士論文。
11.Beltrami E.J. & Bodin L.D. (1974), “Networks and vehicle routing for municipal waste collection”, Networks, Vol.4, pp. 65–94.
12.Campbell A.M. & Hardin J.R. (2005), “Vehicle minimization for periodic deliveries”, European Journal of Operational Research, Vol.165, No.3, pp. 668-684.
13.Chao I.M., Golden B.L.& Wasil E. (1995), “An Improved Heuristice for the Period Vehicle Routing Problem”, Networks, Vol. 26, N0. 1, pp. 747-765.
14.Christofides N. & Beasley J.E. (1984), “The Period Routing Problem”, Networks, Vol. 14, pp. 237-256.
15.Cordeau J.F., Gendreau M., & Laporte G. (1997), “A Tabe Search Heuristic for Periodeic and Multi-Depot Vehicle Routing Problems”, Networks, Vol. 30, No. 2, pp. 105-109.
16.Gaudioso M. & Paletta G. (1992), “A Heuristic for the Periodic Vehicle Routing Problem”, Transportation Science, Vol. 26, No. 2, pp. 86-92.
17.Grefenstette J.J. (1986), “Optimization of control parameters for genetic algorithms”, IEEE Transactions on Systems, Man, and Cybernetics, Vol 16, No l, pp. 122–128.
18.Holland J.H. (1975), “Adaptation in natural and artificial systems”, Ann Arbor, University of Michigan Press.
19.Jeffay K., Stanat D. & Martel C. (1991), “On Non-preemptive scheduling of periodic and sporadic tasks”, Proceedings of the Twelfth IEEE Real-Time Systems Symposium.
20.Jerne N.K. (1973), “The immune system”, Scientific American, Vol. 229, No. 1, pp. 52–60.
21.Kirkpatrick, S., Gelatt Jr. C.D. & Vecchi, M.P. (1983), “Optimization by Simulated Annealing,” Science, Vol. 220, pp. 671-680.
22.Leung J.Y.T. & Whitehead J. (1982), “On the complexity of fixedpriority scheduling of periodic, real-time tasks”, Performance Evaluation, Vol. 2, pp. 237–250.
23.Li W.T., Shi X.W., Xu L. & Hei YQ (2008), “Improved GA and PSO culled hybrid algorithm for antenna array pattern synthesis”, Progress In Electromagnetics Research, Vol. 80, pp. 461–476.
24.Lim Y.T., Cheng P.C., Rohatgi P. & Clar J.A. (2008), “Mls security policy evolution with genetic programming”, In GECCO ''08: Proceedings of the 10th annual conference on Genetic and evolutionary computation, pp. 1571–1578.
25.Man K.F., Tang K.S. & Kwong S.(1999), Genetic Algorithms: Concepts and designs, Springer-Verlag London.
26.Michalewicz Z. (1996), Genetic Algorithms + Data Structures = Evolution Programs (3rd. ed.), Springer-Verlag Berlin Heidelberg.
27.Park K.S.& Yun D.K. (1985), “Optimal scheduling of periodic activities”, Operations Research, Vol. 33, pp.690–695.
28.Russell R. & Gribbin D. (1991), “A Multiphase Approach To the Period Routing Problem”, Networks, Vol.21, pp.747-765.
29.Russell R., & Igo W. (1979), “An Assignment Routing Problem”, Networks, Vol. 9, pp. 1-17.
30.Tan C.C. &. Beasley J.E. (1984),. “A heuristic algorithm for the period vehicle routing problem”, International Journal of Management Science(OMEGA), Vol. 12, No. 5, pp. 497-504.