(3.227.208.0) 您好!臺灣時間:2021/04/21 02:09
字體大小: 字級放大   字級縮小   預設字形  
回查詢結果

詳目顯示:::

我願授權國圖
: 
twitterline
研究生:朱文正
研究生(外文):Wen-Cheng Chu
論文名稱:考量旅行時間可靠度之車輛途程問題─螞蟻族群演算法之應用
論文名稱(外文):Vehicle Routing Problem with Travel Time Reliability─Application of Ant Colony System
指導教授:馮正民馮正民引用關係邱裕鈞邱裕鈞引用關係
指導教授(外文):Cheng-Min FengYu-Chiun Chio
學位類別:碩士
校院名稱:國立交通大學
系所名稱:交通運輸研究所
學門:運輸服務學門
學類:運輸管理學類
論文種類:學術論文
論文出版年:2003
畢業學年度:91
語文別:中文
論文頁數:112
中文關鍵詞:時窗可靠度車輛途程問題螞蟻族群演算法
外文關鍵詞:Time-Windows ReliabilityVehicle Routing ProblemAnt Colony System
相關次數:
  • 被引用被引用:27
  • 點閱點閱:472
  • 評分評分:系統版面圖檔系統版面圖檔系統版面圖檔系統版面圖檔系統版面圖檔
  • 下載下載:125
  • 收藏至我的研究室書目清單書目收藏:0
