混合式人工蜂群法結合模擬退火演算法求解物流車路徑規劃問題

Abstract

由於全球暖化已經對人類的生活造成許多負面的影響，因此如何節約能源與減少運輸工具的碳排放量已在近年來受到眾多學者的關注。以物流業者為例，藉由安排有效的配送路徑減少耗油量與二氧化碳的排放量是很重要的關鍵。本篇中，我們定義車輛路徑問題(VRP)為物流業者欲從配送中心派遣貨車時，規劃最短的貨車配送路徑且配送給所有的客戶，可獲得最佳的配送距離/成本。本研究將人工蜂群演算法(ABC)結合模擬退火法(SA)的機制，增加解空間(solution space)的多樣性(diversity)，藉此有效地跳脫局部最佳化問題(local optimization problem)。最後，根據模擬結果顯示，在我們所執行的實驗模型中，我們所提倡的演算法(ABC-SA)較原始的人工蜂群演算法(ABC)有更多的潛力去近似最佳解。

As global warming has been negatively affecting many aspects of human lives, how to save energy and reduce carbon emissions via transportation has drawn much research attention in recent years. Take logistics services for example, the way to arrange an efficient delivery path is critical in cutting the carbon dioxide emissions and reducing the gas cost. In this thesis, we define the Vehicle Routing Problem (VRP) which involves dispatching cargo traveling along a delivery path. The scheduled path should visit all required customers while minimizing the delivery distance/cost. We propose to use a combined artificial bee colony (ABC) with simulated annealing (SA) mechanism, which extends the diversity of solution space to effectively escape the local optimization problem. Our simulation results indicate that the proposed approach (ABC-SA) has the potential to approximate optimal solutions than the original ABC algorithm in all conducted experimental cases.