| عنوان فارسی مقاله: |
یک چارچوب برش-و-شاخه برای مسئله ثابت فروشنده دوره گرد |
| عنوان انگلیسی مقاله: |
A branch-and-cut framework for the consistent traveling salesman problem |
چکیده
ما یک راه حل دقیق شبکه ایی را برای مسئله ثابت فروشنده دوره گرد توسعه می دهیم. این مسئله برای شناسایی مجموعه¬ی حداقل هزینه مسیرهایی است که یک حامل واحد باید در طول چندین دوره زمانی یک افق برنامه ریزی ، به منظور ارائه خدمات ثابت با یک مجموعه ایی از مشتریان دنبال کند. همچنین هر یک از مشتریان ممکن است به خدمات، در یک یا چند دوره زمانی نیاز داشته باشند و ممکن است نیاز به خدمات ثابت در هر موقعیت مشتری که خدمات را در بیش از یک دوره زمانی مورد نیاز می سازد داشته باشند. این تقاضا مربوط به محدود کردن تفاوت بین زمان های ورود اولین و آخرین خودرو، در طول چندین دوره زمانی، برای تجاوز نکردن برخی حدهای مجاز داده شده می باشد. ما سه فرمول برنامه نویسی خطی عدد صحیح-مختلط را برای این مسئله ارائه می دهیم و یک طبقه جدیدی از نامساوی های معتبر را برای تقویت این فرمول ها، معرفی می-کنیم. این نامساوی های جدید به همراه نامساوی های سنتی دست فروش در یک چارچوب شاخه ایی-و-برشی استفاده می شوند. ما شبکه یمان را در یک مجموعه جامعی از نمونه های اندازه گیری شده امتحان می کنیم. این نمونه ها توسط بسط نمونه های دست فروش، از کتابخانه TSPLIB خوب شناخته شده، در چند دوره زمانی گردآوری شدند. ما همچنین نشان می دهیم که نمونه هایی با بالاتر از 50 مشتری، تقاضای سرویس بیش از یک افق 5 دوره ایی، می توانند با استفاده از بهینه سازی ضمانتی حل شوند. آزمایش محاسباتی ما پیشنهاد می کند که پیوستگی زمان ورودی اجرایی بصورت دوره زمانی چندتایی می تواند تنها با استفاده از افزایش کوچک در هزینه-های کلی ارسال بدست بیاید.
