Paper Info
Title
Reoptimizing the rural postman problem
Abstract
Given an instance of the Rural Postman Problem (RPP) together with its optimal solution, we study the problem of finding a good feasible solution after a perturbation of the instance has occurred. We refer to this problem as the reoptimization of the RPP. We first consider the case where a new required edge is added. Second, we address the case where an edge (required or not) is removed. We show that the reoptimization problems are NP-hard. We consider a heuristic for the case where a new required edge is added which is a modification of the cheapest insertion algorithm for the traveling salesman problem and show that it has a worst-case ratio equal to 2. Moreover, we show that simple algorithms to remove an edge from an optimal RPP tour guarantee a tight ratio equal to 3/2. Computational tests are made to compare the performance of these algorithms with respect to the Frederickson algorithm running from scratch.
Year
DOI
Venue
2013
10.1016/j.cor.2012.12.010
Computers & OR
Keywords
DocType
Volume
cheapest insertion algorithm,optimal solution,salesman problem,good feasible solution,optimal RPP tour,tight ratio,new required edge,Frederickson algorithm,reoptimization problem,rural postman problem,simple algorithm
Journal
40
Issue
ISSN
Citations 
5
0305-0548
0
PageRank 
References 
Authors
0.34
15
3
Name
Order
Citations
PageRank
C. Archetti11999.69
Gianfranco Guastaroba21488.95
M. G. Speranza329419.55