粒子群演算法應用於多目標車輛途程問題之研究

A Study on the Application of Particle Swarm Algorithm on Multi-objective Vehicle Routing Problem.

楊昆展(Kun-Chan Yang)

指導教授 ： 邱顯明

淡江大學/管理學院/運輸管理學系碩士班/碩士(2009年)

https://doi.org/10.6846/TKU.2009.00719

摘要

物流業之型態也不斷地修正，期望能達到有效率的物流配送方式，同時也針對顧客的需求改變而進行配送型態改變。物流供應鏈逐漸整合，逆物流對於物流業者的重要性逐漸提升，因此正向物流加上逆向物流才能兼顧物流循環的完整性，因此同時考量收貨與送貨的車輛途程規劃就顯得相當重要。正逆向物流同時進行能有效減少車輛固定成本的花費及有效率的執行收貨與送貨需求，因此為了能有效將物流配送的過程也能達到節能減碳的目的，必須有效減少車輛的使用與行駛的里程，並且使車輛空間有效利用。
目前國際間重要的兩個議題為全球暖化與能源短缺，造成全球暖化的最主要原因是二氧化碳的大量排放，根據國際能源總署指出運輸部門為各國二氧化碳主要來源之一，經濟部能源局也指出運輸部門能源損耗為各部門第二。因此在國內各產業繁榮發展的同時，公司與公司間貨物流動更加頻繁，也對於節能減碳也逐漸開始重視，更因應未來碳權交易的實施，因此希望物流業者藉由採用多車種配送下達到此目的。
本研究在模式構建上主要是以物流業者為出發點，考量運輸總成本最小化、二氧化碳排放量最少及運送車輛貨物平均承載率最高等目標，來構建多目標多車種車輛途程規劃。問題的求解則是以C語言自行撰寫粒子群演算法進行求解。
以車輛途程問題的小型範例，來驗證模式與演算法的正確性；並以黃信穎（2005）所設計之模擬退火法進行求解品質與精度測試，由測試結果發現本研究演算法求解品質較佳；演算法參數的選擇上，則是利用了ANOVA檢定及LSD檢定找出較佳的參數。最後進行大型問題求解，經多次測試，提高運送車輛貨物平均承載率有效減少運輸成本與能源損耗；有規劃將需求點分群再進行運送，有效增加多車種運送時的整體效益。若採用低污染運送車輛對於運輸成本無明顯提升，卻能大大減少二氧化碳排放與增加運送車輛貨物承載率。由結果可之合乎一般邏輯性，證明本模式之正確性，具有應用價值，可以作為實務決策之參考。

關鍵字

多目標規劃 ； 粒子群演算法 ； 車輛途程問題

並列摘要

The pattern of logistics is continuous updated to achieve the effective delivery operations and to provide an efficient response to changes in customer demand. With the focus on the integration of the logistics Supply Chain, the importance of the reverse logistics is increasing to the logistics firms. Therefore, the integration of the forward and reverse logistics is critical to the logistics efficiency. The vehicle routing problem with simultaneous delivery and pick-up service is major task in this integration. This task not only reduces the fixed vehicle cost, but also increases the delivery operation. This task not only reduces the fixed vehicle cost, but also increases the delivery operation. With the global warming, the energy saving and carbon reduction is hottest topic in the society. Therefore, the reduction of the vehicle usage should be major concern in logistics will be major contribution for the logistics in this aspect.
The purpose of this study is to develop a Multi-objective Heterogeneous Fleet Vehicle Routing Problem to reflect the versatile concerns with the energy conservation and carbon reduction. A delivery operation plan with the multiple objectives such as minimum total transportation cost, minimum carbon consumption amount and maximum average loading ratio is derived from the proposed model. A solution procedure based on the Particle Swarm Algorithm (PSA) is developed for this model. All the coding of the proposed procedure is based on C-language to be executed in a PC.
To test the validation of the proposed solution procedure, we first apply it on a small size problem with an optimal solution form enumeration. The result indicate the proposed procedure capable of provide the same optimal solution. The case study of the Huang (2005) used to camper the result from his simultaneous annealing algorithm with our from the particle swarm algorithm, which demonstrates that superiority of our procedure. The parameters in the PSA are selected by the ANOVA and LSD tests to identify the best parameter value. A large scale of case study is then constructed to test the capability of the proposed procedure in dealing large delivery network. Based on the results of case study and sensitivity analysis, several findings can be identified as follows: 1.The increase of the loading factor results in reduction in transportation cost and energy consumption. 2.The cluster first and routing second approach can enhances the heterogeneous fleet impact on the improvement of objective function value. 3.The introduction low pollution vehicle can reduce tremendous carbon production and increase the vehicle load factor without significant increase in transportation cost. The results of above tests indicate that the proposed solution procedure can provide the valid and solid solution for the simultaneous consideration of the pickup and delivery operations with forward and reverse logistics.

並列關鍵字

Multi-objective Programming ； Particle Swarm Algorithm ； Vehicle Routing Problem

參考文獻

15. 邱仕銘（2006），「同時收送貨車輛配送問題之研究」，長榮大學經營管理研究所碩士論文，民國95年。

18. 葉仁吉（2006），「以類免疫演算法應用於船席指派問題之研究」，淡江大學運輸管理學系運輸科學碩士班碩士論文，民國95年。

4. 李旺蒼（2006），「以粒子群最佳化為基礎之混合式全域搜尋演算法求解含凹形節線成本最小成本轉運問題之研究」，國立中央大學土木工程研究所碩士論文，民國95年。

8. 敖君瑋（1999），「禁制搜尋法於軟性時窗限制之車輛途程問題研究」，元智大學工業工程研究所碩士論文，民國88年。

2. 吳泰熙，徐俊誠（2000），「車輛途程含取貨問題解法之研究」，大葉大學工業工程研究所碩士論文，民國89年。