跳到主要內容

臺灣博碩士論文加值系統

(44.200.194.255) 您好!臺灣時間:2024/07/23 14:03
字體大小: 字級放大   字級縮小   預設字形  
回查詢結果 :::

詳目顯示

我願授權國圖
: 
twitterline
研究生:涂慧敏
研究生(外文):Huei-Min Tu
論文名稱:週期性車輛排程問題之研究
論文名稱(外文):Investigations for Period Vehicle Routing Problem
指導教授:邱素文邱素文引用關係
指導教授(外文):Suh-Wen Chiou
學位類別:碩士
校院名稱:大同大學
系所名稱:資訊經營研究所
學門:商業及管理學門
學類:一般商業學類
論文種類:學術論文
論文出版年:2004
畢業學年度:92
語文別:英文
論文頁數:130
中文關鍵詞:車輛排程問題週期性車輛排程問題節省法掃瞄法One-Point Movement2-optimal heuristic
外文關鍵詞:Vehicle Routing Problem (VRP)Period Vehicle Routing Problem (PVRP)Savings algorithmSweep algorithmOne-Point Movement2-optimal heuristic
相關次數:
  • 被引用被引用:0
  • 點閱點閱:135
  • 評分評分:
  • 下載下載:0
  • 收藏至我的研究室書目清單書目收藏:1
