成功大學博碩士論文系統

簡易檢索 / 詳目顯示

回結果列表

研究生：	毛皖亭 Mao, Wan-ting
論文名稱：	線上動態車輛巡迴路線演算法之發展：滾動平面法之應用 Development of On-line Dynamic Vehicle Routing Algorithms: A Rolling Horizon Approach
指導教授：	胡大瀛 Hu, Ta-yin
學位類別：	碩士 Master
系所名稱：	管理學院 - 交通管理科學系 Department of Transportation and Communication Management Science
論文出版年：	2007
畢業學年度：	95
語文別：	中文
論文頁數：	83
中文關鍵詞：	動態交通模擬指派軟體DynaTAIWAN 、滾動平面法、禁制搜尋法、線上型車輛巡迴路線問題
外文關鍵詞：	Tabu Search algorithm, Online VRP, DynaTAIWAN, Rolling Horizon Approach
相關次數：	點閱：107 下載：6
分享至:	分享至facebook 分享至twitter

查詢本校圖書館目錄查詢臺灣博碩士論文知識加值系統勘誤回報

現今物流業日益蓬勃發展，在其營運成本之中，運輸成本在整體物流成本中佔有非常高的比例，且為花費最多之物流營運項目；因此若能合理而有效降低運輸成本，相對來說也就是可以增加企業的營利收入。此外，近年來科技日益發達，隨著智慧型運輸系統大力推動，透過應用相關先進的電子、通信、資訊等技術，物流業者可透過相關設備取得運送貨物之商用車輛所在位置、即時交通路況資訊以及即時的顧客需求情況等資訊，進而對派遣車隊做即時的路線改善，或調整原先規劃之車輛派遣計畫，使其運輸成本降低，並對其顧客提供更快速、有效率之服務。
　　在研究車輛巡迴路線問題上，近年來逐漸由傳統的靜態問題演進到可利用即時資訊的動態問題，更進一步擴展成即時的線上型問題。由於車輛巡迴路線問題具有NP-Hard之特性，使用數學規劃方法將無法在有限的時間之內求解較大規模之問題，而啟發式演算法可因應求解問題之內容，在有限之時效內求解出一可接受解，因此現今一般多採用啟發式演算法來求解車輛巡迴路線相關問題。
　　線上型動態車輛巡迴路線問題主要探討在獲得即時資訊後，或是即時顧客需求產生或取消之車輛巡迴路線改變的情況，較傳統的車輛巡迴路線問題能反應出現實生活中之情況，故本研究擬採用一改良式的掃描法－Petals演算法來進行商用車輛初始路線構建，並使用一巨集啟發式演算法禁制搜尋法來進行車輛路線更新改善，且由於滾動平面法具有可即時反應當時現況之特性，因此本研究所使用之演算法建立在一滾動平面法概念之架構下，以期能達到即時反應現況之目的；並利用交通模擬指派模式(DynaTAIWAN)在一虛擬50節點路網以及一真實台南市路網進行模擬，來觀察本研究所發展之演算法對於商用車輛路徑指派所帶來之影響。

As the development of logistics, transportation and/or delivering cost, which accounts for substantial proportion of overall cost, could be reduced to enhance the competitiveness of the enterprise. Due to the advancement of Intelligent Transportation Systems (ITS), dispatching centers can get real-time information, real-time requests, and commercial vehicle routes according to electron, communication, and real-time information technology. The application of ITS technologies can improve deliver/pick-up services; however, the critical question is how to solve the Online Vehicle Routing Problems (Online VRP) under real-time information and real-time requests.
The Vehicle Routing Problems, one of the NP-hard problems, cannot not be solved efficiently by mathematical programming techniques. Although the heuristic approaches do not guarantee to obtain the optimal solution, they can solve the VRP problem more efficiently.
Online VRP consider realistic issues, such as real-time traffic conditions and new requests. This research proposes a heuristic approach to resolve on-line issues, such as real-time travel cost and real-time requests. In the heuristic approach, the Petals method is deployed to build the initial route for commercial vehicle, and the Tabu Search is used to update routes. In order to consider possible new requests, a rolling-horizon approach is implemented to react to real situations. Numerical experiments based on DynaTAIWAN are conducted for a test network and a real network－ Tainan City network to illustrate the proposed algorithm.

