A hybrid meta heuristic algorithm for bi-objective minimum cost flow (BMCF) problem

摘要

In this paper we study the bi-objective minimum cost flow (BMCF) problem which can be categorized as multi objective minimum cost flow problems. Generally, the exact computation of the efficient frontier is intractable and there may exist an exponential number of extreme non-dominated objective vectors. Hence, it is better to employ an approximate method to compute solutions within reasonable time. Therefore, we propose a hybrid meta heuristic algorithm (memetic algorithm hybridized with simulated annealing MA/SA) to develop an efficient approach for solving this problem. In order to show the efficiency of the proposed MA/SA some problems have been generated and solved by both the MA/SA and an exact method. It is perceived from this evaluation that the proposed MA/SA outputs are very close to the exact solutions. It is shown that when the number of arcs and nodes exceed 30 (large problems) the MA/SA model will be more preferred because of its strongly shorter computational time in comparison with exact methods.