跳到主要內容

臺灣博碩士論文加值系統

(44.210.83.132) 您好!臺灣時間:2024/05/25 04:18
字體大小: 字級放大   字級縮小   預設字形  
回查詢結果 :::

詳目顯示

: 
twitterline
研究生:連毅諺
研究生(外文):Yi-Yan,Lian
論文名稱:應用兩階段演算法求解具模糊時窗限制多場站車輛途程問題
論文名稱(外文):Application of A Two-phase Algorithm for The Multi-Depot Vehicle Routing Problem with Fuzzy Time Windows
指導教授:尤昌筧
指導教授(外文):Chang-Chien,Yu
口試委員:尤昌筧沈群英楊哲奇
口試委員(外文):Chang-Chien,YuChun-Ying,ShenChe-Chi,Yang
口試日期:2013-07-12
學位類別:碩士
校院名稱:龍華科技大學
系所名稱:資訊管理系碩士班
學門:電算機學門
學類:電算機一般學類
論文種類:學術論文
論文出版年:2013
畢業學年度:101
語文別:中文
論文頁數:63
中文關鍵詞:模擬退火法車輛途程問題模糊時間窗服務水準
外文關鍵詞:Simulated AnnealingVehicle Routing ProblemFuzzy Time WindowService Level
相關次數:
  • 被引用被引用:1
  • 點閱點閱:345
  • 評分評分:
  • 下載下載:91
  • 收藏至我的研究室書目清單書目收藏:0
本研究針對具模糊時窗限制多場站車輛途程問題(Multi-Depot Vehicle Routing Problem with Fuzzy Time Window, MD-VRPFTW)進行研究。現實生活中的每個人對於時間早晚的認知而會有不同的感受,時間認知具有一定的模糊性,故將客戶時間窗模糊化,利用服務水準(Service Level)作為隸屬函數(Membership Function)的值,依照車輛到達時間的不同而會有不同的服務水準,再利用服務水準得出客戶新的時間窗範圍,可以在規劃路線時能夠更有彈性。本研究求解過程分成兩個階段演算法,第一階段使用傳統啟發式演算法中的插入法求得起始解,第二階段使用巨集啟發式演算法(Meta-Heuristics)中的模擬退火法來改善起始解,其中結合了傳統啟發式演算法中的插入法以及λ-interchange 1-1交換法,利用隨機交換以及插入的方式找出全域最佳解。研究中使用Cordeau (2001)標準時間窗多場站車輛途程問題(Multi-Depot Vehicle Routing Problem with Time Window, MD-VRPTW)例題進行測試,結果顯示利用模糊時窗的方式能夠有效降低成本,在樣本數越大的例題效果越佳,而且能維持在一定服務水準之上,因此本研究結果更貼近現實生活。
This paper describes the problem of Multiple Depot Vehicle Routing Problem with Fuzzy Time Window (MD-VRPFTW). Based on the realities of life for everyone in a matter of time and have different feelings. Therefore, time has some fuzziness. Thus fuzzification the customer time windows, the use of service level as the value of membership function. Different arrival time according to vehicle have different service level. Using the service level can find a new time window range. When planning a route can be more flexible. Algorithms solving process is divided into two phases. The first stage in the use of traditional heuristic initial solution obtained by interpolation. The second phase uses meta-heuristic algorithm simulated annealing method to improve the initial solution, Combines traditional heuristic insertion method and λ-interchange 1-1 exchange. Using random exchange and insertion method to find the global optimum. In this study, using standard MD-VRPTW examples to be tested. The results showed that the use of fuzzy time windows can effectively reduce the cost and Larger the number of samples better the results. The results can maintain a certain service level. Therefore, results of this study closer to real life
摘要 i
ABSTRACT ii
誌謝 iii
目錄 iv
表目錄 vi
圖目錄 vii
第一章 緒論 1
1.1 研究背景與動機 1
1.2 研究目的 2
1.3 研究範圍 2
1.4 研究架構 3
第二章 文獻回顧 6
2.1 車輛途程問題 (Vehicle Routing Problem, VRP) 6
2.1.1 VRP時間窗限制問題 10
2.1.2 VRP求解方法 11
2.1.3巨集啟發式演算法(Meta-heuristic) 18
2.2 模糊理論 24
2.3 服務水準(Service Level) 26
2.4 文獻小結 27
第三章 研究方法 28
3.1 問題定義與假設 29
3.2 MD-VRPFTW數學模式 33
第四章 演算法流程 36
4.1 初始路線建構 36
4.2 模擬退火法改善 42
第五章 實驗結果 45
5.1 參數設定 45
5.2 MD-VRPTW例題說明 46
5.3 演算結果 47
第六章 結論 50
參考文獻 52
附錄 56

