Fuzzy search page for an online travel agency

I'm building the search page for an OTA (online travel agency). The brief has a few quirks that make this task difficult, so I need some help to identify some feasible ideas.

Most OTAs have a "standard" interface with a form asking for dates, places, and the number of rooms or travelers. Then they return a list on the right with a large number of filters available on the left.

This has a number of disadvantages:

  • one needs to know a number of exact pieces of data in order to search
  • filters are complex and highly useful criteria go mixed with marginally useful ones
  • there is almost no space for fuzzy, imprecise criteria such as "I want to travel one of the next weekends" or "I want to go to Europe with my girlfriend for less than 500 Euro"
  • it's almost impossible to book trips, which have multiple parts (e.g. hotels, transports, airplane, activities...) unless they are pre-made packages on offer.

What I need to build needs to:

  • allow for fuzzy and incomplete criteria
  • allow for complex queries involving different flights for different people, for example, total budget, and other complex requirements
  • not to be a fixed form like other OTAs
  • not to be a textbox where one writes their wishes and magically a result appears.

What is normally considered best practice to allow the gathering of fuzzy, imprecise, or incomplete requirements from a user in a website or mobile?