應用蜂群最佳化演算法求解撥召問題－以復康巴士為例

以作者查詢圖書館館藏

、以作者查詢臺灣博碩士

、以作者查詢全國書目

、勘誤回報

、線上人數：25

、訪客IP：3.138.114.140

姓名

林奕隆(Yi-Long Lin) 查詢紙本館藏

畢業系所

土木工程學系

論文名稱

應用蜂群最佳化演算法求解撥召問題－以復康巴士為例
(A bee colony optimization algorithm for the dial-a-ride problem-A case of Fu-kang bus)

相關論文

★ 圖書館系統通閱移送書籍之車輛途程問題	★ 起迄對旅行時間目標下高速公路匝道儀控之研究
★ 結合限制規劃法與螞蟻演算法求解運動排程問題	★ 共同邊界資料包絡分析法在運輸業之應用-以國內航線之經營效率為例
★ 雙北市公車乘客知覺服務品質、知覺價值、滿意度、行為意向路線與乘客之跨層次中介效果與調節式中介效果	★ Investigating the influential factors of public bicycle system and cyclist heterogeneity
★ A Mixed Integer Programming Formulation for the Three-Dimensional Unit Load Device Packing Problem	★ 高速公路旅行時間預測之研究--函數資料分析之應用
★ Behavior Intention and its Influential Factors for Motorcycle Express Service	★ Inferring transportation modes (bus or vehicle) from mobile phone data using support vector machine and deep neural network.
★ 混合羅吉特模型於運具選擇之應用-以中央大學到桃園高鐵站為例	★ Preprocessing of mobile phone signal data for vehicle mode identification using map-matching technique
★ 含額外限制式動態用路人均衡模型之研究	★ 動態起迄旅次矩陣推估模型之研究
★ 動態號誌時制控制模型求解演算法之研究	★ 不同決策變數下動態用路人均衡路徑選擇模型之研究

檔案

[Endnote RIS 格式]

[Bibtex 格式]

[相關文章]

[文章引用]

[完整記錄]

[館藏目錄]

[檢視]

[下載]

本電子論文使用權限為同意立即開放。
已達開放權限電子全文僅授權使用者為學術研究之目的，進行個人非營利性質之檢索、閱讀、列印。
請遵守中華民國著作權法之相關規定，切勿任意重製、散佈、改作、轉貼、播送，以免觸法。

摘要(中)

近年來台灣社會福利制度日趨健全，身心障礙者的運輸接送問題也日益受到社會大眾關注，特別是成身心障礙者及年長者的運輸服務。而撥召問題是針對具有特定起迄需求的乘客來設計車輛路線，撥召問題特性與含時窗之收送貨問題(Pickup and Delivery Problem with Time Windows, PDPTW)相似，但運送的是乘客非貨物，因此必須考慮乘客乘坐之時間。
因此，本研究必須先瞭解復康巴士問題特性，考量以乘客預期上車時間前後增減十分鐘之方式設計時窗，再以最少總旅行時間以及車輛等待時間為目標來求解復康巴士車輛途程問題。本研究以蜂群最佳化演算法(Bee Colony Optimization, BCO)為求解演算法，然後以魏健宏等人(2007)與Cordeau and Laporte (2003)之範例進行求解比較，最後提出結論與建議。

摘要(英)

In recent years, more attention is being focused on the disabilities and elders to their transportation demand. This makes the dial-a-ride system which is provided with high accessibility and mobility an important issue in Taiwan. The dial-a-ride problem (DARP) consists of designing vehicle routes for many users who specify diversified pick-up and drop-off requests between various origins and destinations. DARP is similar to the pick-up and delivery problem with time windows, but considering passenger transportation rather than goods transportation.
In the following study, we will identify the main features of the problem associated with Fu-kang Bus’s specific routing concerns. This study focused on solving Fu-kang Bus’ problem, with minimum total travel time and waiting time. To solve the problem, meta-heuristics called bee colony optimization algorithm (BCO) are proposed. Numerical examples are presented to validate the results of the model. Finally conclusions and suggestions are presented.

關鍵字(中)

★ 復康巴士
★ 撥召問題
★ 巨集啟發式演算法
★ 蜂群最佳化演算法

關鍵字(英)

★ Fu-kang Bus
★ Dial-a-ride problem
★ Meta-heuristic
★ Bee Colony Optimization

論文目次

