يک الگوريتم بهبود يافته جمعيت مورچگان براي حل مساله مسيريابي وسيله نقليه همراه با دريافت و تحويل همزمان کالا

مساله مسيريابي وسيله نقليه (VRP) يکي از مهم ترين مسايل بهينه سازي ترکيباتي است که بسيار مورد توجه دانشمندان و محققان قرار گرفته است. اين مساله شامل مسيريابي براي يک ناوگان وسيله نقليه است که در آن هر کدام از وسايل، مجموعه اي از مشتري ها را مورد ملاقات قرار مي دهند، به شرط آن که هر مشتري فقط و تنها فقط به وسيله يک وسيله نقليه ملاقات شود. هدف در اين مساله کمينه سازي فاصله هاي پيموده شده توسط همه وسايل نقليه است. مساله مسيريابي وسيله نقليه همراه با دريافت و تحويل همزمان کالا (VRP_SPD) يک گسترش از مساله VRP که در آن وسايل نقليه نه تنها کالاهايي را به مشتريان تحويل مي دهند، بلکه همزمان کالاهايي را نيز از مشتريان تحويل مي گيرند. روش بهينه سازي مورچگان (ACO) يک تکنيک احتمالي است که رفتار غذايابي مورچگان را شبيه سازي کرده و آن را براي حل مسايلي که تاکنون الگوريتم کارايي براي آن وجود ندارد، مورد استفاده قرار مي دهد. الگوريتم جمعيت مورچگان (ACS) يکي از مشهورترين روش هاي فراابتکاري است که در قانون انتقال و بروزرساني فرمون با ساير نسخه هاي ACO تفاوت دارد. اين مقاله يک روش بهبود يافته روش ACS ترکيب شده با الگوريتم جستجوي محلي سه گانه را براي حل مساله VRP_SPD ارايه مي کند که در اطلاعات ابتکاري و ضريب تبخير فرمون الگوريتم ACS با روش معمولي تفاوت دارد. اين عمل سبب جلوگيري از همگرايي زودرس، فرار از نقاط بهينه محلي و يافتن جواب هاي بهتر براي الگوريتم مي شود. الگوريتم پيشنهادي روي 34 مثال استاندارد از ادبيات موضوع اجرا شده است. نتايج محاسباتي نشان مي دهد که الگوريتم توانسته است که بهترين جوابي كه تاکنون به دست آمده را در چهار مثال ارتقا دهد و رقابت نزديکي را با ديگر الگوريتم هاي فراابتکاري براي حل مساله VRP_SPD داشته باشد.