状态依赖旅行商问题（SDTSP）

本文编辑来源：胡敏, 肖金伟, 张天天, 陶雪峰 (2026) "面向中高轨小卫星批量部署的轨道转移飞行器任务规划"
本站地址：https://cislunarspace.cn

定义

状态依赖旅行商问题（State-dependent Traveling Salesman Problem, SDTSP）是经典旅行商问题（TSP）的变体，其核心特征是转移成本不仅取决于起点和终点，还取决于当前的状态或阶段。

在轨道部署任务中，SDTSP的"状态"通常指执行转移的飞行器质量状态——由于每次部署卫星后飞行器质量发生离散阶跃，相同的起点到终点转移在不同质量状态下的成本不同。

部署序列 $\Pi = (\pi_1, \pi_2, \dots, \pi_N)$ ，其中 $\pi_k$ 是第k个部署的小卫星编号。

最小化任务总成本：

\min J = C_f = \sum_{k=1}^{N} \Delta C_k(\Pi, u_k(t); \eta_{abs}, \eta_{rel})

其中 $\Delta C_k$ 为第k段转移的成本消耗。

根据贝尔曼最优性原理，动态规划递推关系为：

J(S, j) = \min_{i \in S \setminus \{j\}} \{J(S \setminus \{j\}, i) + C(i, j, k)\}

其中 $C(i, j, k)$ 表示OTV在已部署k颗卫星后，从轨道i转移到轨道j的成本。

胡敏等（2026）将OTV批量部署任务建模为SDTSP：

成本矩阵 $C(i, j, k)$ 是三维的：

该矩阵通过Q-law控制律离线仿真生成。

对于中等规模任务（N≤12），动态规划可保证全局最优解：

研究结果表明（胡敏等, 2026）：

SDTSP是经典TSP的状态依赖扩展，转移成本 $C_{ij}^k$ 依赖于当前状态k，使得问题更接近实际工程约束。

状态依赖性使得问题更真实地反映物理现实，特别是在质量变化显著的航天任务中。

精确的SDTSP建模是获得高质量部署方案的关键，状态无关模型会系统性低估后期成本。

胡敏, 肖金伟, 张天天, 陶雪峰. 面向中高轨小卫星批量部署的轨道转移飞行器任务规划[J]. 航天器工程, 2026, 25(3): 634-646.
Bellman R. Dynamic Programming[M]. Princeton: Princeton University Press, 2010.
Narayanaswamy S, Wu B, Ludivig P, et al. Low-thrust rendezvous trajectory generation for multi-target active space debris removal using the RQ-law[J]. Advances in Space Research, 2023, 71(10): 4276-4287.