DH and I love to travel internationally. We do so at least once a year. It is built into our budget to the tune of $6000 a year. We don't spend this every year, so it gets rolled over.
During our travels, we focus money spent on the things that are important to us. For example, we don't really care about nice hotels, so we stay at places that are just above hostels. However, we are foodies, so we go to at least one super-fancy dinner on each trip. The rest of the time, we eat cheap ethnic or street food. I love museums, so large amounts of money are budgeted for us to get in to places, but we spend a lot of time trying to figure out free cultural activities and museum days. Transportation is not very important to us, so we almost never use taxis, just busses, walking, and bikes.
Figure out what you like about vacations, spend on that and cut everthing else as low as possible.