ปัญหาการไหลเวียนของสินค้าหลายชนิด (multi-commodity flow problem ) คือปัญหาการไหลเวียนในเครือข่ายที่มีสินค้าหลายชนิด (ความต้องการการไหลเวียน) ระหว่างโหนดต้นทางและปลายทางที่แตกต่างกัน

กำหนดให้เครือข่ายการไหล โดยที่ขอบมีความจุ มีสินค้าซึ่งกำหนดโดย โดยที่และคือแหล่งที่มาและปลายทางของสินค้าและคือความต้องการของสินค้า ตัวแปรกำหนดสัดส่วนของการไหลตามขอบโดยที่ในกรณีที่การไหลสามารถแบ่งออกเป็นหลายเส้นทางได้ และ ในกรณีอื่น ๆ (เช่น "การกำหนดเส้นทางเดียว") จงหาการกำหนดค่าของตัวแปรการไหลทั้งหมดที่สอดคล้องกับข้อจำกัดสี่ข้อต่อไปนี้: ${\displaystyle \,G(V,E)}$${\displaystyle (u,v)\in E}$${\displaystyle \,c(u,v)}$${\displaystyle \,k}$${\displaystyle K_{1},K_{2},\dots ,K_{k}}$${\displaystyle \,K_{i}=(s_{i},t_{i},d_{i})}$${\displaystyle \,s_{i}}$${\displaystyle \,t_{i}}$${\displaystyle \,i}$${\displaystyle \,d_{i}}$${\displaystyle \,f_{i}(u,v)}$${\displaystyle \,i}$${\displaystyle \,(u,v)}$${\displaystyle \,f_{i}(u,v)\in [0,1]}$${\displaystyle \,f_{i}(u,v)\in \{0,1\}}$

(1) ความจุของลิงก์:ผลรวมของการไหลทั้งหมดที่ส่งผ่านลิงก์ต้องไม่เกินความจุของลิงก์

${\displaystyle \forall (u,v)\in E:\,\sum _{i=1}^{k}f_{i}(u,v)\cdot d_{i}\leq c(u,v)}$

(2) การอนุรักษ์การไหลบนโหนดทางผ่าน:ปริมาณการไหลที่เข้าสู่โหนดกลางจะเท่ากับปริมาณการไหลที่ออกจากโหนด ${\displaystyle u}$

${\displaystyle \forall i\in \{1,\ldots ,k\}:\,\sum _{(u,w)\in E}f_{i}(u,w)-\sum _{(w,u)\in E}f_{i}(w,u)=0\quad \mathrm {เมื่อ} \quad u\neq s_{i},t_{i}}$

(3) การอนุรักษ์การไหลที่แหล่งกำเนิด:การไหลต้องออกจากโหนดแหล่งกำเนิดอย่างสมบูรณ์

${\displaystyle \forall i\in \{1,\ldots ,k\}:\,\sum _{(s_{i},w)\in E}f_{i}(s_{i},w)-\sum _{(w,s_{i})\in E}f_{i}(w,s_{i})=1}$

(4) การอนุรักษ์การไหลที่ปลายทาง:การไหลต้องเข้าสู่โหนดปลายทางอย่างสมบูรณ์

${\displaystyle \forall i\in \{1,\ldots ,k\}:\,\sum _{(w,t_{i})\in E}f_{i}(w,t_{i})-\sum _{(t_{i},w)\in E}f_{i}(t_{i},w)=1}$

การกระจายโหลด (Load balancing)คือความพยายามที่จะกำหนดเส้นทางการไหลของข้อมูลเพื่อให้การใช้งานลิงก์ทั้งหมดมีความเท่าเทียมกัน โดยที่ ${\displaystyle U(u,v)}$${\displaystyle (u,v)\in E}$

${\displaystyle U(u,v)={\frac {\sum _{i=1}^{k}f_{i}(u,v)\cdot d_{i}}{c(u,v)}}}$

ปัญหาดังกล่าวสามารถแก้ไขได้ เช่น โดยการลดค่าให้เหลือน้อยที่สุดการแปลงปัญหาให้เป็นเชิงเส้นที่นิยมใช้กันคือการลดค่าการใช้ประโยชน์สูงสุดให้เหลือน้อยที่สุดโดยที่ ${\displaystyle \sum _{u,v\in V}(U(u,v))^{2}}$${\displaystyle U_{max}}$