目錄
第一章  緒論..............................................1
1.1 研究背景與動機	....................................... 1
1.2 研究目的..............................................3
1.3 研究方法與流程	........................................3
第二章　文獻回顧..........................................6
2.1 供應鏈與物流之間的關係................................6
2.2 線上型車輛巡迴路線問題................................8
2.2.1 傳統車輛巡迴路線問題................................8
2.2.2 動態車輛巡迴路線問題................................9
2.2.3 線上型車輛巡迴路線問題.............................11
2.3 車輛指派.............................................12
2.4 禁制搜尋法...........................................16
2.4.1 禁制搜尋法之原理...................................16
2.4.2 禁制搜尋法之相關應用...............................20
2.5 滾動平面法...........................................21
2.6  DynaTAIWAN模擬指派模式..............................24
2.7 台灣地區物流配送公司相關現況.........................26
第三章　線上型車輛巡迴路線問題之分析.....................31
3.1 問題描述.............................................31
3.2 線上型車輛問題之研究架構.............................32
3.3 線上型車輛巡迴路線演算法設計.........................34
3.3.1 滾動平面法.........................................34
3.3.2 車輛指派演算法.....................................37
3.3.3 路線更新演算法.....................................40
3.4 服務績效指標.........................................43
第四章　程式架構流程與路網說明...........................45
4.1 程式架構.............................................45
4.2 測試路網說明.........................................48
4.2.1 虛擬50節點路網.....................................48
4.2.2 台南市路網.........................................50
4.3 基本測試.............................................51
4.3.1 基本系統功能確認...................................51
4.3.2 基本數值實驗	.......................................54
4.3.2.1 數值實驗設計.....................................54
4.3.2.2 數值實驗結果與分析...............................54
第五章　即時車輛派遣實驗與結果分析.......................59
5.1 模擬情境與實驗設計...................................59
5.1.1 路網情境設定	.......................................60
5.1.2 商用車輛數設定.....................................60
5.1.3 滾動週期頻率設定...................................61
5.1.4 實驗設計...........................................61
5.2 虛擬50節點路網實驗結果...............................62
5.2.1 均一需求型態下實驗結果.............................64
5.2.1.1 分析階段間之路徑指派比較.........................64
5.2.1.2 不同商用車輛數間之路徑指派比較...................66
5.2.1.3 不同滾動週期頻率之路徑指派比較...................68
5.2.2 常態需求型態下實驗結果.............................69
5.2.2.1 分析階段間之路徑指派比較.........................69
5.2.2.2 不同商用車輛數間之路徑指派比較...................71
5.2.2.3 不同滾動週期頻率之路徑指派比較...................73
5.3 台南市路網實驗結果...................................74
5.4 實驗結果分析.........................................76
第六章 結論與建議........................................78
6.1 結論.................................................78
6.2 建議.................................................79
參考文獻.................................................81
 
表目錄
表3.4-1 評估準則.........................................43
表4.2.1-1  虛擬50節點路網屬性設定值......................50
表4.3.2.2-1 均一分布下各階段車輛旅行情況.................55
表4.3.2.2-2 尖峰分布下各階段車輛旅行情況.................56
表4.3.2.2-3 常態分布下各階段車輛旅行情況.................56
表5.1.4-1  50節點路網均一型態實驗設計....................61
表5.1.4-2  50節點路網常態型態實驗設計....................61
表5.1.4-3  台南市路網均一型態實驗設計....................61
表5.3-1 實際物流配送車輛行駛路徑.........................75
 
