การเพิ่มประสิทธิภาพเส้นทาง 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) เพื่อนบ้านใกล้ที่สุด: ไป (3,4) d=5.0 แล้ว (2,7) d=3.2 แล้ว (8,5) d=6.3 แล้ว (6,1) d=4.5 กลับ d=6.1 รวม = 25.04 (ผลรวมช่วงที่ปัดเศษได้ 25.1) เมื่อมี 4 จุด นี่คือเส้นทางที่สั้นที่สุดแล้ว — ไม่มีลำดับใดใน 24 ลำดับที่สั้นกว่า — และวิธีประหยัด (savings) ก็ได้ 25.04 เท่ากัน

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

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

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

• สมมติว่าผลลัพธ์เพื่อนบ้านใกล้สุดคือค่าที่ดีที่สุด
• ใช้ระยะทางเส้นตรงสำหรับเส้นทางถนน
• ลืมรวมเที่ยวกลับไปคลัง
• ใช้ 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 เป็นพื้นฐานแต่ซอฟต์แวร์จริงเพิ่มข้อจำกัดเหล่านี้