يك روش اصلاحي جمعيت مورچگان تركيب شده با الگوريتم هاي ابتكاري درج و جابه جايي براي حل مسئله مسيريابي وسيله نقليه همراه با پنجره هاي زماني

A Modified Ant Colony System Hybridized with inser‎t and Swap Heuristic Algorithms for the Vehicle Routing Problem with Time Windows

مسئله مسيريابي وسيله نقليه همراه با پنجره هاي زماني (VRPTW) يكي از مشهورترين مسائل بهينه سازي تركيباتي در حوزه حمل و نقل است. چون اين مسئله متعلق به مسائل -NP سخت است، بسياري از دانشمندان و محققين روش هاي فراابتكاري براي حل آن ارايه داده اند. در اين مقاله، به علت ضعف هاي موجود در الگوريتم سيستم مورچگان (ACS)، نسخه اي اصلاحي از اين الگوريتم به نام HACS براي حل مسئله VRPTW ارايه مي گردد. به منظور افزايش كارايي الگوريتم، دو روش جستجوي همسايه به نام هاي درج و جابجايي مورد استفاده قرار گرفته شده است. اين اصلاحات سبب مي شود كه الگوريتم جديد از همگرايي زودرس اجتناب كند و به جواب هاي بسيار خوبي دست پيدا كند. در نهايت براي تست كارايي الگوريتم، تعدادي از مجموعه مثال 56 تايي سالامان در نظر گرفته و نتايج اين الگوريتم با ديگر روش ها در ادبيات موضوع مقايسه شده است. نتايج نشان مي دهد كه نه تنها الگوريتم پيشنهادي توانسته جواب هاي بسيار خوبي را به دست آورد بلكه هفت عدد از بهترين جواب هاي تاكنون به دست آمده به وسيله الگوريتم HACS حاصل مي گردد.

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.