圖目錄
圖1.3-1 研究方法流程圖....................................5
圖2.1-1 物流運送過程圖....................................7
圖2.1-2 直接式運送網路圖..................................8
圖2.1-3 配送中心式運送網路圖..............................8
圖2.2.3-1 線上型與離線型演算法求解方式之比較.............12
圖2.3-1 掃描法示意圖.....................................13
圖2.3-2 1-petal路線圖....................................14
圖2.3-3 2-petals路線圖...................................14
圖2.3-4 最終產生的r-petals路線圖.........................15
圖2.3-5 λ-interchange交換圖	..............................15
圖2.4.1-1 禁制搜尋法流程圖...............................17
圖2.5-1 滾動平面法示意圖.................................21
圖2.5-2 MORSS法中的滾動平面概念示意圖....................23
圖2.5-3 以雙時間平面為基礎之演算法應用於PDPTW之示意圖....24
圖2.6-1 DynaTAIWAN 系統模擬進行流程......................26
圖2.7-1 統一超商物流系統運作之示意圖	.....................29
圖3.2-1  線上型動態車輛路線規劃架構......................33
圖3.3.1-1  滾動平面法概念示意圖..........................35
圖3.3.1-2  滾動平面法執行流程圖..........................36
圖3.3.1-3  滾動平面法示意圖	..............................37
圖3.3.2-1  改良式Petals method演算流程圖.................39
圖3.3.3-1  2-opt交換法...................................41
圖3.3.3-2  即時資訊提供下的禁制搜尋法演算流程圖..........42
圖4.1-1 程式架構流程圖...................................46
圖4.2.1-1 虛擬50節點路網示意圖...........................49
圖4.2.2-1 台南市路網圖...................................51
圖4.3.1-1 滾動平面程式初始畫面...........................52
圖4.3.1-2 Stage 0開始模擬畫面............................52
圖4.3.1-3 Stage 1開始模擬畫面............................53
圖4.3.1-4 模擬結束畫面...................................53
圖5.2.1 派遣2、3、4輛商用車輛之分析階段Stage 0結果.......63
圖5.2.1.1-1  實驗50-U-2-5 分析階段Stage 0之指派路線結果..64
圖5.2.1.1-2  實驗50-U-2-5 分析階段Stage 1之指派路線結果..65
圖5.2.1.2-1  派遣2輛商用車輛服務之Stage 0及Stage 1路徑指派情況.....................................................67
圖5.2.1.2-2  派遣3輛商用車輛服務之Stage 0及Stage 1路徑指派情況.....................................................67
圖5.2.1.3-1  滾動週期頻率5分鐘以及10分鐘之Stage 1路徑指派情況.......................................................69
圖5.2.2.1-1  實驗50-N-2-5 分析階段Stage 0之指派路線結果..70
圖5.2.2.1-2  實驗50-N-2-5 分析階段Stage 1之指派路線結果..71
圖5.2.2.2-1  派遣2輛商用車輛服務之Stage 0及Stage 1路徑指派情況.....................................................72
圖5.2.2.2-2  派遣3輛商用車輛服務之Stage 0及Stage 1路徑指派情況.....................................................72
圖5.2.2.3-1  滾動週期頻率5分鐘以及10分鐘之Stage 1路徑指派情況.......................................................73
圖5.3-1  實際物流配送車輛行駛路徑與模擬路徑指派情況......74
                                    

