Can I read An Exact Framework for Solving the Space-Time Dependent TSP on EtoBox?

An Exact Framework for Solving the Space-Time Dependent TSP by Rudich, Isaac; Cappart, Quentin; López-Ibáñez, Manuel; Römer, Michael; Rousseau, Louis-Martin is a scholarly article available to read on EtoBox.

What is An Exact Framework for Solving the Space-Time Dependent TSP about?

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

Author

Rudich, Isaac; Cappart, Quentin; López-Ibáñez, Manuel; Römer, Michael; Rousseau, Louis-Martin

Published

2023

Language

EN