Minimum-Cost Network Flow with Excel (and Python PuLP)
พิจารณาปัญหาการกระจายสินค้า ขนส่งจาก supply nodes ไปยัง demand nodes โดยสามารถผ่าน transshipment nodes (เช่น distribution center (DC)) เพื่อให้ได้ต้นทุนขนส่งรวมต่ำสุด โดยที่สามารถตอบสนองความต้องการลูกค้า และไม่เกินความสามารถในการผลิตที่ supply node.
หากไม่มี transshipment nodes สามารถแก้ปัญหาได้โดยใช้ transportation model เช่น blog นี้.
โจทย์ปัญหาตัวอย่าง (Example 14.4 Albright & Winston 2019) ดังในรูป
- Supply nodes 1,2,3 เป็นโรงงาน โดยมีกำลังการผลิตต่อเดือน คือ 200, 300 และ 100 หน่วยตามลำดับ.
- Demand nodes 6,7 เป็น retailer โดยมีความต้องการสินค้า (demand) ต่อเดือนคือ 400 และ 180 หน่วยตามลำดับ.
- Transshipment nodes 4,5 คือ ศูนย์กระจายสินค้า (DC) ซึ่งไม่ได้ผลิตสินค้าและไม่ได้ให้ลูกค้า (end customer) มารับสินค้าโดยตรงที่ DC แต่จะส่งให้ retailer.
สังเกตว่าในตัวอย่างนี้ กำลังการผลิตรวมมากกว่าปริมาณความต้องการรวม
total supply = 600 ≥580 = total demand.
ค่าขนส่งต่อหน่วยในแต่ละเส้นทาง (arc) ดังแสดงในตาราง (หน่วย: บาทต่อหน่วย)
นอกจากนี้ สมมติว่าแต่ละเส้นทาง ปริมาณขนส่งต้องไม่เกิน 200 ซึ่งจะเรียกว่า arc capacity. ในโจทย์ข้อนี้ arc capacity เท่ากันหมดทุกเส้นทาง; ในทางปฏิบัติ arc capcity ไม่จำเป็นต้องกัน ขึ้นกับสภาพเส้นทางระหว่างต้นทางปลายทางนั้น เช่น หากเป็นถนนชนบท น้ำหนักบรรทุกของรถแต่ละคันอาจจะน้อยกว่าเส้นทางที่เป็น highway.
เราต้องการหาปริมาณขนส่ง (flow) แต่ในละเส้นทาง เพื่อให้ต้นทุนรวมต่ำสุด: นั่นคือ
Decision variable: Flow ≥ 0, ≤ (arc capacity)
Minimize (total cost) = ผลรวมของ (unit cost)*flow รวมกันทุกเส้นทาง
สำหรับแต่ละ node n, balance constraint เป็นตามนี้
- Supply constraint:
(flow out of n) - (flow into n) ≤ (supply at n) - Transshipment constraint:
(flow out of n) - (flow into n) = 0 - Demand constraint:
(flow into n) - (flow out of n) ≥ (demand at n)
ใน minimum cost network flow model ที่มี supply, demand ทุก node และ arc capacity เป็นจำนวนเต็ม, optimal flow ที่ได้จะเป็น integer (เนื่องจาก constraint matrix เป็น totally unimodular), จึงไม่จำเป็นต้องใส่กำหนดให้ decision variable เป็น integer.
Excel
ตัวอย่าง Excel ในรูป โดยมี input data คือ unit cost, arc capacity, supply, demand ใน cell สีน้ำเงิน
Cell C36: ต้นทุนรวม total shipping cost จากสูตร
=SUMPRODUCT(C8:C33,D8:D33)Cell I8: Outflow คำนวณปริมาณรวมที่ขนส่งจากแต่ละ node (outflow)
=SUMIF($A$8:$A$33,H8,$D$8:$D$33)Cell J8: Inflow คำนวณปริมาณรวมที่ขนส่งเข้าสู่แต่ละ node (inflow)
=SUMIF($B$8:$B$33,H8,$D$8:$D$33)Cell M8: Net inflow = inflow-outflow =J8 — I8
Cell O8: Net demand = demand-supply =L8-K8
เราสามารถ optimize ได้ดังนี้.
ปัญหา minimum cost network flow ที่พิจารณาอยู่นี้ linear programming จึงใช้ algorithm คือ Simplex LP. เราจะได้ optimal solution คือ node 1 ส่งไป node 3 เป็นจำนวน 180 หน่วย, node 2 ส่งผ่านไป DC node 4 จำนวน 120 หน่วย และส่งตรงไปลูกค้า node 6 จำนวน 180 หน่วยตามลำดับ เป็นต้น. จากแผนการกระจายสินค้านี้ ทำให้ได้ต้นทุนรวมต่ำสุดคือ 3260 บาท.
สังเกตว่า balance constraint ที่ใส่เข้าไปใน Solver คือ สำหรับแต่ละ node n
net inflow ≥ net demand นั่นคือ
(flow into n)-(flow out of n) ≥ (demand at n) -(supply at n).
เมื่อ optimize แล้วที่ transshipment node จะได้ inflow = outflow ตามใน balance constraint ใน section ที่อยู่ด้านบนสุด.
Python
ตัวอย่าง Python code สำหรับปัญหาข้างต้น
ส่วนบนของ code เป็น input data ระบุชื่อ node (ใน list ชื่อ nodes). ใน ตัวแปร nodeData เป็น dictionary โดยตัวแรกใน list คือ demand และตัวหลังคือ supply. หาก node นั้นเป็น transshipment node (nodes 4, 5) จะมี demand=supply=0. ในตัวแปร arcData เป็น dictionary โดยเป็น list ของ unit cost, lower bound และ upper bound (arc capacity) ตามลำดับ.
สังเกตว่า balance constraint ที่อยู่ใน Line 87–90 สำหรับแต่ละ node n
net inflow ≥ net demand นั่นคือ
(flow into n) - (flow out of n) ≥ (demand at n) - (supply at n) นั่นคือ
(supply at n) + (flow into n) ≥ (demand at n) + (flow out of n).
เมื่อ optimize แล้วจะได้แผนการขนส่ง optimal solution ที่ทำให้ได้ต้นทุนต่ำสุด ตามนี้
Code ดัดแปลงมาจาก
Sensitivity Analysis
หากเลือกให้แสดง Sensitivity Report จาก Excel จะได้ reduced cost ซึ่งแสดงผลจากการเปลี่ยนแปลงของ unit cost ตามนี้:
สำหรับเส้นทางของ Cell D8 (จาก node 1 ไป 2), ไม่มีการขนส่ง (flow = 0 ซึ่งอยู่ที่ lower bound); reduced cost = 2 แปลผลได้ว่า หาก unit cost ในเส้นทางนี้ลดลงมามากกว่า 2 บาท/หน่วย (นั่นคือ น้อยกว่า 5–2 = 3 บาท/หน่วย), จะเริ่มมีการขนส่งในเส้นทางนี้.
สำหรับเส้นทางของ Cell D30 (จาก node 5 ไป 6), มีการขนส่งอยู่ที่ปริมาณสูงสุด (flow = 200 = arc capacity ซึ่งอยู่ที่ upper bound); reduced cost = -5 แปลผลได้ว่า หาก unit cost ในเส้นทางนี้ เพิ่มขึ้นไปมากกว่า 5 บาท/หน่วย (นั่นคือ มากกว่า 2+5 = 7 บาท/หน่วย), ปริมาณขนส่งจะลดลงมาจาก upper bound.
ผลจากการเปลี่ยนแปลงของ supply และ demand สามารถดูได้จาก shadow price ในตารางด้านล่าง
โรงงาน 3 มีกำลังการผลิตปัจจุบันอยู่ที่ 100 หน่วยต่อเดือน; จากตาราง มี shadow price = 3 แปลผลได้ว่า หากโรงงานนี้มีกำลังการผลิตเพิ่มขึ้น 1 หน่วยต่อเดือน จะทำให้ได้ต้นทุนรวมลดลง 3 บาท. การแปลผลทำนองเดียวกันสำหรับโรงงาน 2. สำหรับโรงงาน 1 ข้อจำกัดเป็น non-binding constraint และมี shadow price = 0 หากมีกำลังการผลิตเพิ่มก็ไม่ได้ส่งผลต่อ optimal objective value. (หากเขียน constraint เป็น net outflow ≤ supply จะได้ shadow price = -3.)
ปัจจุบัน retailer 3 มี demand อยู่ที่ 180 หน่วยต่อเดือน; จากตาราง มี shadow price = 12 แปลผลได้ว่า หาก retailer นี้มี demand เพิ่มขึ้น 1 หน่วยต่อเดือน จะทำให้ต้นทุนรวมเพิ่มขึ้น 12 บาท. สำหรับ shadow price = 12 นี้ใช้ได้เฉพาะการเปลี่ยนแปลงของ R.H. side เพิ่มขึ้นไม่เกิน Allowable Increase และลดลงไม่เกิน Allowable Decrease นั่นคือใช้ได้เฉพาะในช่วง (180–80, 180+20) = (100, 200) เท่านั้น.
Excel Solver’s sensitivity report แสดงผลลัพธ์จากการเปลี่ยนแปลงของ input ค่าใดค่าหนึ่งค่าเดียวเท่านั้น. หากเราต้องการอยากเปลี่ยนหลาย input พร้อมกัน สามารถใช้ Python สร้างเป็น function ได้. ตัวอย่างเช่น ในโจทย์ข้างต้น, arc capacity=200 หน่วยสำหรับทุกเส้นทาง, เราต้องการทราบต้นทุนที่เปลี่ยนไป หาก arc capacity เปลี่ยนจาก 200 เป็น 150, 300 ตามลำดับ.
เมื่อเรา invoke function จะได้ผลการเปลี่ยนแปลงดังนี้
หากเราสามารถขนส่งได้เป็นจำนวนมากขึ้นในแต่ละเส้นทาง เช่น arc capacity เพิ่มขึ้นจาก 200 เป็น 300 หน่วย จะทำให้ได้ต้นทุนรวมลดลงจาก 3260 เป็น 2320. ในทางกลับกัน หาก arc capacity ลดลงจาก 200 เป็น 150 หน่วย จะส่งผลให้ต้นทุนรวมเพิ่มขึ้นเป็น 4120 เป็นต้น. เราสามารถแสดงต้นทุนรวมที่เปลี่ยนไปตาม arc capacity ได้ในรูปนี้
เมื่อ arc capacity มีค่าเพิ่มขึ้น (เช่น รถบรรทุกขนาดใหญ่ขึ้น), ต้นทุนรวมที่ได้จะลดต่ำลง โดยมีอัตราการลดลงที่ไม่เท่ากัน. สังเกตว่า เมื่อ arc capacity > 300 ต้นทุนรวมยังคงเป็น 2320 เช่นเดียวกับที่ arc capacity = 300, จึงไม่จำเป็นต้องหารถบรรจุที่มีขนาดใหญ่ขึ้นกว่า 300 หน่วย.
เอกสารอ้างอิง
S. C. Albright and W. L. Winston (2019). Business Analytics: Data Analysis and Decision Making. Mason: South-Western Cengage Learning.
