完整後設資料紀錄
DC 欄位語言
dc.contributor.author王春鎰en_US
dc.contributor.authorChuen-Yih Wangen_US
dc.contributor.author韓復華en_US
dc.contributor.authorAnthony Fu-Wha Hanen_US
dc.date.accessioned2014-12-12T03:07:45Z-
dc.date.available2014-12-12T03:07:45Z-
dc.date.issued2007en_US
dc.identifier.urihttp://140.113.39.130/cdrfb3/record/nctu/#GT009432502en_US
dc.identifier.urihttp://hdl.handle.net/11536/81577-
dc.description.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%)。其中有十題與文獻已知最佳解結果相同。zh_TW
dc.description.abstractVehicle 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.en_US
dc.language.isozh_TWen_US
dc.subject具時間窗車輛路線問題zh_TW
dc.subject混合演化巨集啟發式解法zh_TW
dc.subject(μ, λ)-演化策略zh_TW
dc.subject可回溯式門檻接受法zh_TW
dc.subjectVehicle Routing Problem with Time Windowsen_US
dc.subjectHybrid Evolutionary Metaheuristicsen_US
dc.subject(μ, λ)-evolution Strategyen_US
dc.subjectBacktracking Adaptive Threshold Acceptingen_US
dc.title混合演化巨集啟發式解法應用於具時間窗車輛路線問題之研究zh_TW
dc.titleA Hybrid Evolutionary Metaheuristics for the Vehicle Routing Problem with Time Windowsen_US
dc.typeThesisen_US
dc.contributor.department運輸與物流管理學系zh_TW
顯示於類別:畢業論文


文件中的檔案:

  1. 250201.pdf

若為 zip 檔案,請下載檔案解壓縮後,用瀏覽器開啟資料夾中的 index.html 瀏覽全文。