我是 optaplanner 的新手。我正在尝试修改 vrp 示例 [无论是 CVRP 还是 VRPTW] 以支持的不仅仅是欧几里德距离作为节点之间的边权重。我正在使用最新版本的 optaplanner 6.0.0.CR5
问问题
1508 次
1 回答
1
有几种方法可以处理这个问题。所有人都假设您有一个 GPS 系统（例如谷歌地图），可以轻松返回 2 点 A 和 B 之间的距离。
请注意，决定从 A 到 B 的实际道路是 GPS 系统的责任（这不是 NP 完全问题，GPS 系统已经针对它进行了优化）。OptaPlanner 将决定执行 A、B、C、D、... 的顺序（这是 NP 完全的）。
A）计算 hoc 距离（不推荐）
只需将 getLocation.get...Distance(Location)方法替换为对 GPS 系统的调用即可。
缺点：通常该方法每秒调用数千次，并且您的 GPS 系统不会那么快地返回答案，从而大大减慢了您的平均分数计算速度。
B）预先计算距离并将其存储在内存中
在类Location中，添加一个Map<Location, int> dinstanceMap以保持彼此之间的距离Location。Map在调用solve()和实现之前填写它get...Distance()只是做return distanceMap.get(otherLocation)。
缺点：内存扩展：如果您有太多客户，您将获得 OutOfMemory 异常。
解决方法：对于每个Location，仅在该地图中添加 1000 个最近的位置。过滤移动选择器，使其永远不会尝试连接不在彼此地图中的 2 个位置。不过，这可能会影响结果的质量。
C) 预先计算距离并将其存储在磁盘上并缓存在内存中
同B)，但由于距离矩阵太大，将其存储在磁盘上。使用缓存仅在最近没有被询问时才从磁盘中获取值。
2019 年更新：从optaweb-vehicle-routing开始
于 2013-10-17T07:46:43.343 回答