週期性車輛排程問題是一個為服務所有的顧客而設計車輛路徑的分配問題,並且指定的日期須在一個短的設定區間內,稱為週期。此目的是希望能將此週期間的配送成本最小化。因此如何能以非常短的時間求解出一個可接受的解則是一個非常重要的課題。
在第一階段,我們研究一個方法來為每位顧客選擇配送日期的組合。首先,我們先排列所有顧客之順序,接著我們按照此順序來指派顧客之服務組合。根據週期性車輛排程問題的目標,我們使用了旅行推銷員問題中的最近插入法來計算所指派顧客之成本,然後選擇增加最少的成本並可行的運送組合。在第二階段,針對每日車輛路徑問題,我們使用Sequential Savings和Modified Sweep演算法產生每日的初始車輛路徑,並且使用2-optimal方法來改善每日的路徑。
為了測試及驗證我們在所提出的方法,另外,我們在第一階段也使用 “Lindo What’s Best” 來求解Chao et al. (1995) 所提出的整數規劃法求出顧客配送日期的組合,在第二階段使用Sequential Savings和Modified Sweep演算法求解每日的初始車輛路徑,並以Chao et al. (1995) 所提出one-point movement方法及2-optimal來改善每日的初始路徑。我們測試了5題國際標竿題庫和2題隨機產生的例題,根據實驗的結果,我們可以發現我們所提出的方法是較佳並可行的,且都可在4秒內求算出可行解。我們也和Christofides and Beasley (1984), Tan and Beasley (1984), and Rusell and Gribbin (1991),比較5題國際標竿題庫的配送成本,平均誤差分別為10%、5%c 和 13%;而和目前已知的最佳解比較,平均誤差則為16%。
The Period Vehicle Routing Problem (PVRP) is a distribution problem about designing vehicle routes to serve those customers, which are assigned to that day over a short planning period. The objective is to minimize the cost of distribution over the period. How to determine the acceptable solutions in very short time is an important issue.
In the first phase we investigated one method to determine a choice of delivery day combinations for customers. First, we formed the ordering of the customers, and then we assigned each customer along the order. According to the objective of PVRP, we used Nearest Insertion of Traveling Salesman Problem (TSP) to evaluate the cost of assigning the customer, and chose the least increase cost and feasible delivery day combination. In the second phase, we adopted Savings and Modified Sweep for the daily vehicle routing problem (VRP), and then used 2-optimal approach to improve the daily routes. In order to test and verify the method we proposed in the first phase, we employed an integer program in Chao et al. (1995) for determining customer delivery day combinations; in the second phase, solved the daily VRP using Savings and Modified Sweep and the daily routes were improved by modified one-point movement plus 2-optimal interchange. And we used these two different methods in the first phase, and used the same method in the second phase to test five benchmarks and two randomly generated instances. According to the experimental results, we can find the method in the first phase we proposed is the better and feasible, and the computation time is all within 4 seconds. We also compared the delivery cost of the five benchmarks with Christofides and Beasley (1984), Tan and Beasley (1984), Rusell and Gribbin (1991), and the best-known solutions, and found the average deviations are respectively about 10%, 5%, 13% and 16%.
CHINESE ABSTRACT……………………………………….……………… i
ENGLISH ABSTRACT……………………………………….……………… ii
ACKNOWLEDGEMENT……………………………………………………. iii
TABLE OF CONTENTS….……………………………...……….………….. iv
TABLE OF CONTENTS………………………………………….………….. v
TABLE OF CONTENTS………………………………………….………….. vi
LIST OF FIGURES……………………………………………….………….. vii
LIST OF TABLES………………………………………………….………… viii
CHAPTER
1 Introduction……..……………………………………..……………… 1
1.1 Background……………………………..………………..………… 1
1.2 Objective……………………………………………....……...……. 2
1.3 Structure of the thesis.……………………………….……….…….. 2
2 Literature review……….……………………………..……….……… 4
2.1 Traveling Salesman Problem (TSP)….....…….……………………. 4
2.1.1 The Nearest Neighbor Algorithm…..…………..……………... 4
2.1.2 The Nearest Insertion Algorithm…..….………..……………... 5
2.1.3 γ-optimal (γ-opt) Tour Algorithm…….……………………….. 5
2.2 Vehicle Routing Problem (VRP)…….…..…….…...………………. 8
2.2.1 Sequential Savings Algorithm...…….…..…………………….. 8
2.2.2 Sweep Algorithm………………...……..……………………... 9
2.2.3 VRP Formulation……………...……..………………………... 11
2.3 Period Vehicle Routing Problem (PVRP)…….…..…….…...…….… 13
2.3.1 List of Notation……………...……..……………………….…. 13
2.3.2 Integer Programming Model of PVRP.………………………... 14
2.3.3 PVRP Heuristics………………………………………………. 15
3 Period Vehicle Routing Problem Formulation……………………… 25
3.1 A simple heuristic to solve the PVRP…..…...….………………….. 26
3.1.1 In the First Phase……...….….………………………………… 26
3.1.2 In the Second Phase..…...….….……………………………….. 27
3.1.2.1 Sequential Savings Method……………………………….. 28
3.1.2.2 Modified Sweep Method………………………………….. 28
3.1.2.3 2-optimal (2-opt) Method…………………………………. 31
3.2 A Modified heuristic from Chao et al. (1995) for PVRP…………... 31
3.3 The Differences of Object Function in the First Phase…………….. 32
4 Numerical experiments and Comparisons………………………….. 38
4.1 Verification Tests for Sequential Savings heuristic.....…………….. 38
4.1.1 Experimental results of Sequential Savings Method……...….. 38
4.1.2 Experimental results of Sequential Savings and Modified Sweep Method………………………………………………… 39
4.2 Experiment Results and Comparisons for PVRP.....……………….. 44
4.2.1 Comparison between Nearest Insertion of TSP and Integer Program in Chao et al. (1995) in the first phase……………… 46
4.2.2 Comparison between TSP_Sweep+2-optimal and the Modified Chao et al. Heuristic..…………………………………………. 55
4.3 Comparison results with the literature..….………………………… 60
4.4 Summary……………………...……………………………………. 64
5 Conclusions and Future Works……………………………………… 66
5.1 Conclusions……………………………………………………........ 66
5.2 Future works………………………………………….………......... 66
REFERENCES……………………………………………….……………… 68
APPENDIX I Information of the Results………….……………….…..…..
72
APPENDIX II Information of the New Instances....……………….…..…..
122
English
1. Anily, S., A Federgruen (1993), “Two-Echelon Systems with Vehicle Routing Costs and Central Inventory”, Operations Research 41, pp.37-47.
2. Bard, J. F., L. Huang, P. Jaillet, and M. Dror (1998), “A Decomposition Approach to the Inventory Routing Problem with Satellite Facilities”, Transportation Science 32, pp.189-203.
3. Bellmore, M. and G. L. Nemhauser (1968), “The Traveling-Salesman Problem: A Survey”, Operations Research 16, pp.538-558.
4. Chao. I., B. L. Golden and E. Wasil (1995), “An improved Heuristic for the Period Vehicle Routing Problem”, Networks 26, pp.25-44.
5. Christofides, N. and J. E. Beasley (1984), “The Period Routing”, Networks 14, pp.237-256.
6. Christofieds, N. and S. Eilon (1969), “An Algorithm for the Vehicle Dispatching Problem”, Operational Research. Quarterly. 11, pp.568-581.
7. Christofides, N., A. Mingozzi , and P. Toth (1979), “The Vehicle Routing problem”, in: N. Christofides et al.(eds), Combinatorial Optimization, Chichester-New York-Brisbane-Toronto, Wiley, pp. 315-338.
8. Clarke, G. and J. W. Wright (1964), “Scheduling of Vehicles from a Central Depot to a Number of Delivery Points”, Operations Research 12, pp.568-581.
9. Cordeau, J., M. Gendreau, and G. Laporte (1997), “A Tabu Search Heuristic for Periodic and Multi-Depot Vehicle Routing Problem”, Networks 30, pp.105-119.
10. Desrochers, M,, and T. W. Verhoog (1991), “A New Heuristic for the Fleet Size and Mix Vehicle Routing Problem, Computers and Operations Research 18, pp.263-274.
11. Dror, M., M. Ball, and B. Golden (1986), “A Computational Comparison of Algorithms for the Inventory Routing Problem”, Annals of Operations Research 4, pp.3-23.
12. Dror, M. and L. Levy (1986), “A Vehicle Routing Improvement Algorithm Comparison of a ‘Greedy’ and a Matching Implementation for Inventory Routing”, Computation and Operations Research 13, pp.33-45.
13. Dror, M. and M. Ball (1987), “Inventory/Routing: Reduction from an Annual to a Short-Period Problem”, Naval Research. Logistics 34, pp.891-905.
14. Dueck, G. (1993), “New Optimization Heuristics, the Great Deluge Algorithm and the Record-to-Record Travel”, Journal of Computational Physics 44, pp.86-92.
15. Eilon, S. and N. Christofides (1971), “The Loading Problem”, Management Science 17, pp.259-268.
16. Fisher, M. L. and R. Jaikumar (1981), “A Generalized Assignment Heuristic for Vehicle Routing”, Networks 11, pp.109-124.
17. Gaudioso, M. and G. Paletta (1992), “A Heuristic for the Period Vehicle Routing Problem”, Transportation Science 26, pp.86-92.
18. Gendreau, M. G. Laporte, C. Musaraganyi and E. Taillard (1999), “A Tabu Search Heuristic for the Heterogeneous Fleet Vehicle Routing Problem”, Computers and Operations Research 26, pp.1153-1173.
19. Gaskell, T. J. (1967), “Bases for Vehicle Fleet Scheduling”, Opnal. Res. Quart. 18, pp.281-295.
20. Gillett, B. and L. Miller (1974), “A Heuristic Algorithm for the Vehicle Dispatch Problem”, Operations Research 22, pp.340-349.
21. Golden, B.L., A. Assad, L. Levy and F.G. Gheysens (1984), “The Fleet Size and Mix Vehicle Routing Problem”, Computers and Operations Research 11, pp.49-66.
22. Golden, B.L., T. L. Magnanti, and H. Q. Nguyen (1977), Implementing Vehicle routing algorithm, Networks 7, pp.113-148.
23. Lin, S. and B. W. Kernighan (1973), “An Effective Heuristic Algorithm for the Traveling-Salesman Problem”, Operations Research 21, pp.498-516.
24. Liu, F., and S. Shen (1999), “The Fleet Size and Mix Vehicle Routing Problem with Time Windows”, Journal of Operational Research Society 50, pp.721-732.
25. Osman, I. and S. Salhi (1996), “Local Search Strategies for Vehicle Fleet Mix Problem”, in V. Rayward-Smith, I. Osman, C. Reeves and G. Smith (eds.), Modern Heuristic Search Methods. John Wiley and Sons, New York, pp.131-153.
26. Paessens, H. (1988), “The Savings Algorithm for the Vehicle Routing Problem”, Operations Research 34, pp.336-344.
27. Russell, R. (1977), “An Effective Heuristics for M-Tour Traveling Salesman Problem with Some Side Conditions”, Operations Research 21, pp.517-524.
28. Russell, R. and W. Igo (1979), “An Assignment Routing Problem”, Networks 9, pp.1-17.
29. Russell, A and D. Gribbin (1991), “A multiphase Approach to the Period Routing Problem”, Network 21, pp.747-765.
30. Salhi, S., G. K. Rand (1993), “Incorporating Vehicle Routing into the Vehicle Fleet Composition Problem”, European Journal of Operational Research 66, pp.313-330.
31. Simchi-Levi, Kaminsky, and Siminsky-Levi (2000), Designing and Management the Supply Chain Concepts, Strategies, and Case Studies, New york: McGraw-Hill, pp.1-13.
32. Tan, C. C. N. and J. E. Beasley (1984), “A Heuristic Algorithm for the Period Vehicle Routing Problem”, OMEGA 12, pp.497-504.
Chinese
1. Liu, Ming-Yun (1993/06), “Heuristic Methods and Applications of Period Vehicle Routing”, Master Thesis, Institute of Civil Engineering, National Chiao Tung University.
2. Cho, Yuh-Jen. (2001/07), “A New Metaheuristic Approach for HVRP and PVRP”, Doctoral Thesis, Institute of Transportation Engineering and Management College Management, National Chiao Tung University.
QRCODE
 
 
 
 
 
                                                                                                                                                                                                                                                                                                                                                                                                               
第一頁 上一頁 下一頁 最後一頁 top