การแก้ปัญหาการจัดเส้นทางการขนส่งแบบมีกรอบเวลาโดยใช้วิธีเชิงพันธุกรรมแบบผสมผสานด้วยฮิวริสติกแบบแทรกไปข้างหน้าและวิธีการค้นหาคำตอบเฉพาะที่
Article Sidebar
Main Article Content
บทคัดย่อ
ปัญหาการจัดเส้นทางการขนส่งแบบมีกรอบเวลา (Vehicle Routing Problem with Time Window; VRPTW) เป็นส่วนขยายของปัญหาการจัดเส้นทางการขนส่ง (Vehicle Routing Problem; VRP) ที่มีการเพิ่มข้อจำกัดด้านกรอบเวลาเข้าในตัวแบบทางคณิตศาสตร์ VRP แบบดั้งเดิม ปัญหา VRPTW เป็นปัญหาแบบเอ็นพี-ฮาร์ด (NP-hard) ด้วยเหตุนี้การใช้เทคนิคแบบแม่นตรง (Exact Optimization Techniques) เพื่อที่จะหาคำตอบที่ดีที่สุดสำหรับปัญหา VRPTW จะมีความยุ่งยากเมื่อปัญหามีขนาดใหญ่ ดังนั้นในงานวิจัยนี้จึงเป็นการนำเสนออัลกอริทึมเชิงพันธุกรรมแบบผสมผสาน (hybrid Genetic Algorithm; hybrid GA) สำหรับการแก้ปัญหา VRPTWs ซึ่งอัลกอริทึม hybrid GA เป็นการบูรณาการระหว่างฮิวริสติกแบบแทรกไปข้างหน้า (Push Forward Insertion Heuristic; PFIH) วิธีเชิงพันธุกรรม (Genetic Algorithm; GA) และการค้นหาคำตอบเฉพาะที่จำนวน 3 วิธี (Three Local Searches) โดยที่ PFIH จะถูกนำมาใช้สำหรับการสร้างคำตอบเริ่มต้น (Initial Population) แทนที่การสุ่มของวิธีเชิงพันธุกรรมแบบดั้งเดิม ส่วนการค้นหาคำตอบเฉพาะที่ทั้ง 3 วิธี จะใช้ในขั้นตอนการปรับปรุงคำตอบให้ดียิ่งขึ้น จากนั้นอัลกอริทึมที่นำเสนอได้ถูกนำไปทดสอบประสิทธิภาพกับปัญหามาตรฐานจำนวน 14 ปัญหา โดยการสุ่มจาก 56 ปัญหา ของ Solomon ผลการศึกษาแสดงให้เห็นว่าอัลกอริทึมที่นำเสนอมีประสิทธิภาพในการหาคำตอบที่ดีเมื่อเปรียบเทียบกับปัญหามาตรฐานเหล่านี้
Article Details
บทความที่ลงตีพิมพ์เป็นข้อคิดเห็นของผู้เขียนเท่านั้น
ผู้เขียนจะต้องเป็นผู้รับผิดชอบต่อผลทางกฎหมายใดๆ ที่อาจเกิดขึ้นจากบทความนั้น
References
[2] J. F. Bard, G. Kontoravdis, and G. Yu, “A branchand-cut procedure for the vehicle routing problem with time windows,” Transportation Science, vol. 36, no. 2, pp. 250–269, 2002.
[3] M. Desrochers, J. Desrosiers, and M. Solomon, “A new optimization algorithm for the vehicle routing problem with time windows,” Operations Research, vol. 40, no. 2, pp. 342–354, 1992.
[4] N. Azi, M. Gendreau, and J.-Y. Potvin, “An exact algorithm for a vehicle routing problem with time windows and multiple use of vehicles,” European Journal of Operational Research, vol. 202, no. 3, pp. 756–763, 2010.
[5] W.-C. Chiang and R. A. Russell, “Simulated annealing metaheuristics for the vehicle routing problem with time windows,” Annals of Operations Research, vol. 63, no. 1, pp. 3–27, 1996.
[6] J. F. Cordeau, G. Laporte, and A. Mercier, “A unified tabu search heuristic for vehicle routing problems with time windows,” Journal of the Operational Research Society, vol. 52, no. 8, pp. 928-936, 2001.
[7] É. Taillard, P. Badeau, M. Gendreau, F. Guertin, and J.-Y. Potvin, “A tabu search heuristic for the vehicle routing problem with soft time windows,” Transportation Science, vol. 31, no. 2, pp. 170–186, 1997.
[8] G. Kontoravdis and J.F. Bard, “A GRASP for the vehicle routing problem with time windows, ” ORSA Journal on Computing, vol. 7, no. 1, pp. 10–23, 1995.
[9] G. B. Alvarenga, G. R. Mateus, and G. de Tomi, “A genetic and set partitioning two-phase approach for the vehicle routing problem with time windows,” Computers & Operations Research, vol. 34, no. 6, pp. 1561–1584, 2007.
[10] İ. Küçükoğlu and N. Öztürk, “An advanced hybrid meta-heuristic algorithm for the vehicle routing problem with backhauls and time windows,” Computers & Industrial Engineering, vol. 86, pp. 60–68, 2015.
[11] R. Baños, J. Ortega, C. Gil, A. L. Márquez, and F. de Toro, “A hybrid meta-heuristic for multiobjective vehicle routing problems with time windows,” Computers & Industrial Engineering, vol. 65, no. 2, pp. 286–296, 2013.
[12] E. Jabir, V. V. Panicker, and R. Sridharan, “Design and development of a hybrid ant colonyvariable neighbourhood search algorithm for a multi-depot green vehicle routing problem,” Transportation Research Part D: Transport and Environment, vol. 57, pp. 422–457, 2017.
[13] L. Cui, L. Wang, J. Deng, and J. Zhang, “A new improved quantum evolution algorithm with local search procedure for capacitated vehicle routing problem,” Mathematical Problems in Engineering, vol. 2013, pp. 17, 2013.
[14] M. A. Hannan, M. Akhtar, R. A. Begum, H. Basri, A. Hussain, and E. Scavino, “Capacitated vehiclerouting problem model for scheduled solid waste collection and route optimization using PSO algorithm,” Waste Management, vol. 71, pp. 31–41, 2018.
[15] 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.
[16] J. H. Holland, Adaptation in natural and artificial systems: An introductory analysis with applications to biology, control, and artificial intelligence. London, England: The MIT press, 1992.
[17] H. C. Brandão de Oliveira and G. C. Vasconcelos, “A hybrid search method for the vehicle routing problem with time windows,” Annals of Operations Research, vol. 180, no. 1, pp. 125–144, 2010.
[18] S. R. Thangiah, I.H. Osman, and T. Sun, “Hybrid genetic algorithm simulated annealing and tabu search methods for vehicle routing problem with time windows,” Computer Science Department, U.S.A., Technical Report 27., 1994.
[19] N. Wichapa and P. Khokhajaikiat, “Using the hybrid fuzzy goal programming model and hybrid genetic algorithm to solve a multi-objective location routing problem for infectious waste disposal,” Journal of Industrial Engineering and Management, vol. 10, no. 5, pp. 853–886, 2017.
[20] N. Wichapa and P. Khokhajaikiat, “Solving a multi-objective location routing problem for infectious waste disposal using hybrid goal programming and hybrid genetic algorithm,” International Journal of Industrial Engineering Computations, vol. 9, no. 1, pp. 75–98, 2018.
[21] M. M. Solomon. (2005, Oct.). Best Known Solutions Identified by Heuristics, Northeastern University, Massachusetts, Boston [Online]. Available: http://web.cba.neu.edu/~msolomon/heuristi.htm.