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

ปัญหาพนักงานขายเดินทาง (TSP) คืออะไร?

TSP ถาม: เส้นทางที่สั้นที่สุดที่เยี่ยมทุกจุดพอดีหนึ่งครั้งแล้วกลับจุดเริ่มต้นคืออะไร? เป็นปัญหาที่ศึกษามากที่สุดในการหาค่าเหมาะสมเชิงจัดหมู่

TSP เป็น NP-hard ไม่มีอัลกอริทึมที่แก้ได้สมบูรณ์ในเวลาพหุนาม วิธีปฏิบัติใช้ heuristic: เพื่อนบ้านใกล้สุด (เร็ว ไกลกว่าดีที่สุด ~25%), Clarke-Wright และ meta-heuristic

TSP ใช้ในการจัดส่งปลายทาง บริการภาคสนาม เจาะ PCB และเส้นทางหยิบสินค้าในคลัง

Formula: เป้าหมาย: min Σ d(route[i], route[i+1]) เพื่อนบ้านใกล้สุด: เยี่ยมจุดที่ยังไม่ไปที่ใกล้ที่สุด ประหยัด: s(i,j) = d(คลัง,i) + d(คลัง,j) − d(i,j)

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

คลัง (0,0) 4 จุด (3,4),(6,1),(8,5),(2,7) เพื่อนบ้านใกล้สุด: รวม 25.1 Clarke-Wright อาจหา 23.4

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

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

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

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

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

• เปรียบเทียบผลลัพธ์ Nearest Neighbor กับ Clarke-Wright
• เวลาคำนวณช่วยประเมินความเป็นไปได้ของการเปลี่ยนเส้นทางแบบเรียลไทม์
• การแสดงภาพแผนที่เส้นทางช่วยระบุความไม่มีประสิทธิภาพ

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

• Nearest Neighbor และการประหยัดแบบ Clarke-Wright (1964) — ฮิวริสติกเชิงสร้างที่นำมาเปรียบเทียบในเครื่องมือนี้
• การค้นหาเฉพาะที่ Lin-Kernighan — ฮิวริสติกอ้างอิงโดยพฤตินัยสำหรับเส้นทาง TSP คุณภาพสูง
• TSPLIB — คลังเกณฑ์เปรียบเทียบสาธารณะมาตรฐานที่ใช้เปรียบเทียบคุณภาพของตัวแก้ปัญหา TSP

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

ควรใช้อัลกอริทึมไหน?

ต่ำกว่า 15 จุด: เพื่อนบ้านใกล้สุด 15-50: Clarke-Wright + 2-opt 50+: meta-heuristic หรือ Google OR-Tools

TSP ต่างจากการจัดเส้นทางจัดส่งจริงอย่างไร?

จริงมีช่วงเวลา ความจุรถ การจราจร ถนนเดียว และหลายคัน TSP เป็นพื้นฐานแต่ซอฟต์แวร์จริงเพิ่มข้อจำกัดเหล่านี้