Analysis of Complex Networks

15.3 Optimal Dynamic Multicommodity Flow Problems and Algorithms for Solving Them

In this section we formulate and investigate the optimal multicommodity flow problems on dynamic networks ([18, 31]). The multicommodity flow problem consists in shipping several different commodities from their respective sources to their sinks through a given network satisfying certain objectives in such a way that the total flow going through arcs does not exceed their capacities. No commodity ever transforms into another commodity, so that each one has its own flow conservation constraints, but they compete for the resources of the common network. We consider the minimum cost multicommodity flow problem on dynamic networks with time-varying capacities of arcs and transit times on arcs that depend on a kind of commodity entering them. We assume that cost functions, defined on arcs, are nonlinear and depend on time and flow, and demand–supply functions depend on time. For solving the considered problem, we propose algorithms based on the time-expanded network method.

15.3.1 The Minimum Cost Dynamic Multicommodity Flow Problem

The minimum cost dynamic multicommodity flow problem is a problem of finding the flow of a set of commodities through a network with a given time horizon, satisfying all supplies and demands with minimum total cost such that arc capacities are not exceeded. We consider the discrete time model, where all times are integral and bounded by horizon T, which defines the set = {0, ...