Heuristic algorithm for the Split-Demand One-Commodity Pickup-and-Delivery Travelling Salesman Problem

در این مقاله، مسئله طراحی مسیرهای حداقل هزینه برای یک وسیله نقلیه با ظرفیت حمل کالایی بین یک مجموعه از مشتریان، به دو ویژگی غیر معمول در ادبیات تحویل و تحویل می پردازیم. یکی از ویژگی های این است که یک مشتری ممکن است چندین بار بازدید کند. یکی دیگر از ویژگی های این است که مشتری می تواند به عنوان محل متوسط ​​برای موقت جمع آوری و تحویل محصول استفاده شود. این مقاله یک الگوریتم ماتوئیستی را توصیف می کند که تکرار یک روش سازنده و یک روش پالایش را اعمال می کند. روش سازنده نشان دهنده هر مشتری با مجموعه ای از گره ها است که هر کدام با یک بازدید بالقوه مرتبط است؛، تقسیم هر تقاضای مشتری را به تقاضای جزئی مربوط به گره های آن، و حل یک کالا تحویل و تحویل حمل و نقل فروشنده با یک محله متغیر جستجو کردن. روش پالایش یک الگوریتم شاخه ای و برش برای بهینه سازی برخی قطعات از یک راه حل معین است. نتایج محاسباتی کامل در نمونه های معیار نشان دهنده عملکرد خوب الگوریتم هنگام حل موارد با 500 مشتری می باشد.