Solving Transportation Problem with Python PuLP
พิจารณาปัญหาการขนส่งอย่างง่าย. ในแต่ละสัปดาห์, เราต้องการทราบปริมาณขนส่งจากต้นทาง (เช่น โรงงาน) ไปยังปลายทาง (เช่น คลังสินค้าย่อยของแต่ละพื้นที่การขาย) เพื่อให้ได้ต้นทุนต่ำสุด โดยสอดคล้องกับข้อจำกัดเรื่องความสามารถในการผลิตของโรงงาน และปริมาณสินค้าขั้นต่ำที่คลังต้องจัดเก็บ.
โจทย์ (Example 14.3 Albright & Winston 2019): บริษัทมี 3 โรงงานผลิต และมี 4 คลังสินค้าย่อยกระจายในภาคต่างๆ ของประเทศ. ในแต่ละสัปดาห์, โรงงานมีความสามารถในการผลิตจำกัด ดังแสดงในช่อง Capacity. ปริมาณขั้นต่ำที่คลังต้องมีดังแสดงในแถว Demand. ค่าขนส่งต่อหน่วยแสดงตรงกลางของตาราง.
บริษัทต้องการหาแผนการขนส่ง (ปริมาณที่ส่งจากแต่ละโรงงานไปยังแต่ละคลัง) เพื่อให้ได้ต้นทุนต่ำสุด โดยปริมาณรวมที่แต่ละโรงงานส่งต้องไม่เกินกำลังการผลิตในแต่ละสัปดาห์ และปริมาณรวมที่แต่ละคลังได้รับต้องไม่น้อยกว่า demand.
Network diagram สำหรับ transportation problem ข้างต้น ดังแสดงในรูป
โดยทั่วไป, transportation problem ประกอบด้วย nodes (วงกลม) และ arcs (เส้นทาง) โดย arc มีลูกศรออกแสดงต้นทางและลูกศรเข้าแสดงปลายทาง. ตัวเลขบน arc คือค่าขนส่งต่อหน่วย. ตัวเลขตรง origin node ทางซ้าย คือ supply สำหรับแต่ละ origin. ตัวเลขตรง demand node ทางขวา คือ demand สำหรับแต่ละ destination.
ปัญหาข้างต้นเป็น linear programming model สามารถใช้ PuLP หาคำตอบได้
ด้านบนตรง #dataเป็นส่วนของข้อมูลนำเข้า
Line 4–5 list ชื่อโรงงานในตัวแปร PLANT และชื่อคลังในตัวแปร REGION
Line 6 สร้างเส้นทางจากทุกโรงงานไปยังทุกคลัง
Line 7–11 สร้าง dictionary ชื่อ plantCap เก็บข้อมูลกำลังการผลิตของแต่ละโรงงาน
Line 12–17 ทำนองเดียวกัน ตัวแปร regionDemand เก็บ demand ของแต่ละคลัง
Line 18–23 ตัวแปร shipping cost เก็บค่าขนส่งต่อหน่วยของแต่ละโรงงานไปยังแต่ละคลัง
ด้านล่างตรง #model เป็นส่วนของตัวแบบ linear programming
Line 26 สร้างปัญหา minimization เก็บไว้ในตัวแปรชื่อ mod
Line 27 ระบุ decision variable xShipโดยใช้ฟังก์ชัน LpVariable.dicts. สังเกตว่า xShip มี index อยู่บน (PLANT, REGION) เนื่องจากเราต้องระบุว่าส่งจากโรงงานใดไปที่คลังในภูมิภาคใด
Line 28 ระบุ objective function โดยใช้ฟังก์ชัน lpSum คำนวณผลรวมของค่าขนส่งทั้งหมดทุกเส้นทางใน ARC
Line 29–30 ระบุ constraint ที่บอกว่า สำหรับแต่ละโรงงาน i (ใน list PLANT), ปริมาณขนส่งรวมที่ออกจากโรงงานนี้ไปยังทุกคลังทั้งหมดในภูมิภาค (ใน list REGION) ต้องไม่เกินกำลังการผลิตของโรงงาน plantCap[i]
Line 31–32 ระบุ constraint ที่บอกว่า สำหรับแต่ละคลัง j (ใน list REGION), ปริมาณที่คลังรับรวมจากทุกโรงงาน (ใน list PLANT) ต้องอย่างน้อยความต้องการของคลัง regionDemand[j]
เรา optimize ตัวแบบข้างต้น แสดงปริมาณขนส่งที่ดีสุดจากโรงงานไปคลัง (เฉพาะเส้นทางที่มีการขนส่ง นั่นคือมี flow > 0) ได้ดังนี้
ต้นทุนต่ำสุดที่ได้คือ 176,050 ต่อสัปดาห์. แผนการขนส่งที่ดีสุดสามารถ ดังแสดงในรูป เช่น Plant1 ส่งไป Region1 และ Region4 เป็นจำนวน 150 และ 300 หน่วยตามลำดับ เป็นต้น
สังเกตว่าในโจทย์นี้ กำลังการผลิตรวมของทุกโรงงาน มากกว่า ปริมาณความต้องการรวมของทุกคลัง
total supply = 450+600+500 = 1550 > 1250 = total demand
ปริมาณขนส่งที่ดีสุด optimal flow รวมกันได้ 150+300+…+200+300=1250. ใน constraint ตรง demand node (Line 32 ของ code) สามารถเปลี่ยนจาก ≥ เป็น = ได้และได้ optimal solution เช่นเดิม. หาก total supply = total demand, สามารถเปลี่ยนเครื่องหมายทั้งสอง constraints เป็น = ได้.
อนึ่ง ใน transportation model ที่มี supply ที่ origin และ demand ที่ destination เป็นจำนวนเต็ม, optimal flow ที่ได้จะเป็น integer (เนื่องจาก constraint matrix เป็น totally unimodular), จึงไม่จำเป็นต้องใส่ LPInteger ตอนที่ระบุ decision variable.
หากมีต้นทางและปลายทางเป็นจำนวนมาก อาจไม่ต้องการใช้ string เรียกชื่อ node. เราสามารถใช้ตัวเลขแทนได้ดังนี้
ใน network, หากเรามีศูนย์กระจายสินค้า ที่อยู่ระหว่างต้นทางและปลายทาง แล้วเราสามารถแก้ปัญหาได้โดย minimum-cost network flow model ใน blog นี้
เอกสารอ้างอิง
S. C. Albright and W. L. Winston (2019). Business Analytics: Data Analysis and Decision Making. Mason: South-Western Cengage Learning.
