基于距离和约会时间的预约位置路线

Question

我想开发一种算法，在人员需要从他/她的办公室开始访问的不同地点的位置和约会时间中进行。在完成所有预约访问后，此人必须回到办公室。我想规划路线为他/她，涵盖这样的方式，所有的约会：

• 他/她的旅行的最小距离
• 考虑到该帐户的预约时间路线建设。也就是说，在决定接下来应该访问哪个位置时，预​​约时间应优先于两个位置之间的距离。

我的问题是开放式的。我知道，如果我只是想考虑构建路线的距离，这直接适用于旅行推销员问题。但是，我也想把预约时间考虑在内。我对图很陌生，我想知道这个问题是否适合我不知道的其他算法。如果没有，我正在寻找修改TSP算法以考虑这两个参数的建议。

在考虑这个问题的时候，我考虑过如何实现Dijkstra寻找路线。我知道这与TSP完全不同。但是，您认为我可以结合两个参数（距离和约会时间）来比较我的优先队列ADT中的两个节点是否为Dijkstra。

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

Answer 1

假设你需要按时约会而不是早期，那么你可以从一个完全连通的图开始，然后根据约会时间消除节点之间的边缘，如果它们相距太远。

例如，如果节点A的时间为10:00，节点B的时间为11:00，且它们之间的最短距离超过1小时，则可以修剪此边缘。

这也包括修整边缘（A，B）如果节点A节点B后的约会时间

这一点，你只需要找到最短哈密顿圈之后 - 这是TSP。

编辑：直接回答你的问题：没有必要考虑TSP部分问题的预约时间。只需设置图（如上所述），然后运行TSP算法。