Graph-theoretic solutions for transport network flow problems
摘要
This paper explores the optimization of flow within transport networks, focusing on the efficient transfer of a commodity between two points in the National Capital Region of India. According to a survey, the NCR’s outer ring roads network accommodates an average of 5 lakh vehicles daily, with National Highways accounting for approximately 80% of this traffic. The analysis models the network as a capacitated directed graph, with the dual objectives of maximizing the total flow of a commodity and minimizing the cost of transporting a prescribed flow. Graph-theoretic methods have been widely employed to address these problems in the field of operations research. This study reviews several key contributions, including work by Beckenbach, Even, Tarjan, Fulkerson, Cappanera, and Gallo, etc. This paper also explores the fundamental maximum flow problem and presents a systematic approach to determining optimal flows in networks.