This paper describes the development of a heuristic learning algorithm to solve traveling salesman problems. The heuristic evaluation function of this algorithm considers both local and global estimated distance information. The heuristic learning mechanism allows the algorithm to update the heuristic estimates of visited states and hence modify the tour configuration along the search process. The search engine of the algorithm incorporates Delaunay Triangulations as part of the search strategy to identify candidate edges during the search process.