‧柯景文 (2002)，禁制搜尋法於動態巡迴路線問題之研究，逢甲大學交通工程與管理研究所碩士論文。
‧胡大瀛等(2004)，區域級智慧型運輸系統示範計畫－核心交通分析與預測系統(第一年期)，交通部運輸研究所。
‧陳勝男 (1996)，禁忌搜尋法應用於車輛路線問題之研究，大葉大學工業工程研究所碩士論文。
‧陳德政 (2005)，即時資訊下物流配送問題之研究，逢甲大學交通工程與管理研究所碩士論文。
‧敖君瑋 (1999)，禁忌搜尋法於軟性時窗限制之車輛途程問題研究，元智大學工業工程研究所碩士論文。
‧梅明德 (1998)，線上型時窗限制車輛路線問題之模式與求解演算法，國立中央大學土木工程研究所博士論文。
‧郭欣華 (2006)，即時資訊下車隊管理問題之研究，國立成功大學交通管理科學系碩士論文。
‧統一超商7-ELEVEN官方網頁，http://www.7-11.com.tw/。
‧統一集團官方網頁，http://www.uni-president.com.tw/。
‧黃冠雄 (2002)，時效導向的娃娃車接送之車輛途程問題－以禁忌搜尋法求解，國立中正大學數學研究所碩士論文。
‧廖亮富 (1997)，含時窗限制多部車車輛途程問題解算之研究，元智大學工業工程研究所碩士論文。
‧Boctor, F. F., Renaud, J. and Laporte, G. (1996), “An improved petal heuristic for the vehicle routing problem,” Journal of the Operational Research Society, Vol. 47, pp. 329-336.
‧Chen, H.K., Hsueh, C.F., and Chang, M.S. (2005), “The real-time time-dependent vehicle routing problem,” Submitted to Transportation Research Part E.
‧Chopra, S., and Meindl, P. (2001), “Supply Chain Management,” Prentice-Hall, pp.457.
‧Clarke, G. and Wright, J.W. (1964), “Scheduling of vehicles from a central depot to a number of delivery points,” Operations Research, Vol. 12, pp. 568-581.
‧Coyle, J. J., Bardi, E.J., and Langley, C.J. (2003), “The Management of Business Logistics－A Supply Chain Perspective,” Thomson Learning, pp.14.
‧Gendreau, M., Hertz, A. and Laporte, G. (1992), “New Insertion and Post optimizatioin Procedures for the Traveling Salesman Problem,” Operations Research, Vol.40, No.6, pp.1086-1094.
‧Gendreau, M., Laporte, G., Musaraganyi, C., and Taillard, E.D. (1999), “A tabu search heuristic for the heterogeneous fleet vehicle routing problem,” Computers & Operations Research, 26, pp.1153-1173.
‧Ghiani, G., Guerriero, F., Laporte, G. and Musmanno, R. (2003), “Real-time vehicle routing: Solution concepts, algorithms and parallel computing strategies,” European Journal of Operational Research, pp.151, 1-11.
‧Gillett, B. and Miller, L. (1974), “A heuristic algorithm for the vehicle dispatch problem,” Operations Research, Vol. 22, pp. 340-349.
‧Glover, F. (1986), “Future Paths for Integer Programming and Links to Artificial Intelligence,” Computers & Operations Research, Vol.13, pp.533-549.
‧Lin, S. (1965), “Computer Solutions of the Traveling Salesman Problem,” The Bell System Technical Journal, Dec., pp. 2245-2269.
‧Lin, S. and Kernighan, B.W. (1973), “An Effective Heuristic Algorithm for the Traveling Salesman Problem,” Operations Research, Vol.21, pp. 498-516.
‧Mahmassani, H. S., Jaillet, P., and Yang, J. (1999), “On-line algorithms for truck fleet assignment and scheduling under real-time information,” Transportation Research Board 78th Annual Meeting.
‧Mitrović-Minić, S., Krishnamurti, R., and Laporte, G. (2004), “The double-horizon heuristic for the dynamic pickup and delivery problem with time windows,” Transportation Research Part B, 38, pp669-685.
‧Osman, I. H. (1991), “Metastrategy simulated annealing and tabu search algorithms for combinatorial optimization problem,” Ph.D. Dissertation, The Management School, Imperial Collage, London.
‧Osman, I. H. (1993), “Metastrategy simulated annealing and tabu search algorithms for the vehicle routing problem,” Annals of Operations Research, 41:421–451.
‧Psaraftis, H. N. (1988), “Dynamic Vehicle Routing Problems,” in Golden, B.L. and A.A. Assad (eds), Vehicle Routing: Methods and Studies, Elsevier (North-Holland), Amsterdam.
‧Psaraftis, H.N. (1995), “Dynamic vehicle routing: Status and prospect,” Annals of Operations Research, 61, pp.143-164.
‧Renaud, J., Boctor, F.F., and Laporte, G. (1996), “An Improved Petal Heuristic for the Vehicle Routing Problem,” Journal of the Operational Research Society, Vol. 47, pp. 329-336.
‧Rosenkrantz, D., Sterns, R. and Lewis, P. (1977), “An Analysis of Several Heuristics for the Traveling Salesman Problem,” SIAM Journal of Computing, Vol. 6, pp. 563-581.
‧Sgall, J, (1996), “Randomized online scheduling of parallel jobs,” Journal of Algorithms, Vol. 21, No. 1, pp. 149-175.
‧Sleator, D. D. and Tarjan, R. E., (1985), “Amortized efficiency of list update and paging rules,” Communications of the ACM, Vol. 28, No. 2, pp. 202-208.

校內：立即公開
校外：2007-08-24公開

簡易檢索 / 詳目顯示

相關論文