The longest simple path problem on graphs arises in a variety of context, e.g., information retrieval, VLSI design, robot patrolling. Given an undirected weighted graph
), the problem consists of finding the longest simple path (i.e., no vertex occurs more than once) on
. We propose in this paper an exact and a tabu search algorithm for solving this problem. We show that our techniques give competitive results on different kinds of graphs, compared with recent genetic algorithms.