An Ant Colony Optimization Method for the Constrained Shortest Hamiltonian Path Problem in the Grid networks

In a grid network, the nodes could be traversed either horizontally or vertically. The constrained shortest path goes over the nodes between a source node and a destination node, and it is constrained to traverse some nodes at least once while others are unrestricted to travers several times or not. The original destination node is assumed to traverse as the last node. This problem is called the constrained shortestHamiltonian path problem, and there are various applications of the problem especially in routing problems. It is an NP-complete problem, and the well-known Bellman- Held-Karp algorithm could solve the shortest Hamiltonian circuit problem within 2 (2) n On time complexity. So, ametaheuristic ant colony optimization based algorithm is applied to obtain the optimal solution. The solution method is based on the rooted shortest path tree structure, since in the optimal solution the paths between the restricted nodes are the shortest paths. Then, the proposed method obtained the shortest path tree at most 3 ()On time complexity in every iteration, and the current solution is improved by antsas much as possible

کلیدواژه ها:

Shortest hamilitonian path ، constrained shortest path ، ant colony optimization ، grid networks.