交通阻塞下的java车辆路径选择

Question

我正在使用谷歌地图和optaplanner构建一个车辆路径应用程序的原型。我将基于距离的评分更改为基于持续时间的评分，其中持续时间值是使用车辆的距离/平均速度计算的

现在我想在我的应用程序中添加交通堵塞变量。交通堵塞变量作为从当前位置到另一个位置的附加持续时间值来实现（我使用位置地图和double，就像RoadLocation类中的距离变量一样）。当我尝试运行它时，结果总是与前一个相同。以下是第一次运行的结果：

我画了一些红线来表示交通堵塞，然后尝试重新运行解决阶段。下面是第二个结果：

结果与前一次相同。我的问题是，将交通阻塞变量应用于车辆路径问题的最佳方法是什么？有人有添加此变量的经验吗？如有任何意见和建议，将不胜感激。 谢谢和问候

Answer 1

这一段只是介绍。如果你想跳过它，就去做吧。；-） 我已经对交通堵塞实施了类似的方法，但它不是一个实时系统。解决方案每X分钟运行一次，这是绝对正确的。 这使我能够在实际的optaPlanner计算开始之前，预先计算整个道路网的道路和路线。 这为optaPlanner的实际计算节省了时间。 网络由顶点和圆弧组成。对于每个弧，你都有一个重量

这才是真正的交易。 让我们假设您实现了一个Dijkstra或A-Star算法，用于所有位置的预计算步骤以及如何到达那里。这些寻路算法选择的是“旅行”成本最低的圆弧。对于每个将被阻挡的弧线/道路，我们假设距离为DOUBLE.MAX_VALUE。这个值可以解释为“不可驱动”，或者说：在当前的解决方案查找过程中，两个顶点之间甚至不存在这种连接。因此，寻路算法将跳过这条路。对于每一条可行驶道路，我们都会计算实际成本，例如距离或从经验中得出近似值

optaplanner过程本身只是使用预先计算的寻路机制，例如，比较从A地到B地的计算距离

要将distance变量设置为DOUBLE.MAX_VALUE，您可以在基于用户的信息、其他提供者的信息（如google）或基于管理员的规则之间进行选择。根据我的经验，基于用户的内容和基于管理员的操作，我可以推荐两种方法

让我们讨论一下基于用户的操作：用户可以拥有与管理员相同的GUI操作集，用于将一条路径标记为“阻塞”。在下一次optaPlanner迭代中，将涉及该标志。如果你有用户的GPS数据，你可以得到大致的速度。对于GPS测量的每个间隔，你可以计算出速度。如果速度在道路上（不是十字路口），并且低于定义的最小速度（比如1英里/小时或2公里/小时），那么您可以通过弹出窗口询问用户是不是交通堵塞，或者自动封锁该道路，而无需询问用户。如果你选择了弹出对话框，那么很多不同的用户必须在规定的时间段内投票“是”，例如半小时，那么道路就会被堵塞。当许多用户再次驾驶道路并发送该道路的GPS坐标时，可以解决交通堵塞问题。 自动方法的主要优点是，您将有一个基于系统的方法，错误率低

如果您通过管理采用手动方式，那么您必须注意实现一个GUI来显示道路，并启用/禁用道路的阻塞属性