On and off for quite a few years I've had these symptoms. In my teen years it was horrible.
I do believe caffeine and nicotine makes it worse, and although I still indulge I have found something that works for me: Magnesium. I take pills containing magnesium whenever I get these troubles, but it also seems a couple of bananas also does the trick.
Anyone else who has been able to manage RLS with magnesium/bananas?