algorithm - 使用 google maps API 距离矩阵来解决带有时间窗(TSPTW)或带有时间窗的车辆路径规划(VRPTW)的旅行商问题

标签 algorithm google-maps google-maps-api-3 routes traveling-salesman

<分区>

关闭。这个问题不符合Stack Overflow guidelines .它目前不接受答案。

我们不允许提问寻求书籍、工具、软件库等的推荐。您可以编辑问题，以便用事实和引用来回答。

关闭 4 年前。

Google API 为路由点 a-b 提供了很好的方向，现在提供了多个路径点和 TSP 优化 ( https://developers.google.com/maps/documentation/directions/#Waypoints )。

我想更进一步，解决带时间窗的旅行商问题 (TSPTW)，也称为带时间窗的车辆路径问题。换句话说，我想在优化步骤中添加约会和服务时间。

Google map 提供了 distanceMatrix API 方法，给定一组多个起始位置和多个结束位置，该方法返回一个距离矩阵和每个位置之间的估计行程时间。鉴于这些信息，人们将如何计算一条在特定时间必须访问 n 个航点的路线，即约会？ https://developers.google.com/maps/documentation/javascript/reference#DistanceMatrixService

我找到了一篇关于该主题的论文，但很难将理论和数学转化为实际代码: http://www.akk.ke.hu/index.php?mid=60&did=739

我是一名 LAMP 开发人员，正在寻找 PHP 或 JavaScript 的解决方案。

对于使用来自谷歌地图 API 或任何其他 map 解决方案的数据来解决 VRPTW 是否有任何其他建议？

最佳答案

试试这个:为每个约会创建一个数组，并添加一个“努力”属性。逐步遍历阵列并将工作量计算为每个项目与其上方和下方项目之间的物理距离的平方和，计算空间距离和时间距离。在数组中找到“努力”值最高的项目，并尝试将其重新放置在数组中的每个位置，以找到该项目的最低位置。对每个项目执行此过程。重复上述过程，直到所有项目的总 Effort 停止减少，或低于可接受的值。

关于algorithm - 使用 google maps API 距离矩阵来解决带有时间窗(TSPTW)或带有时间窗的车辆路径规划(VRPTW)的旅行商问题，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/23275942/

上一篇：algorithm - 最快的Cortex M0+ Thumb 32x32=64乘法函数？

下一篇：arrays - 如何在两个排序数组的并集中找到第 k 个最小的元素？

相关文章：

c# - 如何从 O(1) 中匹配特定条件的数组中选择随机元素

algorithm - 图像转换算法

java - 从Gradle中删除Play服务 map 实现

mysql - 将标记从 XML 文件加载到 Google Map API

javascript - 谷歌地图 SVG 标记不显示在 IE 11 上

java - 在 Java 中使用递归的主要因素

python - 用 m 个硬币找 n 美元

javascript - 谷歌地图 onclick 信息窗口在刷新周期后消失

java - Android 运行时错误，ActivityNotFoundException : No Activity

javascript - 如何设置信息框的动态像素偏移？