Node Dependency in Multi-Commodity Flow Problem with Applications to Transportation Networks

In this research, we study the multi-commodity flow problem (MCFP) in the context of air transportation systems. MCFP deals with assigning a variety of goods to flow from sources to their destinations in a network. While many optimization problems in transportation networks can be formulated as a classic MCFP, previous research has mostly considered the edge capacity as a network flow constraint. Based on a traditional path-flow model and edge-flow model, this research proposes new modifications with the consideration of node capacity in the network. In addition, we implement new optimization heuristics improving the path-finding stage of the algorithm. These optimizations allow us to solve the MCFP for networks with around one hundred nodes. Based on these results, we define and compute the node-dependency relationship in MCFP networks. For preliminary evaluation, our novel techniques are evaluated on an air transportation network consisting of 164 nodes. The experiment showed that dependencies on a node are the results of joint influence of the network structure factors and flows. Moreover, the dependencies in our network come in geographical clusters.