一种带路径约束的多商品流网络设计问题及其禁忌算法

多商品流网络设计问题在实际中有很广阔的应用背景，然而在多商品流模型中，有些实际应用问题对运送商品的路径提出了额外要求，如时间、可行性等．在此，将考虑一种带路径约束的多商品流网络设计问题，并借助改进单纯形法、列生成和最短路径算法为提出的模型构造一种禁忌(tabu search)算法，最后给出该算法的计算实验结果．

A Capacitated Multi-commodity Network Design Problem with Side Constraints on Paths and Its Tabu Search Algorithm

The multicommodity network-flow model concerns routing of a number of commodities through a capacitated network at minimal cost.In the basic model,it is assumed that for each commodity,the flow can be routed on any path connecting its origin and its destination.While in some realistic problem,there are some restrictions on the routing paths,e.g.time-delay or reliability requirements.It considers the fixed-charge network design with this side constraint on paths,and provide an efficient heuristic methods-tabu search algorithm to solve this kind of model,which combines the revised simplex with column generation and the shortest path algorithm to produce a search that explores the space of the continuous path flow variables.