함께하는 is an "adjective" while 함께 is an adverb.
함께하는 literally means "to be together", transformed to an "adjective" so to say which is usual in Korean building sub sentences.
함께하는 isn't that often used in normal situations, and it suits more commercial slogans such as:
"언제나 당신과 함께하는 AAA생명보험~" - AAA life insurance, always with you~
And you should take 여행하다 as a standalone verb, NOT noun+verb.
함께 여행 할래요?
Also you should note that 함께 is more suited for groups, and for static activities, hence it isn't very suited for travel.
같이 is clearly the better pick.