algorithm - 基于距离和约会时间的约会地点路线

Question

我想开发一种算法，该算法考虑一个人从他/她的办公室开始需要访问的不同地点的位置和预约时间。完成所有预约访问后，此人必须回到办公室。我想为他/她计划一条涵盖所有约会的路线，方式如下:

• 他/她行驶的最短距离
• 路线构建考虑了预约时间。也就是说，在决定接下来应该去哪个地点时，约会时间应该优先于两个地点之间的距离。

我的问题是开放式的。我知道，如果我只想在构建路线时考虑距离，这直接适合旅行商问题。但是，我也想考虑预约时间。我是图形的新手，我想知道这个问题是否更适合我不知道的其他算法。如果没有，我正在寻找修改 TSP 算法以考虑这两个参数的建议。

在思考这个问题时，我想到了如何实现 Dijkstra 来寻找路径。我知道这是一个与 TSP 完全不同的问题。但是，你认为我如何结合两个参数(距离和约会时间)来比较我的 Dijkstra 优先级队列 ADT 中的两个节点。

这两个问题可能需要不同的问题，但我觉得这是一个普遍的问题。我正在寻找有关解决这些图形问题的建议，其中有两个因素需要考虑。如何获取两个参数并将它们合并为一个参数，以便我可以比较两个节点？

Answer 1

假设您需要准时赴约而不是早到，那么您可以从一个完全连接的图开始，然后根据约会时间移除相距太远的节点之间的边。

比如节点A的时间是10:00，节点B的时间是11:00，并且它们之间的最短距离超过1小时，那么你可以修剪这条边。

如果节点 A 在节点 B 之后有预约时间，这还包括修剪边(A，B)。

在此之后，您只需要找到最短的哈密尔顿循环 - 即 TSP。

编辑:直接回答您的问题:无需在问题的 TSP 部分考虑预约时间。只需设置图表(如上所述)，然后运行 ​​TSP 算法。