Attacks on classic complex problem solving focus on both their ecological validity and the difficulty to analyze such a complex interplay of system variables. But we argue that the domain of travel planning is in some sense a much more "natural" domain and at least partially able to deal with this kind of criticism. We first review the main existing scenarios and paradigms like Lohhausen, Tailorshop, and Moro and compare them to what we call the TRAVELPLAN problem. This problem contains a number of computationally well-investigated problems, which are worked out and can be described by so-called constrained satisfaction problems. The formal investigations have led to the development of a computational architecture which is able to deal with these kinds of subproblems simultaneously. More important, however, is that it serves as a basis for developing experiments and particularly to determine aspects of the computational complexity of the main problem. This in turn allows us to specify and to formulate experimental ideas. Finally, the status quo of ongoing experiments is briefly presented.