Integration of sophisticated planning algorithms into Naval operations requires the systematic design of decision-support systems (DSS) that improve the understanding of AI-suggested courses of action (CoAs) by humans without overwhelming their cognitive processes. A successful interface would permit operators to fully understand the context of the problem so that they can select a computer-generated CoA that best matches their preferences. In this paper, the authors investigated such a system for routing ships using two sequential human-in-the-loop experiments, one which evaluated the impact of various forms of graphical decision support on decision-making and the cognitive load, and another in which time pressure was manipulated. The results showed that a mix between tabular and graphical information reduced the cognitive load, given adequate time to make a decision. Participant responses were used to build models of human decision rules to integrate into the DSS, revealing that humans heavily weighted certain contextual attributes that were indirectly integrated into the planning algorithm through the cost structure. A novel technique for representing decisions as a distribution of common heuristic trade-offs among Pareto solutions found that the context of each scenario dictated the choice of the heuristic. The results of these experiments guided the design of a follow-up experiment on multi-ship routing that is currently in pilot testing.