This problem is a special case of the optimal euler circuit problem where all edge weights are 1; the original problem is NP-complete. Moreover, this problem can be used to solve the Hamiltonian Graph problem (a Hamiltonian cycle exists if and only if the optimal circuit traverses all nodes), so it remains NP-complete even with the special case restriction. Any exact solution will (unless P = NP) require exponential time. You may find this paper helpful; it describes a polynomial-time approximation algorithm for this problem, as well as a polynomial-time algorithm for cases where the graph has at most degree 4:
Qiao, Yu. "Optimal Euler Circuit of Maximum Contiguous Cost." IEICE Trans. Fundamentals E90-A, no. 1 (2007): 274-280.
A good approximation gives the Hilbert Curve.