9

我在谷歌地图上有很多点代表学生的家

我也有很多公共汽车。

我必须根据学生的位置将最近的学生用同一辆公共汽车分组。

所以巴士司机会把他们送到学校。

关于算法的任何想法？有任何想法吗？？

4

6 回答 6

4

我不太确定我是否完全理解了您的问题（尤其是您在评论中提到“公共汽车的路线是学生家的纬度/经度”）。所以我假设您没有预定义的巴士路线，但想找到最好的路线。

现在澄清一下，我们应该将任务拆分为子任务，根据我的假设，我们可以说：

  1. 您需要一种算法来将学生之家分配到最近的公交车站。公共汽车站可能是预定义的，也可能不是 - 您需要澄清公共汽车站是否已定义。

  2. 由于您有多辆公共汽车，因此需要将每辆公共汽车分配给他们负责停靠的一组公共汽车站（我们称之为公共汽车区）。

  3. 然后你需要解决每个公交区域（公交车站组）的 TSP（旅行推销员问题）。

可能的解决方案

1 - 您要研究的是如何对由 (lat,lon) 定义的点（在这种情况下是指学生之家）进行分组。为此，您需要能够计算地球上两点之间的距离，Haversine 公式被广泛用于此。如果您搜索它，您可以找到很多现有的实现 - 这是一个简单的 JS 实现：

var R = 6371; // km
var dLat = (lat2-lat1).toRad();
var dLon = (lon2-lon1).toRad();
var lat1 = lat1.toRad();
var lat2 = lat2.toRad();

var a = Math.sin(dLat/2) * Math.sin(dLat/2) +
        Math.sin(dLon/2) * Math.sin(dLon/2) * Math.cos(lat1) * Math.cos(lat2); 
var c = 2 * Math.atan2(Math.sqrt(a), Math.sqrt(1-a)); 
var d = R * c;

Google Maps API v3 中还实现了一个功能，您可以在这个SO question中找到更多信息。

因此，如果您有预定义的公交车站，只需计算每个学生家到每个公交车站的距离，然后将每个学生分组到最近的公交车站（即计算出的最低距离）

根据项目所需的数据/计算量，您可能需要考虑将其移至后端解决方案，而不是在客户端中进行。

2 - 这同样取决于您的项目的要求，如果您有预定义的公交车区（多边形），那么您只需确定哪些公交车站属于每个公交车区。这只是解决球体多边形中的点的问题。如果您需要自己的实现搜索 SO，有很多现有的解决方案可用。Othwerise Google maps API v3 有一个 containsLocation() 函数，您可以使用它：

google.maps.geometry.poly.containsLocation(google.maps.LatLng(latitude, longitude),polygons);

3 - 有很多关于解决 TSP 的信息。在谷歌地图中获得最快路线的一个很好的解决方案是OptiMap。源代码也可用。您应该能够为每个公共汽车区（公共汽车站组）运行它。

于 2013-10-08T08:38:10.077 回答
2

我不知道这是否有帮助：Genetic Algorithm Traveling Salesman Problem with Javascript

于 2013-10-14T14:54:47.487 回答
0

您可以尝试使用分层集群对学生进行分组。然后您可以使用开放的 tsp 算法来查找路线。Gebweb 的 Optimap 是一个免费的求解器。要将学生分组，您可以查找 clusterfck JavaScript。您还可以尝试像保存算法这样的启发式算法。

于 2013-10-08T08:51:44.303 回答
0

蛮力方法

如果您知道公共汽车在哪里并且您拥有所有学生的位置，那么您应该计算所有学生与所有公共汽车站的距离。对于每个学生，对他们到每个公共汽车站的距离进行排序，并将他们分配到最近的公共汽车站。

优化一

排除一些学生的公共汽车站。有些公交车站不需要计算距离，您可能马上就知道这一点。你可以说如果某个学生属于某个象限。然后你只需要计算总线子集的距离（只有 1/4 而不是全部）。这可能会导致边境出现有趣的情况，但你可以解释这一点。

优化2

基于之前的优化，您可以进一步执行此操作，直到您基本上可以保证不计算任何距离为止。如果用户落入某个节点，那么他们最终将前往某个公共汽车站。如果学生落在某个网格节点内，他们将去那个公共汽车站，你基本上会在地图上覆盖一个网格。前面的问题也基本解决了。到公共汽车站的距离是否稍长一点也没关系，因为它相对微不足道。但是，您可以保证任何学生的最大旅行距离。

解决方案

每辆公共汽车都有一个可用区域（一个命中框）。对于某个象限/节点内的每个学生，确定他们是否属于公共汽车的服务区域。如果不将它们冒泡到更高级别的象限/节点。

于 2013-10-08T18:24:24.127 回答
0

是的，我一次使用了 500 多个标记，我可以向您发送一些链接以寻求帮助： 第一个链接 第二个链接

阅读并在数组的帮助下申请。

于 2013-10-11T14:24:31.747 回答
0

喜欢这个项目.....应该很有趣

我会正确地拆分地图并让巴士负责每个区域，而不是有一些故障安全程序（如果 1 个区域最终有 99% 的学生，在这种情况下，这些区域会动态变化以使其更加均匀）。你也可以这样，如果一辆公共汽车的路线最终超过其他公共汽车的 20%，而不是减少那辆公共汽车的学生。

从那里每辆公共汽车都会有一个学生，您可以从中计算出路线。然而，创建一个算法来计算多辆公共汽车的最佳路线将是很多工作。

您可能希望考虑已经这样做的服务，例如 MapBox。这将使您的生活更轻松，但是它也会产生持续的成本。

希望有帮助

于 2013-08-07T12:12:30.470 回答