کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
6896063 1445988 2016 10 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
A branch-and-cut algorithm for the profitable windy rural postman problem
ترجمه فارسی عنوان
یک الگوریتم شاخه ای و برش برای مسائل پستچی روستایی باتلاقی سودمند است
کلمات کلیدی
مشکل پستچی رومیزی بادیه مسیر یابی قوس، سود، الگوریتم شعبه و برش، چندضلعی،
ترجمه چکیده
در این مقاله، مساله پستچی روستایی باتلاقی سودمند مورد بررسی قرار گرفته است. این یک مساله مسیریاب قوس با سود است که در یک گراف بادی تعریف شده است که در آن سود با برخی از لبه های نمودار همراه است، که شامل یافتن مسیری است که حداکثر تفاوت بین مجموع سود جمع آوری شده و هزینه کل را به دست می دهد. این مشکل مساله پستچی روستایی و دیگر مسائل مسیریاب شناخته شده را عمومیت می دهد و برنامه های عمرانی عمدتا در عملیات برداشت برفی را تعریف می کند. در اینجا پیشنهاد یک فرمول برای مسئله و بررسی چند بعدی آن را بررسی می کنیم. چندین خانواده از نابرابری های ناشی از چهره در طراحی و طراحی یک شاخه و برش مورد استفاده قرار می گیرند. الگوریتم در مجموعه ای بزرگ از نمونه های معیار مورد آزمایش قرار گرفته و در مقایسه با سایر الگوریتم های موجود مورد آزمایش قرار گرفته است. نتایج بدست آمده نشان می دهد که الگوریتم شاخه ای و برش قادر به حل موارد بزرگ با اندازه های بزرگ در زمان محاسبات معقول است.
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر علوم کامپیوتر (عمومی)
پیش نمایش مقاله
یک الگوریتم شاخه ای و برش برای مسائل پستچی روستایی باتلاقی سودمند است
چکیده انگلیسی
In this paper we study the profitable windy rural postman problem. This is an arc routing problem with profits defined on a windy graph in which there is a profit associated with some of the edges of the graph, consisting of finding a route maximizing the difference between the total profit collected and the total cost. This problem generalizes the rural postman problem and other well-known arc routing problems and has real-life applications, mainly in snow removal operations. We propose here a formulation for the problem and study its associated polyhedron. Several families of facet-inducing inequalities are described and used in the design of a branch-and-cut procedure. The algorithm has been tested on a large set of benchmark instances and compared with other existing algorithms. The results obtained show that the branch-and-cut algorithm is able to solve large-sized instances optimally in reasonable computing times.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: European Journal of Operational Research - Volume 249, Issue 3, 16 March 2016, Pages 1092-1101
نویسندگان
, , , ,