跳到主要內容

臺灣博碩士論文加值系統

(54.80.249.22) 您好!臺灣時間:2022/01/20 06:28
字體大小: 字級放大   字級縮小   預設字形  
回查詢結果 :::

詳目顯示

我願授權國圖
: 
twitterline
研究生:吳旻樵
論文名稱:新VRP啟發式解法之開發
指導教授:汪進財汪進財引用關係
學位類別:碩士
校院名稱:國立交通大學
系所名稱:交通運輸研究所
學門:運輸服務學門
學類:運輸管理學類
論文種類:學術論文
論文出版年:2002
畢業學年度:90
語文別:中文
中文關鍵詞:車輛巡行問題掃描法集群化
相關次數:
  • 被引用被引用:7
  • 點閱點閱:547
  • 評分評分:
  • 下載下載:0
  • 收藏至我的研究室書目清單書目收藏:2
在追求運輸配送作業的效率化與精確化的過程中,運具巡行路線的配置是最核心的問題。近年來,國內外於車輛巡行問題相關研究之焦點均集中在巨集啟發式解法之開發,即透過新近發展之人工智慧搜尋機制改善傳統車輛巡行問題啟發式解法精度不佳之毛病。但其往往使得整個解題結構變得龐大而複雜且計算繁複,令一般人對於該等演算法在理解與應用方面有相當大的接近障礙。因此,本研究嚐試構建求解架構簡單且計算量精簡之車輛巡行問題演算法。
本研究針對基本車輛巡行問題,發展兩階段式啟發式解法─先集群化後構建路線的方法,第一階段依客戶點之分布位置執行集群化工作,第二階段配合前一階段集群化提出路線建構搜尋策略,完成車輛巡行問題求解。其中,第一階段集群化工作中,以客戶點極座標(r,θ)為輸入資料,以K平均數法為集群方法,將極座標系統中相鄰之客戶點歸入同一集群中,第二階段路線建構工作配合這樣的集群法則,結合半徑方向搜尋與角度方向搜尋建構出具效率性之路線,再執行精化路線步驟。
本演算法測試了十題TSPLIB題庫例題並與塔布搜尋法、掃描法與節省法之運算結果相比較。在計算時間方面,明顯優於其它演算法(塔布搜尋法、掃描法與節省法),皆能於5秒內完成運算。由例題測試結果可發現本演算法當問題規模越大,運算時間上的優勢越明顯,且計算時間隨著客戶點規模增加,呈現近似線性的成長。至於求解品質方面,平均劣於塔布搜尋法7.21%;平均優於掃描法2.62%,其中有三題求解結果超越掃描法;平均劣於節省法1.02%,其中有兩題求解結果超越節省法。在叢集性明顯的客戶點分布型態下,幾可與塔布搜尋法並駕齊驅,且計算時間上達到大幅度之節省。
目錄
目錄 i
圖目錄 ii
表目錄 iv
第一章 緒論 1
1.1研究動機與目的 1
1.2研究範圍 2
1.3研究方法與流程 2
第二章 文獻回顧 5
2.1VRP問題 5
2.2VRP問題解題方法 8
2.3文獻評析 18
第三章 集群化處理 21
3.1車輛巡行問題為什麼要集群化 21
3.2何謂集群化? 21
3.3本研究集群化架構 26
第四章 路線搜尋與建立 33
4.1路線建構 33
4.2路線交叉檢查 35
4.2路線內節點交換檢查 38
第五章 實驗測試設計與結果分析 40
5.1不同問題規模下之求解表現 41
5.2客戶點分佈叢集性明顯下之求解表現 50
5.3以不同之車輛容量限制處理同一問題之求解表現 54
5.4綜合分析 59
第六章 結論與建議 63
參考文獻 65
參考文獻
1. Billy E. Gillett & Leland R. Miller(1974)”A Heuristic Algorithm for the Vehicle-Dispatch Problem”,Operation Research 1974 volume22,pp.340-349
2. Clarke,G.& J.W.Wright(1964)”Scheduling of Vehicles from a Central Depot to a Number of Delivery Point”Operation Research,Vol.12,No.4,pp568-581
3. Dilek Tuzun、Michael A.Magent and Laural L. Burke(1997),”Selection Vehicle Routing Heuristic Using Neural Network”International Transactions in Operation Research,Vol 4,No 3
4. Dueck,G.(1993)”Threshold Accepting :A General Purpose Optimization Algorithm Appearing Superior to Simulated Annealing”Journal of Computational Physics,Vol.90,pp.161-175
5. Fisher M.L(1995),”Vehicle Routing,”Chapter 1 in M.Ball,T.Magnanti,C.Monma and G.Nemhauser(eds.)Network Routing,Handbooks in Operations Research and Management Science 8,pp.1-33.
6. Frederick S.Hillier & Gerald J. Lieberman(1995)”Introduction to Operation Research”1995,McGraw-Hill,Inc.
7. Gendreau,M.,A.Hertz&G.Laporte(1994)”A Tabu Search Heuristic for the Vehicle Routing Problem”Management Science,Vol.40,No.10,pp.1276-1290
8. Irene Charon & Olivier Hundry(1993)”The noising method :a new method for combinatorial optimization”Operation Research Letters,pp133-137
9. Jacques Renaud and Fayez F.Boctor and Gilbert Laporte(1996),”An improved petal heuristics for the vehicle routing problem”,Journal of Operation Research Society,vol 47,pp.329-336
10. Laporte G.,Gendreau M.,Potivn J.V and Semet F.(2000),”Classical and modern heuristics for the vehicle routing problem”,International Transactions in Operation Research 7,pp.285-300.
11. Laporte,G.(1991)”The Traveling Routing Problem:An Overview of Exact and Approximate Algorithms”,European Journal of Operation Research Vol59.pp.231-247
12. Laporte,G.(1991)”The Vehicle Routing Problem:An Overview of Exact and Approximate Algorithms”,European Journal of Operation Research Vol59.pp.231-247
13. Lawrence Bodin and Bruce Golden(1981)”Classification in Vehicle Routing and Scheduling”,Network,Vol.11,1981
14. Lawrence D. Bodin(1990)“Twenty Years of Routing and Scheduling”,Operation Research Vol.38.No.4,1990
15. Lin,S.(1965),”Computer Solution of the Traveling Salesman Prolem,”The Bell System Technical Journal,Dec.,pp.2245-2269.
16. Lin,S.and B.W.Kernighan(1971)”An Effective Heuristic Algorithm for the Traveling Salesman Problem”,Operation Research,pp.498-516
17. Marshall L. Fisher and Ramchandran Jaikumar(1981)”A Generalized Assignment Heuristic for Vehicle Routing”,NETWORKS,Vol.11,1981
18. Michel gendreau & alain hertz & gilbert laporte(1992)”new insertion and postoptimization procedures for the traveling salesman problem”,operation research 1992 vol.40,no.6
19. Xu,J.,Kelly,J.P.,1996.A network flow-based tabu search heuristic for the vehicle routing problem.Transportation science 30,281-283
20. 徐世輝、郭中豐(2001)”應用模擬退火法於限制驅導式現場排程之研究”,國立台灣科技大學工業技術研究所自動化及控制學程碩士學位論文(90)
21. 國立交通大學運輸科技與管理學系網路實驗室:www.tem.nctu.edu.tw/~network/。
22. 曾國雄、王日昌(1997)”基因演算法在多目標組合最佳化文提之研究-以旅行推銷員問題為例”,國立交通大學交通運輸研究所博士論文,No.14
23. 曾國雄、王日昌、黃明居(1996)”以基因演算法與樣板路徑求解旅行推銷員問題”運輸計劃季刊,pp.493~516
24. 曾國雄、鄧振源”第六章 群落分析”,多變量分析(一)-理論應用篇,pp.202-223
25. 楊國樑(1988)”啟發式解法在不同節點分布下對旅行推銷員問題適用性之研究”國立交通大學交通運輸研究所碩士論文(77)
26. 楊智凱(1995),”以門檻接受法改善TSP與VRP路網成本之研究”國立交通大學土木工程學系碩士論文
27. 韓復華、卓裕仁、陳國清(1999)”五種巨集啟發式解法在VRP問題上的應用與比較”,中華民國第四屆運輸網路研討會論文集
28. 韓復華、卓裕仁”網路節點服務TSP與VRP問題回顧”,運輸網路分析,pp.202-223
29. 韓復華、陳正元(1991)” 節省法與路線間交換改善法在車輛路線問題(VRP)上之應用”國立交通大學土木工程學系碩士論文
30. 韓復華、陳國清(1998)” GDA與RRT啟發式解法在(VRP)問題上之應用”國立交通大學土木工程學系碩士論文
31. 韓復華、陳建緯,網路試驗室,Http://www.tem.nctu.edu.tw/~network/,國立交通大學運輸工程與管理學系韓復華等(1999)”TA與GDA巨集啟發式解法在VRPTW問題上之應用” ,中華民國第四屆運輸網路研討會論文集
33. 蘇純繒、王璟瑩(1998)”應用禁制搜尋法於物流中心區位選擇之研究”,國立雲林科技大學工業工程與管理技術研究所碩士論文(87)
34. 蘇純繒、廖韋翔(1998)”應用門檻接受法之多目標車輛路徑規劃”,國立雲林科技大學工業工程與管理技術研究所碩士論文(87)
QRCODE
 
 
 
 
 
                                                                                                                                                                                                                                                                                                                                                                                                               
第一頁 上一頁 下一頁 最後一頁 top