christofides' algorithm for s-t traveling salesman problem in Grid Networks

The grid topology of the networks has many applications in various fields of sciences e.g. GIS,transportation, image processing, textile, etc. The Hamiltonian path detection is classified as an NP-hard problem. In the grid networks, the directions of the movements are restricted in the horizontal and the vertical directions. Some nodes are restricted to travers at least once between the predetermined source and destination nodes those are traversed as the initial node and the last node, respectively. An approximation algorithm based on cristofieds' heuristic is applied to find an approximation solution in a constructed complete graph, and then it is transformed as a solution for the original grid network. The method is developed to construct a solution formed by the orthogonal paths.

کلیدواژه ها:

Christofides ، algorithm ، path Traveling salesman problem ، Grid networks ، Restricted Hamiltonian path