dc.description.abstract | “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.
| en_US |