GRASP with path relinking for the selective pickup and delivery problem

• We study the selective pickup and delivery problem.
• We present a GRASP with path-relinking for solving the described problem.
• The heuristic is simple to implement and has only three parameters.
• The heuristic can generate high quality solutions using small computing times.
• The heuristic improves the existing results in the literature by 5.72% on average.

Bike sharing systems are very popular nowadays. One of the characteristics is that bikes are picked up from some surplus bike stations and transported to all deficit bike stations by a repositioning vehicle with limited capacity to satisfy the demand of deficit bike stations. Motivated by this real world bicycle repositioning problem, we study the selective pickup and delivery problem, where demand at every delivery node has to be satisfied by the supply collected from a subset of pickup nodes. The objective is to minimize the total travel cost incurred from visiting the nodes. We present a GRASP with path-relinking for solving the described problem. Experimental results show that this simple heuristic improves the existing results in the literature with an average improvement of 5.72% using small computing times. The proposed heuristic can contribute to the development of effective and efficient algorithms for real world bicycle reposition operations.