摘要 i
Abstract ii
致謝 iii
表目錄 vi
圖目錄 viii
第一章緒論 1
1-1 研究背景與動機 1
1-2 研究目的 3
1-3 研究範圍與內容 3
1-4 研究方法與流程 4
第二章文獻回顧 7
2-1 車輛途程相關文獻 7
2-1-1 車輛途程問題 7
2-1-2 車輛途程問題的分類 8
2-2 具特定起迄需求之車輛途程問題11
2-2-1 撥召問題 11
2-2-2 圖書館車輛途程問題 20
2-3 車輛途程相關演算法 21
2-3-1 巨集啟發式演算法 22
2-3-2 蜂群最佳化演算法 23
2-4 文獻小結 28
第三章模型建構 30
3-1 台北市小型復康巴士現況與特性30
3-1-1 台北市小型復康巴士現況 30
3-1-2 小型復康巴士問題特性 35
3-2 研究假設 38
3-3 符號說明 39
3-4 數學模型 40
第四章求解演算法 42
4-1 演算法架構42
4-2 建構車輛初始途程 42
4-2-1 車輛初始途程 42
4-3 改善車輛初始途程 47
4-3-1 蜂群最佳化演算法 47
第五章範例測試與分析 57
5-1 範例測試1 57
5-2 範例測試2 61
第六章結論與建議 63
6-1 結論 63
6-2 建議 64
參考文獻 65
附錄A 測試範例資料 69
附錄B 車輛路線 71

參考文獻

