Baggallini!!!

They make wonderful nylon bags that unzip from a small pouch (actually fits in your purse) to a large bag that can be checked. The one I use most fits four shoe boxes plus some clothing once its opened to the full-size. I don't travel without it.

I believe they sell them on e-bags, although I purchased mine at a Berkshire-Hanes outlet for about half price.