I would have gone travelling or I would have gone to travel?

Modals are only followed by the infinitive in the present tense. What you are looking at here is a "past modal".

Past modals take the past participle of the verb.

I would have gone home.

You should have slept longer.

He might have listened to me.

Also note that the object verb in the sentence is "gone" (the past participle of "go") not "travel". "travelling" is a gerund because it is the object of "gone". The use of the gerund is nothing to do with the modal verb, and would be used in the same way without it.

I am going travelling.