模擬退火演算法應用於車輛途程問題之研究

A Study on Vehicle Routing Problem by Simulated Annealing

陳坤賓(Kun-Pin chen)

指導教授 ： 胡黃德

元智大學/工程學院/工業工程與管理學系/碩士(1997年)

摘要

物流中心的物品輸出頻繁，其與一般工廠之差異在於物流中心有高比例
的運輸成本，而路線之規劃傳統上被視為車輛途程問題。所謂車輛途程
問題是指物流中心指派有載重限制的車輛，配送貨物給已知需求、位置
的顧客，然後回物流中心，使得運送成本最小。本研究加入考慮所有車
輛有一全程時間限制並利用最鄰近法、節省法來求得初始解，接著使用
允許系統狀態往高於目前能量的狀態空間移動的模擬退火演算法來得到
較佳的解。以往模擬退火擾動得到一新解便判斷是否接受新解，而本文
從數個新解中找一最佳的，然後判斷接受與否，且隨著鄰近解定義之不
同有3種模擬退火改善初始解。最後，本研究並藉由實驗設計找出最佳
的參數設定。結果顯示，初溫、停止法則、冷卻率對求解品質有顯著影
響。

關鍵字

模擬退火 ； 車輛途程問題

並列摘要

The transportation rate and cost of the goods for distribution
center(DC) is far more than that of a manufacturing factory.
The planning of the vehicle routing of the DCs is tradionally
treated as a vehicle routing problem(VRP). VRP is defined as a
set of vehicles of limited capacity at a DC serve all customers
exactly one and then return to the DC with minimized total
routing cost. This study considered that all vehicles have a
full time window and nearest and saving methods were employed
to get the initial solutions. Then the procedure utilized the
simulated annealing(SA) method to search for better solutions
by jumping off the trap to improve the initial solution.
Finally, an experimental design for the design parameters was
conducted for statistics analysis. The results show that the
factors of initial temperature, stopping rule and cooling rate
are significant for the solution quality.

並列關鍵字

Simulated Annealing ； Vehicle Routing Problem

參考文獻

陳功欽,"一般性車輛途程之探討",元智工學院工業工程研究所,1996

徐明輝, "多部車一般性車輛途程解算法之研究", 元智工學院工業工程研究所, 1997

Bodin, L. and B. Golden, "Classification in Vehicle Routing and Scheduling," Networks, Vol. 11, pp. 97-108, 1981.

Bonmi, E. and J. Lutton, "The N-city Traveling Salesman Problem: Statistical Mechanics Algorithm and the Metropolis Algorithm," SIAM Review, Vol. 26, No. 4, pp. 551-568, 1984.

Burkard, R. E. and F. Rendle, "A Thermodynamically Motivated Simulation Procedure for Combinatorial Optimization," European Journal of Operational Research, Vol. 17, pp. 169-174, 1984.