توسعه ی الگوریتم ترکیبی ازدحام گربه‌ها با عملگرهای ژنتیکی برای حل مسئله ی مسیریابی وسیله ی نقلیه با محدودیت پنجره زمانی

نوع مقاله : یادداشت فنی

نویسندگان

1 دانشکده‌ی عمران، دانشگاه زنجان، زنجان

2 دانشکده‌ی عمران و حمل‌ونقل، دانشگاه اصفهان، اصفهان

10.24200/j30.2024.63335.3268

چکیده

حمل و نقل کارآمد کالا برای کاهش هزینه‌ها، تسریع زمان تحویل، و بهبود کیفیت خدمات ضروری است. مسئله‌ی مسیریابی وسیله‌ی نقلیه با محدودیت پنجره‌ی زمانی (VRPTW)، یک مسئله‌ی بهینه‌سازی NP-hard در لجستیک است. در نوشتار حاضر، یک الگوریتم ترکیبی ازدحام گربه‌ها با عملگرهای ژنتیکی برای حل مؤثر مسئله‌ی مسیریابی وسیله‌ی نقلیه با محدودیت پنجره‌ی زمانی ارائه شده است. تابع هدف روی کمینه‌سازی کل مسافت طی‌شده و تعداد وسائط نقلیه‌ی استفاده‌شده تمرکز دارد. برای ارزیابی اثربخشی، الگوریتم با مجموعه‌ی داده‌های شبیه‌سازی‌شده از نمونه‌های سالامون آزمایش شده است. تجزیه و تحلیل مقایسه‌‌یی با سایر الگوریتم‌های موجود برتری آن را از نظر کیفیت راه‌حل و کارایی محاسباتی برجسته می‌کند. برای نمونه‌های با اندازه‌ی 50 مشتری تا 48/59٪ بهبود در پاسخ‌های پیشین و برای نمونه‌های با اندازه‌ی 100 مشتری در تعدادی از نمونه‌ها پاسخ‌های بهینه سراسری به‌دست‌آمده از نوشتارهای پیشین به‌دست‌آمده است. الگوریتم پیشنهادی برای سیستم‌های حمل و نقل و لجستیک با مشتری محدود مناسب است و منجر به کاهش هزینه‌ها، بهبود زمان تحویل، و افزایش کیفیت خدمات می‌شود.

کلیدواژه‌ها

موضوعات

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

Innovative Hybrid Algorithm for Solving Vehicle Routing Problem with Time Window

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

  • A.M. Rahimi 1
  • B. Yadegari 2
  • M. Aboutalebi Esfahani 2
1 Associate Professor, Civil Engineering Department, Faculty of Engineering, University of Zanjan, Zanjan, Iran
2 MSc. Graduated of Transportation Planning, Faculty of Civil Engineering and Transportation, University of Isfahan, Isfahan, Iran.
چکیده [English]

Efficient transportation of goods is crucial for cost reduction, improved delivery time, and enhanced service quality. Advanced logistics systems analyze data to find the most efficient routes. This minimizes fuel consumption and decreases transportation costs. The Vehicle Routing Problem with Time Window Constraints (VRPTW) is a classic optimization problem in the field of operations research and logistics. It is a challenging optimization problem in logistics, classified as NP-hard. Hybrid approaches combine multiple optimization techniques to improve the quality and efficiency of solutions. This paper presents a hybrid cat-swarming algorithm that utilizes genetic operators to effectively address the VRPTW problem. The goal is to determine the optimal routes for the vehicles, considering both the vehicle capacity constraints and the time window constraints at each customer location. In this paper the objective function of the algorithm aims to minimize both the total distance traveled and the number of vehicles utilized, ensuring efficient and cost-effective routing. The hybrid cat swarming algorithm proposed in this study offers a novel approach to tackle the challenges posed by the VRPTW problem. By integrating genetic operators such as crossover and mutation, the algorithm enhances performance and improves the quality of solutions. Its primary objective of minimizing total distance and vehicle usage guarantees efficient and economically viable routing strategies. To evaluate the effectiveness of the algorithm, it was tested using a simulated dataset of salmon samples as a benchmark. For samples comprising 50 customers, an improvement of up to 48 to 59 percent in previous response rates has been achieved. For samples comprising 100 customers, optimal global responses, as obtained from previous articles, have been observed in several instances. The proposed algorithm is suitable for transportation and logistics systems with limited customers and leads to cost reduction, improved delivery times, and increased service quality.

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

  • Hybrid optimization vehicle routing-scheduling
  • Vehicle routing problem
  • Time window
  • Cat swarm optimization
  • Genetic algorithm

