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

The Library Vehicle Routing Problem with Deliveries and Pickups

陳惠國(Huey-Kuo Chen) ； 余彥儒(Yen-Ju Yu)

《運輸學刊》 25卷1期 (2013/03) Pp. 1-29

https://doi.org/10.6383/JCIT.201303_25(1).0001

摘要

「圖書館書籍通閱移送之車輛途程問題」（Library Vehicle Routing Problem with Deliveries and Pickups, LVRP-DP）係指車輛由圖書總館出發至各圖書分館進行通閱移送書籍收送之服務。其中，各圖書館可同時為供給點與需求點，而且收送之書籍其有特定的起點與迄點，因此LVRP-DP問題求解過程必須同時處理「車輛路線規劃」之車流問題與「書籍起迄指派」之書流問題，本質上屬於運算難度極高之組合數學問題，比起單純之車輛途程問題更為複雜。在過去的研究中，組合數學問題常採用巨集啟發式演算法求解，其中又以基因演算法（Genetic Algorithm, GA）較為常見。本研究發展改良式基因演算法（Hybrid Genetic Algorithm, HGA）以求解LVRP-DP，並利用舊金山圖書館系統資料進行測試，將所得結果與過去文獻之研究進行比較，有不錯之成果。此外，本研究亦針對臺北市立圖書館系統進行測試，根據所得結果顯示，本研究所發展之LVRP-DP數學模型與求解演算法比起國內、外現行之圖書館系統之運作方式，更為周詳且其有彈性。

關鍵字

圖書館車輛途程問題 ； 兩階段求解法 ； 改良式基因演算法

並列摘要

The library vehicle routing problem with deliveries and pickups (LVRP-DP) is to find optimal vehicle routes starting from the main library, visiting all library branches to provide delivery and pickup services for interlibrary loan books, and then returning to the main library. Each library could be an origin, a destination, or both. In addition, each interlibrary loan book being delivered or picked up is origin-destination specified. Since the LVRP-DP must consider ”vehicle flow” in vehicle routing and “book flow” in book assignment simultaneously, it is essentially difficult combinatorial problem, and indeed more difficult than the original vehicle routing problem alone. To solve the LVRP-DP, a meta-heuristic algorithm called hybrid genetic algorithm (HGA) is proposed. To demonstrate, real data taken from the San Francisco Library System is used and the obtained results are compared with those appeared in the literature. To further justify the advantage of our proposed model and solution algorithm, real data from the Taipei Public Library System with necessary modification is also tested. The results show that the library vehicle routes scheduled by the proposed HGA are superior to those arranged by the manual method in terms of several performance indices. Hence, the proposed solution algorithm has good potential for real applications in the future.

並列關鍵字

Library vehicle routing problem ； Two-stage solution algorithm ； Hybrid genetic algorithm

參考文獻

陳奐宇(2009)。圖書館系統通閱移送書籍之車輛途程問題(碩士論文)。中央大學土木工程學系。

Apte, U. M.,Mason, F. M.(2006).Analysis and Improvement of Delivery Operations at the San Francisco Public Library.Journal of Operations Management.24(4),325-346.

Baker, B. M.,Ayechew, M. A.(2003).A Genetic Algorithm for the Vehicle Routing Problem.Computers and Operations Research.30(5),787-800.

Beasley, D.,Bull, D. R.,Martin, R. R.(1993).An Overview of Genetic Algorithms: Part 1, Fundamentals.University Computing.15(2),58-69.

Beasley, D.,Bull, D. R.,Martin, R. R.(1993).An Overview of Genetic Algorithms: Part 2, Research Topics.University Computing.15(4),170-181.