圖書館系統通閱移送書籍之車輛途程問題

以作者查詢圖書館館藏

、以作者查詢臺灣博碩士

、以作者查詢全國書目

、勘誤回報

、線上人數：12

、訪客IP：3.133.121.160

姓名

陳奐宇(Huang-Yu Chen) 查詢紙本館藏

畢業系所

土木工程學系

論文名稱

圖書館系統通閱移送書籍之車輛途程問題
(Library Vehicle Routing Problem with Deliveries and Pickups)

相關論文

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

[相關文章]

[文章引用]

[完整記錄]

[館藏目錄]

至系統瀏覽論文 ( 永不開放)

摘要(中)

「圖書館系統通閱移送書籍之車輛途程問題」(以下簡稱圖書途程問題)係指運用車輛途程問題的最佳化技術，安排圖書分館與各圖書分館彼此之間書本流通，以滿足每個圖書總館或分館之所有讀者的訂閱需求。圖書途程問題因為須同時處理「書籍起迄指派」之書流問題與「車輛途程安排」之車流問題，因此屬於運算複雜度極高之組合數學問題。
本研究先將圖書途程問題按照「車輛數已知」與「車輛數未知」之假設加以區分，前者又進一步按照有無設置「接駁式轉運中心」再加以細分，總共建構三種情境加以探討。每種情境均分別建構數學模型及發展求解演算法。本研究數例測試發現：(1) 在車輛數已知且沒有接駁式轉運中心之情境下，本研究發展出掃瞄法搭配2-opt法之演算法，其求解結果比起Apte與Mason(2006)策略一所求解的結果：(i) 總旅行距離較短；(ii) 可滿足服務之書本量較多；(iii) 目標值亦較佳，但各駕駛人間之各項工作量差異卻較大。(2) 在車輛數已知且有接駁式轉運中心之情境下，本研究發展出四種求解方法，其中三種方法皆可適用於含有接駁式轉運中心之圖書館系統。數例測試所得結果並與Apte與Mason(2006)策略二進行比較分析。(3) 車輛數未知時，本研究發展出混合式基因求解演算法，經使用舊金山圖書館系統之資料進行測試，發現本演算法提出車輛路線比Apte與Mason(2006)提出之策略一結果：(i) 總旅行距離較短，(ii) 可滿足服務之書本量較多，但是駕駛間工作量差異很大。
由於本研究針對圖書途程問題所發展之數學模型與近似演算法考慮層面比國內外現行之圖書館系統之運作方式更為周詳且具有彈性，因此極具應用潛力。

摘要(英)

“Library Vehicle Routing Problem with Deliveries and Pickups” (LVRP-DP) is defined as a problem to find optimal routes for library vehicles to deliver and pickup books between library branches in a library system consisting of a main library and several branch libraries. The LVRP-DP is a difficult combinatorial problem as it is essentially an extension of traditional vehicle routing problem with an additional constraint which requires the books with specified origin and destination (i.e., library branches) being delivered and pickup.
The LVRP-DP is tackled first by dividing it into two categories, i.e., “the number of vehicles is limited” and “the number of vehicles is unlimited”. The former is further decomposed into two subclasses, i.e., “with cross-docking facility” and “without cross-docking facility”. This kind of arrangement yields three scenarios; each scenario is extensively studied by formulating a mathematical model, developing workable solution heuristics, and providing numerical examples. As compared with the two strategies, i.e., number strategy 1 and strategy 2, in Apte and Mason (2006), we observed: (1) under the situation of “the number of vehicles is limited” and “without cross-docking facility”, the results obtained by our proposed solution heuristic (which combines sweeping method and 2-opt method together) is superior to strategy 1 in many aspects: (i) traverse shorter total travel distance; (ii) transship more books；(iii) achieve better objective value. However, our results perform worse in terms of the maximum deviation of drivers’ workload. (2) under the situation of “the number of vehicles is limited” and “with cross-docking facility”, we have proposed four solution heuristics, three of which are demonstrated workable for library system “with cross-docking facility”. A detailed comparison was then made between our results and the strategy 2 of Apte and Mason (2006). (3) under the situation of “the number of vehicles is unlimited”, we have proposed a modified Genetic Algorithm and demonstrated with the numerical example of San Francisco library system. Our result is better than the strategy 1 in terms of total travel distance and total number of books serviced. However, again, our result is inferior with respect to the maximum deviation among all drivers’ workload.
As compared with many existing library systems as well as many cases in the literature, our mathematical models take more factors into consideration and hence have very high potential to be implemented in the near future.

