  Efficient optimisation algorithms have become important tools for finding
high-quality solutions to hard, real-world problems such as production
scheduling, timetabling, or vehicle routing. These algorithms are typically
"black boxes" that work on mathematical models of the problem to solve.
However, many problems are difficult to fully specify, and require a "human in
the loop" who collaborates with the algorithm by refining the model and guiding
the search to produce acceptable solutions. Recently, the Problem-Solving Loop
was introduced as a high-level model of such interactive optimisation. Here, we
present and evaluate nine recommendations for the design of interactive
visualisation tools supporting the Problem-Solving Loop. They range from the
choice of visual representation for solutions and constraints to the use of a
solution gallery to support exploration of alternate solutions. We first
examined the applicability of the recommendations by investigating how well
they had been supported in previous interactive optimisation tools. We then
evaluated the recommendations in the context of the vehicle routing problem
with time windows (VRPTW). To do so we built a sophisticated interactive visual
system for solving VRPTW that was informed by the recommendations. Ten
participants then used this system to solve a variety of routing problems. We
report on participant comments and interaction patterns with the tool. These
showed the tool was regarded as highly usable and the results generally
supported the usefulness of the underlying recommendations.
