大论文结构

小论文1：基于基础图神经网络的无约束TSP求解

1.问题一：

2.问题二：

3.问题三：

创新点：

设计一种基于多层混合图卷积与图注意力机制的强化学习模型（MLH-GCN），

1. 通过多层混合图卷积注意力编码器
2. 动态概率解码器
3. 自适应 PPO 训练算法

解决无约束 TSP 的特征表征与训练稳定性问题。

小论文2：基于多模态异构图神经网络的带约束TSP求解

1.带时间窗约束TSP(TSP-TW): 时间窗约束：给每个城市或客户点加上一个时间范围[a_i, b_i], 推销员必须在a_i之后到达, 在b_i之前离开这个城市

如：例子：快递员送件，小区 A 的收件时间是上午 9:00-11:00，小区 B 是下午 2:00-4:00，快递员必须在这个时间段内到达，早到了要等，晚到了就失效。

难点：

1.计算复杂度高：属于 NP 难问题，当城市数量超过 100 时，传统的精确算法（如动态规划）几乎无法在合理时间内求出最优解。

2.约束耦合性强：时间窗约束和路径选择是相互影响的 —— 选了这条路径，可能导致某个城市的时间窗满足不了；为了满足时间窗，可能需要绕远路，增加总距离。

1.多模态：多种不同类型的特征集合

对于TSP-TW来说，常见的多模态特征包括：

空间模块：城市的坐标、城市之间的直线距离、实际道路距离。

时间模块：每个城市的时间窗 [a_i, b_i]、城市之间的行驶时间、道路的拥堵时间（随时间变化）。

属性模块：客户的优先级（比如 VIP 客户需要优先配送）、城市的服务时间（比如在这个城市需要停留 30 分钟才能完成服务）、车辆的载重限制、车辆的最大行驶时间。

2.异构图神经网络

异构图：图中存在多种不同类型的节点，或者多种不同类型的边

对于 TSP-TW 的异构图设计，一个典型的例子：
节点类型：不仅有城市节点，还有时间窗节点、车辆节点。
边类型：不仅有城市之间的距离边，还有城市到时间窗的约束边表示这个城市的时间窗约束、车辆到城市的可行边表示这辆车可以到达这个城市、城市之间的行驶时间边。

为了解决带时间窗的旅行商问题的高复杂性，以及传统模型中约束建模困难和多特征融合效果差的两个痛点，我们提出了一种新的模型：这个模型采用异构图作为基础数据结构，把问题中的多种不同类型的节点、边和多模态特征都组织在这个异构图中，从而实现对约束条件的显式建模和对多模态特征的高效融合，最终求出更优、更符合实际需求的解。