Solving the Vehicle Routing Problems with Time Windows Using Hybrid Genetic Algorithm with Push Forward Insertion Heuristic and Local Search Procedure

Abstract

ปัญหาการจัดเส้นทางการขนส่งแบบมีกรอบเวลา (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 ผลการศึกษาแสดงให้เห็นว่าอัลกอริทึมที่นำเสนอมีประสิทธิภาพในการหาคำตอบที่ดีเมื่อเปรียบเทียบกับปัญหามาตรฐานเหล่านี้

The Vehicle Routing Problem with Time Windows (VRPTW) is a kind of important variant of VRP with adding time windows constraints to the model. The VRPTW is classified as an NP-hard problem. Hence, the use of exact optimization techniques may be hard to solve these problems in acceptable CPU times, when the problem involves real-world data sets that are very large. To solve this problem, this paper suggests a hybrid genetic algorithm (hybrid GA) combined with Push Forward Insertion Heuristic (PFIH) to make an initial solution instead of traditional GA and three local searches to neighborhood search and improving method. The proposed algorithm was tested on fourteen instances from an online data set in the Solomon`s 56 benchmark problems-selected randomly. The results indicate the good quality of the proposed algorithm.