The paired many-to-many pickup and delivery problem: an application

This paper addresses a variation of pickup and delivery problems, named the paired many-to-many pickup and delivery problem (PMPDP), which has never been formally classified in the literature. Given “paired” demands between customer nodes, the PMPDP is to find a set of feasible vehicle routes starting from and ending at the depot such that the constructed objective function can be optimized subject to a set of desired constraints. When the PMPDP is applied to public library delivery operations, interchangeably used with the library vehicle routing problem (LVRP) hereafter, the customer nodes are replaced by library branches and the items to be delivered and picked up become books, videos and materials. To explore the LVRP, a mathematical model is rigorously formulated and a two-stage solution algorithm involving a modified bee colony optimization method is elaborately developed. Using real data from the San Francisco library system, the computational results show that our approach performs fairly well as compared with those approaches that have appeared in the literature. Provided each customer node is visited once, the sensitivity analysis indicates that when the number of dispatched library vehicles is more than what are needed, then the obtained result may get worse.