VRP เพิ่มประสิทธิภาพเส้นทาง

ปัญหาจัดเส้นทางยานพาหนะ (VRP) คืออะไร?

VRP ขยาย TSP เป็นหลายคัน แต่ละคันมีข้อจำกัดความจุ จากคลังกลาง เป้าหมายคือลดระยะทางรวมโดยรับประกันบริการทุกลูกค้าไม่เกินความจุ

CVRP เป็นรูปแบบที่พบบ่อยที่สุด Heuristic: เพื่อนบ้านใกล้สุด, Clarke-Wright, GA และ ALNS

VRP เป็นรากฐานของการดำเนินงานโลจิสติกส์ การเพิ่มประสิทธิภาพลดระยะทาง 15-25% เทียบกับการวางแผนด้วยมือ

Formula: เป้าหมาย: min Σ(ระยะทางรถ) เงื่อนไข: - ลูกค้าแต่ละรายเยี่ยม 1 ครั้ง - รถแต่ละคันเริ่มและจบที่คลัง - Σ(อุปสงค์บนเส้นทาง) ≤ ความจุ

ตัวอย่างการคำนวณ

คลังที่ (0,0) ลูกค้า 6 รายที่ (2,8), (5,9), (9,2), (−6,3), (1,5), (7,−1) ความต้องการ [10, 15, 20, 25, 10, 20] ความจุรถ = 50 รถ 3 คัน วิธีประหยัด (savings) ได้ผล: รถคันที่ 1 ส่งลูกค้า 5, 1, 2 (ความต้องการ = 35, ระยะทาง = 21.7) รถคันที่ 2 ส่งลูกค้า 3, 6 (ความต้องการ = 40, ระยะทาง = 19.9) รถคันที่ 3 ส่งลูกค้า 4 (ความต้องการ = 25, ระยะทาง = 13.4) ระยะทางรวม = 55.0 เพื่อนบ้านใกล้ที่สุดบนข้อมูลเดียวกันต้องใช้ 67.5

เมื่อใดควรใช้เครื่องคำนวณนี้

• ผู้จัดการยานพาหนะวางแผนเส้นทางจัดส่งประจำวันสำหรับรถบรรทุกหลายคัน
• ผู้วางแผนโลจิสติกส์เพิ่มประสิทธิภาพการกระจายจากศูนย์กระจายสินค้า
• บริษัทเก็บขยะออกแบบเส้นทางรถเก็บขยะ
• บริษัทจัดส่งอาหารลดระยะทางยานพาหนะ

ข้อผิดพลาดที่พบบ่อยที่ควรหลีกเลี่ยง

• ใช้รถน้อยเกินไป
• ไม่สนใจข้อจำกัดจริงนอกเหนือจากความจุ
• ตั้งความจุรถสูงเกินจริงสำหรับทดสอบ
• ไม่เปรียบเทียบผลลัพธ์อัลกอริทึม

วิธีตีความผลลัพธ์

• จำนวนรถที่ใช้น้อยกว่าสูงสุดที่กำหนดแสดงว่าอัลกอริทึมหาคำตอบที่มีประสิทธิภาพ
• เปรียบเทียบระยะทางรวมกับขอบเขตล่าง: เส้นทางที่เหมาะสมควรเป็น 40-60% ของขอบเขตล่าง
• รายละเอียดเส้นทางที่แสดงภาระไม่สมดุลอาจต้องปรับด้วยตนเอง

มาตรฐานและเอกสารอ้างอิงที่เกี่ยวข้อง

• Dantzig & Ramser (1959), "The Truck Dispatching Problem" — การกำหนดสูตรดั้งเดิมของปัญหาการจัดเส้นทางยานพาหนะ
• อัลกอริทึมการประหยัด Clarke & Wright (1964) — ฮิวริสติกเชิงสร้างแบบคลาสสิกสำหรับ VRP ที่มีข้อจำกัดความจุ
• CVRPLIB — ชุดอินสแตนซ์เกณฑ์เปรียบเทียบ VRP ที่มีข้อจำกัดความจุมาตรฐานสำหรับการเปรียบเทียบคุณภาพของผลเฉลย

คำถามที่พบบ่อย

ต้องใช้กี่คัน?

ขั้นต่ำ = ceil(อุปสงค์รวม / ความจุ) จริงต้องเพิ่ม 10-30% จากการกระจายทางภูมิศาสตร์

ALNS คืออะไร? เมื่อไหร่ควรใช้?

Adaptive Large Neighborhood Search ทำลายและสร้างส่วนของคำตอบซ้ำๆ ดีเยี่ยมสำหรับขนาดใหญ่ (100+ ลูกค้า) ให้คำตอบภายใน 1-3% ของค่าที่ดีที่สุด