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

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

نویسندگان

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

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

چکیده

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

کلیدواژه‌ها


  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.