Integrating maximum flow and minimum cost flow for optimized transportation networks

Abstract

In network theory, a captivating challenge is presented by the interplay between Maximum Flow (MF) and Minimum Cost Flow (MCF). A network is comprised of nodes and edges. The highest volume of flow achievable between source and sink nodes is signified by the MF of a network, considering constraints such as capacity, direction, and supply-demand. Applications are prevalent in distribution, transportation, and various other networks, which are manually addressed using algorithms such as Ford-Fulkerson and Edmonds-Karp. The minimum cost flow, defined as the feasible flow with the lowest network cost while meeting supply and demand constraints like capacity and direction, is known. Plumbing, transportation, and communication systems are among the examples. Solutions are manually found using algorithms such as the primal network simplex method and cycle-cancelling. This study investigated the integration of MCF with MF within a unified mathematical model, utilizing the network's minimum cut. The optimal path for heavy vehicles navigating two-way roads in a particular part of Kandy city was focused, where the maximum flow was determined by the network's minimum cut. The most efficient routes were identified by applying the minimum cut and MCF approach while excluding connector roads to prevent heavy vehicles from travelling through them. In conclusion, the minimum cut of the network provides a definitive solution for determining the maximum flow. Identifying the bottleneck path through the minimum cut, analysing and optimizing heavy vehicle flow ensures the minimum cost and maximum efficiency in the transportation network. Future work will explore dynamic adjustments to the minimum cut in response to real-time traffic variations, enabling the recalibration of optimal paths and consistent transportation efficiency.