臺灣博碩士論文加值系統

開放式車輛路線問題 (Open Vehicle Routing Problem, OVRP) 為VRP的一種衍生問題，它與傳統VRP的主要區別在於路線型態，OVRP路線型態為Hamiltonian path，而VRP路線型態為Hamiltonian cycle。OVRP中車輛從場站出發，終於顧客，車輛並不會返回場站。本研究應用粒子群演算法 (Particle Swarm Optimization, PSO) 求解OVRP問題，主要求解架構為參考Ai 和 Kachitvichyanukul [1]的第二種編碼方式(SR-2)，並根據本研究問題稍作修改，與此文獻求解架構最大不同為增加了2-Opt*、Or-Opt、Reduction鄰域改善模組，加強演算法的深度搜尋，因此粒子數設定也不同，文獻使用粒子數為50，而本研究使用粒子數為20，求解時間為更有效率。
本研究以Christofides 等人[6]中C1至C14題、Fisher [11]題庫中F11及F12、Li 等人 [15]題庫O1至O8以及MirHassani和Abolghasemi [17]文獻中的15題，一共39題作為測試例題。以C語言進行程式撰寫，測試環境為Windows 7作業系統，Intel (R) i3-2100，3.10GHz的個人電腦。本研究求解之績效為，若不考慮旅行時間限制的例題，一共使用224輛車，總車輛數誤差為0輛，若考慮之，則總車輛數誤差為2輛；一共使用290輛車，總車輛數誤差為2輛；39題標竿例題中有20題可以達到目前文獻已知最佳解。另外將本演算法應用於求解VRP問題，以14題國際標竿例題進行測試，結果顯示，平均誤差為0.51%，14題中有7題可以達到目前文獻已知最佳解。

中文摘要 i
英文摘要 ii
誌謝 iii
圖目錄 v
表目錄 vi
第一章 緒論 1
1.1 研究背景與動機 1
1.2 研究內容與範圍 1
1.3 研究方法與流程 3
第二章 文獻回顧 5
2.1 開放式車輛路線問題定義 5
2.2 開放式車輛路線問題之啟發式解法回顧 6
2.3 啟發式解法回顧 8
2.3.1 啟發式解法 8
2.3.2 粒子群演算法 11
2.4 小結 15
第三章 OVRP之PSO巨集啟發式解法構建 16
3.1 PSO 主要求解架構及學習策略設計 16
3.2 鄰域改善模組設計 17
第四章 PSO執行測試與分析 19
4.1 標竿題庫說明 19
4.2 實驗設計 20
4.2.1 參數部分 20
4.2.2 粒子數、迭代數測試 21
4.2.3 小結 22
第五章 測試結果與討論 23
5.1 演算法績效比較與分析 23
5.2 單一PSO架構求解效度測試 27
5.3 鄰域搜尋模組測試 29
第六章 結論與建議 34
6.1 結論 34
6.2 建議 35
參考文獻 36
附錄 39

系統網頁上的「英文摘要欄位」，請填入英文摘要，謝謝


