Reoptimizing the rural postman problem
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 -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. Link to the article
ARCHETTI, C., GUASTAROBA, G. and SPERANZA, M.G. (2013). Reoptimizing the rural postman problem. Computers & Operations Research, 40(5), pp. 1306-1313.
Keywords : #Reoptimization, #Rural-postman-problem, #Heuristic-algorithms, #Worst, #case-analysis