การประยุกต์ใช้วิธีวิวัฒนาการโดยใช้ผลต่างกับปัญหาการจัดเส้นทางการเดินรถ โดยมีข้อจำกัดด้านกรอบเวลาและความต้องการที่หลากหลาย
Article Sidebar
Main Article Content
บทคัดย่อ
ปัญหาการจัดเส้นทางการเดินรถภายใต้ข้อจำกัดด้านกรอบเวลาจัดอยู่ในกลุ่มปัญหาเอ็นพีแบบยาก (NP-Hard) ที่มีความยุ่งยากซับซ้อนในการคำนวณหาคำตอบและสอดคล้องกับสภาพปัญหาที่แท้จริงที่เกิดขึ้นในอุตสาหกรรมต่าง ๆ วัตถุประสงค์ของงานวิจัยนี้คือ การจัดเส้นทางการเดินรถให้มีค่าใช้จ่ายโดยรวมที่ต่ำที่สุด ซึ่งประกอบด้วยสองส่วนคือ ต้นทุนการใช้เชื้อเพลิงและต้นทุนค่าเสียโอกาสที่เกิดจากการใช้ยานพาหนะ ไม่เต็มประสิทธิภาพภายใต้เงื่อนไขของกรอบเวลาที่กำหนดและความต้องการของลูกค้าที่ไม่เท่ากัน กระบวนการแก้ปัญหาเริ่มจากการสร้างแบบจำลองทางคณิตศาสตร์เพื่อเป็นตัวแทนของกรณีศึกษา และทำการทดสอบด้วยโปรแกรมสำเร็จรูป LINGO จากนั้นทำการเปรียบเทียบผลลัพธ์กับการใช้วิธีวิวัฒนาการ โดยใช้ผลต่าง ซึ่งเป็นการแก้ปัญหาแบบเมตะฮิวริสติกส์ที่สามารถแก้ปัญหาขนาดใหญ่ที่มีความซับซ้อนและมีตัวแปรตัดสินใจจำนวนมากได้อย่างรวดเร็ว ผลการวิจัยสรุปได้ว่าวิธีวิวัฒนาการโดยใช้ผลต่างให้ค่าของต้นทุน โดยรวมสูงกว่าคำตอบจากการทดสอบด้วยแบบจำลองทางคณิตศาสตร์ แต่ใช้เวลาในการประมวลผลรวดเร็ว โดยคำตอบที่ได้มีความใกล้เคียงคำตอบที่ดีที่สุด จากผลการคำนวณพบว่า การใช้วิธีวิวัฒนาการโดยใช้ผลต่างได้คำตอบที่ให้ต้นทุนโดยรวมสูงกว่าประมาณ 0.8 % แต่สามารถประหยัดเวลาได้ถึง 12 %
Article Details
เอกสารอ้างอิง
Sethanan, K. (2015). Metaheuristics and Applications for Industry. Khon Kaen, Thailand: Klangnanawittaya Publishers. (in Thai)
Office of the National Economic and Social Development Board. (2018). International Logistics Performance Index (LPI) 2018. Access (2 June 2019). Available (https://www.nesdb.go.th/ewt_dl_link.php?nid=8143&filename=index) (in Thai)
López-Sánchez, A. D., Hernández-Díaz, A. G., Vigo, D., Caballero, R., and Molina, J. (2014). A Multi-Start Algorithm for a Balanced Real-World Open Vehicle Routing Problem. European Journal of Operational Research. Vol. 238, Issue 1, pp. 104-113. DOI: 10.1016/J.EJOR.2014.04.008
Wen, L. and Eglese, R. (2015). Minimum Cost VRP with Time-Dependent Speed Data and Congestion Charge. Computers & Operations Research. Vol. 56, pp. 41-50. DOI: 10.1016/j.cor.2014.10.007
Boonmee, A., Sethanan, K., Arnonkijpanich, B., and Theerakulpisut, S. (2015). Minimizing the Total Cost of Hen Allocation to Poultry Farms using Hybrid Growing Neural Gas Approach. Computers and Electronics in Agriculture. Vol. 110, pp. 27-35. DOI: 10.1016/J.COMPAG.2014.10.006
Sommut, N. and Sintusoaw, S. (2009). GRASP Heuristic for Vehicle Routing Problem. RMUTI Journal. Vol. 2, No. 1, pp. 3-13
Sethanan, K. and Neungmatcha, W. (2016). Multi-Objective Particle Swarm Optimization for Mechanical Harvester Route Planning of Sugarcane Field Operations. European Journal of Operational Research. Vol. 252, Issue 3, pp. 969-984. DOI: 10.1016/J.EJOR.2016.01.043
Pichpibul, T. (2015). Improving Vehicle Routing Decision for Travel Agency in Chonburi, Thailand. pp. 251-258. In: Gen, M., Kim, K., Huang, X., Hiroshi, Y. (eds) Industrial Engineering, Management Science and Applications 2015. Lecture Notes in Electrical Engineering, Vol. 349, Springer, Berlin, Heidelberg
Lopes Silva, M. A., de Souza, S. R., Freitas Souza, M. J., and Bazzan, A. L. C. (2019). A Reinforcement Learning-Based Multi-Agent Framework Applied for Solving Routing and Scheduling Problems. Expert Systems with Applications. Vol. 131, pp. 148-171. DOI: 10.1016/j.eswa.2019.04.056
Solomon, M. M. (1987). Algorithms for the Vehicle Routing and Scheduling Problems with Time Window Constraints. European Journal of Operational Research. Vol. 35, Issue 2, pp. 254-265. DOI: 10.1287/opre.35.2.254
Figliozzi, M. A. (2010). The Impacts of Congestion on Commercial Vehicle Tour Characteristics and Costs. Transportation Research Part E: Logistics and Transportation Review. Vol. 46, Issue4, pp. 496-506. DOI: 10.1016/j.tre.2009.04.005
Karoonsoontawong, A. (2015). Effcient Insertion Heuristics for Multitrip Vehicle Routing Problem with Time Windows and Shift Time Limits. Transportation Research Record: Journal of the Transportation Research Board. Vol. 2477, Issue 1, pp. 27-39. DOI: 10.3141/2477-04
Prasetyo, H., Alfatsani, M. A., and Fauza, G. (2018). Solving Capacitated Closed Vehicle Routing Problem with Time Windows (CCVRPTW) using BRKGA with local search. IOP Conference Series: Materials Science and Engineering. Vol. 352, DOI: 10.1088/1757-899x/352/1/012014
Wang, B., Liang, Y., Yuan, Meng, Zhang, H., and Liao, Qi. (2019). A Metaheuristic Method for the Multireturn-to-Depot Petrol Truck Routing Problem with Time Windows. Petroleum Science. Vol. 16, pp. 701-712. DOI: 10.1007/s12182-019-0316-8
Storn, R. and Price, K. (1997). Differential Evolution - A Simple and Efficient Heuristic for Global Optimization over Continuous Spaces. Journal of Global Optimization. Vol. 11, pp. 341-359. DOI: 10.1023/A:1008202821328
Sethanan, K. and Pitakaso, R. (2016). Differential Evolution Algorithms for Scheduling Raw Milk Transportation. Computers and Electronics in Agriculture. Vol. 121, pp. 245-259. DOI: 1016/j.compag.2015.12.021
Dechampai, D., Tanwanichkul, L., Sethanan, K., and Pitakaso, R. (2017). A Differential Evolution Algorithm for the Capacitated VRP with Flexibility of Mixing Pickup and Delivery Services and the Maximum Duration of a Route in Poultry Industry. Journal of Intelligent Manufacturing. Vol. 28, pp. 1357-1376. DOI: 10.1007/s10845-015-1055-3
Wang, B., Liang, Y., Yuan, M., Zhang, H., and Liao, Q. (2019). A Metaheuristic Method for the Multi return-to-Depot Petrol Truck Routing Problem with Time Windows. Petroleum Science. Vol. 16, pp. 701-712. DOI: 10.1007/s12182-019-0316-8
Dhoruri, A., Sari, E. R. and Lestari, D. (2013). Solving Capacitated Vehicle Routing Problems with Time Windows by Goal Programming Approach. In Proceeding of IndoMS International Conference on Mathemathics and Its Applications. pp. 155-162
