تلفن: ۰۴۱۴۲۲۷۳۷۸۱
تلفن: ۰۹۲۱۶۴۲۶۳۸۴

ترجمه مقاله چارچوب برش-و-شاخه برای مسئله ثابت فروشنده دوره گرد – نشریه الزویر

عنوان فارسی: یک چارچوب برش-و-شاخه برای مسئله ثابت فروشنده دوره گرد
عنوان انگلیسی: A branch-and-cut framework for the consistent traveling salesman problem
تعداد صفحات مقاله انگلیسی : 12 تعداد صفحات ترجمه فارسی : 36
سال انتشار : 2016 نشریه : الزویر - Elsevier
فرمت مقاله انگلیسی : PDF فرمت ترجمه مقاله : ورد تایپ شده
کد محصول : 35 رفرنس : دارد
محتوای فایل : zip حجم فایل : 2.20Mb
رشته های مرتبط با این مقاله: ریاضی، مهندسی کامپیوتر و فناوری اطلاعات و ارتباطات
گرایش های مرتبط با این مقاله: تحقیق در عملیات، مهندسی الگوریتم ها و محاسبات و دیتا
مجله: مجله اروپایی تحقیقات عملیاتی - European Journal of Operational Research
دانشگاه: گروه مهندسی شیمی، دانشگاه Carnegie Mellon، پیتسبورگ، ایالات متحده آمریکا
کلمات کلیدی: مساله فروشنده دوره گرد، مسیریابی چند دوره ای، ثبات خدمات
وضعیت ترجمه عناوین تصاویر و جداول: ترجمه شده است
وضعیت ترجمه متون داخل تصاویر و جداول: ترجمه نشده است
وضعیت فرمولها و محاسبات در فایل ترجمه: به صورت عکس، درج شده است
ترجمه این مقاله با کیفیت عالی آماده خرید اینترنتی میباشد. بلافاصله پس از خرید، دکمه دانلود ظاهر خواهد شد. ترجمه به ایمیل شما نیز ارسال خواهد گردید.
فهرست مطالب

چکیده

1. مقدمه

2. تعریف مسئله و نماد

3. فرمولاسیون

3.1 فرمولبندی 1

2.3 فرمولبندی 2

3.3 فرمولبندی 3

4.3 اندازه ها و قدرت فرمولبندی های پیشنهادی

نامساوی های معتبر

4.1محدودیت های حذفی زیر تور

2.4 محدودیت های انطباقی

3.4 قیدهای حذفی مسیر متناقض

4.4 تجزیه و تحلیل پلی هدرال(چندوجهی)

5.چارچوب برش و شاخه

1.5 روال های جداسازی

1.1.5 قیدهای حذفی زیر تور

2.1.5 قیدهای 2-تطبیقی

3.1.5 قیدهای حذفی مسیر متناقض

2.5 پروتکل جداسازی

6.نتایج محاسباتی

1.6 فشردگی فرمولاسیون ها تناوبی و تاثیر نامساوی های معتبر

2.6 عملکرد چارچوب برش-و-شاخه

3.6 قیمت ثبات و سازگاری

7. نتایج

نمونه متن انگلیسی

Abstract

We develop an exact solution framework for the Consistent Traveling Salesman Problem. This problem calls for identifying the minimum-cost set of routes that a single vehicle should follow during the multiple time periods of a planning horizon, in order to provide consistent service to a given set of customers. Each customer may require service in one or multiple time periods and the requirement for consistent service applies at each customer location that requires service in more than one time period. This requirement corresponds to restricting the difference between the earliest and latest vehicle arrival-times, across the multiple periods, to not exceed some given allowable limit. We present three mixed-integer linear programming formulations for this problem and introduce a new class of valid inequalities to strengthen these formulations. The new inequalities are used in conjunction with traditional traveling salesman inequalities in a branch-and-cut framework. We test our framework on a comprehensive set of benchmark instances, which we compiled by extending traveling salesman instances from the well-known TSPLIB library into multiple periods, and show that instances with up to 50 customers, requiring service over a 5-period horizon, can be solved to guaranteed optimality. Our computational experience suggests that enforcing arrival-time consistency in a multi-period setting can be achieved with merely a small increase in total routing costs.

نمونه متن ترجمه

چکیده

ما یک راه حل دقیق شبکه ایی را برای مسئله ثابت فروشنده دوره گرد توسعه می دهیم. این مسئله برای شناسایی مجموعه¬ی حداقل هزینه مسیرهایی است که یک حامل واحد باید در طول چندین دوره زمانی یک افق برنامه ریزی ، به منظور ارائه خدمات ثابت با یک مجموعه ایی از مشتریان دنبال کند. همچنین هر یک از مشتریان ممکن است به خدمات، در یک یا چند دوره زمانی نیاز داشته باشند و ممکن است نیاز به خدمات ثابت در هر موقعیت مشتری که خدمات را در بیش از یک دوره زمانی مورد نیاز می سازد داشته باشند. این تقاضا مربوط به محدود کردن تفاوت بین زمان های ورود اولین و آخرین خودرو، در طول چندین دوره زمانی، برای تجاوز نکردن برخی حدهای مجاز داده شده می باشد. ما سه فرمول برنامه نویسی خطی عدد صحیح-مختلط را برای این مسئله ارائه می دهیم و یک طبقه جدیدی از نامساوی های معتبر را برای تقویت این فرمول ها، معرفی می-کنیم. این نامساوی های جدید به همراه نامساوی های سنتی دست فروش در یک چارچوب شاخه ایی-و-برشی استفاده می شوند. ما شبکه یمان را در یک مجموعه جامعی از نمونه های اندازه گیری شده امتحان می کنیم. این نمونه ها توسط بسط نمونه های دست فروش، از کتابخانه TSPLIB خوب شناخته شده، در چند دوره زمانی گردآوری شدند. ما همچنین نشان می دهیم که نمونه هایی با بالاتر از 50 مشتری، تقاضای سرویس بیش از یک افق 5 دوره ایی، می توانند با استفاده از بهینه سازی ضمانتی حل شوند. آزمایش محاسباتی ما پیشنهاد می کند که پیوستگی زمان ورودی اجرایی بصورت دوره زمانی چندتایی می تواند تنها با استفاده از افزایش کوچک در هزینه-های کلی ارسال بدست بیاید.