關鍵字(中)

★ 接駁式轉運中心
★ 混合式基因演算法
★ 書流
★ 車輛途程問題
★ 圖書館

關鍵字(英)

★ Book flow
★ Vehicle routing problem
★ Library
★ Cross docking
★ Hybrid genetic algorithm

論文目次

中文摘要 i
Abstract ii
致謝 iii
圖目錄 viii
表目錄 x
第一章緒論 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求解方法 9
2.1.3 基因演算法概述 22
2.2 收送貨車輛途程問題 32
2.3 救災車輛途程問題 34
2.4 圖書館車輛途程問題 35
第三章模型建構 40
3.1圖書館之車輛途程問題之描述 40
3.2研究假設 41
3.3符號說明 43
3.4數學模型 45
第四章車輛數已知之求解演算法 48
4.1沒有接駁式轉運中心 48
4.1.1求解演算法 48
4.1.2比較分析 51
4.2有接駁式轉運中心 55
第五章車輛數未知之求解演算法 71
5.1初始母體 74
5.1.1路線分群之概念 74
5.1.2最近插入法產生超時間容量路線 79
5.1.3隨機產生超時間容量路線 84
5.1.4 引用現況之初始解 84
5.2 改善途程 85
5.2.1 編碼及初始母體之產生 86
5.2.2 基因運算元與停止機制 87
5.2.3 鄰域搜尋法與世代之定義 91
第六章範例測試 93
6.1 混合式基因演算法 93
6.1.1變動交配率 93
6.1.2變動突變率 96
6.1.3變動染色體數 98
6.1.4 變動執行回合數 106
6.2 小結 116
第七章結論與建議 117
7.1 結論 117
7.2 建議 118
參考文獻 120
附錄A 車輛數已知且沒有接駁式轉運中心 125
附錄B 車輛數已知且有接駁式轉運中心 130

參考文獻

