An Ant System for the Selective Pickup and Delivery Problem

摘要

The selective pickup and delivery problem (SPDP) aims for the shortest path that satisfies the load constraint to supply the commodities demanded by all delivery nodes with some selected pickup nodes. This problem is relevant to many real-world problems, e.g., logistic and transportation problems. The SPDP has two major differences from the conventional pickup and delivery problem (PDP): One is to relax the constraint of visiting all pickup nodes, the other is to impose an additional constraint to vehicle load. This study proposes an ant system to solve the SPDP. The ants construct the routes for the SPDP considering the selection of pickup nodes and visiting order of delivery nodes. Moreover, the routes found by the ants can satisfy the constraint on the vehicle load. Experiments are carried out to examine the performance of the proposed method. The results show that the ant system outperforms genetic algorithm in terms of route length, which validates its advantage and effectiveness in solving the SPDP.