การประยุกต์ใช้วิธีหาค่าที่เหมาะสมแบบวาฬสำหรับปัญหาการจัดเส้นทางยานพาหนะ หลายประเภทภายใต้เงื่อนไขด้านกรอบเวลาแบบยืดหยุ่น
คำสำคัญ:
การจัดเส้นทางยานพาหนะ, เงื่อนไขด้านกรอบเวลา, วิธีหาค่าที่เหมาะสมแบบวาฬ, พารามิเตอร์ที่เหมาะสม, การออกแบบการทดลองบทคัดย่อ
วิธีหาค่าที่เหมาะสมแบบวาฬ (Whale optimization algorithm: WOA) เป็นวิธีเมตาฮิวริสติกส์ที่เลียนแบบมาจากพฤติกรรมการล่าเหยื่อของวาฬที่ประกอบไปด้วย การค้นหาเหยื่อ บีบวงล้อม และโจมตีเหยื่อ ขั้นตอนการค้นหาคำตอบประกอบไปด้วยการหาคำตอบแบบสุ่มกระจาย (Exploration) และการหาคำตอบในพื้นที่ใกล้เคียง (Exploitation) ซึ่งทำให้ผลของคำตอบที่ได้มีคุณภาพที่ดี งานวิจัยนี้นำเสนอการประยุกต์ใช้วิธี WOA ร่วมกับวิธีค้นหาเฉพาะที่ (Local search: LS) มาใช้ในการปรับปรุงคำตอบ เรียกว่าวิธี WOA-LS สำหรับการแก้ปัญหาการจัดเส้นทางยานพาหนะหลายประเภทภายใต้เงื่อนไขด้านกรอบเวลา (Heterogeneous vehicle routing problem with time windows: HVRPTW) ที่มีกรอบเวลาแบบยืดหยุ่น (Soft time windows) โดยมีขั้นตอนการแก้ปัญหาประกอบด้วย การปรับค่าพารามิเตอร์ที่เหมาะสมของวิธี WOA-LS ที่ประกอบด้วย จำนวนวาฬ (Number of populations) และจำนวนรอบการค้นหาคำตอบ (Number of iterations) โดยใช้วิธีทากูชิ (Taguchi orthogonal arrays) ในการออกแบบการทดลองและการวิเคราะห์ความแปรปรวน (ANOVA) นำผลค่าพารามิเตอร์ที่ได้มาทดสอบการหาคำตอบกับปัญหาเทียบเคียงที่มีตำแหน่งของลูกค้าแตกต่างกันจำนวนทั้งหมด 56 ปัญหา และนำคำตอบที่ได้ไปเปรียบเทียบกับวิธีค้นหาแบบต้องห้าม (Tabu Search: TS) ผลการหาคำตอบพบว่าวิธี WOA-LS สามารถหาคำตอบได้ดีกว่าวิธี TS จำนวน 9 ปัญหาจาก 56 ปัญหา และสามารถหาคำตอบได้เท่ากับวิธี TS จำนวน 4 ปัญหา จากทั้งหมด 56 ปัญหา โดยมีค่าเฉลี่ยของคำตอบทั้งหมดทุกปัญหามากกว่าค่าเฉลี่ยคำตอบของวิธี TS 3.29% ผลการหาคำตอบแสดงให้เห็นว่าวิธีที่นำเสนอมีประสิทธิภาพที่ดีในการแก้ปัญหา
References
G. B. Dantzig and J. H. Ramser, “The Truck Dispatching Problem,” Management Science., vol. 6, no. 1, pp. 80-91, 1959.
É. D. Taillard, “A heuristic column generation method for the heterogeneous fleet VRP,” RAIRO - Operations Research., vol. 33, pp. 1-14, 1999.
B. Golden, A. Assad, L. Levy and F. Gheysens, “The fleet size and mix vehicle routing problem,” Computers and Operations Research., vol. 11, pp. 49-66, 1984.
J. Ferland and P. Michelon, “The Vehicle Scheduling Problem with Multiple Vehicle Types,” Journal of the Operational Research Society., vol. 39, pp. 577-583, 1988.
F. Li, B. Golden and E. Wasil, “A record-to-record travel algorithm for solving the heterogeneous fleet vehicle routing problem,” Computers and Operations Research., vol. 34, no. 9, pp. 2734-2742, 2007.
J. Jiang, K. M. Ng, K. L. Poh, and K. M. Teo, “Vehicle routing problem with a heterogeneous fleet and time windows,” Expert Systems with Applications., vol. 41, no. 8, pp. 3748-3760, 2014.
M. M. Solomon, “Algorithms for the Vehicle Routing and Scheduling Problems With Time Window Constraints,” Operations Research., vol. 35, no. 2, pp. 254-265, 1987.
D. C. Paraskevopoulos, P. P. Repoussis, C. D. Tarantilis, G. Ioannou, and G. P. Prastacos, “A reactive variable neighborhood tabu search for the heterogeneous fleet vehicle routing problem with time windows,” Journal of Heuristics., vol. 14, no. 5, pp. 425-455, 2008.
J. C. Molina, J. L. Salmeron and I. Eguia, “An ACS-based memetic algorithm for the heterogeneous vehicle routing problem with time windows,” Expert Systems with Applications., vol. 157, p. 113379, 2020.
J. J. De La Cruz, C. D. Paternina-Arboleda, V. Cantillo, and J. R. Montoya-Torres, “A two-pheromone trail ant colony system - Tabu search approach for the heterogeneous vehicle routing problem with time windows and multiple products,” Journal of Heuristics.,
vol. 19, no. 2, pp. 233-252, 2013.
S. Mirjalili and A. Lewis, “The Whale Optimization Algorithm,” Advances in Engineering Software., vol. 95, pp. 51-67, 2016.
S. K. Dewi and D. M. Utama, “A New Hybrid Whale Optimization Algorithm for Green Vehicle Routing Problem,” Systems Science and Control Engineering., vol. 9, pp. 61-72, 2021.
A. S. Elmousel, O. M. Khairy, O. M. Shehata, and E. I. Morgan, “A Novel Discrete Whale Optimization Algorithm for Solving the Capacitated Vehicle Routing Problem,” in 2021 7th International Conference on Mechatronics and Robotics Engineering (ICMRE), pp. 169-173, 2021.
J. Zhang, L. Hong, and Q. Liu, “An improved whale optimization algorithm for the traveling salesman problem,” Symmetry., vol. 13, no. 1, pp. 1-13, 2021.
S. Yodwangjai and K. Malampong, “An Improved Whale Optimization Algorithm for Vehicle Routing Problem with Time Windows,” The Journal of Industrial Technology., vol. 18, no. 1, pp. 104-122, 2022.
Downloads
เผยแพร่แล้ว
How to Cite
ฉบับ
บท
License

This work is licensed under a Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International License.