[smallhadron]

The travel agent has existed since at least 1841

http://en.wikipedia.org/wiki/Thomas_Cook

For simple trips people are choosing not to pay the overhead for their personal travel now that you can shop around easily yourself. The agent is still pretty good for package holidays, though.

Companies like American Express offer corporate travel services. My last job had this service: one could call or email them from the back of the cab between meetings and they'd call back in 30 minutes with a whole itinerary, with flights, car and hotel. Needless to say, this is very expensive, but probably cheaper than having dedicated personnel at your company.

So the optimize-for-cheap and optimize-for-easy markets are probably covered. Perhaps there is a gap in between, but you'll be competing with some established companies from either side.