Multi-commodity Contraflow Problem on Lossy Network with Asymmetric Transit times

During transmission of commodities from one place to another, there may be loss due to death, leakage, damage, or evaporation. To address the problem, each arc of the network contains a gain factor. The network is a lossy network with a gain factor at most one on each arc. The generalized multi-commodity flow problem deals with routing several distinct goods from specific supply points to the corresponding demand points on an underlying network with minimum loss. The sum of all commodities on each arc does not exceed its capacity. Motivated by the uneven road condition of transportation network topology, we incorporate a contraflow approach with orientation-dependent transit times on arcs and introduce the generalized multi-commodity contraflow problem on a lossy network with orientation-dependent transit times.

In general, the generalized dynamic multi-commodity contraflow problem is $\mathcal{NP}$-hard. For a lossy network with symmetric transit time on anti-parallel arcs, the problem is solved in pseudo-polynomial-time. We extend the analytical solution with symmetric transit time on anti-parallel arcs to asymmetric transit times and present algorithms which solve it within the same time complexity.