以啟發式演算法求解時窗限制車輛途程問題

A Meta-Heuristic Method for Vehicle Routing Problem with Time Window Constraints

陳百傑(Bai-Jie Chen)

指導教授 ： 陳建良

中原大學/工學院/工業工程研究所/碩士(2002年)

https://doi.org/10.6840/cycu200200299

摘要

摘要
近代探討車輛途程問題之研究，多以啟發式演算法求解相關議題居多。啟發式搜尋法雖不能保證求得最佳解，但其具有求解快速且能求得最佳解之近似解的優點。本研究結合禁制搜尋法 (Tabu Search, TS) 與噪音擾動法 (Noising Method, NM) ，發展出新的改良型啟發式演算法，禁制擾動法 (Tabu-Disturbance Algorithm, TDA) ，可求解具時窗限制之車輛途程問題 (Vehicle Routing Problem with Time Window Constraints, VRPTW) 。首要目標求總車輛行走距離最小，次目標為求配送車輛數最少，本研究並以Solomon (1987) 提出之56題國際題庫測試演算法績效。
車輛途程問題 (Vehicle Routing Problem, VRP) 在學術上已是耳熟能詳的熱門話題，然而因實務應用上仍有許多複雜的限制條件，且VRP求解複雜度高，若強調求解品質，一般求解時間動輒數小時，在實務上難以實際運用。以半導體業為例，為避免損失昂貴的產能，相對其時窗要求也相對嚴謹，因此迅速回應 (Quick Response) 顧客需求以提高服務水準(較短的行走距離) 比降低運輸成本 (較少的配送車輛數) 更為重要，因此本研究所提出之演算法以在短時間內求得高品質之近似解為另一追求目標，增加在目前實務應用之彈性。時間因子在物流配送的行業中已逐步被重視，因此具時窗限制之車輛途成問題也逐漸被廣泛討論。
本研究架構主要包含起始解建構、區域改善模組以及TDA改善模組三階段。第一階段建構應用時間導向最鄰近法快速求得初始解；第二階段區域改善模組應用車輛縮減模組以及傳統交換型演算法對初始解做粗略改善；TDA改善模組則針對求解品質做深度及廣度搜尋，以達到途程最佳化之目的。

關鍵字

噪音擾動法 ； 車輛途程問題 ； 禁制搜尋法 ； 時窗限制

並列摘要

ABSTRACT
This research proposes a heuristic, Tabu-Disturbance Algorithm (TDA), to efficiently and effectively solve Vehicle Routing Problem with Time Window Constraints (VRPTW). TDA integrates Tabu Search (TS) and Noising Method (NM). TS is the most popular generic heuristic in solving VRPHTW in recent years and NM is a combinatorial optimization meta-heuristic. The first objective is to determine the route that minimizes the total vehicle travel distances. This leads to quick response to satisfy customer demands. The second objective is to find the minimum required number of vehicles. This can reduce the transportation cost. Solomon’s 56 benchmark instances were tested for TDA.
TDA consists of three phases: initial solution construction, local search improvement, and disturbed search improvement. In the initial solution construction phase, enhanced Nearest Neighbor Method is used. In the local search improvement phase, vehicles reduction and Neighborhood Search modules are proposed. In the disturbed search improvement phase, a hybrid algorithm of TS and NM is used to improve the initial solution.
TDA results in good solution quality and efficiency. The average deviation of distance is less than 3% and the average deviation of number of vehicles is about 9.5%, compared to the known “best” solutions. The average computation time is approximately 8 minutes to solve an instance.

並列關鍵字

Time Window ； Noising Method ； Tabu Search ； Vehicle Routing Problem ； Tabu-Disturbance Algorithm

參考文獻

17. 陳契伸，「硬性/軟性時窗限制之車輛途程研究」，中原大學工業工程研究所碩士論文，2001。

11. 徐明輝，「多部車一般性車輛途程解算法之研究」，元智大學工業工程研究所碩士論文，1997。

21. 曾維豪，「軟性時窗與回程撿收之車輛途程問題研究」，元智大學工業工程研究所碩士論文，2000。

8. 林書銘，「禁制搜尋法於含時窗與裝載限制車輛途程問題解算之研究」，元智大學工業工程研究所碩士論文，1998。

16. 陳坤賓，「模擬退火演算法應用於車輛途程規問題之研究」，元智大學工業工程研究所碩士論文，1998。