${\displaystyle \forall (u,v)\in E:\,U_{max}\geq U(u,v)}$

ในปัญหาการไหลเวียนของสินค้าหลายชนิดที่มีต้นทุนต่ำสุดจะมีต้นทุนสำหรับการส่งกระแสสินค้าหนึ่งไปยังอีกกระแสหนึ่งดังนั้นคุณจึงต้องลดต้นทุนนี้ให้เหลือน้อยที่สุด ${\displaystyle a(u,v)\cdot f(u,v)}$${\displaystyle \,(u,v)}$

${\displaystyle \sum _{(u,v)\in E}\left(a(u,v)\sum _{i=1}^{k}f_{i}(u,v)\cdot d_{i}\right)}$

ในปัญหาการไหลเวียนของสินค้าหลายชนิดสูงสุดความต้องการของสินค้าแต่ละชนิดไม่คงที่ และปริมาณการไหลเวียนรวมทั้งหมดจะถูกทำให้สูงสุดโดยการเพิ่มผลรวมของความต้องการทั้งหมดให้สูงสุด${\displaystyle \sum _{i=1}^{k}d_{i}}$

รูปแบบต้นทุนต่ำสุดของปัญหาการไหลหลายสินค้าเป็นรูปแบบทั่วไปของปัญหาการไหลต้นทุนต่ำสุด (ซึ่งมีแหล่งกำเนิดและปลายทางเพียงแหล่งเดียว) รูปแบบต่างๆ ของปัญหาการหมุนเวียนเป็นรูปแบบทั่วไปของปัญหาการไหลทั้งหมด กล่าวคือ ปัญหาการไหลใดๆ ก็สามารถมองได้ว่าเป็นปัญหาการหมุนเวียนเฉพาะ^{[ 1 ]}${\displaystyle s}$${\displaystyle t}$

การกำหนดเส้นทางและการจัดสรรความยาวคลื่น (RWA) ในการสลับสัญญาณแบบออปติคอลของเครือข่ายออปติคอลจะดำเนินการผ่านสูตรการไหลของสินค้าหลายชนิด หากเครือข่ายนั้นมีอุปกรณ์แปลงความยาวคลื่นที่ทุกโหนด

การจัดสรรรีจิสเตอร์สามารถจำลองได้เป็นปัญหาการไหลของสินค้าหลายชนิดที่มีต้นทุนขั้นต่ำจำนวนเต็ม: ค่าที่ผลิตโดยคำสั่งเป็นโหนดต้นทาง ค่าที่บริโภคโดยคำสั่งเป็นโหนดปลายทาง และรีจิสเตอร์รวมถึงช่องสแต็กเป็นขอบ^{[ 2 ]}

ในเวอร์ชันการตัดสินใจของปัญหา ปัญหาของการผลิตกระแสจำนวนเต็มที่ตอบสนองความต้องการทั้งหมดคือNP -complete ^{[ 3 ]}แม้จะมีเพียงสองสินค้าและความจุหน่วย (ทำให้ปัญหานี้เป็นNP-complete อย่างมากในกรณีนี้)

หากอนุญาตให้มีการไหลแบบเศษส่วน ปัญหาจะสามารถแก้ไขได้ในเวลาพหุนามผ่านการเขียนโปรแกรมเชิงเส้น [ ^{4 ]} หรือผ่านแผนการ ประมาณค่าในเวลาพหุนามเต็มรูปแบบ⁽ซึ่งโดยทั่วไปจะเร็วกว่ามาก) ^{[ 5 ]}

การไหลของสินค้าหลายประเภทถูกนำมาใช้ในการกำหนดเส้นทางแบบโอเวอร์เลย์ในการส่งมอบเนื้อหา^{[ 6 ]}

• บทความของ Clifford Stein เกี่ยวกับปัญหานี้: http://www.columbia.edu/~cs2035/papers/#mcf
• ซอฟต์แวร์ที่แก้ปัญหานี้: https://web.archive.org/web/20130306031532/http://typo.zib.de/opt-long_projects/Software/Mcf/