Abstract:
We consider the problem of optimizing interdependent nonhomogeneous flows (Steiner's multicommodity problem with flows in graphs) in which the fixed costs change when different commodity flows are overlapped. The proposed solution method reduces the enumeration by transforming the original problem to a concave programming problem of the form $\min\{f(x)|x\in X\}$, where $f:\mathbb{R}^n\to\mathbb{R}$ is a concave function, $X\subset\mathbb{R}_{\geq0^n}$ is the flow polytope defined by transportation network constraints. For large applications that arise in the design of transportation networks on a homogeneous terrain defined by a digital model, we propose a local optimization method on the set of vertices of the flow polytope which is more efficient than the Gallo- Sodini method.