حل مسئله مسيريابي ظرفيت‌دار با استفاده از تقليل به مسئله كوله‌پشتي و ارائه روش ابتكاري مبتني بر كلاسه‌بندي حريصانه

Solving the CVRP with Reduction to Knapsack Problem and Greedy Clustering Heuristic Method

مسئله مسيريابي وسايل نقليه يكي از شناخته­‌شده‌ترين مسائل بهينه‌سازي محسوب مي­‌شود كه هدف آن، طراحي مجموعۀ بهينه‌اي از مسيرها با كمترين هزينه براي سرويس‌دهي به مشتريان است؛ به‌گونه‌اي كه با محدوديت‌هاي موجود سازگار باشد. كاربرد عملي زياد و وسعت حوزه اين مسئله باعث توجه بسيار زياد پژوهشگران به اين مسئله شده است؛ اما سختي حل اين مسئله مشكلاتي را ايجاد كرده كه نياز به وجود روش­‌هاي حل ابتكاري و فراابتكاري را افزايش داده است. اين پژوهش يك روش ابتكاري حريصانه بر پايه روش­‌هاي ابتدا دسته­‌بندي، سپس مسيريابي، براي حل مسئله مسيريابي وسايل نقليه ظرفيت­‌دار (CVRP) با استفاده از قابليت‌هاي تقليل مسئله به مسئله كوله­‌پشتي ارائه كرده است. از مزاياي اين روش مي­‌توان به مواردي همچون درنظر­گرفتن توأم معيارهاي مؤثر مانند فاصله بين مشتري­‌ها، فاصله تا دپو و تقاضاي نقاط در تصميم­‌گيري، سرعت و كيفيت جواب خوب و توانايي استفاده از مزاياي تقليل اشاره كرد. براي بررسي نتايج و مقايسه آن­ها از نمونه­‌هاي استاندارد مربوط به CVRPLIB استفاده شده است.

The vehicle routing problem is one of the most well-known optimization problems, which aims to design an optimum set of routes with the lowest cost for servicing the customers in a way that is consistent with the existing constraints. The wide practical application and scope of this problem has attracted much attention from researchers. But in return, the severity of solving has created difficulties and increased the need for heuristic and meta-heuristic solutions. This research represents a greedy heuristic method based on first categorizing then routing methods, to solve the capacitated vehicle routing problem (CVRP) using the capabilities of problem reduction to the knapsack problem. The advantages of this method include the consideration of effective criteria such as distance between customers, distance between customers to depot and demand of points in decision making, decent speed and quality of solution and the ability to utilize the benefits of reduction. Standard samples from CVRPLIB were used to evaluate the results and comparing them.