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

مسئله مسیریابی وسایل نقلیه یکی از شناخته ‌شده‌ترین مسائل بهینه‌سازی محسوب می ‌شود که هدف آن، طراحی مجموعۀ بهینه‌ای از مسیرها با کمترین هزینه برای سرویس‌دهی به مشتریان است؛ به‌گونه‌ای که با محدودیت‌های موجود سازگار باشد. کاربرد عملی زیاد و وسعت حوزه این مسئله باعث توجه بسیار زیاد پژوهشگران به این مسئله شده است؛ اما سختی حل این مسئله مشکلاتی را ایجاد کرده که نیاز به وجود روش ‌های حل ابتکاری و فراابتکاری را افزایش داده است. این پژوهش یک روش ابتکاری حریصانه بر پایه روش ‌های ابتدا دسته ‌بندی، سپس مسیریابی، برای حل مسئله مسیریابی وسایل نقلیه ظرفیت ‌دار (cvrp) با استفاده از قابلیت‌های تقلیل مسئله به مسئله کوله ‌پشتی ارائه کرده است. از مزایای این روش می ‌توان به مواردی همچون درنظر گرفتن توام معیارهای موثر مانند فاصله بین مشتری ‌ها، فاصله تا دپو و تقاضای نقاط در تصمیم ‌گیری، سرعت و کیفیت جواب خوب و توانایی استفاده از مزایای تقلیل اشاره کرد. برای بررسی نتایج و مقایسه آن ها از نمونه ‌های استاندارد مربوط به cvrplib استفاده شده است.

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

The vehicle routing problem is one of the most wellknown 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 metaheuristic 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.