带距离约束的收益最大化TSP变体问题技术咨询

问题归属确认 #

你描述的是经典定向问题（Orienteering Problem, OP），属于带收益约束的TSP变种，核心特征完全匹配你的需求：总行驶距离有上限、节点仅可单次访问、要求返回起点、目标为最大化访问总收益。你提到的不同方向通行成本有差异的场景，属于有向闭途定向问题，是定向问题的标准分支。
该问题属于NP-hard问题，不存在通用的多项式时间精确解法，需要根据你的节点规模选择匹配的求解方案。

是否需要采用动态规划求解？ #

动态规划是小规模场景下的首选精确解法，非常适配你的需求：
标准状态可以定义为 dp[mask][u]，其中mask是二进制整数，代表已访问的节点集合，u代表当前停留的节点，状态值存储两个维度：当前累计行驶距离、当前累计访问收益，也可以优化为仅存储固定mask和u下的最大收益，同步记录该收益对应的最小行驶距离，剪除掉同状态下收益更低、距离更长的无效分支，进一步提升运行效率。
但该方案仅适用于节点数≤15~20的场景，当节点规模更大时，二进制DP的时间复杂度O(n²*2ⁿ)会急剧上升，无法在合理时间内得到结果，需要换用其他方案。

不同规模下的求解思路 #

• 节点数≤20：直接用上述动态规划方案求精确最优解即可，实现难度低，结果完全准确。
• 节点数在20~100区间：如果必须要精确解，可选择分支定界法，通过合理的上界剪枝能大幅压缩搜索空间；如果接受近似最优解，可选择禁忌搜索、模拟退火这类元启发式算法，能在可控时间内得到和最优解差距极小的结果。
• 节点数≥100：首选基于成本收益比的贪心策略构造初始路径，再结合2-opt、3-opt等局部搜索方法做路径优化，实现难度低，运行速度快，性价比最高。
  你提到的有向边特性不需要改动算法核心框架，仅需在边权计算环节区分两个方向的不同距离即可。

内容的提问来源于stack exchange，提问作者curiousbetsygw