解决这样一个需求。有三个时间段，每个时间段有很多订单。现在需要将订单进行组合 A->B->C， ABC 分别是三组订单中的某个。ABC 都有地理位置信息。要求是 A_>B_>C 路程时间最短，并且两者之间的路程时间小于所在时间段的时间间隔。

[xiatong]

解决这样一个需求。有三个时间段，每个时间段有很多订单。现在需要将订单进行组合 A->B->C，ABC 分别是三组订单中的某个。ABC 都有地理位置信息。要求是 A_>B_>C 路程时间最短，并且两者之间的路程时间小于所在时间段的时间间隔。

[xupefei]

就是个 Nearest neighbour 问题吧。如果当前的点是类型 A 那么下一步只能走类型 B 或 C 的点，如此往复，不保证最优。
算最优的话可能是 NP HARD，感觉可以用动态规划解决。

[xiatong]

@xupefei 其实是一个环形的，有很多个起点，起点->A_>B_>C_>起点。订单只能走一次。找到每个起点的最优路线。

[xupefei]

带回程的话，感觉更是 np hard，但我一时半会想不出算是什么问题了。但我知道，branch and bound 算法一定可用，能拿到最优。

[xupefei]

哦，找图中最短的环，如果 ABC 访问顺序固定的话，这好像是个 BFS 能简单解决的问题。

[xiatong]

@xupefei 谢谢你，我去看一下相关资料。