A hybrid particle swarm optimization for the selective pickup and delivery problem with transfers

In pickup and delivery problems, all the demands should be transported from pickup points (suppliers) to delivery points (customers) by vehicles while respecting a set of constraints. Honoring all demands is sometimes impossible when taking all the constraints into account. Therefore, the selective aspect is added to relax the constraint that all the demands should be satisfied. This paper studies a variant called the selective pickup and delivery problem with transfers (SPDPT). The transfers mean that some demands can be transferred from one vehicle to another one, which gives a chance to find more solutions. A mixed integer linear program is firstly proposed to describe the studied problem. Two objectives have been considered in the paper, maximizing the profit and minimizing the distance. The model is then validated on new generated instances. Due to the complexity of the problem, large instances could not be solved to optimality in a reasonable time. As an alternative, a new metaheuristic based on a hybrid particle swarm optimization is developed to tackle this bi-objective problem. The results show that this proposed method is efficient and competitive.