圖書館書籍通閱移送之車輛途程問題－巨集啟發式演算法之應用

以作者查詢圖書館館藏

、以作者查詢臺灣博碩士

、以作者查詢全國書目

、勘誤回報

、線上人數：8

、訪客IP：18.219.83.70

姓名

余彥儒(Yen-ju Yu) 查詢紙本館藏

畢業系所

土木工程學系

論文名稱

圖書館書籍通閱移送之車輛途程問題－巨集啟發式演算法之應用
(The Library Vehicle Routing Problem with Deliveries and Pickups: Application of Meta-Heuristics)

相關論文

★ 圖書館系統通閱移送書籍之車輛途程問題	★ 起迄對旅行時間目標下高速公路匝道儀控之研究
★ 結合限制規劃法與螞蟻演算法求解運動排程問題	★ 共同邊界資料包絡分析法在運輸業之應用-以國內航線之經營效率為例
★ 雙北市公車乘客知覺服務品質、知覺價值、滿意度、行為意向路線與乘客之跨層次中介效果與調節式中介效果	★ 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 格式]

[相關文章]

[文章引用]

[完整記錄]

[館藏目錄]

[檢視]

[下載]

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

摘要(中)

「圖書館書籍通閱移送之車輛途程問題」(LVRP-DP)係車輛於圖書總出發至各間圖書分館進行同時收送書籍之服務，各圖書館間彼此為供給點及需求點，而車輛所運送之書籍具有其特定的起點與迄點關係，求解問題的過程中必須同時處理「車輛路線規劃」之車流問題以及「書籍起迄指派」之書流問題，比單純之車輛途程問題更為複雜，因此屬於運算難度極高之組合數學問題，在過去研究中，最常採用的求解演算法為巨集啟發式演算法。基因演算法 ( Genetic Algorithm, GA) 其基本概念源自達爾文進化論所提出之「物競天擇、適者生存」，所發展而成的巨集啟發式演算法；蜂群最佳化演算法(Bee Colony Optimization, BCO)為根據蜜蜂採集花蜜之行為產生靈感而發展而成的巨集啟發式演算法。因此，本研究分別發展混合式基因演算法及混合式蜂群最佳化演算法，應用於求解LVRP-DP。最後，進行舊金山圖書館系統資料測試並與過去相關研究背景之文獻進行比較，另外，針對台北市立圖書館系統資料進行測試規劃。根據結果發現，本研究針對圖書館書籍通閱移送之車輛途程問題所發展之數學模型與求解演算法考慮層面比國內外現行之圖書館系統之運作方式更為周詳且具有彈性。

摘要(英)

The library vehicle routing problem with delivery and pickup (LVRP-PD) is a problem of finding optimal routes to transport origin-destination paired books in a library system comprising a main library and several library branches. The LVRP-PD is an extension of the traditional vehicle routing problem but is more difficult to solve because books are associated with fixed origin-destination pairs. To solve the LVRP-PD, two meta-heuristics called hybrid genetic algorithm (HGA) and hybrid bee colony optimization algorithm (HBCOA) are proposed. Two real library systems, one in San Francisco and the other in Taipei, are then demonstrated with the two meta-heuristics. The library vehicle routes scheduled by HGA and HBCOA are superior to the existing manual operations and those appeared in the literature in terms of some performance indices. The experiments also show that HGA is a bit better than HBCOA but the superiority is not significant. Hence both proposed solution algorithms have equally good potential for real applications in the future.

關鍵字(中)

★ 混合式基因演算法
★ 書流
★ 同時收送書籍
★ 巨集啟發式演算法
★ 車輛途程問題
★ 圖書館
★ 混合式蜂群最佳化演算法

關鍵字(英)

★ Hybrid Bee Colony Optimization
★ Pickup and Delivery
★ Meta-heuristic
★ Vehicle Routing Problem
★ Library
★ Book Flow
★ Hybrid Genetic Algorithm

論文目次

