塔布搜尋法於含時窗與裝載限制車輛途程問題解算之研究

A Tabu Search for the Vehicle Routing Problemwith Time Window and Capacity Constraints

林書銘(Shu-Ming Lin)

指導教授 ： 徐旭昇 博士

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

摘要

本文旨在研發一個優良之塔布搜尋法來求解一個較廣形式之時窗與
裝載限制車輛途程問題，差別在於本研究將顧客群依其所在之街道位置
與道路型態，區分為網枝顧客與節點顧客，而以往的車輛途程問題研究
只專注於節點顧客。
本文所提演算法之獲取步驟如下：首先分別以『最鄰近法』及『掃
瞄+最鄰近法』求得初始解，再研究數種不同搜尋規則之塔布搜尋法來改
善這些初始解。本文以C++語言撰寫這些搜尋法之程式，測試題目之產生
採與實際狀況接近之田字型網圖，再綜合變異數分析法、最小顯著差法
(Least Significant Difference Method) 與初始解之平均改良績效來
分析各搜尋法演算成果數據並決定各搜尋法之參數值。最後在這些參數
值之下再進行實驗分析，比較各搜尋法之平均改良績效，最優者即為所
選。另本文所使用的塔布表單是採用途程轉換數字方式，與以往研究不
同；此方式不僅使用很少電腦記憶體，同時可完全保留禁制解之內容。
在此情況之下，塔布搜尋法要素之一『免禁規則』可被省略。

關鍵字

塔布搜尋法 ； 時窗 ； 車輛途程問題

並列摘要

This paper describes a tabu search heuristic for the vehicle
routing problem with time window and capacity constraints(VRPTC)
. In this problem, a fleet of vehicles with the same limited
capacity is available at a common depot to serve a set of
customers with known demands. Each customer must be visited with
in a specified time interval. All customers are divided into
node-customer and arc-customer according to their locations and
the type of the street segments where they are located. The
heuristic considers the total transportation cost as the main
objective and the minimum number of vehicles as the secondary
objective.We study two algorithms for obtaining the initial
solution, "nearest neighbor" and " angle scanning + nearest
neighbor," and three different solution improvement algorithms
under the tabu search setting. There are totally six heuristics
produced by the combination of these algorithms. We analyze
the simulated data and set the best parameter values for these
six heuristics by the Least Significant Difference and the
ANOVA methods. According to our experimental results, the
second heuristic, Tabu II, is recommended for the practical use.
This research also introduces a new tabu list structure, which
can keep all information of the past several tabu moves by
very limited memory space. Thus, the element of tabu search
"Aspiration" can be omitted.

並列關鍵字

Tabu Search ； Time Window ； Vehicle Routing Problems

參考文獻

Alfa, A. S., Heragu, S. S. and Chen M. "A 3-opt Based Simulated Annealing Algorithm for Vehicle Routing Problems," Computers Industrial Engineering, Vol. 21, No.1-4, pp. 635-639. 1991.

Altinkemer, K. and B. Gavish. "Parallel Savings Based Heuristic for the Delivery Problem," Operation Research, Vol. 39, pp. 456-469. 1991.

Cornuejols, G. and J. W. Wright. "Scheduling of Vehicles from a Central Depot to a Number of Delivery Points," Operation Research, Vol. 12, pp. 568-581. 1964.

Desrochers, M. and T. W. Verhoog. "A Matching Based Saving Algorithm for the Vehicle Routing Problem," Cahier du GERAD G-89-04, Ecole des Hautes Etudes Commerciales de Montreal. 1989.

Dueck, G. and Scheuer, T. "Threshold Accepting Ageneral Purpose Optimization Algorithm Appearing Superior to Simulated Annealing," Joural of Computational Physics, Vol 90, pp. 161-175. 1990.