Analyzing the impact of MOACO components: An algorithmic study on the multi-objective shortest path problem

Multi-objective Ant Colony Optimization (MOACO) algorithms have been successfully applied to several multi-objective combinatorial optimization problems (MCOP) over the past decade. Recently, we proposed a MOACO algorithm named GRACE for the multi-objective shortest path (MSP) problem, confirming the efficiency of such metaheuristic for this MCOP. In this paper, we investigate several extensions of GRACE, proposing several single and multi-colony variants of the original algorithm. All variants are compared on the original set of instances used for proposing GRACE. The best-performing variants are also assessed using a new benchmark containing 300 larger instances with three different underlying graph structures. Experimental evaluation shows one of the variants to produce better results than the others, including the original GRACE, thus improving the state-of-the-art of MSP.

► A MOACO algorithm from the state-of-the-art of the MSP is extended. ► Seven novel variants of the original algorithm are proposed. ► Several MOACO components from the literature are tested on the MSP. ► A new benchmark is created and filtered with the help of an exact algorithm. ► One of the novel variants outperforms the original algorithm on both benchmarks.