مرکز تحقیقات راه ، مسکن و شهرسازی پژوهشنامه حمل و نقل 1735-3459 13 1 2016 04 20 A Modified Ant Colony System Hybridized with Insert and Swap Heuristic Algorithms for the Vehicle Routing Problem with Time Windows یک روش اصلاحی جمعیت مورچگان ترکیب شده با الگوریتم‌های ابتکاری درج و جابه‌جایی برای حل مسئله مسیریابی وسیله‌نقلیه همراه با پنجره‌های زمانی 101 114 48155 FA شاهرود اعظمی استادیار، دانشگاه آزاد اسلامی، واحد پرند، تهران، ایران پیام بصیری مربی، گروه ریاضی، دانشگاه پیام نور، تهران، ایران فرزاد دیده‌ور استادیار، دانشکده ریاضی و علوم کامپیوتر، دانشگاه صنعتی امیرکبیر، تهران، ایران فرهاد رحمتی دانشیار، دانشکده ریاضی و علوم کامپیوتر، دانشگاه صنعتی امیرکبیر، تهران، ایران مجید یوسفی خوشبخت دانشگاه آزاد اسلامی، واحد همدان، باشگاه پژوهشگران و نخبگان، همدان، ایران Journal Article 2017 07 09 The vehicle routing problem with time windows (VRPTW) is one of the most well-known combinatorial problems in the transportation domain. Because this problem belongs to NP-Hard problems, many researchers have presented meta-heuristics for it. In this paper, aimed at the disadvantages existed in the current Ant Colony System (ACS), a modification of this algorithm called HACS is proposed for solving VRPTW. To improve the performance of ACS, two neighborhood search in the name of insert and swap algorithms are used. This new algorithm can avoid premature convergence and exploit more strong solutions. Finally, the effectiveness of the HACS on solving a number of the Solomon’s 56 VRPTW is validated by comparing the computational results with those previously presented in the literature. The results show that not only the proposed HACS algorithm can find good solutions but also seven best known solutions of the benchmark problem are also found by the proposed method. مسئله مسیریابی وسیله نقلیه همراه با پنجره‌های زمانی (VRPTW) یکی از مشهورترین مسائل بهینه‌سازی ترکیباتی در حوزه حمل و نقل است. چون این مسئله متعلق به مسائل -NP سخت است، بسیاری از دانشمندان و محققین روش‌های فراابتکاری برای حل آن ارایه داده‌اند. در این مقاله، به علت ضعف‌های موجود در الگوریتم سیستم مورچگان (ACS)، نسخه‌ای اصلاحی از این الگوریتم به نام HACS برای حل مسئله VRPTW ارایه می‌گردد. به منظور افزایش کارایی الگوریتم، دو روش جستجوی همسایه به نام‌های درج و جابجایی مورد استفاده قرار گرفته شده است. این اصلاحات سبب می‌شود که الگوریتم جدید از همگرایی زودرس اجتناب کند و به جواب‌های بسیار خوبی دست پیدا ‌کند. در نهایت برای تست کارایی الگوریتم، تعدادی از مجموعه مثال 56 تایی سالامان در نظر گرفته و نتایج این الگوریتم با دیگر روش‌ها در ادبیات موضوع مقایسه شده است. نتایج نشان می‌دهد که نه تنها الگوریتم پیشنهادی توانسته جواب‌های بسیار خوبی را به دست آورد بلکه هفت عدد از بهترین جواب‌های تاکنون به دست آمده به وسیله الگوریتم HACSحاصل میگردد.

https://www.trijournal.ir/article_48155_f021a5566d8509939615e02a20f267e3.pdf