.png){kind=icon}
返回
An Exact Framework for Solving the Space-Time Dependent TSP
.png){kind=icon}
PRE
AI
DOI：10.1287/ijoc.2024.0866.png)
.png){kind=icon}
原文求助.png){kind=icon}
分享.png){kind=icon}
收藏
摘要
En 中文
许多实际场景涉及求解双层优化问题，其中包含一个外层离散优化问题和一个涉及昂贵或黑箱计算的内层问题。这在时空依赖型的旅行商问题变体中尤为突出，例如在规划访问多个天体的太空任务时。由于相关天体的相对运动是持续变化的，这些任务的规划面临显著挑战。此类问题包含一个外层组合问题，即寻找最优的访问天体顺序，以及一个内层优化问题，需要确定每对天体间的最优出发时间和轨迹。天体的持续运动使内层问题复杂化，导致计算成本高昂。本文提出了一种新颖的框架，利用决策图（DDs）和基于DD的分支定界技术——剥皮定界法，在假设内层问题优化器质量足够好的前提下，实现此类双层优化问题的精确解。该框架利用问题特定知识来加速搜索过程并减少昂贵评估的次数。作为案例研究，我们将此框架应用于小行星路径规划问题，这是一个全球轨迹优化的基准问题。实验结果证明了该框架的可扩展性，并展示了其能为测试实例生成稳健的启发式解的能力。其中许多解在假设内层问题优化器质量足够好的情况下是精确的。
Keyword:
decision diagrams
spacecraft trajectory optimization
dynamic programming
combinatorial optimization
sequencing
期刊
I
IF:
2.1
论文数:
90
被引数:
3.2K
机构
查看更多机构
引用论文
暂无论文信息