مراجع

1. Lenstra, J.K. and Kan, A.R., 1981. Complexity of vehicle routing and scheduling problems. Networks, 11(2), pp.221-227. DOI: https://doi.org/10.1002/net.3230110211. 2. Bucur, P.A., Hungerländer, P., Jellen, A., Maier, K., and Pachatz, V., 2021. Shift planning for smart meter service operators. In: Data Science–Analytics and Applications: Proceedings of the 3rd International Data Science Conference–iDSC2020. Springer Fachmedien Wiesbaden, pp.8-10. DOI: https://doi.org/10.1007/978-3-658-32182-6_2. 3. Cissé, M., Yalçındağ, S., Kergosien, Y., Şahin, E., Lenté, C., and Matta, A., 2017. OR problems related to home health care: A review of relevant routing and scheduling problems. Operations Research for Health Care, 13, pp.1-22. DOI: https://doi.org/10.1016/j.orhc.2017.06.001. 4. Wang, X. and Wasil, E., 2021. On the road to better routes: Five decades of published research on the vehicle routing problem. Networks, 77(1), pp.66-87. DOI: https://doi.org/10.1002/net.21942. 5. Desrosiers, J., Soumis, F., and Desrochers, M., 1984. Routing with time windows by column generation. Networks, 14(4), pp.545-565. DOI: https://doi.org/10.1002/net.3230140406. 6. Solomon, M.M., 1987. Algorithms for the vehicle routing and scheduling problems with time window constraints. Operations Research, 35(2), pp.254-265. DOI: https://doi.org/10.1287/opre.35.2.254. 7. Kallehauge, B., Boland, N., and Madsen, O.B., 2007. Path inequalities for the vehicle routing problem with time windows. Networks: An International Journal, 49(4), pp.273-293. DOI: https://doi.org/10.1002/net.20178. 8. Chu, S.-C., Tsai, P.-w., and Pan, J.-S., 2006. Cat swarm optimization. In: Berlin, Heidelberg: Springer Berlin Heidelberg. DOI: https://doi.org/10.1007/978-3-540-36668-3_94. 9. Ji, X.F., Pan, J.S., Chu, S.C., Hu, P., Chai, Q.W., and Zhang, P., 2020. Adaptive cat swarm optimization algorithm and its applications in vehicle routing problems. Mathematical Problems in Engineering, 2020, pp.1-14. DOI: https://doi.org/10.1155/2020/1291526. 10. Yadegari, Y.B., Rahimi, A.M., and Aboutalebi Esfahani, M., 2020. Solving the vehicle routing problem with time windows using cat swarming optimization algorithm. In: The 19th International Conference on Transportation and Traffic Engineering, Tehran. [In Persian]. 11. Alvarenga, G.B., Mateus, G.R., and de Tomi, G., 2007. A genetic and set partitioning two-phase approach for the vehicle routing problem with time windows. Computers & Operations Research, 34(6), pp.1561-1584. DOI: https://doi.org/10.1016/j.cor.2005.07.025. 12. Gong, Y.J., Zhang, J., Chung, H.S.H., Chen, W.N., Huang, R.Z., and Wang, T., 2012. Optimizing the vehicle routing problem with time windows: A discrete particle swarm optimization approach. IEEE Transactions on Systems, Man, and Cybernetics, Part C (Applications and Reviews), 42(2), pp.254-267. DOI: https://doi.org/10.1109/TSMCC.2011.2148712.

فایل ها

هم رسانی

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

آمار