@article{
 title = {Reoptimizing the rural postman problem},
 type = {article},
 year = {2013},
 identifiers = {[object Object]},
 keywords = {Heuristic algorithms,Reoptimization,Rural postman problem,Worst-case analysis},
 pages = {1306-1313},
 volume = {40},
 websites = {http://linkinghub.elsevier.com/retrieve/pii/S0305054812002791},
 month = {5},
 publisher = {Elsevier},
 id = {84f29d86-e7c7-37c0-8f66-336a9733ddf4},
 created = {2015-03-23T18:50:29.000Z},
 accessed = {2014-09-12},
 file_attached = {true},
 profile_id = {756a70ce-605d-3e50-9cbb-a99c29afcbe8},
 group_id = {1f5b486a-d8ac-3a35-9104-56111360dab7},
 last_modified = {2017-03-14T11:36:44.206Z},
 read = {true},
 starred = {false},
 authored = {false},
 confirmed = {true},
 hidden = {false},
 citation_key = {Archetti2013},
 private_publication = {false},
 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. ?? 2012 Elsevier Ltd.},
 bibtype = {article},
 author = {Archetti, C. and Guastaroba, G. and Speranza, M. G.},
 journal = {Computers and Operations Research},
 number = {5}
}

{"_id":"yRtkwzgQouPHjZ4Ss","bibbaseid":"archetti-guastaroba-speranza-reoptimizingtheruralpostmanproblem-2013","downloads":0,"creationDate":"2018-03-26T07:07:40.738Z","title":"Reoptimizing the rural postman problem","author_short":["Archetti, C.","Guastaroba, G.","Speranza, M., G."],"year":2013,"bibtype":"article","biburl":null,"bibdata":{"title":"Reoptimizing the rural postman problem","type":"article","year":"2013","identifiers":"[object Object]","keywords":"Heuristic algorithms,Reoptimization,Rural postman problem,Worst-case analysis","pages":"1306-1313","volume":"40","websites":"http://linkinghub.elsevier.com/retrieve/pii/S0305054812002791","month":"5","publisher":"Elsevier","id":"84f29d86-e7c7-37c0-8f66-336a9733ddf4","created":"2015-03-23T18:50:29.000Z","accessed":"2014-09-12","file_attached":"true","profile_id":"756a70ce-605d-3e50-9cbb-a99c29afcbe8","group_id":"1f5b486a-d8ac-3a35-9104-56111360dab7","last_modified":"2017-03-14T11:36:44.206Z","read":"true","starred":false,"authored":false,"confirmed":"true","hidden":false,"citation_key":"Archetti2013","private_publication":false,"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. ?? 2012 Elsevier Ltd.","bibtype":"article","author":"Archetti, C. and Guastaroba, G. and Speranza, M. G.","journal":"Computers and Operations Research","number":"5","bibtex":"@article{\n title = {Reoptimizing the rural postman problem},\n type = {article},\n year = {2013},\n identifiers = {[object Object]},\n keywords = {Heuristic algorithms,Reoptimization,Rural postman problem,Worst-case analysis},\n pages = {1306-1313},\n volume = {40},\n websites = {http://linkinghub.elsevier.com/retrieve/pii/S0305054812002791},\n month = {5},\n publisher = {Elsevier},\n id = {84f29d86-e7c7-37c0-8f66-336a9733ddf4},\n created = {2015-03-23T18:50:29.000Z},\n accessed = {2014-09-12},\n file_attached = {true},\n profile_id = {756a70ce-605d-3e50-9cbb-a99c29afcbe8},\n group_id = {1f5b486a-d8ac-3a35-9104-56111360dab7},\n last_modified = {2017-03-14T11:36:44.206Z},\n read = {true},\n starred = {false},\n authored = {false},\n confirmed = {true},\n hidden = {false},\n citation_key = {Archetti2013},\n private_publication = {false},\n 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. ?? 2012 Elsevier Ltd.},\n bibtype = {article},\n author = {Archetti, C. and Guastaroba, G. and Speranza, M. G.},\n journal = {Computers and Operations Research},\n number = {5}\n}","author_short":["Archetti, C.","Guastaroba, G.","Speranza, M., G."],"urls":{"Paper":"https://bibbase.org/service/mendeley/756a70ce-605d-3e50-9cbb-a99c29afcbe8/file/35b8bd6f-ac6e-5607-2381-1b928fd9c808/2013-Reoptimizing_the_rural_postman_problem.pdf.pdf","Website":"http://linkinghub.elsevier.com/retrieve/pii/S0305054812002791"},"bibbaseid":"archetti-guastaroba-speranza-reoptimizingtheruralpostmanproblem-2013","role":"author","keyword":["Heuristic algorithms","Reoptimization","Rural postman problem","Worst-case analysis"],"downloads":0},"search_terms":["reoptimizing","rural","postman","problem","archetti","guastaroba","speranza"],"keywords":["heuristic algorithms","reoptimization","rural postman problem","worst-case analysis"],"authorIDs":[]}