Dynamic Multicommodity Contraflow Problem with Asymmetric Transit Times

Abstract

A maximum dynamic multicommodity flow problem concerns with the transportation of several different commodities through the specific source-sink path of an underlying capacity network with the objective of maximizing the sum of commodity flows within a given time horizon. Motivated by the uneven road condition of transportation network topology, we introduce the dynamic multicommodity contraflow problem with asymmetric transit times on arcs that increase the outbound lane capacities by reverting the orientation of lanes towards the demand nodes. Moreover, a pseudo-polynomial time algorithm by using a time-expanded graph and an FPTAS by using a Δ-condensed time-expanded network are presented.