This paper investigates the prize-collecting vehicle routing problem (PCVRP), which has a strong background in practical industries. In the PCVRP, the capacities of all available vehicles are not sufficient to satisfy the demands of all customers. Consequently it is not a compulsory requirement that all customers should be visited. However, a prize can be collected once a customer is visited. In addition, it is required that the total demands of visited customers should reach a pre-specified value at least. The objective is to establish a schedule of vehicle routes so as to minimize the total transportation cost and at the same time maximize the prize collected by all vehicles. The total transportation cost consists of the total distance of vehicle routes and the sum of vehicles used in the schedule. To solve the PCVRP, a two-level self-adaptive variable neighborhood search (TLSAVNS) algorithm is developed according to the two levels of decisions in the PCVRP, namely the selection of customers to visit and the visiting sequence of selected customers in each vehicle route. The proposed TLSAVNS algorithm is self-adaptive because the neighborhoods and their search sequence are determined automatically by the algorithm itself based on the analysis of its search history. In addition, a graph extension method is adopted to obtain the lower bound for PCVRP by transforming the proposed mixed integer programming model of PCVRP into an equivalent traveling salesman problem (TSP) model, and the obtained lower bound is used to evaluate the proposed TLSAVNS algorithm. Computational results on benchmark problems show that the proposed TLSAVNS algorithm is efficient for PCVRP. 
A two-level self-adaptive variable neighborhood search algorithm for the prize-collecting vehicle routing problem