วิธืฮิวริสติก GRASP สำหรับปัญหาการจัดเส้นทางยานพาหนะ GRASP Heuristic for Vehicle Routing Problem

Abstract

บทคัดย่อ

งานวิจัยนี้นำเสนอวิธีฮิวริสติกสำหรับปัญหาการจัดเส้นทางยานพาหนะ (Vehicle routing problem) ผู้วิจัยได้ประยุกต้ใ,ซํวิธีฮิวริสติก Greedy Randomized Adaptive Search Procedure (GRASP) สำหรับ การค้นหาคำตอบ โดยมีวัตถุประสงค์เพิอให้ระยะทางรวมตาสุด ภายใต้เงื่อนไขความต้องการสินค้า ของลูกค้าแต่ละรายไม^,แน่นอน ความจุของยานพาหนะมีจำนวนจำก้ด กระบวนการทำงานของ GRASP แบ่งเป็น 2 ระยะคือ ระยะแรก เป็นการสร้างคำตอบเริ่มต้น (Initial solution phase) ๆเงพิจารณาพื้นที่ ของคำตอบที่เป็นไปได้ที่ไม^,ขดแย้งกับเงื่อนไข และระยะที่สองเป็นการปรับปรุงคุณภาพคำตอบ โดยวิธี 2-opt, Swap operator and Move exchanges ผลการทดสอบพบว่า วิธีฮิวริสติกที่นำเสนอให้ ผลลัพธ์อยู่ในระดับที่ดี สามารถลดระยะทางขนส่งจากเดิม 154.8 กิโลเมตรต่อวัน ลดลงเหลือ 120.5 กิโลเมตรต่อวัน คิดเป็น 19.25%

คำสำคัญ : ฮิวริสติก GRASP ปัญหาการจัดเส้นทางยานพาหนะ ความต้องการสินค้าไม่^,แน่นอน

Abstract

This paper presents heuristic for solving the vehicle routing problem. We apply a Greedy Randomized Adaptive Search Procedure (GRASP) to solve for solutions with the objective of minimizing the total distance traveled. The demand from each customer is uncertain and the vehicle capacity is limited. GRASP consists of two phase. The first phase is to construct an initial feasible solution and in the second phases, the solution is improved by applying local search methods that are 2-opt, Swap and Move exchanges procedures. The computational results show that the proposed heuristic provides good solutions. The total distance can be decreased from 154.8 kilometers to 120.5 kilometers reduced by 19.25 %

Keywords : Heuristic GRASP; Vehicle routing problem; Uncertain demand