Solving the biobjective selective pickup and delivery problem with memetic algorithm

Abstract

The pickup and delivery problem (PDP) arises in many real-world scenarios such as logistics and robotics. This problem combines the traveling salesman problem (or the vehicle routing problem) and object distribution. The selective pickup and delivery problem (SPDP) is a novel variant of the PDP that enables selectivity of pickup nodes for particular applications. Specifically, the SPDP seeks a shortest route that can supply all delivery nodes with required commodities from some pickup nodes. The two key factors in the SPDP-travel distance and vehicle capacity required-form a tradeoff in essence. This study formulates the biobjective selective pickup and delivery problem (BSPDP) for minimization of travel distance and vehicle capacity required. To resolve the BSPDP, we propose a multiobjective memetic algorithm (MOMA) based on NSGA-II and local search. Furthermore, a repair strategy is developed for the MOMA to handle the constraint on vehicle load. Experimental results validate the efficacy of the proposed algorithm in approaching the lower bounds of both objectives. Moreover, the results demonstrate the characteristics of the BSPDP.