Page Header

ระบบชาญฉลาดวางแผนเส้นทางอัตโนมัติโดยขั้นตอนวิธีเชิงพันธุกรรมออนไลน์
Intelligence Online System for Automatic Route Planning by Using Genetic Algorithm

Woranit Thongyu, Krit Somkantha, Wilaiporn Kultangwattana

Abstract


งานวิจัยฉบับนี้ได้เสนอการประยุกต์ใช้ขั้นตอนวิธีเชิงพันธุกรรม (Genetic Algorithm) เพื่อสร้างเส้นทางอัตโนมัติออนไลน์ โดยจะนำข้อมูลเส้นทางเดินของพนักงานจ่ายพัสดุเพื่อนำข้อมูลไปวิเคราะห์และปรับปรุงเส้นทางการนำจ่ายพัสดุของระบบบริการขนส่งแบบด่วนพิเศษในจังหวัดอุดรธานีให้ได้เส้นทางที่ดีที่สุดสั้นที่สุด ประหยัดเวลา และสะดวกสบาย เพื่อให้ทันต่อความต้องการของลูกค้าและการใช้ทรัพยากรที่น้อยที่สุดไม่ว่าจะเป็นด้านเวลาและระยะทางของเส้นทาง เพื่อที่จะใช้บริหารทรัพยากรให้คุ้มค่ามากที่สุดในการเดินทางของพนักงานขนส่งพัสดุในจังหวัดอุดรธานี ซึ่งพนักงานนำจ่ายพัสดุจะทำการกำหนดสถานที่ในการจัดส่งตามจำนวนที่ต้องการ จากนั้นระบบจะทำการประมวลผลเพื่อหาเส้นทางที่ดีที่สุดโดยจะเดินทางไปในทุกจุดที่กำหนดไว้โดยใช้ขั้นตอนวิธีเชิงพันธุกรรม ในการทดสอบประสิทธิภาพของงานวิจัยที่นำเสนอผู้วิจัยได้ทำการทดสอบเปรียบเทียบกับวิธีการค้นหาแบบที่ดีที่สุดกรีดี (Greedy Best First Search) การค้นหาแบบเอ-สตาร์ (A* Search) และการค้นหาโดยพนักงานนำจ่ายพัสดุที่มีความเชี่ยวชาญในการส่งของ ซึ่งจากผลการทดลองพบว่าวิธีการที่นำเสนอสามารถจัดการหาเส้นทางที่ดีมากกว่าวิธีการที่นำมาเปรียบเทียบทั้งด้านระยะทางและเวลา และจากการทดสอบความพึงพอใจของผู้ใช้พบว่าระบบที่นำเสนอมีความพึงพอใจของผู้ใช้ในระดับที่ดี ซึ่งจากการทดสอบทั้งหมดพบว่าวิธีการที่นำเสนอสามารถหาเส้นทางที่เหมาะสมได้อย่างมีประสิทธิภาพและเหมาะสมที่จะเป็นเครื่องมือในการช่วยเหลือพนักงานขนส่งให้สามารถทำงานได้อย่างมีประสิทธิภาพมากขึ้น

This research proposes the application of genetic algorithms to create online automated routes by using the distributer staff’s routes to analyze and improve the distribution routes in the transportation system in Udon Thani province in Thailand in order to determine the best and shortest routes, the lowest cost, and the shortest and most convenient period of time in order to serve the customer needs by using minimal resources. The distributor staff will define a delivery destinations according to the number of packages. Then the system’s process begins to find the best routes to travel to all of the desired destinations by using a genetic algorithm. The research effectiveness was tested by comparing the algorithm’s search with the Greedy Best First Search, the A*search and the manual search by the distributer staff who are experts in delivery. The results revealed that the method proposed can handle the deliveries better than the other methods both in terms of the distance and time. The user satisfaction test result was at the good level. The tests indicated that the proposed method is able to determine the proper route effectively and is a suitable tool for helping the distributor staff to work more efficiently.


Keywords



Full Text: PDF

DOI: 10.14416/j.kmutnb.2018.09.002

ISSN: 2465-4698