The cross-entropy method for solving bi-criteria network flow problems in discrete-time dynamic networks

Abstract

The present study tries to focus on the problem of finding the maximum flow along with the shortest path in a dynamic network. Networks basically state problems where the transfer is not instantaneous and time is required to traverse the arcs. For solving bi-criteria network problems, a two-phased exact algorithm and a cross-entropy (CE) algorithm based on bi-criteria are proposed, where the costs change as time functions. First, the two-phased complete enumeration algorithm was proposed to generate the non-dominated paths. Then, the efficiency and validation of the solutions generated by both the algorithms are compared. The computational results for 53 random instances showed that in problems with sizes of 50–300 nodes, the non-dominated paths obtained from the two algorithms are identical. The only difference is that the solution time of the CE algorithm is significantly less; however, for problems with more than 300 nodes, the non-dominated paths generated in the CE algorithm have sometimes a few path(s) less than the other one. In addition, the mean of the CPU time for the CE algorithm is about 0.073 s, whereas the mean of the CPU time of the other algorithm is far more, about 200 s. For greater size problems, CPU time has exponential growth compared with that of the complete enumeration algorithm.

Keywords:

• bi-criteria network flow
• cross-entropy
• discrete-time