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

Solving a Multi-Depot Routing Problem with Time Windows and Heterogeneous Vehicles by Multi-objective Differential Evolution Algorithm: A Case Stud

مساله مسيريابي وسايط نقليه چندقرارگاهي با در نظر گرفتن پنجره زماني و وسايط نقليه متفاوت 1، يكي از انواع مسايل مسيريابي وسايط نقليه 2 است. وسايط نقليه داراي ظرفيتهاي متفاوتي هستند و به قرارگا ههاي متفاوتي تخصيص داده مي شوند. بنابراين، اين مساله شامل طراحي يك مجموعه از مسيرهايي است كه در آن وسايط نقليه با ظرفي تهاي متفاوت از يك قرارگاه شروع به حركت م يكنند، به مجموعه اي از مشتريان كه داراي تقاضاي معيني هستند سرويس دهي كرده و در نهايت به همان قرارگاه باز م يگردند. بيشتر مسايلي كه در اين زمينه مطرح شده اند، مربوط به مسايل تك هدفه با هدف كمينه كردن هزينه هستند، اما پيچيدگي هاي مسايل واقعي عموما كاربرد مسايل تك هدفه را به چالش م يكشد. از اين رو در اين مقاله براي انطباق مسايل با دنياي واقعي، در ابتدا يك مدل چند هدفه ارايه مي گردد كه در آن علاوه بر كمينه كردن هزين ههاي كل، عدم توازن حجم كاري بر حسب مسافت طي شده توسط وسايط نقليه، همچنين بار قابل حمل آنها نيز مد نظر قرار گرفته است و از آنجايي كه اين مساله جز مسايل NP-hard است، استفاده از الگوريت مهاي فراابتكاري الزامي است، به همين منظور براي حل مدل ارايه شده، روش فراابتكاري تكامل ديفرانسيلي چند هدفه 3 پيشنهاد شد و براي نشان دادن كارآيي الگوريتم پيشنهادي، جوابهاي به دست آمده در ابعاد كوچك با جوابهاي به دست آمده از روش محدوديت اپسيلون 4 مقايسه شد. نتايج به دست آمده، نشان م يدهند كه درصد خطاي توابع هدف نسبت به روش دقيق در تمام يمسايل حل شده كمتر از 3.2 % است كه نشانگر كارآيي روش پيشنهادي است و در نهايت به بررسي اين موضوع در يك شركت پخش روغن نباتي پرداخته شده است كه نتايج حاصل، نشان دهنده كاهش قابل توجه هزينه هاي آن شركت است.

A Multi-depot Heterogeneous Vehicle Routing Problem with Time Windows (MDHVRPTW) is a variant of the Vehicle Routing Problem (VRP), in which the vehicles do not necessarily have the same capacity and they belong to different depots. Therefore, the MDHVRPTW involves designing a set of vehicle routes, each starting and ending at the depot, for a heterogeneous fleet of vehicles which services a set of customers with known demands. Most problems presented in this field are single-objective problems with the aim of minimizing the cost; however, the complexity of real problems usually doubts the use of single-objective problems. This paper considers not only the minimum travel cost, but also the distance travelled by the used vehicles and their loads. Since this problem is NP-hardness, the use of a meta-heuristic algorithm is obligatory. Therefore a meta-heuristic algorithm based on Multi-Objective Differential Evolution (MODE) is proposed. In addition, to show the efficiency of the proposed MODE, a number of test problems in small and large sizes are considered and then solved. The associated results are evaluated with the results obtained by the ?-constraint method and results showed that the gained function gap was less than 3.5% in all the solved problems. Furthermore, to run the proposed MODE, a real-case study in an oil distribution company is carried out. Finally, the obtained results are reported and discussed.