ترکیب الگوریتم‌های جستجوی ممنوع و جمعیت مورچگان برای مسئله مسیریابی وسیله نقلیه

مسئله مسیریابی وسیله نقلیه (vrp) یکی از مهم‌‌ترین مسائل بهینه‌سازی ترکیباتی است که امروزه به علت کاربردهای وسیع که در مشکلات روزمره دارد بسیار مورد توجه قرار می‌گیرد. در این مسئله ناوگانی از وسایل نقلیه با ظرفیت q از گره‌ای به نام انبار شروع به حرکت می‌کنند و بعد از سرویس‌دهی به مشتریان به آن باز می‌گردند به شرط آنکه هر کدام از مشتریان را فقط یک‌بار مورد ملاقات قرار دهند و در هیچ زمانی بیشتر از ظرفیت محدود q بارگذاری نکنند. هدف در این مسئله کمینه‌کردن تعداد وسایل نقلیه به همراه مسیرهای پیموده شده توسط آن‌ها است. این مقاله نوعی روش ترکیبی جستجوی ممنوع را برای این مسئله پیشنهاد می‌کند. در این روش برای جستجوی همسایگی و حرکت از یک جواب به جواب دیگر از سه حرکت درج، جابجایی و الگوریتم جمعیت مورچگان استفاده می‌شود. برای آزمایش کارایی الگوریتم، چهارده مثال استاندارد کریستوفیدز در نظر گرفته شده و الگوریتم بر روی آن مورد اجرا قرار گرفته است. نتایج محاسباتی روی این مثال‌ها که دارای اندازه‌ای از 50 تا 199 می‌باشند نشان می‌دهد که الگوریتم پیشنهادی توانسته است که رقابت خوبی با الگوریتم‌های مشهور فراابتکاری از نظر کیفیت جواب‌ها داشته باشد. به علاوه جواب‌های نزدیک به بهترین جواب‌های تاکنون بدست آمده  برای بیشتر مثال‌ها بدست آورده است به طوری که سه بهترین جواب توسط این الگوریتم به دست آمد.

Combination of Taboo Search and Ant Colony System Approach to Solve the Vehicle Routing Problem

The Vehicle Routing Problem (VRP) is one of the most important combinational optimization problems that is received much attention because of wide applications in routing problems. In this problem, fleet vehicles with Q capacity start to move from the depot and return after servicing to customers in which visit only ones each customer and load more than its capacity not at all. The objective is to minimize the number of used vehicles and total distance traversed. This paper proposes a hybrid tabu search for the VRP. In this algorithm, three types of neighborhood moves including insert, swap and ant colony system are used for searching the neighborhood and moving from current solution to next solution. Computational experience with the benchmark test instances involving from 50 to 199 confirms that proposed algorithm is competitive in compared to the famous metaheuristic algorithms in terms of the quality of generated solutions. In addition, this algorithm finds closely the bestknown solutions (BKS) for most of the instances in which three bestknown solutions are also found