| 摘要: | 「圖書館系統通閱移送書籍之車輛途程問題」(以下簡稱圖書途程問題)係指運用車輛途程問題的最佳化技術，安排圖書分館與各圖書分館彼此之間書本流通，以滿足每個圖書總館或分館之所有讀者的訂閱需求。圖書途程問題因為須同時處理「書籍起迄指派」之書流問題與「車輛途程安排」之車流問題，因此屬於運算複雜度極高之組合數學問題。 本研究先將圖書途程問題按照「車輛數已知」與「車輛數未知」之假設加以區分，前者又進一步按照有無設置「接駁式轉運中心」再加以細分，總共建構三種情境加以探討。每種情境均分別建構數學模型及發展求解演算法。本研究數例測試發現：(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. |
