A simulated annealing for multi-criteria network path problems

This paper investigates an oriented spanning tree (OST) based simulated annealing (SA) for solving the multi-criteria shortest path problem (MSPP) as well as the multi-criteria constrained shortest path problem (MCSPP), especially for those with nonlinear objectives. As a popular search algorithm, because of “search-from-a-point” searching mechanism, there have been only a few attempts in extending SA to multi-criteria optimization, particularly, for various MSPPs. In contrast with the existing evolutionary algorithms (EAs), by representing a path as an OST, the designed SA provides an entirely new searching mechanism in sense of “search from a paths set to another paths set” such that both of its local and global search capabilities are greatly improved. Because the possibility of existing a feasible path in a paths set is usually larger than that of one path being feasible, the designed SA has much predominance for solving MCSPPs. Some computational comparisons are discussed and the test results are compared with those obtained by a recent EA of which the representing approach and the ideas of evolution operators such as mutation and crossover are adopted in most of the existing EAs for the shortest path problems. The test results indicate that the new algorithm is available for both of MSPPs and MCSPPs.