中文摘要 i
Abstract ii
誌謝 iii
圖目錄 viii
表目錄 xi
第一章緒論 1
1.1 研究背景與動機 1
1.2 研究目的 2
1.3 研究範圍與內容 2
1.4 研究方法與流程 3
第二章文獻回顧 6
2.1 車輛途程問題相關文獻 6
2.1.1 車輛途程問題 6
2.1.2 VRP求解演算法 10
2.1.3 基因演算法概述 19
2.1.4 蜂群最佳化概述 24
2.2 一般化收送貨問題 29
2.2.1 救災車輛途程問題 31
2.2.2 撥召問題 32
2.3圖書館車輛途程問題 33
2.4 文獻回顧之結論 37
第三章模型建構 38
3.1 問題描述與特性 38
3.2 研究假設 39
3.3 符號說明 40
3.4 數學模型 42
第四章求解演算法 45
4.1 演算法架構 45
4.2 建構車輛初始途程 46
4.2.1 車輛初始途程解 46
4.3 改善車輛初始途程 49
4.3.1 混合式基因演算法 49
4.3.2 蜂群最佳化演算法 55
第五章範例測試與分析 61
5.1 舊金山圖書館系統範例測試 61
5.2舊金山圖書館系統範例之敏感度測試 65
5.2.1 變動使用車輛數 65
5.2.2 變動駕駛間工作時間公平性基準值 68
5.3 台北市立圖書館系統範例測試 72
第六章結論與建議 75
6.1 結論 75
6.2 建議 76
參考文獻 78
附錄A舊金山圖書館系統資料 84
附錄B 台北市立圖書館系統資料 87
附錄C 巨集式啟發演算法相關參數設定 92
C.1 初始解 92
C.2 混合式基因演算法參數設定測試 93
C.3 混合式蜂群最佳化演算法參數設定測試 97
C.4 初始解結合2-OPT、初始解結合巨集啟發式演算法(GA、BCO)及初始解結合混合式巨集啟發式演算法(HGA、HBCO)之求解測試 102
附錄D 目標值權重設定 103
附錄E 車輛路線 105
I. 舊金山圖書館系統範例測試 105
II. 舊金山圖書館系統範例之敏感度分析 110
III. 台北市立圖書館系統範例測試 121

參考文獻