1. 魏健宏、王穆衡、蔡欽同、辛孟鑫，「臺北市復康巴士路線規劃問題之研究」，運輸學刊，第十九卷第三期，頁301-332，2007。
2. 袁智偉，「動態撥召公車問題等待策略之研究」，國立交通大學運輸科技與管理學系，碩士論文，2006。
3. 吳韻雯，「長途運輸場站共乘小巴士排程服務之研究」，中原大學土木工程學系，碩士論文，2006。
4. 余彥儒，「圖書館書籍通閱移送之車輛途程問題－巨集啟發式演算法之應用」，國立中央大學土木工程研究所，碩士論文，2010。
5. 陳惠國，網路與物流分析，一版，五南圖書出版股份有限公司，臺北，2009。
6. 馮正民、邱裕鈞，研究分析方法，建都文化事業股份有限公司，頁369-384，2004。
7. Attanasio, A., Cordeau, J.F., Ghiani, G., Laporte, G., “Parallel tabu search heuristics for the dynamic multi-vehicle dial-a-ride problem,” Parallel Computing, Vol. 30, Issue 3, 2004.
8. Bodin, L. D. and Sexton, T., “The multi-vehicle subscriber dial-a-ride problem,” TIMS Studies in Management Science, Vol. 2, pp. 73–86, 1986.
9. Borndörfer, R., Klostermeier, F., Grötschel, M. and Küttner, C., “Telebus Berlin: vehicle scheduling in a dial-a-ride system,” Technical report SC 97-23, Konrad-Zuse-Zentrum für Informationstechnik, Berlin, 1997.
10. Beaudry, G., Laporte, G., Melo, T., Nickel, S., “Dynamic transportation of patients in hospitals,” OR Spectrum: Management Science / Operations Research, Vol. 32, pp. 77-107, 2008.
11. Berbeglia, G., Pesant, G., Rousseau, L.M., Checking the feasibility of dial-a-ride instances using constraint programming, research report CIRRELT-2010-16.
12. Berbeglia, G., Cordeau, J.F., Laporte, G., A hybrid tabu search and constraint programming algorithm for the dynamic dial-a-ride problem, research report CIRRELT-2010-14.
13. Cordeau, J.F. and Laporte, G., “A tabu search heuristic for the static multi-vehicle dial-a-ride problem,” Transportation Research Part B, Vol. 37, pp. 579-594, 2003.
14. Cordeau, J.F. and Laporte, G., “The dial-a-ride problem (DARP): variants, modeling issues and algorithms,” Quarterly Journal of the Belgian, French and Italian Operations Research Societies, pp. 89-101, 2003.
15. Coslovich, L., Pesenti, R., Ukovich, W., “A two-phase insertion technique of unexpected customers for a dynamic dial-a-ride problem,” European Journal of Operational Research, Vol. 175, pp. 1605-1615, 2006.
16. Cordeau, J.F., “A branch-and-cut algorithm for the dial-a-ride problem,” Operational Research, Vol. 54, pp. 573-586, 2006.
17. Dumas, Y., Desrosiers, J. and Soumis, F., “Large scale multi-vehicle dial-a-ride problems,” Les Cahiers du GERAD, G-89-30, Ecole des Hautes Etudes Commerciales, Montreal, 1989.
18. Diana, M. and Dessouky, M. M., “A new regret insertion heuristic for solving large-scale dial-a-ride problems with time windows,” Transportation Research Part B, Vol. 38, pp. 539-557, 2004.
19. Davidovic, T., Teodorovic, D., “Scheduling independent tasks: bee colony optimization approach,” Mediterranean Conference on Control and Automation, Makedonia Palace, Thessaloniki, Greece, 2009.
20. Fu, L. and Teply S., “On-line and off-line routing and scheduling of dial-a-ride paratransit vehicles,” Computer-Aided Civil and Infrastructure Engineering Vol. 14, Issue 5, 1999.
21. Heilporn, G., Cordeau, J.F., Laporte, G., “An integer l-shaped algorithm for the dial-a-ride problem with stochastic customer delays,” Discrete Applied Mathematics, Vol. 159, Issue 9, 2011.
22. Jaw, J., Odoni, A. R., Psarafits, H. N. and Wilson, N. H. M., “A heuristic algorithm for the multi-vehicle advance request dial-a-ride problem with time windows,” Transportation Research Part B, Vol. 20, pp. 243-257, 1986.
23. Jorgensen, R.M., Larsen, J., Bergvinsdottir, K.B., “Solving the dial-a-ride problem using genetic algorithms,” Journal of the Operational Research Society, Vol.58, pp. 1321-1331, 2007.
24. Karaboğa, D., and Baştürk, B., “A powerful and efficient algorithm for numerical function optimization: Artificial bee colony (ABC) algorithm,” Journal of Global Optimization, Vol. 39, pp. 459-471, 2007.
25. Lucic, P., and Teodorovic, D., “Computing with bees: Attacking complex transportation engineering problems,” International Journal on Artificial Intelligence Tolls, Vol. 12, pp. 375-394, 2003.
26. Luo, Y., and Schonfeld, P., “A rejected-reinsertion heuristic for the static dial-a-ride problem,” Transportation Research Part B, Vol. 41, pp. 736-755, 2007.
27. Madsen, O. B. G., Ravn, H. F. and Rygaard, J. M., “A heuristic algorithm for the a dial-a-ride problem with time windows, multiple capacities, and multiple objectives,” Annals of Operations Research, Vol. 60, pp. 193–208, 1995.
28. Mitrovic-Minic, S. and Laporte, G., “Waiting strategies for the dynamic pickup and delivery problem with time windows,” Transportation Research Part B, Vol. 38, pp. 635-655, 2004.
29. Marković, G., Teodorović, D., Aćimović Raspopović, V., “Routing and wavelength assignment in all-optical networks based on the bee colony optimization,” AI Communications- European Journal of Artificial Intelligence, Vol. 20, pp. 273-285, 2007.
30. Nhicolaievna, P.N., Thanh, L.V., “Bee colony algorithm for the multidimensional knapsack problem,” Proceeding of the International Multi-Conference of Engineers and Computer Scientists, Vol. 1, pp. 1-5, 2008.
31. Özbakır, L., and Tapkan, P., “Bees colony intelligence in zone constrained two-sided assembly line balancing problem,” International Journal of Expert Systems with Applications, ESWA 6192, 2011.
32. Parragh, S.N., Cordeau, J.F., Doerner, K.F., Hartl, R.F., Models and algorithms for the heterogeneous dial-a-ride problem with driver related constraints, research report CIRRELT-2010-13.
33. Psaraftis, Harilaos N., “A dynamic programming solution to the single vehicle many-to-many immediate request dial-a-ride problem,” Transportation Science, Vol. 14, pp. 130–154, 1980.
34. Toth, P. and Vigo, D., “Fast local search algorithms for the handicapped persons transportation problem,” In I. H. Osman and J. P. Kelly (Eds.), Meta-heuristics: theory and applications, pp. 677–690, 1996.
35. Toth, P. and Vigo, D., “Heuristic algorithms for the handicapped persons transportation problem,” Transportation Science, Vol. 31, pp. 60–71, 1997.
36. Teodorovic, D., Radivojevic, G., “A fuzzy logic approach to dynamic dial-a-ride problem,” Fuzzy Sets and Systems, Vol. 116, pp. 23-33, 2000.
37. Teodorovic, D., Lucic, P., Markovic, G., Dell’ Orco, M., “Bee colony optimization: principles and applications,” Proceedings of the Eight Seminar on Neural Network Applications in Electrical Engineering, pp. 151-156, 2006.
38. Teodorovic, D., “Swarm intelligence systems for transportation engineering: principle and application,” Transportation Research Part C, Vol. 16, pp. 651-667, 2008.
39. Teodorovic, D., and Dell’ Orco, M., “Mitigating traffic congestion: solving the ride-matching problem by bee colony optimization,” Transportation Planning and Techonlogy, Vol. 31, pp. 135-152, 2008.
40. Teodorovic, D., Davidovic, T., Selmic, M., “Bee colony optimization: the applications survey,” ACM Transactions on Computational Logic, 2011.
41. Wolfler, C. R. and Colorni, A., “An approximation algorithm for the dial-a-ride problem,” (submitted for publication), 2002.
42. Wong, L.P., Puan, C.Y., Low , M.Y.H., Chong , C.S., “Bee colony optimization algorithm with big valley landscape exploitation for job shop scheduling problem,” Proceedings of the 2008 Winter Simulation Conference, pp. 2050-2058, 2008.
43. Xiang, Z., Chu, C., Ukovich, W., “The study of a dynamic dial-a-ride problem under time-dependent and stochastic environments,” European Journal of Operational Research, Vol. 185, pp. 534-551, 2008.

指導教授

陳惠國(Hui-Kuo Chen)

審核日期

2011-8-15

推文