臺灣博碩士論文加值系統

為滿足企業的物流配送需求，車輛路線安排與規劃就越顯重要，車輛途程問題以達到最短行車距離為目標，以節省成本並提高效率。容量限制車輛途程問題(Capacity of Vehicle Routing Problem, CVRP)是一種組合最佳化問題，如何在車輛容量限制、有限車數下進行最短距離的派車途程規劃屬於NP-hard問題。以往求解車輛途程問題分成客戶分群與排序兩階段，因為排序階段缺乏記憶性，故每次新的分群後都需要重新排序，需花費很多時間。本研究方法先利用離散型細菌演算法(Discrete Bacterial Foraging Optimization, DBFO)進行分群，再利用兩種機率矩陣(Probability Matrix)進行排序：排序矩陣(Sorting Matrix, SM)抓取記憶矩陣(Memory Matrix, MM)內機率並進行細菌演化操作產生新的途程解，而好的途程解對應的機率值將回存到記憶矩陣內供後續使用。該方法不但解決每次分群後都需要重新排序的問題，也增加記憶性提升解的品質和程式執行效率。實驗結果顯示，本研究所提出之演算法能夠有效解決容量限制下之車輛途程問題。

Vehicle routing problem (VRP) becomes more important in the distribution industry. Capacitated vehicle routing problems (CVRP) are a combinatorial optimization problem. It has been proved that CVRP is an NP-hard problem. Therefore it is hard to find optimal solutions for large-sized problems. This paper proposes a Discrete Bacterial Foraging Optimization with Probability Matrix (DBFOMAT) approach to solve the CVRP. The proposed approach uses a probability matrix as the main mechanism for solution matrix decoding. The algorithm first uses DBFO for assigning customers to routes and then uses probability matrices to arrange customer visiting sequences for each vehicle. This approach also uses another probability matrix to memorize customer sequences, which are used to guide customer sequencing in next iteration. The experimental results show that the proposed algorithm is an effective approach for solving the CVRP.

摘要 i
ABSTRACT ii
目錄 iii
圖目錄 iv
表目錄 vi
第壹章 簡介 1
1.1 研究背景與動機 1
1.2 研究範圍與限制 3
1.3 研究方法與流程 3
1.4 論文架構 4
第貳章 文獻探討 5
2.1容量限制車輛途程問題 5
2.2粒子群演算法 7
2.3細菌覓食最佳化演算法 10
2.4機率矩陣 11
第參章 方法論 13
3.1 數學模型 14
3.2 DBFOMAT演算法的基本概念 16
3.2.1解的表達 16
3.3離散型細菌演算法解顧客分群 17
3.3.1 翻滾與游泳 19
3.4機率矩陣解顧客排序 20
3.5 DBFOMAT演化流程： 22
3.6 不合理解的處理 26
3.7 區域搜尋 26
第肆章 排序範例說明 29
第伍章 實驗與比較 32
第陸章 結論 37
參考文獻 38

