An ILP-refined tabu search for the Directed Profitable Rural Postman Problem

In transportation services, the costs are highly dependent on the opportunity to serve neighboring customers. In this paper we study the problem faced by a shipper that has to serve a set of customers with one internal vehicle and to outsource the service of some of them. The problem is to identify the set of customers to outsource with the goal of minimizing the sum of the traveling costs (routing costs) and the costs associated with the outsourced customers (penalty costs). As the problem can be expressed as the maximization of the difference between a profit gained from the served customers and the traveling cost, we call this problem the Directed Profitable Rural Postman Problem (DPRPP). We propose an ILP-refined tabu search algorithm that combines a tabu search scheme with an Integer Linear Programming (ILP) model. Computational experiments carried out on several sets of instances show the good performance of the proposed solution procedure.