求经典仓储-门店产品分配问题的名称、复杂度及求解算法

问题定位 #

你遇到的是扩展型运输问题（Extended Transportation Problem），本质属于**最小成本流问题（Minimum Cost Flow, MCF）**的典型应用场景——核心是在带容量限制的网络中，以最小成本完成供需匹配（含过剩物资的废弃处理）。

复杂度说明 #

该问题不是NP完全问题，属于多项式时间可解问题。因为它可以转化为标准的最小成本流模型，而最小成本流问题存在多项式时间复杂度的求解算法。

为何现有尝试不适用 #

• 匈牙利算法：仅适用于供需数量完全相等的指派问题（Assignment Problem），是运输问题的极端特例，无法处理多仓库、多门店带容量限制的场景。
• 全1成本的最大流：只是最小成本流当单位成本均为1时的特例，当成本存在差异时，必须引入成本权重进行优化，因此单纯的最大流算法无法满足需求。

可行求解算法 #

经典多项式算法 #

• 连续最短路算法（Successive Shortest Path Algorithm）：在残量网络中反复寻找从供应节点到需求节点（含垃圾站）的最短路径，沿路径增广流量，直到所有供应都被分配。若单位成本非负，可使用Dijkstra算法加速；若存在负成本（比如门店支付供货价格时的收益最大化，可转化为负成本的最小化），则用Bellman-Ford算法。
• 原始-对偶算法（Primal-Dual Algorithm）：结合线性规划的原始与对偶问题，通过迭代调整对偶变量来寻找最优流，效率优于连续最短路算法在某些场景下的表现。
• 网络单纯形法（Network Simplex Method）：针对网络流问题优化的单纯形法，是实际工程中求解这类问题效率最高的算法之一，多数商用求解器都基于该算法实现。

工程实现方案 #

• 直接建模为线性规划（LP）问题：将仓库库存、门店容量、单位成本作为约束与目标函数，调用开源/商用求解器（如OR-Tools、Gurobi、CPLEX）求解，无需手动实现复杂算法。
• 自定义网络流模型：基于图论库实现上述经典算法，适合需要定制化逻辑的场景。

建模思路参考 #

将问题转化为最小成本流网络：

1. 构建源点：连接所有仓库节点，边的容量为对应仓库的库存总量，单位成本为0。
2. 仓库节点：
   • 连接到每个门店节点，边的容量为门店的接收上限，单位成本为C(Wn,Sm)。
   • 连接到垃圾处理站节点，边的容量设为足够大（如总库存总量），单位成本为垃圾处理的单位成本。
3. 门店节点与垃圾处理站节点：连接到汇点，边的容量分别为门店接收上限和总库存总量，单位成本为0。
   目标是让源点到汇点的总流量等于所有仓库的总库存，同时总成本最小（若为收益最大化，可将单位成本取负值，转化为最小化负收益）。

内容的提问来源于stack exchange，提问作者remi