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. In some realistic problems, 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 provides an efficient heuristic method (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.