(3.236.214.19) 您好!臺灣時間:2021/05/10 04:34
字體大小: 字級放大   字級縮小   預設字形  
回查詢結果

詳目顯示:::

我願授權國圖
: 
twitterline
研究生:周蘇江
研究生(外文):Chou Su-Chiang
論文名稱:含時窗限制的動態車輛途程問題之研究
論文名稱(外文):A Study of The Dynamic Vehicle Routing Problem With Time Windows
指導教授:杜志挺杜志挺引用關係
指導教授(外文):Timon Chih-Ting Du
學位類別:碩士
校院名稱:中原大學
系所名稱:工業工程研究所
學門:工程學門
學類:工業工程學類
論文種類:學術論文
論文出版年:2001
畢業學年度:89
語文別:中文
論文頁數:122
中文關鍵詞:即時反應啟發示解法動態車輛途程
外文關鍵詞:real-time reactionheuristic solutiondynamic vehicle routing
相關次數:
  • 被引用被引用:11
  • 點閱點閱:185
  • 評分評分:系統版面圖檔系統版面圖檔系統版面圖檔系統版面圖檔系統版面圖檔
  • 下載下載:0
  • 收藏至我的研究室書目清單書目收藏:0
傳統上解決靜態的車輛途程問題的方法,無法應用於B2C (Business to Customer)的物流環境中,主要的因素是在於顧客需求及位置是即時而且不確定的,因此有動態的車輛途程問題的產生。
本研究在有容量及時窗的限制條件下,探討動態的車輛途程問題,並提出了利用解決靜態問題的啟發式演算法加以調整及修改,利用初始路線建構的方式,配合路線改善的方法,以雙向連結串列的資料結構,及反覆循序式的方法,並且強調求解時間的長短,使其適合於動態的問題,解決顧客需求及位置的不確定性的車輛途程問題。對於各種不同的演算法,利用實驗設計的方法,進行模擬結果的討論,探討各因子的不同水準間對不同績效指標的影響,針對插單的顧客,探討演算法對此類型的顧客的反應能力及其影響,並且分析模擬的結果。最後提出本研究的結論及未來可繼續發展的方向。
Dynamic vehicle routing problems arise when customers’ demands occur in real-time without knowing the information in advance. The conventional static model can’t apply to the dynamic environment. In this study, we consider the dynamically vehicle routing problem that deliver to customers with both capacity and time windows constraints. This research proposes a two-step algorithm that is modified from the heuristic approach of static problems. The first step constructs initial routes, and the second step improves the routes. The data structure of proposed algorithm is a double link list with re-optimization method. It focuses on how fast the system can solve the dynamic problem. This study also uses experimental design to simulate the model and the analysis of different indexes will be covered.
中文摘要………………………………………………………….………I
英文摘要………………………………………………………….………II
謝誌………………………………………………………….……………III
目錄………………………………………………………….……………IV
圖目錄………………………………………………………….…………VII
表目錄………………………………………………………….…………X
第一章緒論…………………………………………………….………1
1.1研究背景與動機…………………………………….………1
1.2研究目的、範圍與假設…………………………….………2
1.3論文架構…………………………………………….………3
第二章文獻探討…………………………………………….………….5
2.1車輛途程問題…………………………………….………….5
2.1.1車輛途程問題之定義……………………….…………5
2.1.2車輛途程問題之數學模式……………………….……5
2.1.3車輛途程問題求解策略……………………….………6
2.2動態車輛途程問題……………………………….………….8
2.2.1動態車輛途程問題的定義……………….……………9
2.2.2動態車輛途程問題的解法回顧………….……………9
2.2.3動、靜態問題特性與差異………….…………………10
2.2.4動態模式的衡量指標…………………….……………11
2.3啟發示解法…………………………………….…………….12
2.3.1插入╱節省法…………………………….……………14
2.3.2掃瞄法………………………………….………………16
2.3.3二階段式演算法……………………….………………17
2.3.4途程間的2-exchange交換法……….……………..18
2.3.5途程間的2-swap交換法…………….………………19
2.3.6途程間的插入法……………………….………………20
2.3.7途程內的2-OPT……………………….……………..21
2.3.8途程內的Or-OPT……………………….……………22
2.3.9途程內的2-Swap……………………….……………22
2.3.10塔布搜尋法……………………….……………………23
2.3.11遺傳演算法……………………….……………………25
第三章研究方法…………………………………….…………………..27
3.1問題的定義……………………………….…………………..27
3.2系統架構與物件模型建立……………….………………….27
3.2.1系統架構………………………….……………………27
3.2.2系統描述………………………….……………………29
3.2.3系統的物件模型………………….……………………30
3.2.4系統的績效指標………………….……………………33
3.3動態演算法……………………………….…………………..35
3.3.1動態演算法概述…………………….…………………35
3.3.2動態求解策略…………………….……………………36
3.3.3各階段演算法之求解策略……….……………………38
3.4動態演算法之設計…………………….……………………..41
3.4.1動態演算法之資料結構………….……………………42
3.4.2時窗限制…………………………….…………………43
3.4.3先適法的最鄰近法………………….…………………44
3.4.4最適法的最鄰近法………………….…………………46
3.4.5掃瞄法…………………………….……………………48
3.4.6途程間改善的插入法…………….……………………50
3.4.7途程間改善的交換法………………….………………52
3.4.8途程內改善的or-OPT法…………….………………54
3.4.9途程內改善的2-Swap法…………….………………56
3.5系統模擬…………………………….………………………..59
3.5.1動態演算法之資料結構……….……………………….59
3.5.2名詞定義……………………….………………………59
3.5.3系統假設……………………….………………………61
3.5.4測試環境……………………….………………………62
第四章模擬結果與討論…………………………….…………………63
4.1實驗設計…………………………….………………………64
4.2模擬時間之分析結果與探討……….………………………69
4.3車輛行駛距離之分析結果與探討….………………………77
4.4顧客在系統中時間之分析結果與探討….…………………85
4.5延遲最晚時窗時間之分析結果與探討….…………………94
4.6模擬結果的分析與探討……………….……………………102
第五章結論與未來展望…………………………….………………….116
5.1結論……………………….…………………………………..116
5.2未來展望……………………….……………………………..117
參考文獻…………………………….……………………………………119
附錄A…………………………….……………………………………….A-1
參考文獻(Bertsimas and Ryzin 1993) Bertsimas D. J., Van Ryzin G., 1993, Stochastic and dynamic vehicle routing in the Euclidian plane with multiple capacitated vehicles, Operations Research, 41, 60-76.(Christofidesh, et. al. 1979)Christofides, N., Mingozzi, A., Toth, P., 1979, The vehicle routing problem, in: N. Christofides, A. Mingozzi, P. Toth and C. Sandi(eds.), Combinatorial Optimization, Wiley, Chichester, 315-338.(Clarke and Wright 1964) Clarke, G., and Wright, J.W., 1964, Scheduling of vehicles from a central depot to a number of delivery points, Operation Research, 12, 568-581.(Fish and Jaikumar 1981) Fish, M.L., and Jaikumar, R., 1981, A generalized assignment heuristic for vehicle routing, Operational Research Quarterly, 27, 367-384.(Garey and Johnson 1979) Garey M.R., and Johnson, D.S., 1979, Computers and Intractability: A Guide to the Theory of NP-Completeness, Freeman, San Francisco.(Gillett and Miller 1974) Gillett, B., and Miller, L., 1974, A heuristic algorithm for the vehicle dispatch problem, Operation Research, 22, 340-349.(Glover 1989)F. Glover, 1989, Tabu search part I, ORSA Journal on Computing, 1, 190-206.(Glover 1990)F. Glover, 1990, Tabu search part II, ORSA Journal on Computing, 2, 4-32.(Golden and Bodin 1983) Golden, B.L., L. Bodin, A. Assad, and M. Ball, 1983, Routing and scheduling of vehicle and crew: the state of art, Special Issue of Computers & Operations Research, 10, No. 2, 63-211.(Ichoua, et. al. 2000) Ichoua S., Gendreau M., Potvin J-Y., 2000, Diversion issues in Real-Time vehicle dispatching, Transportation Science, 34, No. 4, 426-438.(Laporte 1992a) Laporte, G., 1992, The Traveling Salesman Problem: An overview of exact and approximate algorithms, European Journal of Operational Research, 59, 345-358.(Laporte 1992b) Laporte, G., 1992, The Vehicle Routing Problem: An overview of exact and approximate algorithms, European Journal of Operational Research, 59, No. 2, 231-248.(Potvin, et. al. 1996) Potvin J-Y., Kervahut, T., Garcia, B.L., and Rousseau, J.M., 1996, The vehicle routing problem with time windows, part I: tabu search, INFORMS Journal on Computing, 8, No. 2, 158-164.(POTVIN, et al., 1996) Potvin, J-Y., Duhamel, C., and Guertin, F., 1996, A genetic algorithm for vehicle routing with backhauling, Applied Intelligence, 6, pp.345-355.(Powell 1988) Powell W., 1988, A comparative review of alternative algorithms for the dynamic vehicle allocation problem with uncertain demands, Vehicle Routing: Methods and Studies, pp. 249-292. (Powell, et al. 1995) Powell W. B., Jaillet P., Odoni A., 1995, Stochastic and Dynamic Networks and Routing, Handbooks in Operations Research and Management Science, vol. 8, pp. 141-295.(Psaraftis 1988) Psaraftis, H. N., 1988, Dynamic vehicle routing problems, Vehicle Routing: Methods and Studies, Elsevier Science Publishers, North-Holland, pp. 223-248.(Psaraftis 1995) Psaraftis, H. N., 1995, Dynamic vehicle routing - status and prospects, Annals of Operations Research, 61, 143-164.(Rumbaugh 1996)James Rumbaugh, 1996, OMT Insight, New York: SIGS Books.(Savelsbergh and Sol 1998) Savelsbergh, M. and Sol, M., 1998, Drive: dynamic routing of independent vehicles, Operations Research, 46, No. 4, 474-490.(Seguin, et al. 1997)Seguin R., Potvin J-Y, Gendreau M., Crainic T. G., Marcotte P., 1997, Real-time decision problems: an operational research perspective, Journal of the operational Research Society, 48, 162-174.(Shen and Potvin 1995) Shen Y., Potvin J-Y., 1995, A computer assistant for vehicle dispatching with learning capabilities, Annals of Operations Research, 61, 189-211. (Solomon, et. al. 1988) Solomon, M. M., Baker, E. K., Schaffer, J. R., 1988, Vehicle routing and scheduling problems with time window constraints: efficient implementations of solution improvement procedures, In Golden B.L. and Assad, A.A., Eds, Vehicle Routing: Methods and Studies, Elsevier Science Publishers, Amsterdam, pp.85-105. (Van Breedam 1994) Van breedam, A., 1994, An analysis of the behavior of heuristics for the vehicle routing problem for a selection of problems with vehicle-related, customer-related, and time-related constraints, Ph.D. dissertation, University of Antwerp.
QRCODE
 
 
 
 
 
                                                                                                                                                                                                                                                                                                                                                                                                               
第一頁 上一頁 下一頁 最後一頁 top
系統版面圖檔 系統版面圖檔