[1] Ai, T. J. and Kachitvichyanukul, V., “Particle swarm optimization and two solution representations for solving the capacitated vehicle routing problem,” Computers & Industrial Engineering, Vol. 56, No. 1, pp.380–387, 2009.
[2] Ai, T. J. and Kachitvichyanukul, V., “A particle swarm optimization for the vehicle routing problem with simultaneous pickup and delivery,” Computers & Operations Research, Vol. 36, No. 5, pp. 1693-1702, 2009.
[3] Amini, S., “A novel PSO for solving the VRPTW with real case study,” Proceedings of the 2011 International Conference on Industrial Engineering and Operations Management, Kuala Lumpur, Malaysia, 2011.
[4] Bodin, L., Golden, B., Assad, A., and Ball, M., “Routing and scheduling of vehicles and crews: The state of the art,” Computers & Operations Research, Vol. 10, No. 2, pp. 63-211,1983.
[5] Brandão, J., “A tabu search heuristic algorithm for open vehicle routing problem,” European Journal of Operational Research, Vol. 157, No. 3, pp. 552-564, 2004.
[6] Christofides, N., Mingozzi, A., and Toth, P., The vehicle routing problem. In: Christofides, N., Mingozzi, A., Toth, P., Sandi, C., editors. Combinatorial optimization. Chichester, UK: Wiley, pp.315-38, 1979.
[7] Clarke, G. and Wright, J. W., “Scheduling of vehicles form a central depot to a number of delivery points,” Operations Research, Vol. 12, No. 4, pp. 568-581, 1964.
[8] Clerc, M., “The swarm and the queen: towards a deterministic and adaptive particle swarm optimization,” Proceedings of the IEEE Congress on Evolutionary Computation, Vol.3, Institute of Electrical and Electronics Engineers, pp.1951-1957, 1999.
[9] Dantzig, G. B. and Ramser, R.H., “The truck dispatching problem,” Management Science, Vol. 6, pp.80–91, 1959.
[10] Eberhart, R. C. and Shi, Y., “Comparison between genetic algorithms and particle swarm optimization,” Proceedings of the 7th international conference on evolutionary programming VII, 1998.
[11] Fisher, M., “Optimal solution of vehicle routing problems using minimum k-trees,” Operations Research, Vol. 42 No. 4, pp.626-42, 1994.
[12] Fleszar, K., Osman, I. H., and Hindi, K. S., “A variable neighborhood search algorithm for the open vehicle routing problem,” European Journal of Operational Research, Vol. 195, No. 3, pp. 803-809, 2009.
[13] Fu, Z., Eglese, R., and Li, LYO, “A new tabu search heuristic for the open vehicle routing problem,” Journal of the Operational Research Society, Vol. 56, No. 3, pp. 267-274, 2005.
[14] Kennedy, J. and Eberhart, R. C., “Particle swarm optimization, ” Proceedings of IEEE international conference on neural networks, Vol. 4, Institute of Electrical and Electronics Engineers, pp.1942-1948, 1995.
[15] Li, F., Golden, B., and Wasil, E., “The open vehicle routing problem: algorithms, large-scale test problems, and computational results,” Computers & Operations Research, Vol. 34, No.10, pp. 2918-2930, 2007.
[16] Li, X-Y, Tian, P,and Leung, S C H, “An ant colony optimization metaheuristic hybridized with tabu search for open vehicle routing problems,” Journal of the Operational Research Society, Vol. 60, No. 7, pp. 1012-1025, 2009.
[17] MirHassani, S.A. and Abolghasemi, N., “A particle swarm optimization algorithm for open vehicle routing problem,” Expert Systems with Applications, Vol. 38, No. 9, pp. 11547-11551, 2011.
[18] Or, I., “Traveling salesman-type combinatorial problems and their relation to the logistics of regional blood banking,” PhD. Dissertation, Northwestern University, 1976.
[19] Park, J. B., Lee, K. S., Shin, J. R., and Lee, K.Y., “A particle swarm optimization for economic dispatch with nonsmooth cost functions”, IEEE Transactions on Power Systems. Vol. 20, no. 1, pp. 34-42, 2005.
[20] Pisinger, D. and Ropke, S., “A general heuristic for vehicle routing problems,” Computers & Operations Research, Vol. 34, No. 8, pp. 2403-2435, 2007.
[21] Pongchairerks P. and Kachitvichyanukul V., “A Non-homogenous Particle Swarm Optimization with Multiple Social Structures,” Proceedings of international conference on simulation and modeling, pp. A5-02, 2005.
[22] Ren, C., Li, S., and Yue, B., “Research on the application of impoved hybrid genetic algorithm in open vehicle routing problem,” Progress in 2009 ISECS Second International Symposium on Electronic Commerce and Security, Vol. 1, Institute of Electrical and Electronics Engineers, pp.532-535, 2009.
[23] Repoussis, P.P., Tarantilis, C.D., Bräysy, O., and Ioannou , G., “A hybrid evolution strategy for the open vehicle routing problem,” Computers and Operations Research, Vol. 37, No. 3, pp. 443-455, 2010.
[24] Rosenkrantz, D., Sterns, R. and Lewis, P., “An analysis of several heuristics for the traveling salesman problem,” SIAM Journal of Computing, Vol. 6, pp. 563-581, 1977.
[25] Sariklis, D. and Powell, S., “A heuristic method for the open vehicle routing problem,” Journal of the Operational Research Society, Vol. 51, No. 5, pp. 564-573, 2000.
[26] Schrage, L., “Formulation and structure of more complex/realistic routing and scheduling problems,” Networks, Vol. 11, No. 2, pp. 229-232, 1981.
[27] Shi, Y. and Eberhart, R. C., “Parameter selection in particle swarm optimization,” Proceedings of Evolutionary Programming, Vol. 98, pp. 591-600, 1998.
[28] Tarantilis, C., Kiranoudis , C. T., and Vassiliadis, V. “A threshold accepting metaheuristic for the heterogeneous fixed fleet vehicle routing problem,” European Journal of Operational Research, Vol. 152, pp.148-158, 2004.
[29] Yu, B., Yang, Z. Z., and Yao, B., “An improved ant colony optimization for vehicle routing problem,” European Journal of Operational Research, Vol. 196, No. 1, pp. 171-176, 2009.
[30] Yurtkuran, A. and Emel, E., “A new hybrid electromagnetism-like algorithm for capacitated vehicle routing problems,” Expert Systems with Applications, Vol. 37, No. 4, pp.3427-3433, 2010.
[31] Zachariadis E. E. and Kiranoudis C. T., “An open vehicle routing problem metaheuristic for examining wide solution neighborhoods,” Computer & Operations Research, Vol. 37, No. 4, pp. 712-723, 2010.
[32] 王雅賢，「粒子群最佳化演算法改良之研究」，中原大學，碩士論文，民國95年。
[33] 李佩玲，「以混合基因與粒子群演算法求解旅行銷售員問題」，中原大學，碩士論文，民國95年。
[34] 卓裕仁，「以巨集啟發式方法求解多車種與週期性車輛路線問題之研究」，國立交通大學，博士論文，民國89年。