  Many real-world scenarios involve solving bi-level optimization problems in
which there is an outer discrete optimization problem, and an inner problem
involving expensive or black-box computation. This arises in space-time
dependent variants of the Traveling Salesman Problem, such as when planning
space missions that visit multiple astronomical objects. Planning these
missions presents significant challenges due to the constant relative motion of
the objects involved. There is an outer combinatorial problem of finding the
optimal order to visit the objects and an inner optimization problem that
requires finding the optimal departure time and trajectory to travel between
each pair of objects. The constant motion of the objects complicates the inner
problem, making it computationally expensive. This paper introduces a novel
framework utilizing decision diagrams (DDs) and a DD-based branch-and-bound
technique, Peel-and-Bound, to achieve exact solutions for such bi-level
optimization problems, assuming sufficient inner problem optimizer quality. The
framework leverages problem-specific knowledge to expedite search processes and
minimize the number of expensive evaluations required. As a case study, we
apply this framework to the Asteroid Routing Problem (ARP), a benchmark problem
in global trajectory optimization. Experimental results demonstrate the
framework's scalability and ability to generate robust heuristic solutions for
ARP instances. Many of these solutions are exact, contingent on the assumed
quality of the inner problem's optimizer.
