بررسي مقايسه‌اي الگوريتم‌هاي فرا ابتكاري براي مسيريابي وسيله نقليه پويا به منظور بهره‌وري وكارايي سيستم‌هاي حمل ‌و نقل

A Comparative Study of Meta-heuristic Algorithms for dynamic vehicle routing problem in order to provide efficiency of transportation systems

مسأله مسيريابي وسيله نقليه (VRP) يكي از معروف­ترين مسائل بهينه ­سازي است كه در دهه ها‌ي اخير كاربرد­هاي زيادي به منظور بهره‌وري و كارايي سيستم‌هاي حمل‌ و نقل داشته است. مسأله مسيريابي وسائل نقليه با بارگيري و تحويل همزمان، كه توزيع و جمع آوري همزمان كالا از مبدأ به مقصد (مشتريان) را انجام مي­دهد يكي از انواع كلاسيك مسأله مسيريابي مي باشد كه در آن مشتريان نيازمند تكميل فرآيند بارگيري و تحويل در انبار در يك پنجره زماني خاص مي­باشند. كاربرد­هاي اين مسأله در بسياري از مسائل روزمره واقعي همچون حمل و نقل و بهينه سازي برنامه­ ريزي منطقي مشهود مي­ باشد. اين مقاله از الگوريتم­هاي فرا ابتكاري براي اين منظور استفاده كرده است. روش پيشنهادي براي حل مسأله مسيريابي وسيلۀ نقليه ظرفيت­دار جهت بهبود بهره­وري و كارايي توزيع (با كمينه كردن فاصله كل طي شده در هر مسير) و با در نظر گرفتن ظرفيت مسير­هاي مختلف به كار گرفته شده است. اين مسأله، ذاتاً يك مسألهNP-Hard مي باشد بنابراين هيچ روش بهينه با زمان چند جمله­ اي براي آن وجود ندارد. روش پيشنهادي كه برمبناي الگوريتم ژنتيك مي باشد، بر روي برخي از مسائل آزمون استاندارد با درنظر گرفتن بهره ­وري محاسباتي و كيفيت جواب آزمون شده است. عملكرد روش ارائه شده با ساير الگوريتم هاي ابتكاري موجود بر روي همان مسأله مقايسه شده است. نتايج عددي نشان دهندۀ موفقيت رويكرد پيشنهادي براي مسائل مقيد سخت مي­باشد و مكانيزم جواب ساده و پايداري را براي كاربردهاي دنياي واقعي بويژه بهينه ­سازي مسير­يابي وسائل نقليه را ارائه مي­دهد.

Vehicle Routing Problem (VRP) wasone of the mostpopular optimization problems that hadmany usages for productivity and efficiency of transportation systems in recent decades.The Vehicle Routing Problem with Simultaneous pick-up and deliveries (VRP/SPD), which considers simultaneous distribution and collection of goods from/to customers (VRP/SDP/SDC) was a variant of the classical vehicle routing problem where customers require simultaneous pick-up and delivery at their locations to be completed within a specified time. Applications of the SPD and its related variants are commonly come across in every day transportation and optimizing logistic planning. This paper had used Meta-heuristic to this end. The proposed method was applied for solving capacitated vehicle routing problem (CVRP) to improve the distribution efficiency and productivity with an objective of minimizing the total distance covered in each route, while considering the capacity of different routes. This problemwas essentially an NP-Hard in nature, so there was no known optimal solution method with polynomial time. To solve this NP-hard VRP a hybrid genetic based algorithm was developed. The proposed geneticalgorithm was tested on some standardproblem with respect to computational efficiency and solution quality. The presented method was implemented and its performance was further investigated by comparing it against existing heuristics for the same problem. Theresults showed that the success of the proposed approach in handling the difficult problem constraints and devising simple and robust solution mechanisms that can be integrated with routing optimization tools and used in real world applications.