An Adaptive Hybrid VNS/SA Approach to the One-Commodity Pickup and Delivery Problem

摘要

The One-Commodity Pickup and Delivery Problem (1-PDP) is an NP-hard problem, in which one type of commodity is collected from a set of pickup customers to be delivered to a set of delivery customers, and the origins and destinations of the goods are not paired. We introduce a new adaptive hybrid VNS/SA (Variable Neighborhood Search/Simulated Annealing) approach for solving the 1-PDP. We perform multiple VNS runs, where neighborhood sizes, within which the search is performed at each run, are adaptable and depend on the search progress. Experimental results on a large number of benchmark instances indicate that the algorithm outperforms previous heuristics in 90% of the large size benchmark instances. Nevertheless, this comes at the expense of an increased processing time.