簡易檢索 / 詳目顯示

回結果列表
研究生： 吳達彥
Ng, Tat-In
論文名稱： 應用人工免疫演算法求解集群路線車輛規劃問題－以機場接送服務為例
An Artificial Immune Algorithm for Vehicle Routing Problems with Clustered Backhauls in Airport Shuttle Service
指導教授： 胡大瀛
Hu, Ta-Yin
學位類別： 碩士
Master
系所名稱： 管理學院 - 交通管理科學系
Department of Transportation and Communication Management Science
論文出版年： 2014
畢業學年度： 102
語文別： 英文
論文頁數： 69
中文關鍵詞： 集群車輛路線規劃問題 、機場接駁服務 、人工免疫演算法 、DynaTAIWAN
外文關鍵詞： Vehicle Routing Problem with Clustered Backhauls (VRPCB), airport shuttle service, Artificial Immune Algorithm, DynaTAIWAN
相關次數： 點閱：105  下載：5 
分享至:
查詢本校圖書館目錄 查詢臺灣博碩士論文知識加值系統 勘誤回報

    • 近年來台灣航空航業快速成長，全國機場總旅客人數從2008年到2013年間上升了28%，並有持續上升趨勢。面對迅速增長的機場旅客，連接機場的陸路接駁服務越趨重要。而機場共乘接駁服務為其中一項接送機場旅客的運輸服務，因其能夠提供低廉價格，同時提供準時、方便和舒適等特性，已吸引大量機場旅客廣泛使用。對機場共乘接駁服務來說，良好的車隊路線規劃及排程能夠提升服務的效率和降低營運成本，故如何設計一個合適的車隊路線和排程計劃以達到運營最佳化是個相當關鍵的問題。
    本研究把機場接駁服務問題歸類為考慮時窗限制並集群收集的車輛路線規劃問題（Vehicle Routing Problems with Clustered Backhauls and Time Windows, VRP VRPCB-TW），並依其問題特性直接構建相關數學模式，目標是總營運成本最小化。本研究利用人工免疫演算法求解機場接駁服務問題，此演算法為一巨集啟發式演算法並對於求解VRP能得品質較佳的解和快速收歛。為測試演算法之效能，本研究結合DynaTAIWAN交通模擬指派模式在高雄市真實路網中進行求解實驗與分析。從數值實驗結果可得，較小的車容量、較長的時窗或較大的需求量都會導致總營運成本增加。

    According to the statistics of the Ministry of Transportation and Communications, the total number of airport passengers were 35 million persons and 45 million persons in 2008 and 2013, respectively, it increased by 28 % in the past five years. With the rapid growth of the airport passengers, airport rideshare shuttle service provided a punctual, convenient and comfortable airport shuttle service for airport passengers. Well-planned vehicle routing and scheduling for airport shuttle service can improve service efficiency and save total costs. How to design a suitable vehicle routing and schedule plan is an important issue for airport shuttle service problems.
    This study formulates a Vehicle Routing Problems with Clustered Backhauls and Time Windows (VRPCB-TW) Problem for airport shuttle service, toward the objective of minimizing the total cost, including fix start-up costs and operation cost. The artificial immune algorithm is designed to solve the VRPCB-TW under a given demand. DynaTAIWAN, the traffic simulation software is uesd to simulate traffic flows in the simplifed real network of Kaohsiung city and Kaohsiung International Airport. Three scenarios are developed to discuss the airport shuttle. The results illustrates that the smaller capacity of vehicles, the wider length of time windows or the bigger amount of demand occurs more total operational.

    ABSTRACT I ABSTRACT(CHINESE) II ACKNOWLEDGEMENTS(CHINESE) III TABLE OF CONTENTS IV LIST OF TABLES VII LIST OF FIGURES VIII CHAPTER 1 INTORDUCTION 1 1.1 Research Background and Motivation 1 1.2 Research Objectives 3 1.3 Research Flowchart 3 1.4 Overview 6 CHAPTER 2 LITERATURE REVIEW 7 2.1 General Pickup and Delivery Problems 7 2.2 Airport Shuttle Service 9 2.3 Solution Approaches for the VRPCB 11 2.3.1 Exact Algorithm 11 2.3.2 Heuristic Algorithm 12 2.3.3 Meta-heuristic 13 2.4 Artificial Immune System 15 2.5 Summary 18 CHAPTER 3 METHODOLOGY 20 3.1 Problem Statement 20 3.2 Mathematical Formulation 22 3.3 Solution Structure 27 3.4 Artificial Immune Algorithm 30 3.4.1 Antibody Encoding and Adaptive 30 3.4.2 Metabolism Operation of Antibody 31 3.4.3 Memory Cell Library 33 3.4.4 The Framework of Artificial Immune Algorithm 34 3.5 Summary 37 CHARTER 4 NUMERICAL ANALYSIS 38 4.1 The Implement Processes of the Algorithm 38 4.2 Testing Problem and Environment 41 4.3 Basic Experiment of the Mathematical Model 43 4.4 Basic Experiment of the Artificial Immune Algorithm 45 4.5 Analysis of the Basic Experiment Result 47 4.6 Sensitivity Analysis 48 4.6.1 Sensitivity Analysis of Mutation Rate 48 4.6.2 Sensitivity Analysis of Crossover Rate 50 4.6.3 Sensitivity Analysis of Removing Threshold 51 4.7 Summary 52 CHAPTER 5 EMPIRICAL EXPERIMENT 54 5.1 Illustration of the Experimental Network 54 5.2 Experiment Settings 56 5.3 Scenario 1 57 5.4 Scenario 2 58 5.5 Scenario 3 60 5.6 Experiments for 40 Nodes 62 5.7 Summary 62 CHAPTER 6 CONCLUSIONS AND SUGGESTIONS 64 6.1 Conclusions 64 6.2 Suggestions 65 REFERENCES 67

    1. Anily, S. (1996), "The vehicle-routing problem with delivery and back-haul options," Naval Research Logistics (NRL), Vol. 43, No. 3, pp. 415-434.
    2. Ben Abdelaziz, F., Masri, H., and Alaya, H., (2011) "A solution approach for the stochastic airport bus routing problem," In: Modeling, Simulation and Applied Optimization (ICMSAO), 2011 4th International Conference on, kuala lumpur, Malaysia.
    3. Brandão, J. (2006), "A new tabu search algorithm for the vehicle routing problem with backhauls," European Journal of Operational Research, Vol. 173, No. 2, pp. 540-555.
    4. D’Souza, C., Omkar, S.N., and Senthilnath, J. (2012), "Pickup and delivery problem using metaheuristics techniques," Expert Systems with Applications, Vol. 39, No. 1, pp. 328-334.
    5. de Castro, L.N. and Von Zuben, F.J. (2002), "Learning and optimization using the clonal selection principle," Evolutionary Computation, IEEE Transactions on, Vol. 6, No. 3, pp. 239-251.
    6. Dong, G., Tang, J., Lai, K.K., and Kong, Y. (2009), "An exact algorithm for vehicle routing and scheduling problem of free pickup and delivery service in flight ticket sales companies based on set-partitioning model," Journal of Intelligent Manufacturing, Vol. 22, No. 5, pp. 789-799.
    7. Engin, O. and Döyen, A. (2004), "A new approach to solve hybrid flow shop scheduling problems by artificial immune system," Future Generation Computer Systems, Vol. 20, No. 6, pp. 1083-1095.
    8. Farmer, J.D., Packard, N.H., and Perelson, A.S. (1986), "The immune system, adaptation, and machine learning," Physica D: Nonlinear Phenomena, Vol. 22, No. 1–3, pp. 187-204.
    9. Furuhata, M., Dessouky, M., Ordóñez, F., Brunet, M.-E., Wang, X., and Koenig, S. (2013), "Ridesharing: The state-of-the-art and future directions," Transportation Research Part B: Methodological, Vol. 57, No., pp. 28-46.
    10. Gélinas, S., Desrochers, M., Desrosiers, J., and Solomon, M. (1995), "A new branching strategy for time constrained routing problems with application to backhauling," Annals of Operations Research, Vol. 61, No. 1, pp. 91-109.
    11. Ganesh, K. and Narendran, T.T. (2007), "CLOVES: A cluster-and-search heuristic to solve the vehicle routing problem with delivery and pick-up," European Journal of Operational Research, Vol. 178, No. 3, pp. 699-717.
    12. Goetschalckx, M. and Jacobsblecha, C. (1989), "The Vehicle-Routing Problem with Backhauls," European Journal of Operational Research, Vol. 42, No. 1, pp. 39-51.
    13. Hu, T.-Y., Liao, T.-Y., Chen, L.-W., Huang, Y.-K., and Chiang, M.-L., (2007) "Dynamic Simulation-Assignment Model (DynaTAIWAN) under Mixed Traffic Flows for ITS Applications," In: Transportation Research Board 86th Annual Meeting, Washington DC, United States.
    14. Mingozzi, A., Giorgi, S., and Baldacci, R. (1999), "An Exact Method for the Vehicle Routing Problem with Backhauls," Transportation Science, Vol. 33, No. 3, pp. 315-329.
    15. Ojha, U. and Mo-Yuen, C., (2010) "An analysis of Artificial Immune System and Genetic Algorithm in urban path planning," In: IECON 2010 - 36th Annual Conference on IEEE Industrial Electronics Society.
    16. Osman, I.H. and Wassan, N.A. (2002), "A reactive tabu search meta-heuristic for the vehicle routing problem with back-hauls," Journal of Scheduling, Vol. 5, No. 4, pp. 263-285.
    17. Parragh, S.N., Doerner, K.F., and Hartl, R.F. (2008), "A survey on pickup and delivery problems," Journal für Betriebswirtschaft, Vol. 58, No. 1, pp. 21-51.
    18. Potvin, J.-Y., Duhamel, C., and Guertin, F. (1996), "A genetic algorithm for vehicle routing with backhauling," Applied Intelligence, Vol. 6, No. 4, pp. 345-355.
    19. Robert, W., Poole, j., and Griffin, M. (1994), "Shuttle Vans: The Overlooked Transit Alternative." Policy Study. Vol. 176.
    20. Ropke, S. and Pisinger, D. (2006), "A unified heuristic for a large class of Vehicle Routing Problems with Backhauls," European Journal of Operational Research, Vol. 171, No. 3, pp. 750-775.
    21. Shaw, P., (1998) Using Constraint Programming and Local Search Methods to Solve Vehicle Routing Problems, in Principles and Practice of Constraint Programming — CP98, M. Maher and J.-F. Puget, Editors. 1998, Springer Berlin Heidelberg. p. 417-431.
    22. Solomon, M.M. (1987), "Algorithms for the Vehicle Routing and Scheduling Problems with Time Window Constraints," Operations Research, Vol. 35, No. 2, pp. 254-265.
    23. Thangiah, S.R., Potvin, J.-Y., and Sun, T. (1996), "Heuristic approaches to vehicle routing with backhauls and time windows," Computers & Operations Research, Vol. 23, No. 11, pp. 1043-1057.
    24. Toth, P. and Vigo, D. (1999), "A heuristic algorithm for the symmetric and asymmetric vehicle routing problems with backhauls," European Journal of Operational Research, Vol. 113, No. 3, pp. 528-543.
    25. Xu, J., (2009), "The vehicle routing problem based on the immune algorithm," Master's Thesis, Université du Québec à Chicoutimi, Chicoutimi
    26. Yano, C.A., Chan, T.J., Richter, L.K., Cutler, T., Murty, K.G., and Mcgettigan, D. (1987), "Vehicle-Routing at Quality Stores," Interfaces, Vol. 17, No. 2, pp. 52-63.
    27. Ministry of Transportation and Communications, MOTC (2013), http://stat.motc.gov.tw/mocdb/stmain.jsp?sys=100

    下載圖示 校內：立即公開
    校外：立即公開
    QR CODE