[1] 高有成 、張怡凡，2012，”混合粒子群與細菌覓食演算法解決容量限制車輛途程問題”，『中華民國資訊管理學會研討會論文集, ICIM 2012』，1295-1306頁
[2] J. Kennedy and R. Eberhart, “Particle swarm optimization,” in Proc. IEEE international conference on neural networks, vol. 4, pp. 1942-1948, 1995.
[3] G. B. Dantzig and J. H. Ramser, “The truck dispatching problem,” Management
Science, vol.6, no. 1, pp.80-91, 1959.
[4] N. Jozefowiez, F. Semet and E. G. Talbi, ”Multi-objective vehicle routing problems,”European Journal of Operational Research, vol. 189, no. 2, pp. 293-309, 2008.
[5] L. Lenstra and A. R. Karl ,“Complexity of vehicle routing and scheduling
Problems,” Networks, vol. 11, no. 2, pp. 221-228, 1981.
[6] I. H. Osman, “Metastrategy simulated annealing and tabu search algorithms for the vehicle routing problem,” Annals of Operations Research, vol. 41, no. 4, pp. 421-451,1993.
[7] A. V. Breedam, “Improvement heuristics for the Vehicle Routing Problem based on simulated annealing,” European Journal of Operational Research, vol. 86, no. 3, pp. 480-490, 1995.
[8] R.T. Moghaddam, N. Safaei and Y. Gholipour, “A hybrid simulated annealing for capacitated vehicle routing problems with the independent route length,” Applied
Mathematics and Computation, vol. 176, no. 2, pp. 445-454, 2006.
[9] P. Augerat, J.M. Belenguer, E. Benavent, A. Corberan and D. Naddef, “Separating capacity constraints in the CVRP using tabu search,” European Journal of Operational Research, vol. 106, no. 2-3, pp.546-557, 1998.
[10] S.W. Lin, Z.J. Lee, K.C. Ying and C.Y. Lee, “Applying hybrid meta-heuristics for capacitated vehicle routing problem,” Expert Systems with Applications, vol. 36, no. 2, pp.1505-1512, 2009.
[11] B. M. Baker and M. A. Ayechew, “A genetic algorithm for the vehicle routing
problem,” Computers & Operations Research, vol. 30, no. 5, pp. 787-800, 2003.
[12] H. Kanoh and S. Tsukahara, "Virus Evolution Strategy for Vehicle Routing Problems with Time Windows," in Parallel Problem Solving from Nature–PPSN X, ed: Springer, pp. 1041-1050, 2008.
[13] Nazif, Habibeh, and L. S. Lee, "Optimised crossover genetic algorithm for capacitated vehicle routing problem." Applied Mathematical Modelling, Vol.36, no. 5,pp. 2110-2117, 2012.
[14] T. C. Chen, P. W. Tsai, S. C. Chu and J. S. Pan, “A novel optimization approach: Bacterial-GA foraging,” in Proc. IEEE International Conference on Innovative Computing, Information and Control, pp. 391-394, 2007.
[15] H. Chen, Y. Zhu and K. Hu, “Self-adaptation in bacterial foraging optimization
algorithm,” in Proc. IEEE International Conference on Intelligent System and Knowledge Engineering, pp.1026-1031, 2008.
[16] H. Nouri, S. H. Tang, B. T. Hang and M. K. Anuar, “BASE: A bacteria foraging
algorithm for cell formation with sequence data,” Journal of Manufacturing Systems, vol.29, no. 2-3, pp.102-110, 2010.
[17] J. Wang, “The application on attribute reduction by using bacterial foraging
optimization and PSO algorithm,” Communications in Computer and Information Science, vol. 237, no. 17, pp. 590-597, 2011.
[18] M. Wan, L. Li, J. Xiao, C. Wang and Y. Yang, “Data clustering using bacterial
foraging optimization,” Journal of Intelligent Information, vol. 38, no.2, pp.321-341,2011
[19] B. Niu, Y. Fan, H. Xiao and B. Xue, “Bacterial foraging based approaches to
portfolio optimization with liquidity risk,” Neurocomputing, Vol. 98, no.3,pp. 90–100,2012
[20]Sur, Chiranjib, and A. Shukla, "Discrete bacteria foraging optimization algorithm for vehicle distribution optimization in graph based road network management," Recent Advances in Intelligent Informatics, Vol. 235 , pp 351-358,2014
[21] A. L. Chen, G. K. Yang and Z. M. Wu, ”Hybrid discrete particle swarm optimization algorithm for capacitated vehicle routing problem,” Journal of Zhejiang University SCIENCE A, vol. 7, no. 4, pp. 607-614, 2006.
[22] T. J. Ai and V. Kachitvichyanukul, “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.
[23] P. Wei , K. Wang , C. Zhou and L. Dong, "Fuzzy discrete particle swarm optimization for solving traveling salesman problem," Computer and Information Technology, Vol. 9, no 2, pp. 264-271,2012.
[24] B. I. Kim and S. J. Son, “A probability matrix based particle swarm optimization,” Journal of Intelligent Manufacturing, Vol. 23, no. 4, pp. 1119-1126,2012.
[25] B. Jarboui, M. Cheikh, P. Siarry, A Rebai, "Combinatorial particle swarm optimization (CPSO) for partitional clustering problem," Applied Mathematics and Computation, Vol. 192, no. 2, pp. 337–345,2007.
[26] Tan, Lijing, and F. Lin, and H. Wang, "Adaptive comprehensive learning bacterial foraging optimization and its application on vehicle routing problem with time windows," Neurocomputing, Vol.151, no. 3, pp. 1208–1215,2015.
[27] Y. Kao and M. Chen , “A hybrid PSO algorithm for the CVRP Problem,” in
Proc. ECTA 2011 - International Conference on Evolutionary Computation Theory and Applications, Paris, France, pp. 539-543, 2011.
[28] K. M. Passino, “Biomimicry of bacterial foraging for distributed optimization and control,” IEEE Control Systems Magazine, vol.22, no. 3, pp. 52-67, 2002.