| On 2011-10-21 at 14:00:00 (Brussels Time) |
Abstract
Abstract: The Multi-objective Shortest Path Problem (MSP) is a widely studied NP-Hard problem. A few exact algorithms were already proposed to solve this problem, however none is able to solve large instances with three or more objectives. Recently, some metaheuristics have been pro- posed for the MSP, but little can be said about their efficiency regarding each other, since no comparisons among them are presented in the litera- ture. In this paper an Ant Colony Optimization (ACO) algorithm, called GRACE, is proposed for the MSP. The proposed approach is compared to the well-known evolutionary algorithm NSGA-II. Furthermore, GRACE is compared to another ACO algorithm proposed previously for the MSP. Results of a computational experiment with eighteen instances, with three objectives each, show that the proposed approach is able to produce high quality results for the tested instances.
