Discrete Flower Pollination Algorithm for Solving the Symmetric Travelling Salesman Problem

摘要

The Travelling Salesman Problem (TSP) is an important NP-hard combinatorial optimisation problem that forms the foundation of many modern-day, practical problems such as logistic or network route planning. The Flower Pollination Algorithm (FPA) is a continuous optimisation algorithm that demonstrated promising results in comparison to other well-known algorithms. This paper proposes a novel algorithm, Discrete Flower Pollination Algorithm (DFPA) based on the FPA for solving the TSP. The algorithm is compared to the Ant Colony Optimisation’s (ACO) ${mathcal{M}}{mathcal{A}}{mathcal{X}} - {mathcal{M}}{mathcal{I}}{mathcal{N}}$ Ant System (${mathcal{M}}{mathcal{M}}{mathcal{A}}{mathcal{S}}$) as well as the Genetic Algorithm (GA) since they are well studied and developed. The DFPA results are significantly better than the GA in all tested instances.