What does this research mean for the field?

A framework utilizing decision diagrams and a peel-and-bound technique enables scalable, exact solutions for space-time-dependent traveling salesman problems by minimizing the number of computationally expensive inner trajectory evaluations. Novelty: ClaimNovelty.METHODOLOGICAL. Consensus alignment: ConsensusAlignment.NEUTRAL.

What question did this study set out to answer?

The research aims to develop an exact framework for solving bilevel optimization problems, particularly in the context of space-time dependent traveling salesman problems.

April 4, 2026

An Exact Framework for Solving the Space-Time Dependent TSP

Key Points

The research aims to develop an exact framework for solving bilevel optimization problems, particularly in the context of space-time dependent traveling salesman problems.
Introduced a novel framework using decision diagrams (DDs) and a DD-based branch-and-bound technique called peel-and-bound.
Assumed quality of the inner problem optimizer to facilitate the search process.
Applied framework to the asteroid routing problem for practical demonstrations.
Demonstrated scalability of the framework in solving complex optimization problems.
Achieved robust heuristic solutions, with many being exact depending on optimizer quality.

Abstract

Many real-world scenarios involve solving bilevel 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 bilevel 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, a benchmark problem in global trajectory optimization. Experimental results demonstrate the framework’s scalability and ability to generate robust heuristic solutions for tested instances. Many of these solutions are exact, contingent on the assumed quality of the inner problem’s optimizer. History: Accepted by Andrea Lodi, Area Editor for Design & Analysis of Algorithms–Discrete. Supplemental Material: The software that supports the findings of this study is available within the paper and its Supplemental Information ( https://pubsonline.informs.org/doi/suppl/10.1287/ijoc.2024.0866 ) as well as from the IJOC GitHub software repository ( https://github.com/INFORMSJoC/2024.0866 ). The complete IJOC Software and Data Repository is available at https://informsjoc.github.io/ .

Bookmark

Cite This Study

Rudich et al. (Thu,) studied this question.

synapsesocial.com/papers/69d0a9c8659487ece0fa4162 https://doi.org/https://doi.org/10.1287/ijoc.2024.0866

Bookmark