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

نوع مقاله : مقاله پژوهشی

نویسندگان

1 دانشجوی دکتری، دانشگاه بوعلی‌سینا.

2 دانشیار، دانشگاه بوعلی‌سینا.

چکیده

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

کلیدواژه‌ها

عنوان مقاله [English]

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

نویسندگان [English]

  • Amin Farahbakhsh 1
  • Javad Behnamian 2
1 Ph.D Student, Bu-Ali Sina University.
2 Associate Professor, Bu-Ali Sina University.
چکیده [English]

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.

کلیدواژه‌ها [English]

  • Reduction
  • CVRP
  • Greedy Heuristic Algorithm
  • Knapsack Problem
  • Clustering Method

مراجع

  1. Farazmand, M., Pishvaee, M. (2018). Multimodal Transportation Network Design Model under Uncertainty Conditions (Case Study: Cement Transportation in Iran). Journal of Industrial Management Perspective, 8(3), 115-139 (In Persian).
  2. Mortazavi, S., Seif Barghy, M. (2018). Two-Objective Modeling of Location-Allocation Problem in a Green Supply Chain Considering Transportation System and CO2 Emission. Journal of Industrial Management Perspective, 8(1), 163-185 (In Persian).
  3. Nikjoo, N., Javadian, N. (2019). A Multi-Objective Robust Optimization Logistics Model in Times of Crisis under Uncertainty. Journal of Industrial Management Perspective, 8(4), 121-147 (In Persian).
  4. Altinkemer, K., & Gavish, B. (1991). Parallel savings based heuristics for the delivery problem. Operations research, 39(3), 456-469.
  5. Baldacci, R., Hadjiconstantinou, E., & Mingozzi, A. (2004). An exact algorithm for the capacitated vehicle routing problem based on a two-commodity network flow formulation. Operations research, 52(5), 723-738.
  6. Clarke, G., & Wright, J. W. (1964). Scheduling of vehicles from a central depot to a number of delivery points. Operations research, 12(4), 568-581.
  7. Crainic, T. G., Perboli, G., Mancini, S., & Tadei, R. (2010). Two-Echelon Vehicle Routing Problem: A satellite location analysis. Procedia - Social and Behavioral Sciences, 2(3), 5944-5955.
  8. Dantzig, G. B., & Ramser, J. H. (1959). The truck dispatching problem. Management science, 6(1), 80-91.
  9. Dantzig, G. B., & Ramser, J. H. (1959). The Truck Dispatching Problem. Manage. Sci., 6(1), 80-91.
  10. Desrochers, M., & Verhoog, T. (1989). A matching based savings algorithm for the vehicle routing problem. Cahiers du GERAD.
  11. Eksioglu, B., Vural, A. V., & Reisman, A. (2009). Survey: The vehicle routing problem: A taxonomic review. Comput. Ind. Eng., 57(4), 1472-1483.
  12. Farahbakhsh, A., & Forghani, M. A. (2019). Sustainable location and route planning with GIS for waste sorting centers, case study: Kerman, Iran. Waste Management & Research, 37(3), 287-300.
  13. Fisher, M. L. (1994). Optimal solution of vehicle routing problems using minimum k-trees. Operations research, 42(4), 626-642.
  14. Fisher, M. L., & Jaikumar, R. (1981). A generalized assignment heuristic for vehicle routing. Networks, 11(2), 109-124.
  15. Gillett, B. E., & Miller, L. R. (1974). A heuristic algorithm for the vehicle-dispatch problem. Operations research, 22(2), 340-349.
  16. Hannan, M., Akhtar, M., Begum, R. A., Basri, H., Hussain, A., & Scavino, E. (2018). Capacitated vehicle-routing problem model for scheduled solid waste collection and route optimization using PSO algorithm. Waste Management, 71, 31-41.
  17. Jünger, M., Reinelt, G., & Rinaldi, G. (1995). The traveling salesman problem. Handbooks in operations research and management science, 7, 225-330.
  18. Kumar, S. N., & Panneerselvam, R. (2012). A survey on the vehicle routing problem and its variants. Intelligent Information Management, 4(3), 66.
  19. Laporte, G., & Nobert, Y. (1987). Exact Algorithms for the Vehicle Routing Problem*. In G. L. M. M. Silvano Martello & R. Celso (Eds.), North-Holland Mathematics Studies, 132, 147-184.
  20. Lawler, E., Lenstra, J., & Rinnooy Kan, A. (1981). Minimizing maximum lateness in a two-machine open shop. Mathematics of Operations Research, 6(1), 153-158.
  21. Lenstra, J. K., & Kan, A. H. G. R. (1979). Complexity of Vehicle Routing and Scheduling Problems: Math. Centrum.
  22. Lin, C., Choy, K. L., Ho, G. T., Chung, S., & Lam, H. (2014). Survey of green vehicle routing problem: past and future trends. Expert Systems with Applications, 41(4), 1118-1138.
  23. Prodhon, C., & Prins, C. (2014). A survey of recent research on location-routing problems. European Journal of Operational Research, 238(1), 1-17.
  24. Renaud, J., & Boctor, F. F. (2002). A sweep-based algorithm for the fleet size and mix vehicle routing problem. European Journal of Operational Research, 140(3), 618-628.
  25. Ryan, D. M., Hjorring, C., & Glover, F. (1993). Extensions of the petal method for vehicle routeing. Journal of the Operational Research Society, 44(3), 289-296
  26. Sbihi, A., & Eglese, R. W. (2010). Combinatorial optimization and Green Logistics. Annals of Operations Research, 175(1), 159-175.
  27. Solomon, M. M. (1987). Algorithms for the vehicle routing and scheduling problems with time window constraints. Operations research, 35(2), 254-265.
  28. Toth, P., & Vigo, D. (2002). The vehicle routing problem: SIAM.
  29. Vigo, D. (1996). A heuristic algorithm for the asymmetric capacitated vehicle routing problem. European Journal of Operational Research, 89(1), 108-126.
  30. Wei, L., Zhang, Z., Zhang, D., & Leung, S. C. (2018). A simulated annealing algorithm for the capacitated vehicle routing problem with two-dimensional loading constraints. European Journal of Operational Research, 265(3), 843-859.

فایل ها

هم رسانی

ارجاع به این مقاله

آمار