کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
10346201 | 698774 | 2013 | 8 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Reoptimizing the rural postman problem
ترجمه فارسی عنوان
بازسازی مسائل پستچی روستایی
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
بازسازی مجدد مشکل پستچی روستایی، الگوریتم های هورستیک، تجزیه و تحلیل بدترین مورد،
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
علوم کامپیوتر (عمومی)
چکیده انگلیسی
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.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Computers & Operations Research - Volume 40, Issue 5, May 2013, Pages 1306-1313
Journal: Computers & Operations Research - Volume 40, Issue 5, May 2013, Pages 1306-1313
نویسندگان
C. Archetti, G. Guastaroba, M.G. Speranza,