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

A Hybrid Heuristic for Vehicle Routing Problem with Time Window Constraints

張寶豐(Pefo Cheng)

指導教授 ： 陳建良

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

https://doi.org/10.6840/cycu200300178

摘要

車輛途程問題（Vehicle Routing Problem）於物流運輸之研究與應用領域扮演著非常重要的角色。近年來物流宅配業界間之競爭與半導體及TFT-LCD製造廠對設備備份零件配送時效性要求越來越高，這促使具時窗限制之車輛途程問題（Vehicle Routing Problem with Time Window Constraints, VRPTW）的研究與應用盛行。本研究首要目標為總車輛行走距離最小以迅速回應顧客需求，次目標為配送車輛數最少以降低運輸成本，並以Solomon（1987）提出之56題國際題庫測試演算法績效。
VRP與VRPTW目前以啟發式演算法求解相關議題居多。啟發式搜尋法雖不能保證求得最佳解，但其具有求解快速且能求得最佳解之近似解的優點。本研究結合禁制搜尋法（Tabu Search, TS）、噪音擾動法（Noising Method, NM）與兩極跳躍法（Flip Flop Method, FF），發展出新的複合型啟發式演算法，加強型禁制擾動法（Enhanced Tabu - Perturbation Algorithm, ETPA），可求解VRP與VRPTW。本研究共分三階段，包含第一階段為起始解建構模組，應用時間導向最鄰近法快速求得初始解。第二階段為區域改善模組，應用車輛縮減模組以及傳統交換型演算法對初始解做粗略改善。第三階段為ETPA改善模組，針對求解品質做深度及廣度搜尋，以達到途程最佳化之目的。

關鍵字

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

並列摘要

This research proposes a heuristic, Enhanced Tabu - Perturbation Algorithm (ETPA), to efficiently and effectively solve Vehicle Routing Problem with Time Window Constraints (VRPTW). ETPA integrates Tabu Search (TS), Noising Method (NM) and Flip Flop Method (FF). TS is one of the most popular generic heuristics in solving VRPHTW in recent years. FF and NM are combinatorial optimization meta-heuristics. 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 ETPA.
ETPA consists of three phases: initial solution construction, local search improvement, and generic 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 generic search improvement phase, a hybrid algorithm integrating TS, NM and FF is used to improve the initial solution.
ETPA results in good solution quality and efficiency. The average deviation of distance is less than 3.9% and the average deviation of number of vehicles is about 9.5%, compared to the known “best” solutions. The average computation time is approximately 15 minutes to solve an instance.

並列關鍵字

Flip Flop Method ； Noising Method ； Time Window Constraints ； Tabu Search ； Vehicle Routing Problem

參考文獻

17. 陳百傑，「以啟發式演算法求解時窗限制車輛途程問題」，中原大學工業工程研究所碩士論文，2002。

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

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

16. 陳功欽，「一般性車輛途程問題之探討」，元智大學工業工程研究所碩士論文，1996。

19. 陳建良，饒忻，「AMT快速回應顧客需求」，中原大學工業工程研究所專題報告，1990