1.李國村,以蟻群演算法求解動態車輛途程規劃,碩士論文,朝陽科技大學工業工程與管理系,台中(2006)。
2.林韵函,以粒子群最佳化演算法求解具時間窗之開放式車輛途程問題,碩士論文,國立臺灣科技大學工業管理系,台北(2012)。
3.徐嘉吟、黃士滔,「應用改良的最大最小螞蟻系統於旅行推銷員問題」,工程科技與教育學刊,第六卷,第三期,第324~331頁(2009)。
4.張治魯,顧客服務水準控制與供應鏈管理應用於改善傳統產業營業獲利之研究,碩士論文,國立成功大學交通管理科學研究所,台南(2002)。
5.張哲旗,以混合啟發式演算法求解具模糊時窗限制車輛途程問題,碩士論文,龍華科技大學商學與管理研究所,桃園(2009)。
6.莊英群,應用禁忌搜尋法於混合送收貨之車輛途程問題,碩士論文,逢甲大學工業工程研究所,台中(2003)。
7.陳宏昇,以模擬退火法求解時窗限制車輛途程問題,碩士論文,華梵大學資訊管理研究所,台北(2006)。
8.陳建甫,以基因搜尋法求解多桶格車輛途程問題,碩士論文,南台科技大學工業管理研究所,台南(2006)。
9.黃仲正、劉永誠譯,物流管理,新北市:高立圖書有限公司,(2005)。
10.楊明仁、李秋緣、張力允、呂聰輝、林詩偉、李仁鐘,「模擬退火法結合禁忌搜尋演算法求解協同配送問題」,華岡工程學報,第29期,第121-129頁(2012)。
11.楊雅斐,使用改良式遺傳演算法求解車輛途程問題,碩士論文,立德管理學院應用資訊研究所,台南(2005)。
12.鄭惠華,以模擬退火法減少TFT-LCD產品陣列段製程之測試項目之研究,碩士論文,國立交通大學工業工程與管理學系,新竹(2012)。
13.謝昇甫,應用模糊理論求解動態途程規劃,碩士論文,朝陽科技大學工業工程與管理系,台中(2006)。
14.Bell, J. E. and McMullen, P. R. "Ant colony optimization techniques for the vehicle routing problem," Adv. Eng. Inform, 18, 1, 41-48(2004).
15.Boctor, F. F. "Some efficient multi-heurisitc procedures for resource-constrained project scheduling," European Journal of Operational Research, 49, 3-13(1990).
16.Bodin, L., Golden, B., Assad, A. and Ball, M. "Routing and scheduling of Vehicles and Crews," Computers and Operations Research, 29, 2, 63-211(1983).
17.Clarke, G. and Wright, J. W. "Scheduling of vehicles from a central depot to a number of delivery points," Operations Research, 12, 4, 568-581(1964).
18.Cordeau, J. F., Laporte, G. and Mercier, "A Unified Tabu Search Heuristic for Vehicle Routing Problems with Time Windows," The Journal of the Operational Research Society, 52, 8, 928-936(2001).
19.Cordeau, J. F., Gendreau, M. and Laporte, G. "A tabu search heuristic for periodic and multi-depot vehicle routing problems," Networks, 30, 2, 105-119(1997).
20.Crevier, B., Cordeau, J. F. and Laporte, G. "The multi-depot vehicle routing problem with inter-depot routes," European Journal of Operational Research, 176, 2, 756-773(2007).
21.Dantzig, G. B. and Ramser, J. H. "The Truck Dispatching Problem," Management Science, 6, 1, 80-91(1959).
22.Dorigo, M., Maniezzo, V. and Colorni, A. "Ant System: Optimization by a colony of cooperating agents," IEEE Transactions on Systems, 26, 1, 29-41(1996).
23.Eberhart, R. C. and Kennedy, J. "A new optimizer using particle swarm theory," IEEE Int. Symposium on Micro Machine and Human Science, Nagoya, 39-43(1995).
24.Fisher, M. L. and Jaikumar, R. "A Generalized Assignment Heuristic for Vehicle Routing Problems," Networks, 11, 2, 109-124(1981).
25.Flood, M. M. "The Traveling-Salesman Problem," operations Research, 4, 1, 61-75(1995).
26.Gendreau, M., Hertz, A. and Laporte, G. "A tabu search heuristic for the vehicle routing problem," Management Science, 40, 10, 1276-1290(1994).
27.Gillett, B. and Miller, L. "A heuristic algorithm for the vehicle dispatch problem," Operations Research, 22, 2, 340-349(1974).
28.Glover, F. "Tabu search-Part1,"ORSA Journal on Computing, 1, 3, 190-206(1989).
29.Holland, J. H., Adaptation in natural and artificial systems: An introductory analysis with applications to biology, control, and artificial intelligence, Oxford, England: U Michigan Press(1975).
30.Hong, L. and Xu, M. "A Model of MDVRPTW with Fuzzy Travel Time and Time-dependent and Its Solution,"Fifth International Conference on Fuzzy Systems and Knowledge Discovery, Shandong, 473-478(2008).
31.Tang, J., Pan, Z., Fung, R. Y. K. and Lau, H. "Vehicle routing problem with fuzzy time windows," Fuzzy Sets and Systems, 160, 5, 683-695(2009).
32.Kennedy, J. and Eberhart, R. C. "Particle swarm optimization," IEEE International Conference Neural Networks, 4, 1942-1948(1995).
33.Kirkpatrick, S., Gelatt, C. D. and Vecchi, M. P. "Optimization by simulated annealing," Science, 4956, 200, 671-680(1983).
34.Kuo, Y. and Wang, C. C. "A variable neighborhood search for the multi-depot vehicle routing problem with loading cost," Expert Systems with Applications, 39, 8, 6949-6954(2012).
35.Kuo, Y., Wang, C. C. and Chuang, P. Y. "Optimizing goods assignment and the vehicle routing problem with time-dependent travel speeds," Computers and Industrial Engineering, 57, 4, 1385-1392(2009).
36.Lau, H. C. W., Chan, T. M., Tsui, W. T. and Pang, W. K. "Application of Genetic Algorithms to Solve the Multidepot Vehicle Routing Problem," IEEE Transactions, 7, 2, 383-392(2010).
37.Lenstra, J. K. and Rinnooy Kan, A. H. G. "Complexity of Vehicle Routing and Scheduling Problems," Networks, 11, 2, 221-227(1981).
38.Lopez-Castro, L. F. and Montoya-Torres, J. R."Vehicle routing with fuzzy time windows using a genetic algorithm Computational Intelligence In Production And Logistics Systems (CIPLS)," IEEE Workshop, Paris, 1-8(2011).
39.Metropolis, N., Rosenbluth, A. W., Rosenbluth, M. N., Teller, A. H. and Teller, E. "Equations of state calculations by fast computing machines," Journal of Chemical Physics, 21, 6, 1087-1092 (1953).
40.Mole, R. H. and Jameson, S. R. "A sequential route-building algorithm employing a generalized savings criterion," Operational Research Quarterly, 27, 2, 503-511(1976).
41.Or, I., Traveling Salesman-type Combinatorial Problems and Their Relation to the Logistics of Regional Blood Banking, Ph. D. Dissertation, Dept. of Industrial Engineering and Management Sciences, University of Northwestern.(1976)
42.Osman, I. H. "Metastrategy Simulated Annealing and Tabu Search Algorithms for The Vehicle Routing Problem," Annals of Operations Research, 41, 4, 421-451(1993).
43.Sasser, W. E., Olsen, R. P. and Wyckoff, D. D., Management of Service Operations: Text: Cases and Readings, Boston: Allyn & Bacon, 734(1978).
44.Simchi, L. D., Kaminsky, P. and Simchi, L. E., Design and managing the supply chain:Concepts, strategies, and cases studies, McGraw: Hill, 354(2003).
45.Solomon, M. M., Vehicle Routing and Scheduling with Time Window Constraints:Models and Algorithms, Ph.D. Dissertation, Dept. of Decision Sciences, University of Pennsylvania, (1983).
46.Toth, P. and Vigo, D. "Models, relaxations and exact approaches for the capacitated vehicle routing problem," Discrete Applied Mathematics, 123, 1-3, 487-512 (2002).
47.Zadeh, L. A. "Fuzzy sets," Information Control, 8, 3, 338-353(1965).
48.Zarandi, M. H. F., Hemmati, A. and Davari, S. "The multi-depot capacitated location-routing problem with fuzzy travel times," Expert Systems with Application, 38, 8, 10075-10084(2011).

QRCODE
 
 
 
 
 
                                                                                                                                                                                                                                                                                                                                                                                                               
第一頁 上一頁 下一頁 最後一頁 top