Do you find the best itinerary?

Target Visitation Problem

Interactive Presentation, “Long Night of Research” at the University of Klagenfurt

05th of November 2010

Through a practical experiment, the visitors get an insight into the world of combinatorial optimization. They can try to solve three problems of combinatorial optimization: The search for the shortest tour, the search for the best order to visit the cities and the search for the "best" round trip (a combination of the first two). In a large room a map is plotted on the ground and the visitors are instructed to plan three itineraries through the towns on the map. The quality of the first tour depends on the total distance traveld, the quality of the second itinerary depends on the fulfillment of specified preferences (e.g. visit New York before you visit Shanghai) and the objective function of the third tour is a combination of distance travelled and preference fulfillment. On a computer the decisions of the visitors are presented graphically and the quality of their tours is evaluated. The visitors learn in a playful way to optimize different objective functions on a fixed set of objects (cities to be visited) and for a fixed solution structure (round trip, in which all objects have to be visited). Thus they discover relationships and differences between various problems of combinatorial optimization.