ปัญหาพนักงานขายที่ต้องเดินทาง (TSP)
ปัญหาพนักงานขายที่ต้องเดินทาง (Traveling Salesman Problem หรือ TSP) เป็นปัญหาที่ได้รับความนิยมและมีการนำไปใช้จริงในด้านโลจิสติกส์ ในปัญหา TSP พนักงานขายจะได้รับรายชื่อเมืองพร้อมระยะทางระหว่างแต่ละคู่เมือง โดยต้องหาเส้นทางที่สั้นที่สุดที่เริ่มจากจุดต้นทาง ผ่านทุกเมือง แล้วกลับมายังเมืองต้นทางอีกครั้ง ปัญหานี้มีความซับซ้อนในการคำนวณสูง แต่ Miller-Tucker-Zemlin (MTZ) ได้แสดงให้เห็นว่าสามารถแก้ได้ด้วย Integer Linear Programming ในแบบฝึกหัดนี้ คุณจะกำหนดฟังก์ชันวัตถุประสงค์และเงื่อนไขบางส่วนสำหรับ TSP โดยใช้ชุดข้อมูลขนาดเล็กที่มี 15 เมือง (ดูรูปภาพด้านล่าง) เป้าหมายคือฝึกใช้ LpVariable.dicts ร่วมกับ list comprehension
ตัวแปร Python สามตัว ได้แก่ n, cities และ dist ถูกสร้างไว้ให้แล้ว\(^{1}\) โดย n คือจำนวนเมือง, cities คือรายการเมืองที่มีหมายเลขกำกับ และ dist คือ pandas DataFrame ที่เก็บระยะทางระหว่างแต่ละคู่เมือง สามารถสำรวจข้อมูลเหล่านี้ได้ใน console นอกจากนี้ โมเดลได้ถูกกำหนดค่าเริ่มต้นให้แล้ว
\(^{1}\) ชุดข้อมูลมาจาก Gerhard Reinelt, TSPLIB - A Traveling Salesman Problem Library, ORSA Journal on Computing,
แบบฝึกหัดนี้เป็นส่วนหนึ่งของหลักสูตร
Supply Chain Analytics ด้วย Python
แบบฝึกหัดเชิงโต้ตอบแบบลงมือทำ
ลองทำแบบฝึกหัดนี้โดยเติมโค้ดตัวอย่างนี้ให้สมบูรณ์
# Define Decision Variables
x = LpVariable.dicts('X', [(____, ____) for c1 in ____ for c2 in ____],
cat='____')
u = LpVariable.dicts('U', [____ for c1 in ____],
lowBound=0, upBound=(n-1), cat=____)