A hybrid heuristic based on General Variable Neighborhood Search for the Single Vehicle Routing Problem with Deliveries and Selective Pickups

In the Single Vehicle Routing Problem with Deliveries and Selective Pickups (SVRP-DSP) deliveries have to be made to a set of customers and there are also pickup goods to be collected. Although pickups are not obligatory, there is a revenue associated with them. Practical applications of this optimization problem arise in reverse logistics, in which customers return goods back to the depot such as in postal logistics. The SVRPDSP is a NP-hard problem, once it can be reduced to the Traveling Salesman Problem when there aren't any pickups to be made. To solve the problem at hand we propose a hybrid heuristic algorithm, named HGVNS, inspired on the metaheuristic General Variable Neighborhood Search combined with an initial solution generation by means of exact methods. The results show that HGVNS is able to find near optimal solutions and, on average, it performs better than the best known algorithm in literature.