การแก้ปัญหาการจัดเส้นทางการขนส่งแบบมีกรอบเวลาโดยใช้วิธีเชิงพันธุกรรมแบบผสมผสานด้วยฮิวริสติกแบบแทรกไปข้างหน้าและวิธีการค้นหาคำตอบเฉพาะที่

Solving the vehicle routing problems with time windows using hybrid genetic algorithm with push forward insertion heuristic and local search procedure

Name: นรงค์ วิชาผา

Organization : มหาวิทยาลัยกาฬสินธุ์. คณะวิศวกรรมศาสตร์และเทคโนโลยีอุตสาหกรรม

Email : narong.wi@ksu.ac.th

Name: ไทยทัศน์ สุดสวนสี

Organization : มหาวิทยาลัยกาฬสินธุ์. คณะวิศวกรรมศาสตร์และเทคโนโลยีอุตสาหกรรม

Name: พรเทพ ขอขจายเกียรติ

Organization : มหาวิทยาลัยขอนแก่น. คณะวิศวกรรมศาสตร์

keyword: วิธีเชิงพันธุกรรมแบบผสมผสาน

ThaSH: ปัญหาการจัดเส้นทางเดินรถ

ThaSH: ฮิวริสติกอัลกอริทึม

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

Abstract: 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.

มหาวิทยาลัยเทคโนโลยีพระจอมเกล้าพระนครเหนือ. สำนักหอสมุดกลาง

Address: กรุงเทพมหานคร

Email: library@kmutnb.ac.th

Created: 2562

Modified: 2562-05-13

Issued: 2562-05-13

บทความ/Article

application/pdf

BibliograpyCitation : วารสารวิชาการพระจอมเกล้าพระนครเหนือ. ปีที่ 29, ฉบับที่ 1 ‪(ม.ค.-มี.ค. 62)‬, หน้า 4-13

tha

©copyrights มหาวิทยาลัยเทคโนโลยีพระจอมเกล้าพระนครเหนือ

ลำดับที่.	ชื่อแฟ้มข้อมูล	ขนาดแฟ้มข้อมูล	จำนวนเข้าถึง	วัน-เวลาเข้าถึงล่าสุด
1	atc_62_290101.pdf	1.01 MB	64	2025-04-27 13:45:36

ใช้เวลา

0.030254 วินาที