應用人工智慧演算法探討週期性同時收送貨物之路徑規劃問題

Artificial Intelligence Approaches for the Periodic Vehicle Routing Problem with Simultaneous Delivery and Pickup

吳榮榮(Rong-Rong Wu)

指導教授 ： 謝益智

國立虎尾科技大學/管理學院/工業管理系工業工程與管理碩士班/碩士(2016年)

摘要

物流業所追求之目標在於貨暢其流，希望在合理的時間、車輛和配送路徑上將產品有效率地送達至顧客群中。本研究探討週期性同時收送貨物之路線規劃問題，此問題為同時收送貨之車輛路徑問題(Vehicle Routing Problem with Simultaneous Pickup and Delivery，VRPSPD)的延伸問題，主要區別在於本研究增加了各個需求點的固定週期，且問題中各個需求點有不同的收貨量和送貨量。本研究將需求點分為四種情境：(1)收貨=送貨(2)收貨>送貨(3)收貨<送貨(4)部份收貨≥送貨、部份收貨≤送貨，其應用包括宅急便、牛奶(瓶)收送、家庭代工收送貨等。
本研究以桃園市某區域為例，將各需求點之收送貨週期假設為每天都需收送貨、兩天收送貨一次、三天收送貨一次，並提出新的編碼方式同時解決貨物的每天收送地點組合與收送路徑順序，再以不同組合的情境、週期、車輛數、車輛容量、目標權重，應用基因演算法(Genetic Algorithms，GA)、免疫演算法(Immune Algorithms，IA)、粒子群演算法(Particle Swarm Optimization，PSO)，來求解此問題，使六天的路徑總距離為最短(目標1)及最小化車輛間每天路徑距離的差距(目標2)。測試數值結果顯示，免疫演算法與基因演算法求解品質較為穩定，且優於粒子群演算法。

關鍵字

週期性 ； 車輛路徑問題 ； 同時收送貨 ； 基因演算法 ； 免疫演算法 ； 粒子群演算法

並列摘要

The goal of logistics is to deliver goods to customers efficiently. This thesis explored the periodic vehicle routing problem with simultaneous delivery and pickup. This problem is also an extension of the vehicle routing problem with simultaneous pickup and delivery. The main difference is that this study assumes the periodic demand quantity and receipt quantity for each point. In this thesis, we have studied four types of periodic demand quantity and receipt quantity for points, namely, (1) pickup quantity =delivery quantity for all points, (2) pickup quantity > delivery quantity for all points, (3) pickup quantity

並列關鍵字

Periodicity ； Vehicle Routing Problem ； Simultaneous Pickup and Delivery ； Genetic Algorithm ； Immune Algorithm ； Particle Swarm Optimization

參考文獻

5. 邱仕銘(2006)，同時收送貨車輛配送問題之研究，長榮大學經營管理研究所，碩士論文。

19. 簡銓蔚(2013)，粒子群演算法應用於具容量限制的開放式車輛途程問題，元智大學工業工程與管理研究所，碩士論文。

7. 徐志明、陳子安、李漢宗(2011)，以基因規劃和人工免疫演算法最佳化薄型晶圓片切割參數，明新學報，37卷，2期，頁165-183。

8. 涂慧敏(2004)，週期性車輛排程問題之研究，大同大學資訊經營學系(所)，碩士論文。

14. 鄞玉婷(2015)，應用人工智慧演算法於大樓的週期性資源回收之路線規劃問題，虎尾科技大學工業工程與管理研究所，碩士論文。