A study on the solution method of maximum origin-destination flow path in an acyclic network using branch and bound method

The Maximum Origin-Destination Flow Path Problem (MODFP) in an Acyclic Network is known as NP-hard. K.S. Sung has suggested an Optimal Algorithm for MODFP based on the ‘Pseudo flow of arc’ and the K-th shortest path algorithm. When the authors try to solve MODFP problem by general Branch and Bound Method (BBM), the upper and lower bounds of subproblems are so weak that the BBM become very inefficient. Here the authors utilized the ‘Pseudo flow of arc’ for the tight bounds of subproblems so that it can produce an efficient BBM for MODFP problem. [In Korean.]