求解考慮載重油耗之車輛路線問題

Abstract

燃油成本是卡車成本的主要因素，尋找最佳路徑是減少卡車燃料成本的一種方式。這個問題被稱為車輛路線問題VRP或車輛路徑問題是一個組合優化和整數規劃是找到路由的最佳組合，可以最大限度地降低總成本的路線。在這項研究中，研究人員解決它參考的距離和負載作為燃料成本的因素，車輛路徑問題（ VRP ）的問題。燃料消耗相關的因素包括距離，負載，速度，加速度，檔位，道路角度，等本研究的目標函數是盡量減少考慮燃料相關的距離和負載的一個因素燃料成本消費。 本研究採用模擬退火算法作為解決辦法。模擬退火（SA）是一種逼近給定函數的全局最優的隨機優化技術。本研究介紹了如何生成一個可行的解決方案的一個新概念。稱為不平等的概率選擇考慮負荷的概念。該方法的概念是字符串中的每個房間的概率是不一樣的。這取決於它應該和它不應該之間的偏差。研究者產生10個不同的情況下，具有相同數量的節點（25節點）。與這些數據進行測試的算法。基於該實驗，最優解之間通過使用Gurobi和從模擬退火的溶液，其實現不等概率選擇的偏差表明9個10它們的標準偏差是百分之零。這意味著，不存在解決方案的變體。所以，根據該實驗中，不等的概率的選擇表明，它可在實現最優解保持穩定。

Fuel cost is a major element in a truck cost. Finding the best route is a way to reduce fuel cost for the truck. This problem is known as a vehicle routing problem or VRP. Vehicle routing problem is a combinatorial optimization and integer programming which is find the optimal sets of the routes that can be minimize total route cost. In this research, the researchers solve the problem of vehicle routing problem (VRP) which considers the distance and the load as the factors of fuel cost. The factors related on fuel consumption are the distance, the load, speed, acceleration, gear position, road angle, and etc. The objective function of this research is to minimize fuel cost that considers the distance and the load as a factor related on fuel consumption. This research use Simulated Annealing algorithm as a solution approach. Simulated Annealing (SA) is a stochastic optimization technique for approximating the global optimum of a given function. This research introduces a new concept of generating a feasible solution. The concept called as an unequal probability selection considering load. The concept of this method is the probability of each room in the string is not the same. It depends on the deviation between where it should be and where it should not be. The researchers generate 10 different cases with the same number of nodes (25 nodes). The algorithm tested with those data. Based on the experiments, the deviation between optimal solution by using Gurobi and the solution from Simulated Annealing which is implement the unequal probability selection shows that 9 out of 10 the standard deviation of them is zero percent. It means that there is no variation of the solution. So, based on the experiments, the unequal probability selection shows that it can maintain stability in achieving optimal solution.