容量及转运点限制的多品种交通网最小代价流

摘要

传统的运送问题是在运送品种单一、运送条件理想情况下的最小代价流分配,但在实际的交通网络应用中,往往会出现多品种流的运送问题.同时,由于设备的限制,在同一个阶段的不同品种流的容量限制也可能不尽相同,不同品种在转运点的接发能力也不尽相同.本文主要考虑解决各品种的容量约束以及转运点的最大接发能力问题,分情况讨论复合指标修改规则,通过增流链调整规则修改复合参数,并根据汇的调整量修改复合指标,构造不需要改变网络拓扑结构的最小代价流算法.此算法不需要构造增流网络,也避免了二次求解问题.最后通过示例给出了具体的算法步骤,为以后在此基础上的优化研究提供基础.