کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
10225920 1701224 2019 25 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
A two-stage solution approach for the Directed Rural Postman Problem with Turn Penalties
ترجمه فارسی عنوان
یک رویکرد راه حل دو مرحلهای برای مساله پستچی روستایی با مجازات مجدد
کلمات کلیدی
مسیریابی اهریمنی، الگوریتم حریص، مشکل پستچی روستایی، مجازات کردن
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر علوم کامپیوتر (عمومی)
چکیده انگلیسی
In this paper, we consider the Directed Rural Postman Problem with Turn Penalties (DRPP-TP). A solution is a tour that traverses all required arcs of the graph. The total cost of the tour is the sum of the lengths of the traversed arcs plus the penalties associated with the turns. One solution approach involves transforming the arc routing problem into an equivalent node routing problem. An alternative direct approach (without graph transformation) that involves two stages has been proposed in the literature. In the first part of this paper, we investigate the applicability of the direct approach. We identify several characteristics of the input instance that make this approach effective and present several limitations of this approach. In the second part of this paper, we describe an integer linear program that is combined with a local search algorithm. This combination produces high-quality solutions to the DRPP-TP in a reasonable amount of computing time.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: European Journal of Operational Research - Volume 272, Issue 2, 16 January 2019, Pages 754-765
نویسندگان
, , , , ,