1. 王保元，「物流中心冷凍食品配送模式之研究」，朝陽科技大學工業工程管理學系，碩士論文，2000。
2. 何秉珊，「道路緊急搶修車輛途程問題之研究」，國立中央大學土木工程學系，碩士論文，2008。
3. 林信彥，「有時窗限制的收送貨問題之研究」，國立交通大學運輸科技與管理學系，碩士論文，2004。
4. 卓裕仁、朱佑旌，「兩階段回溯式門檻接受法求解時窗限制回程取貨車輛路線問題之研究」，運輸計劃季刊，第三十七卷第四期，頁405-430，2008。
5. 高世昌，「考量同時送貨及收貨之多場站車輛途程問題」，逢甲大學工業工程學系，碩士論文，2002。
6. 殷敏修，「應用基因演算法求解卡車拖車途程問題」，國立高雄第一科技大學運籌管理學系，碩士論文，2007。
7. 許家筠，「時窗限制虛擬場站接駁補貨車輛途程問題之研究」，國立中央大學土木工程學系，碩士論文，2008。
8. 張寶豐，「以複合啟發式演算法求解時窗限制車輛途程問題」，中原大學工業工程學系，碩士論文，2003。
9. 彭冠儒、陳正芳，「混合送貨、收貨的車輛途程問題」，2002年產業電子化運籌管理學術暨實務研討會論文集，頁 150-157，2002。
10. 馮正民、邱裕鈞，研究分析方法，建都文化事業股份有限公司，頁 339-358，新竹，2004。
11. 邱仕銘，「同時收送貨車輛配送問題之研究」，長榮大學經營管理研究所，碩士論文，2006。
12. 黃信穎，「同時處理收貨與送貨業務之配送路線規劃」，立德管理大學應用資訊研究所，碩士論文，2005。
13. 黃漢瑄，「撥召服務最佳化指派作業之研究」，淡江大學運輸管理學系，碩士論文，2006。
14. 程耀輝，「多路程車輛排程問題之門檻接受啟發式演算法」，義守大學工業工程與管理學系，碩士論文，2005。
15. 莊英群，「應用禁忌搜尋法於混合收送貨之車輛途程問題」，逢甲大學工業工程學系，碩士論文，2003。
16. 楊雅婓，「使用改良式遺傳演算法求解車輛途程問題」，立德管理大學應用資訊研究所，碩士論文，2005。
17. 葉珮婷，「應用變數產生法求解有時窗限制的收送貨問題」，國立交通大學運輸科技與管理學系，碩士論文，2009。
18. 陳惠國，網路與物流分析，一版，五南圖書出版股份有限公司，台北，2009。
19. 陳志明，「應用群蟻演算法於動態車輛途程規劃研究」，朝陽科技大學工業工程管理學系，碩士論文，2004。
20. 陳奐宇，「圖書館系統通閱移送書籍之車輛途程問題」，國立中央大學土木工程學系，碩士論文，2009。
21. 謝伯昂，「考慮收送貨與選擇貨運公司服務的車輛途程問題」，國立海洋大學航運管理學系，碩士論文，2002。
22. 魏健宏、王穆衡、蔡欽同、辛孟鑫，「台北市復康巴士路線規劃問題之研究」，運輸學刊，第十九卷第三期，頁301-332，2007。
23. 蘇文清，「軟時窗限制下探討同時正逆向物流之車輛途程問題」，國立中央大學土木工程學系，碩士論文，2005。
24. Apte, U.M., Mason, F.M., “Analysis and Improvement of Delivery Operations at the San Francisco Public Library,” Journal of Operations Management, Vol. 24, pp. 325-346, 2006.
25. Bodin, L., Golden, B., Assad, A., Ball, M., “Routing and Scheduling of Vehicle and Crews,” Computers and Operations Research, Vol. 10, pp. 63-211, 1983.
26. Baker, B.M., Ayechew, M.A., “A Genetic Algorithm for the Vehicle Routing Problem,” Computers and Operations Research, Vol. 30, pp. 787-800, 2003.
27. Beasley, D., Bull, D.R., Martin, R.R., “An Overview of Genetic Algorithms: Part 1, Fundamentals,” University Computing, Vol. 15, No. 2, pp. 58-69, 1993.
28. Beasley, D., Bull, D.R., Martin, R.R., “An overview of genetic algorithms: Part 2, Research Topics,” University Computing, Vol. 15, No. 4, pp. 170-181, 1993.
29. Cordeau, J.F., 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.
30. Clark, G., Wright, J.W., “Scheduling of Vehicles from a Central Depot to a Number of Delivery Points,” Operations Research, Vol. 12, No. 4, pp. 568-581, 1964.
31. Davidovic, T., Teodorovic, D., “Scheduling Independent Tasks: Bee Colony Optimization Approach,” 17th Mediterranean Conference on Control and Automation, Makedonia Palace, Thessaloniki, Greece, 2009.
32. Fisher, M.L., Jaikumar, R., “A Generalized Assignment Heuristic for Vehicle Routing Problems,” Networks, Vol. 11, pp. 109-124, 1981.
33. Ganesh, K., Narendran, T.T., “A Cluster-and-Search Heuristic to solve the Vehicle Routing Problem with Delivery and Pick-up,” European Journal of Operational Research, Vol.178, pp. 699-717, 2007.
34. Gillett, E.B., Moller, L.R., “A Heuristic Algorithm for the Vehicle Dispatch Problem,” Operation Research, Vol. 22, No. 2, pp. 340-349, 1974.
35. Goldberg, D.E., “Genetic Algorithms in Search,” Optimization and Machine Learning, Reading, MA: Addison Wesley, 1989.
36. Gajpal, Y., Abad, P., “An Ant Colony System for Vehicle Routing Problem with Simultaneous Delivery and Pick-up,” Computers and Operations Research, Vol. 36, pp. 3215-3223, 2009.
37. Garey, M.R., Johnson, D.S., “Computers and Intractability: A Guide to the Theory of NP-Completeness,” Freeman, San Francisco, CA, 1979.
38. Hwang, H.S., “An Improved Model for Vehicle Routing Problem with Time Constraint Based on Genetic Algorithm,” Computers and Industrial Engineering, Vol. 42, pp. 361-369, 2002.
39. Ho, W., Ho, T.S.G., Ji, P., Lau, C.W.H., “A Hybrid Genetic Algorithm for the Multi-Depot Vehicle Routing Problem,” Engineering Applications of Artifical Intelligence, Vol. 21, pp. 548-557, 2008.
40. Hsueh, C.F., Chen H.K., and Chou, H.W., “Vehicle Routing for Rescue Operation in Natural Disasters,” In Caric, T., Gold, H.(Eds), Vehicle Routing Problem, I-Tech Education and Prblishing KG, Vienna, Austria, pp. 71-84, 2008.
41. Holland, J.H., Adaptation in Natural and Artifical Systems, Ann Arbor, Univ. Michigan Press, 1975.
42. 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.
43. Lucic, P., Teodorovic, D., “Computing with Bees: Attacking Complex Transportation Engineering Problems,” International Journal on Artificial Intelligence Tools, Vol. 12, pp. 375-394, 2003.
44. Lu, Q., Dessouky, M., “A New Insertion-Based Construction Heuristic for Solving the Pickup and Delivery Problem with Time Windows,” European Journal of Operational Research, Vol. 175, pp. 672-687, 2006.
45. Liu, S., Huang, W., Ma, H., “An Effective Genetic Algorithm for the Fleet Size and Mix Vehicle Routing Problem,” Transportation Research Part E, Vol. 45, pp. 434-445, 2009.
46. Larson, R., Odoni, A., Urban Operations Research, Prentice Hall, Inc. New Jersey, USA, 1981.
47. Lin, S., “Computer Solution of the Traveling Salesman Problem,” The Bell System Technical Journal, Vol. 44, pp. 2245-2269, 1965.
48. Min, H., “The Multiple Vehicle Routing Problem with Simultaneous Delivery and Pick-up Points,” Transportation Research Part A, Vol. 23, pp. 377-386, 1989.
49. 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.
49. 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.
50. Or, I., “Traveling Salesman-Type Combinatorial Problems and Their Relation to the Logistics of Blood Banking,” Department of Industrial Engineering and Management Science, Ph.D. Thesis, 1976.
51. Psaraftis, H.N., “Dynamic Vehicle Routing: Status and Prospect,” Annuals of Operations Research, Vol. 61, pp. 143-164, 1995.
52. Potvin, J.Y., Rousseau, J.M., “An Exchange Heuristic for Rputing Problems with Time Windows,” Journal of the Operational Research Society, Vol. 46, pp. 1433-1446, 1995.
53. Solomon, M.M., “Algorithms for the Vehicle Routing and Scheduling Problems with Time Window Constraints,” Operations Research, Vol. 35, No. 2, pp. 254-265, 1986.
54. Solomon, M.M., Desrosiers, J., “Time Windows Constrained Routing and Scheduling Problems,” Transportation Science, Vol. 22, pp. 1-13, 1988.
55. Savelsbergh, M.W.P., “The Vehicle Routing Problem with Time Windows: Minimizing Routing Duration,” ORSA Journal on Computing, Vol. 4, No. 2, pp. 146-154, 1992.
56. Savelsbergh, M.W.P., Sol, M., “The General Pickup and Delivery Problem,” Transportation Science, Vol. 29, No. 1, pp. 17-29, 1995.
57. Syswerda, G., “Uniform Crossover in Genetic Algorithms,” In Schaffer J.D. (Ed), Proceceedings of the Third International Conference on Genetic Algorithms, Morgan Kaufmann Publishers Incorporate, San Francisco, CA, USA, pp. 2-9, 1989.
58. 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.
59. Teodorovic, D., “Swarm Intelligence Systems for Transportation Engineering: Principle and Application,” Transportation Research Part C, Vol. 16, pp. 651-667, 2008.
60. Teodorovic, D., Dell’Orco, M., “Mitigating Traffic Congestion: Solving the Ride-Matching Problem by Bee Colony Optimization,” Transportation Planning and Technology, Vol. 31, pp. 135-152, 2008.
61. Wong, L.P., Puan, C.Y., Low, M.Y.H., Chong, C.S., “Bee Colony Optimization Algorithm with Big Valley Landsacpe Exploitation for Job Shop Scheduling Problem,” Proceeding of the 2008 Winter Simulation Conference, pp. 2050-2058, 2008.
62. Wang, C.H., Lu, J.Z., “A Hybrid Genetic Algorithm that Optimizes Capacited Vehicle Routing Problem,” Expert System with Applications: An International Journal, Vol. 36, pp. 2921-2936, 2009.
63. Xu, H., Chen, Z. L., Rajagopal, S., and Arunapuram, S., “Solving a Practical Pickup and Delivery Problem,” Transportation Science, Vol. 37, pp. 347-364, 2003.
64. Zachariadis, E.E., Tarantilis, C.D., Kiranoudis, C.T., “A Hybrid Metaheuristic Algorithm for the Vehicle Routing Problem with Simultaneous Delivery and Pick-up Service,” Expert Systems with Applications, Vol. 36, pp. 1070-1081, 2009.

指導教授

陳惠國(Huey-Kuo Chen)

審核日期

2010-7-19

推文