以模擬退火演算法求解載重相依之車輛途程問題

Solving the Load-Dependent Vehicle Routing Problem using Simulated Annealing Algorithm

近年來，綠色車輛途程問題 (Green Vehicle Routing Problem, GVRP) 的發展受到重視，原因是GVRP 將對環境的影響納入考量，本研究探討之載重相依車輛途程問題 (Load-Dependent Vehicle Routing Problem, LDVRP) 為GVRP 之延伸，將載重量納入目標式中，不再僅考量距離或時間為目標，是物流企業及公司考量環境、社會和企業治理 (Environment, Social, Governance, ESG) 重要一環。由於LDVRP 為NP-hard 問題，本研究使用已被廣泛應用於各種組合最佳化問題中且效果良好的模擬退火演算法 (Simulated Annealing, SA) 進行求解。所提出之SA 針對文獻標竿測試例題進行相關參數設定與測試，並比較其他演算法之結果。實驗結果顯示，本研究所提出之模擬退火演算法在可接受的求解時間下，最多可改善標竿例題的誤差值達0.04%。未來可進行更多的例題測試，並獲得物流實務資料進行所提SA 的求解。

In recent years, the green vehicle routing problem (GVRP) has received more attention due to the sustainability consideration. The subject of our research is the load dependent vehicle routing problem (LDVRP) which includes the vehicle load as additional indicator of the traveling cost. This research is motivated by the logistics operations and the Environment, Social, Governance (ESG) consideration. The objective function of the LDVRP takes the load of the vehicle into account. The travel cost could be represented by the amount of fuel consumption or CO2 emissions. Due to that LDVRP is an NP-hard problem, we develop a simulated annealing algorithm (SA) to solve it. The main difficulty in SA for solving the LDVRP is the neighborhood movement when computing the cost difference. The vehicle load will make the computation more complicated than that of classical VRP. The proposed SA is tested on benchmark instances and compared with the results from the literature. The computational result shows that SA can improve the gap by up to 0.04% within reasonable computational time. We believe that the proposed SA could be applied for the real world logistics operation.