I travel 100K - 125K miles per year of air travel including many day trips
all over, along with train trips and business meetings often over meals in
restaurants. I love eating at home but I often eat out (and I love that too
:-))

My solution to paleo eating on the road is that I do best when I avoid being
hungry. So I eat wherever possible, even if I am not really hungry.

Yesterday I was in New York and Wilmington Delaware. I took the train. Here
is what I ate:

I ate 2 fried eggs, and a bunch of sausage in the morning for breakfast
bought in a fast kind of place in Manhattan where you order your food, get
it on a tray and sit down to eat. No toast, no potatoes.

About 3 hours later I ate a hamburger patty, and cole slaw at a little
bar/restaurant in Wilmington.

About 3 hours later I ate a fruit cup and a tuna salad in the Wilmington
train station.

About 3 hours after that I got home, worked out with weights, walked the
dog, and ate a veal stew, brocolli and yam.

On days when I don't eat enough when traveling, I will cheat more often.
That is, if I am eating at a great restaurant I will eat some bread perhaps.
I can avoid this by not being hungry. I find that I can order steaks,
burgers (toss the bun, veggies instead of fries), chicken/tuna/cobb/chef's
salads, eggs/bacon/sausage, fruit, and be okay in terms of variety and still
be fairly "good" about sticking to what is best for me to eat.

I don't worry too much about a bit of cheese, but I do my best to avoid
grains, legumes, tomatoes/peppers/eggplant because I react badly to these.

--Richard