Generic methods require an argument to allow the compiler to resolve what X is.

A better way might be to make the interface itself generic:

public interface LocalOptimizer< T extends List<Node> & RandomAccess>
{
  void optimize( final T tour );
  T doSomething():
}

public class Foo extends LocalOptimizer<ArrayList<Node>>
{
  public optimize( ArrayList<Node> nodes ) { ... }
  public ArrayList<Node> doSomething(){ ... }
}

You could also drop the generics altogether, at least for doSomething().

public ArrayList<Node> doSomething();

Do you really need the return type to be *any* List that is RandomAccess?  You
could just insist that it be an ArrayList.

I wouldn't suggest using Vector, but perhaps you don't care whether it's an
ArrayList or a Stack.  OTOH, ArrayList and Stack are not usually
interchangeable in an algorithm.  Chances are that the only useful type for
these methods is ArrayList.  If so, you can drop the generics altogether and
just use that.

There was a discussion about this some time ago.
Also, I've written an article about this.

<http://virtualinfinity.net/wordpress/java/esoteric-java-features/2007/03/06/type
-intersection-in-java-or-interest-in-interfaces-is-invaluable/>