由於路網往往受到交通阻塞、違規停車或意外事故等因素影響,因此旅行時間並非是恆定不變的,故有學者開始研究考量隨機旅行時間之車輛途程問題。然而,考量隨機旅行時間車輛途程模式只能得到單一最佳路徑,無法有效反應規劃者需求,故本研究乃導入可靠度工程理論觀念,將路段旅行時間之不確定性轉換為「時窗可靠度」的概念,再結合傳統車輛途程模式,構建一「模糊多目標的車輛途程可靠度模式」,求解總旅行成本最小及總服務失敗機率最小(可靠度最大)之最佳路徑。鑑於螞蟻族群演算法(Ant Colony System)在VRP 相關問題求解績效已獲得驗證,故本研究亦採用此演算法求解本研究模式。
本研究乃以小規模路網與大規模路網測試本研究模式:小規模路網乃是由10 個節點所組成,當同時以本研究模式與軟時窗之車輛途程模式求解小規模路網,發現本模式所求得的路徑,其服務失敗機率為5.8%,而軟時窗模式之服務失敗機率則為0.33%,表示本模式結果能提供較可靠之指派路徑。同時由敏感度分析可知,(1)當要求之時窗可靠度水準增加,指派路徑會改變以提供更好的服務,而總旅行成本會隨之增加;(2)當個別顧客之時窗可靠度水準提高時,指派路徑會改變以提高其時窗可靠度;(3)當路段之旅行時間標準差變大時,會導至原路徑的旅行成本提高而使得指派路徑發生改變,以尋求準確性更高的路段。大規模路網乃是採用Solomon 所提出的R111 標竿範例,研究發現本研究模式可依不同之時窗可靠度水準,提供其最佳之路徑。
Since the traffic conditions are affected by many factors such as congestion, illegal parking and incidents, travel time on urban network is often uncertain. The uncertainty of travel time begins to be taken into consideration by some researches on vehicle routing problems. That’s so called stochastic vehicle routing problems (SVRP). However, SVRP could only provide an optimal route without further considering the different degree of punctuality required by different customers. Based on the theory of reliability engineering,
this research proposes a vehicle routing model with time - window reliability (RTW- VRP) to find an optimal route which has the minimum travel cost and the minimum service
failure (i.e. the maximum reliability). Besides, due to the proven excellent performance of Ant Colony System (ACS) in solving vehicle routing problems, this study employs ACS
algorithm to solve RTW- VRP.
Two examples, one small- scale network with 10 nodes and another large-scale network with 100 nodes (the Solomon’s R111 example), are experimented to validate the RTW- VRP model. The results of small-scale network show that the probabilit ies of service failure for the proposed RTW- VRP model and VRP model with soft time window (STW- VRP) are 5.8% and 30.33%, respectively. It implies that RTW- VRP model can
provide a more reliable route. The results of sensitivity analysis also indicate that the model will provide an optimal route with better service reliability as the required
reliability level getting stricter and an optimal route with more stable travel time as variance of travel time enlarging. The results of large-scale network also demonstrate that
the RTW- VRP model can provide appropriate routes for different required reliability level.
目錄
中 文 摘 要………………………………………………………….….i
英 文 摘 要…………………………………………………………….ii
誌謝 ................................................... iii
目錄 .................................................... iv
表 目 錄................................................. vi
圖 目 錄................................................ vii
一、緒論........ 1
1.1 研究背景與動機.........................................1
1.2 研究目的.............................................. 2
1.3 研究方法與範圍........................................ 3
1.4 研究內容與流程........................................ 5
二、文獻回顧........................................................ 8
2.1 車輛途程問題及相關問題................................ 8
2.2 路網可靠度(Reliability of Network) .................. 17
2.4 多目標規劃法......................................... 21
2.4 車輛途程問題之演算法................................. 26
三、考量旅行時間可靠度之車輛途程模式..................... 30
3.1 研究課題分析....................................................... 30
3.2 模式建立之概念分析................................... 32
3.3 可靠度工程理論....................................................... 34
3.4 旅行時間可靠度指標....................................................... 36
3.5 模式構建............................................. 42
3.6 小結................................................. 53
四、螞蟻族群演算法....................................... 54
4.1 螞蟻族群演算法(Ant Colony System ;ACS) ..............54
4.2 ACS 之應用─求解多目標問題........................... 66
4.3 螞蟻族群演算法之應用─求解研究模式................... 70
五、範例測試與敏感度分析................................. 76
5.1 小規模路網........................................... 76
5.2 大規模路網........................................... 93
六、結論與建議........................................... 96
6.1 結論................................................. 96
6.2 建議................................................. 97
參考文獻................................................. 98
簡 歷....................................................102
參考文獻
英文部分:
1. Ahn B.H. and Shin J.Y., “Vehicle —routing with Time Windows and Time Varying Congestion”, Journal of Operation Research Society, 42, 5, pp. 393-400, 1991.
2. Alfa A. S., “A heuristic algorithm for the traveling salesman problem with time-varying travel costs”, Engmg Optim. 12, pp.391-402, 1987.
3. Asakura Y., “Evaluation of network reliability using stochastic user equilibrium”, Journal of Advanced Transportation, 33, 2, pp.147-158, 1999.
4. Bell M.G.H. and Cassir C., Reliability of Transport Networks, Research Studies Press Ltd, 2000.
5. Bell M.G.H. and Iida, Y., Transportation Network Analysis, Wiley, New York, 1997.
6. Changchien S.W., Wu C.S. ,“An Ant Colony System for Vehicle Routing Problems with Time Window”, The Seven Conference on Artificial
Intelligence and Application, 2002.
7. Chen A. et al. “Capacity reliability of a road network: an assessment
methodology and numerical results”, Transportation Research 36B, pp. 225-252, 2002.
8. Corne D., Dorigo M., Glover F., A New Ideas on Optimization, McGRAW-Hill, 1999.
9. Crainic T.G., Laporte G, Fleet Management and Logistics, Kluwer Academic Publishers, 1998.
10. Dantzig G.B., Ramser J.H., “The truck dispatching problem.” Magament. Science. 6, pp.80-91, 1959.
11. Dorigo M, Gambardella L.M., “Ant Colony System: A Cooperative Learning Approach to the Traveling Salesman Problem”, IEEE Transactions in Evolutionary Computation, 1, 1, pp.53-66, 1997.
12. Dorigo M., Maniezzo V., Colorni A., “Ant System: Optimization by a Colony of Cooperating Agents”, IEEE Transactions on Systems, Man, and
Cybernetics-part B: Cybernetics, 26, 1, pp.29-41, 1996.
13. Eiichi T., Thompson R.G., Tadashi Y. and Ron V.D.. City Logistics :Network Modelling and Intelligent Transport Systems, Elsevier Science Ltd, 2001.
14. Fu L., “Scheduling dial-a-ride paratransit under time-varying, stochastic congestion”, Transportation Research 36B, pp.485-506, 2002.
15. Fu L., Rilett L.R., “Expected Shortest Paths in Dynamic and Stochastic Traffic Networks”, Transportation Research 32B, pp.499-516, 1998.
16. Fuessle R., Bill D. and Liebman J., “Air quality planning: a general chance- constrained model.”, Journal of Environmental Engineering, 113, 1, pp. 106-123, 1987.
17. Gendreau M., Laporte G. and Seguin R.,“Invited Review :Stochastic vehicle routing”, European Journal of Operational Research 88, pp.3-12, 1996.
18. Golden B.L., Assad A.A., Vehicle Routing: Methods and Studies, North-Holland, 1988.
19. Guldmann, J.M., “Supply, storage, and service reliability decisions by gas distribution utilities: a chance-constrained approach.”, Management Science, 29, 8, pp.884-906, 1983.
20. Iida Y., “Basic concepts and future directions of road network reliability analysis”, Journal of Advanced Transportation, 33, 2, pp.125-134, 1999.
21. Jacobs T., Medina M., Ho J., “Chance constrained model for storm-watersystem design and rehabilitation.” Journal of Water Resources Planning and Management, 123, 3, pp.163-168, 1997.
22. Kohler, U., “An innovating concept for city —logistics.”, 4 th World Congress on Intelligent Transport Systems, Berlin, Germany, CD-ROM, 1997.
23. Lam W.H.K., Xu G., “A Traffic Flow Simulator For Network Reliability Assessment”, Journal of Advanced Transportation, 33, 2, pp.159-182, 1999.
24. Lo H.K., Tung Y.K., “Network with degradable links: capacity analysis and design”, Transportation Research 37B, pp.345-363, 2003.
25. Michael P. and Labbe M., Transportation Planning: state of art, Kluwer Academic Publishers, 2002.
26. Taniguchi, E., Thompson R,G., and Yamada, T, “Vehicle routing and scheduling using ITS”, 5 th World Congress on Intelligent Transport Systems, Seoul, CD-ROM, 1998.
27. Taylor M.A.P., “Dense Network Traffic Time Reliability and Traffic Management. I: General Introduction.”, Journal of Advanced Transportation, 33, 2, pp.147-158, 1999.
28. Taylor M.A.P., “Dense Network Traffic Time Reliability and Traffic Management ? : Application to Network Reliability”, Journal of Advanced Transportation, 33, 2, pp.147-158, 1999.
中文部分:
1. Elmer E. Lewis 著,可靠度工程導論,趙浡霖譯,科技圖書股份有限公司,民國
七十八年七月。
2. 張明坤,「可靠度理論與其在捷運系統應用上之實務探討」,捷運技術半年刊,
第十六期,85~95 頁,民國八十五年。
3. 陳順宇、鄭碧娥,統計學,華泰,民國八十七年。
4. 鐘譽偉,「旅行時間可靠度之研究」,國立台灣大學,博士論文,民國88 年6 月。
5. 黃木才,「貨櫃運輸公司VRP 之研究─模糊多目標遺傳演算法之應用」,國立交通大學,碩士論文,民國85 年6 月
6. 張耀明,「台灣城際旅行時間可靠度之分析與量測方法」,國立交通大學,碩士論文,民國88 年6 月。
7. 廖田華,「需求不確定下物流中心車輛路線問題之研究」,國防管理學院,碩士論文,民國89 年6 月。
8. 洪瑜敏,「供應鏈之多目標產銷模式:以自行車製造廠商為例」,國立交通大學,碩士論文,民國90 年6 月。
9. 江文聲,「動態隨機時間相依路網可靠路徑選擇」,國立台灣大學,碩士論文,民國90 年6 月。
10. 呂英志,「即時資訊下車輛問題之研究」,私立逢甲大學,碩士論文,民國91 年6 月。
11. 藍坤銘,「資料挖掘之順序樣式法於螞蟻理論之改善」,國立台北科技大學,碩士論文,民國91 年6 月。
12. 侯政傑,「都會區警察派出所區位設置之研究─模糊多目標組合最佳化之應用」,國立交通大學,碩士論文,民國91 年6 月。
13. 張閔嵐,「模糊多階層多目標供應鏈規劃─以紡織業為例」,國立交通大學,碩士論文,民國91 年6 月。
14. 吳旻樵,「新VRP 啟發式解法之開發」,國立交通大學,碩士論文,民國91 年6月。
QRCODE
 
 
 
 
 
                                                                                                                                                                                                                                                                                                                                                                                                               
第一頁 上一頁 下一頁 最後一頁 top
1. 6.余宜芳,1998年8月,「在家工作薪水照領-HP實驗在職SOHO制度」,SOHO甦活雜誌,14期,pp.72~77。
2. 8.李健成,1998年12月,「隨身帶著走 行動辦公室」,電腦世界,122期,特刊pp.2~4。
3. 9.李俍德,2001年7月,「虛擬辦公室挑戰企業文化」,管理雜誌,325期,pp.116~118。
4. 12.李靜芳,2002年7月,「企業行動化應用案例介紹」,通訊雜誌,pp.32~35。
5. 13.呂玉娟,2001年4月,「中國生產力中心--速度、彈性:行動辦公室的先驅」,能力雜誌,pp.34~39。
6. 14.何琦瑜,2000年10月,「下世紀電子商務入口之爭-M-Commerce對決e-Commerce」,數位時代,第16號,pp.112~116。
7. 15.何琦瑜,2000年10月,「奇錸科技-企業M化整合套餐」,數位時代,第16號,pp.68。
8. 19.林能白、丘宏昌(民88),「服務品質之研究-服務人員人格特質之影響分析與應用」,管理學報,第16 卷第2 期,pp.175-200。
9. 23.張續京,2002年11月,「以行動化打造企業優勢競爭力」,通訊雜誌,pp.28~30。
10. 26.張寶誠,2001年3月,「CPC的策略新藍圖」,能力雜誌,541期,pp.64~65。
11. 29.陳惠君,2002年11月,「企業導入M化提昇經營績效」,通訊雜誌,pp.31~33。
12. 31.萬以寧、陳生民,1996年11月,「CPC組織變革的策略-移動辦公室的真正面貌與理念」,戰略生產力雜誌,pp.17~22。
13. 33.鈕因任,2002年11月,「新世代企業行動辦公室面面觀」,通訊雜誌,pp.24~27。
14. 35.黃曼琴(民80),應用中介模式探討Type A/B 人格特質為中介變項對工作力與工作滿足、工作績效之影響,人力資源學報,第一期,pp.59~74。
15. 39.劉芳梅,2002年7月,「企業行動化服務業的機會與挑戰」,通訊雜誌,pp.46~48。
 
系統版面圖檔 系統版面圖檔