混合演化巨集啟發式解法應用於具時間窗車輛路線問題之研究

Abstract

車輛路線問題由於能廣泛應用於相關實務問題，因此有不少研究針對各種不同之車輛路線問題進行深入的探討。其中具時間窗車輛路線問題是所有車輛路線問題中，最基本也最重要的一個問題，國內外一直都有許多學者針對此問題研究求解方法，希冀能夠獲得不錯的成果。

本研究以Homberger and Gehring (2005)所提出之兩階段混合演化巨集啟發式解法為基礎，結合Solomon I1插入法構建多個起始解，(μ, λ)-演化策略進行第一階段以極小化車輛數為主要目標的改善，回溯式門檻接受法(Backtraking Adaptive Threshold Accepting, BATA)在第二階段以極小化旅行距離為主要目標進行最後之改善，來求解具時間窗車輛路線問題。並以Solomon(1983)所提出之56題國際標竿題庫進行測試，探討本研究提出之解題模組，其求解績效。

本研究在(μ, λ)-演化策略中提出交換模組之車輛節省接受法則，以增進在該階段極小化車輛數之績效，並在可回溯式門檻接受法中探討多種參數組合以及交換模組組合，進行解題績效之探討。經過測試之後，本研究56題測試題庫之最佳結果，車輛數為416輛，總旅行距離為58001.90，與文獻已知最佳解─車輛數為404輛、總旅行距離為56639.00之誤差皆在3%以內(車輛數為2.97%、總旅行距離為2.41%)。其中有十題與文獻已知最佳解結果相同。

Vehicle Routing Problem with Time Windows (VRPTW), an extension of the classical Vehicle Routing Problem (VRP), has been widely applied to logistics and home delivery. The VRPTW considers that customers request the carrier to serve them within a specific time interval, i.e. time window. Such a constraint makes the VRPTW harder to slove than the VRP. Therefore, most of the solution methods for VRPTW are heuristics or metaheuristics.

The objective function of the VRPTW considered combines the minimization of the number of vehicles (first priority) and the total travel distance (second priority). Our research is based on the two-phase hybrid metaheuristics introduced by Homberger and Gehring (2005). The aim of the first phase is the minimization of the number of vehicles by means of a (μ, λ)-evolution strategy, and in the second phase, the total distance is minimized using Backtracking Adaptive Threshold Accepting (BATA) proposed by Tarantilis et al. (2001). Solomon’s 56 benchmark VPRTW instances were utilized to evaluate the performance of this hybrid evolutionary metaheuristics.

In this thesis, we propose a vehicle saving acceptance rule to enhance the performance of (μ, λ)-evolution strategy. In BATA, we test several combinations of parameters and improvement methods. All the experiments of this metaheuristics are coded in C# and implemented on a computer with AMD Athlon(tm) 64 Processor 3000+.

As to all of the 56 instances tested, the total number of vehicles of the best solution found by our proposed hybrid evolutionary metaheuristics is 416, and the total travel distance is 58001.90. As compared to the best known solutions of the benchmark instances, the average deviation of required vehicles is 2.97%, and the average deviation of total distance is 2.41%. Among those 56 benchmark instances, we have found the best known solutions in 10 instances.