การปรับปรุงอัลกอริทึมเพื่อนบ้านที่ใกล้ที่สุดโดยอัลกอริทึมทางพันธุกรรมสำหรับปัญหาการกำหนดเส้นทางยานพาหนะที่มีความจุ
คำสำคัญ:
เพื่อนบ้านที่ใกล้ที่สุด, อัลกอริทึมทางพันธุกรรม, ปัญหาการกำหนดเส้นทางยานพาหนะที่มีความจุบทคัดย่อ
ปัญหาการกำหนดเส้นทางยานพาหนะที่มีความจุ (CVRP) คือปัญหาการขนส่งสินค้าจากโรงงานผลิตสินค้าไปยังลูกค้าแต่ละสถานที่ โดยรับบริการขนส่งสินค้าคนละ 1 ครั้งเท่านั้น และมีระยะทางและค่าขนส่งที่แตกต่างกัน ต้องการให้ค่าใช้จ่ายในการขนส่งน้อยที่สุด และสามารถส่งสินค้าถึงลูกค้าทุกคน โดยส่วนมากใช้อัลกอริทึมเพื่อนบ้านที่ใกล้ที่สุด (NN) แก้ปัญหา CVRP เนื่องจากอัลกอริทึมเพื่อนบ้านที่ใกล้ที่สุดนั้นสามารถใช้งานได้ง่ายและดำเนินการได้อย่างรวดเร็ว แต่คำตอบจากอัลกอริทึมเพื่อนบ้านที่ใกล้ที่สุดนั้นค่อนข้างแย่ เพราะ อัลกอริทึมเพื่อนบ้านที่ใกล้ที่สุดจะเลือกเส้นทางที่สั้นที่สุดในบริเวณข้างเคียง โดยไม่พิจารณาผลรวมของระยะทางในการเดินทางทั้งหมด เพื่อปรับปรุงคำตอบที่ได้จากการค้นหา งานวิจัยฉบับนี้ขอเสนออัลกอริทึมทางพันธุกรรม (GA) ที่ใช้กับอัลกอริทึมเพื่อนบ้านที่ใกล้ที่สุด ปรับปรุงคำตอบ อัลกอริทึมที่เสนอนี้เรียกว่าการปรับปรุงอัลกอริทึมเพื่อนบ้านที่ใกล้ที่สุดโดยใช้อัลกอริทึมทางพันธุกรรมสำหรับปัญหาการกำหนดเส้นทางรถที่มีความจุหรือ NNGA อัลกอริทึมที่เสนอได้รับการทดสอบใน 5 กรณีทดสอบที่เราสร้างขึ้นจาก Google Map ผลจากการทดลองแสดงให้เห็นว่าระยะทางของอัลกอริทึมที่เสนอสามารถลดลง 6.66% เมื่อเปรียบเทียบกับระยะทางของอัลกอริทึมเพื่อนบ้านที่ใกล้ที่สุด
References
Akbar, M. D., & Aurachmana, R. (2020). Hybrid genetic–tabu search algorithm to optimize the route for capacitated vehicle routing problem with time window. International Journal of Industrial Optimization, 1(1), 15-28. doi:10.12928/ijio.v1i1.1421
Bang-Jensen, J., Gutin, G., & Yeo, A. (2004). When the greedy algorithm fails. Discrete Optimization, 1(2), 121-127. doi:10.1016/j.disopt.2004.03.007
Bendall, G., & Margot, F. (2006). Greedy-type resistance of combinatorial problems. Discrete Optimization, 3(4), 288-298. doi:10.1016/j.disopt.2006.03.001
Gutin, G., Yeo, A., & Zverovich, A. (2002). Traveling salesman should not be greedy: Domination analysis of greedy-type heuristics for the TSP. Discrete Applied Mathematics, 117(1-3), 81-86. doi:10.1016/s0166-218x(01)00195-0
Gutin, G., Yeo, A., & Zverovitch, A. (2007). Exponential neighborhoods and domination analysis for the TSP. In G. Gutin & A. P. Punnen (Eds.), The traveling salesman problem and its variations (pp. 223-256). doi:10.1007/0-306-48213-4_6
Ibrahim, M. F., Nurhakiki, F. R., Utama, D. M., & Rizaki, A. A. (2021). Optimised genetic algorithm crossover and mutation stage for vehicle routing problem pick-up and delivery with time windows. IOP Conference Series: Materials Science and Engineering, 1071(2021),. doi:10.1088/1757-899x/1071/1/012025
Ibrahim, M. F., Putri, M. M., Farista, D., & Utama, D. M. (2021). An improved genetic algorithm for vehicle routing problem pick-up and delivery with time windows. Jurnal Teknik Industri, 22(1), 1-17. doi:10.22219/jtiumm.vol22.no1.1-17
Lawler, E. L., Lenstra, J. K., Rinnooy Kan, A. H. G., & Shmoys, D. B. (Eds.). (1985). The traveling salesman problem: A guided tour of combinatorial optimization. Chichester [West Sussex], England: John Wiley & Sons.
Masum, A. K. M., Shahjalal, M., Faruque, F., & Sarker, I. H. (2011). Solving the vehicle routing problem using genetic algorithm. International Journal of Advanced Computer Science and Applications, 2(7), 126-131. doi:10.14569/ijacsa.2011.020719
Ralphs, T. K., Kopman, L., Pulleyblank, W. R., & Trotter, L. E. (2003). On the capacitated vehicle routing problem. Mathematical Programming, 94(2-3), 343–359. doi:10.1007/s10107-002-0323-0
Sadok, A. (2020). A genetic local search algorithm for the capacitated vehicle routing problem. International Journal of Advanced Computer Research, 10(48), 105-115. doi:10.19101/ijacr.2020.1048021
Theodoridis, S., & Koutroumbas, K. (2003). Pattern recognition (2nd ed.). Amsterdam: Academic Press.
