论文部分内容阅读
多商品流网络设计问题在实际中有很广阔的应用背景,比如交通运输、物流网络、电信网络等领域。在这些相关应用中,多种商品(货物、数据、人等)通过有容量限制的网络,各自从起点被运送到终点。在这类多商品流模型中,一般假定商品的运送起点和终点之间任何一条路径都可以用来运送商品。然而有些实际应用问题对运送商品的路径提出了额外要求,比如时间、可行性等要求。这一类问题不仅要考虑运送多个商品的费用,而且还要考虑用来运送商品网络的建设费用,因而这类问题的目标是寻找最优的运送方案使得两类费用的总和最小。
在本文中,将考虑一种带路径约束的多商品流网络设计问题(ACapacitatedMulti-commodityNetworkDesignProblemwithSideConstraintsonPaths),并利用改进单纯形法、列生成、最短路径和最k短路算法构造一种禁忌(TabuSearch)算法,最后给出该算法的计算实验结果。