Paper Info
Title
An ILP-refined tabu search for the Directed Profitable Rural Postman Problem.
Abstract
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.
Year
DOI
Venue
2014
10.1016/j.dam.2012.06.002
Discrete Applied Mathematics
Keywords
DocType
Volume
penalty cost,neighboring customer,tabu search scheme,internal vehicle,outsourced customer,directed profitable rural postman,integer linear programming,computational experiment,good performance,ilp-refined tabu search algorithm
Journal
163
Issue
ISSN
Citations 
P1
0166-218X
10
PageRank 
References 
Authors
0.54
15
3
Name
Order
Citations
PageRank
C. Archetti11999.69
Gianfranco Guastaroba21488.95
M. G. Speranza329419.55