1. 王元鵬(2006)，仿水流離散優化演算法，國立台灣大學工業工程研究所碩士論文，台北。
2. 王文鴻(2003)，基因演算法結合模糊切割應用於配送路徑之研究，中華大學資訊工程學系碩士論文，新竹。
3. 王保元(2000)，物流中心冷凍食品配送模式之研究，朝陽科技大學工業工程管理學系碩士論文，台中。
4. 何秉珊(2008)，道路緊急搶修車輛途程問題之研究，國立中央大學土木工程學系碩士論文，中壢。
5. 李佳蓮(2006)，車輛途程問題的廣域搜尋法，國立成功大學土木工程學系碩士論文，台南。
6. 邱仕銘(2006)，同時收送貨車輛配送問題之研究，長榮大學經營管理研究所碩士論文，台南。
7. 高世昌(2002)，考量同時送貨及收貨之多場站車輛途程問題，逢甲大學工業工程學系碩士論文，台中。
8. 莊英群(2003)，應用禁忌搜尋法於混合送收貨之車輛途程問題，逢甲大學工業工程學系碩士論文，台中。
9. 許家筠(2008)，時窗限制虛擬場站接駁補貨車輛途程問題之研究，國立中央大學土木工程學系碩士論文，中壢。
10. 陳惠國(2009)，網路分析課程講義，國立中央大學，中壢。
11. 陳惠國、黃炳霖(2008)，仿水流優化演算法之應用與改良-以旅行推銷員為例，第十六屆模糊理論及其應用研討會，中壢。
12. 彭冠儒(2002)，考量同時送貨及收貨之車輛途程問題，逢甲大學工業工程學系碩士論文，台中。
13. 彭冠儒、陳正芳(2002)，「混合送貨、收貨的車輛途程問題」，2002年產業電子化運籌管理學術暨實務研討會論文集，pp. 150-157，桃園。
14. 曾惠鈺(2002)，即時行車資訊下物流配送作業規劃之研究，淡江大學運輸管理學系碩士論文，台北。
15. 馮正民、邱裕鈞(2004)，研究分析方法，建都文化事業股份有限公司，新竹，pp. 339-358。
16. 黃信穎(2005)，同時處理收貨與送貨業務之配送路線規劃，立德管理大學應用資訊研究所碩士論文，台南。
17. 楊雅斐(2005)，使用改良式遺傳演算法求解車輛途程問題，立德管理大學應用資訊研究所碩士論文，台南。
18. 楊馥豪(2005)，時窗限制下混合收送貨之配送路線規劃，立德管理大學應用資訊研究所碩士論文，台南。
19. 廖雯慈(1997)，應用基因演算法求解優先順序旅行推銷員問題，元智大學工業工程學系碩士論文，中壢。
20. 謝伯昂(2002)，考慮收送貨與選擇貨運公司服務的車輛途程問題，國立海洋大學航運管理學系碩士論文，基隆。
21. Apte, U.M., Mason, F.M., (2006), “Analysis and Improvement of Delivery Operations at the San Francisco Public Library,” Journal of Operations Management, Vol. 24, pp. 325-346.
22. Bodin, L., Golden, B., Assad, A., Ball, M., (1983), “Routing and Scheduling of Vehicles and Crews,” Computers and Operations Research, Vol. 10, pp. 63-211.
23. Clarke, G., Wright, J.W., (1964), “Scheduling of Vehicles from a Central Depot to a Number of Delivery Points,” Operations Research Quarterly, Vol. 12, No. 4, pp. 568-581.
24. Danzig, G.B., Ramser, R.H., (1959), “The Truck Dispatching Postman,” Management Science, Vol. 6, pp. 80-91.
25. Dorigo, M., Maniezzo, V., Colorni, A., (1991), “Positive Feedback as a Search Strategy,” Technical Report, Milano, Italy.
26. Dueck, G., (1993), “New Optimization Heuristics: The Great Deluge Algorithm and the Record-to-Record Travel,” Journal of Computational Physics, Vol.104, pp. 86-92.
27. Dueck, G., Scheuer, T., (1990), “Threshold Accepting: A General Purpose Optimization Algorithm Appeared Superior to Simulated Annealing,” Journal of Computational Physics, Vol. 90, pp. 161-175.
28. Fisher, M.L., Jaikumar, R., (1981), “A Generalized Assignment Heuristic for Vehicle Routing,” Networks, Vol. 11, pp. 109-124.
29. Garey, M.R., Johnson, D.S., (1979), Computers and Intractability: A Guide to the Theory of NP-Completeness, Freeman, W.H. and Company, New York, NY, USA.
30. Gillett, B., Miller, L., (1974), “A Heuristic Algorithm for the Vehicle Dispatch Problem,” Operations Research, Vol. 22, No. 2, pp. 340-349.
31. Glover, F., (1989), “Tabu Search-Part I,” ORSA Journal on Computing, Vol. 1, No. 3, pp. 190-206.
32. Glover, F., (1990), “Tabu Search-Part II,” ORSA Journal on Computing, Vol. 2, No. 1, pp. 4-32.
33. Ho, W., Ho, T.S.G., Ji, P., Lau, C.W.H., (2008), “A Hybrid Genetic Algorithm for the Multi-Depot Vehicle Routing Problem,” Engineering Applications of Artificial Intelligence, Vol. 21, pp. 548-557.
34. Holland, J.H., (1975), Adaptation in Natural and Artificial System, University of Michigan Press, Ann Arbor, Michigan, USA.
35. Hsueh, C.F., Chen, H.C., Chou, H.W., (2008), “Vehicle Routing for Rescue Operation in Natural Disasters,” In Caric, T., Gold, H.(Eds), Vehicle Routing Problem, I-Tech Education and Publishing KG, Vienna, Austria, pp. 71-84.
36. Hwang, H.S., (2002), “An Improved Model for Vehicle Routing Problem with Time Constraint Based on Genetic Algorithm,” Computers and Industrial Engineering, Vol. 42, pp. 361-369.
37. Kirkpatrick, S., Gelatt, C.D., Vecchi, M.P., (1983), “Optimization by Simulated Annealing,” Science, Vol. 220, pp. 671-680.
38. Lin, S., (1965), “Computer Solution of the Traveling Salesman Problem,” Bell System Technical Journal, Vol. 44, pp. 2245-2269.
39. Min, H., (1989), “The Multiple Vehicle Routing Problem with Simultaneous Delivery and Pick-up Points,” Transportation Research, Part A. Vol. 23, pp. 377-386.
40. Or, I., (1976), Traveling Salesman-Type Combinatorial Problems and Their Relation to the Logistics of Blood Banking, Ph.D. Thesis, Department of Industrial Engineering and Management Science, Northwestern University, Evanston, Illinois, USA.
41. Potvin, J.Y., Kervahut, T., Garcia, B.L., Rousseau, J.M., (1996), “The Vehicle Routing Problem with Time Windows Part I: Tabu Search,” INFORMS Journal on Computing, Vol. 8, No. 2, pp. 158-164.
42. Potvin, J.Y., Rousseau, J.M., (1995), “An Exchange Heuristic for Routing Problems with Time Windows,” Journal of the Operational Research Society, Vol. 46, pp. 1433-1446.
43. Psaraftis, H.N., (1995), “Dynamic Vehicle Routing: Status and Prospect,” Annals of Operations Research, Vol. 61, pp. 143-164.
44. Savelsbergh, M.W.P., (1992), “The Vehicle Routing Problem with Time Windows: Minimizing Routing Duration,” ORSA Journal on Computing, Vol. 4, No. 2, pp. 146-154.
45. Schruben, L.W., Clifton, R.E., (1968), “The Lockset Method of Sequential Programming Applied to Routing Delivery and Pickup Trucks,” American Journal of Agricultural Economics, Vol. 50, No. 4, pp. 854-867.
46. Solomon, M.M., (1986), “On the Worst-case Performance of Some Heuristics for the Vehicle Routing and Scheduling Problem with Time Windows Constraints,” Networks, Vol. 16, pp. 161-174.
47. Solomon, M.M., (1987), “Algorithm for the Vehicle Routing and Scheduling Problems with Time Windows Constraints,” Operations Research, Vol. 35, pp. 254-265.
48. Solomon, M.M., Desrosiers, J., (1988), “Time Windows Constrained Routing and Scheduling Problems,” Transportation Science, Vol. 22, pp. 1-13.
49. Syswerda, G., (1989), “Uniform Crossover in Genetic Algorithms,” In Schaffer, J.D.(Ed), Proceedings of the Third International Conference on Genetic Algorithms, Morgan Kaufmann Publishers Incorporate, San Francisco, CA, USA, pp. 2-9.
50. Wang, C.H., Lu, J.Z., (2009), “A Hybrid Genetic Algorithm that Optimizes Capacitated Vehicle Routing Problem,” Expert System with Applications: An International Journal, Vol. 36, pp. 2921-2936.

指導教授

陳惠國(Huey-Kuo Chen)

審核日期

2009-7-9

推文