چکیده
|
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 shortest
Hamiltonian 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, a
metaheuristic 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 ants
as much as possible.
|