OptaPlanner VRP边缘权重需要使用实际GPS数据而不是欧几里得距离 [英] OptaPlanner VRP edge weights need to use actual GPS data instead of Euclidean distance

问题描述

我是optaplanner的新手.我正在尝试修改vrp示例(无论是CVRP还是VRPTW)，以支持不仅仅是欧几里得距离作为节点之间的边缘权重.我正在使用最新版本的optaplanner 6.0.0.CR5

I am new to optaplanner. I am trying to modify the vrp example [whether the CVRP or the VRPTW] to supports more than just the Euclidean distance as the edge weight between nodes. I am using the newest release optaplanner 6.0.0.CR5

推荐答案

有几种方法可以解决此问题.所有人都假设您拥有一个GPS系统(例如Google地图)，可以轻松返回A点和B点之间的距离.

There are several ways to handle this. All presume you have a GPS system (such as google maps) that can easily return the distance between 2 points A and B.

请注意，决定从A到B的实际道路是GPS的系统责任(这不是NP完整的问题，GPS系统已经为此进行了优化). OptaPlanner将决定执行A，B，C，D ...(NP完整)的顺序.

Note that's it's the GPS's system responsibility to decide the actual roads to take from A to B (that's not an NP-complete problem and GPS systems have already been optimized for it). OptaPlanner is to decide which order to do A, B, C, D, ... (which is NP-complete).

A)计算临时距离(不推荐)

只需将get Location.get...Distance(Location)方法替换为对GPS系统的调用即可.

Just replace the get Location.get...Distance(Location) method with a call to your GPS system.

缺点:通常该方法每秒被调用数千次，并且您的GPS系统不会很快返回答案，从而大大降低了平均得分的计算速度.

Disadvantage: normally that method is called thousands of time per second and your GPS system won't return the answer that fast, slowing down your average score calculation enormously.

B)预先计算距离并将其存储在内存中

在类Location中，添加一个Map<Location, int> dinstanceMap来保持与每个其他Location的距离.在调用solve()之前填充该Map并实现get...Distance()以便执行return distanceMap.get(otherLocation).

In the class Location, add a Map<Location, int> dinstanceMap to holds the distance to every other Location. Fill that Map before calling solve() and implement get...Distance() to just do return distanceMap.get(otherLocation).

缺点:内存扩展:如果您有太多客户，则会收到OutOfMemory异常.

Disadvantage: memory scaling: if you have too many customers you'll get a OutOfMemory exception.

解决方法:对于每个Location，仅在该地图中添加1000个最近的位置.过滤移动选择器，使其永远不会尝试连接彼此不在地图中的2个位置.不过，这可能会影响结果的质量.

Workaround: for each Location, only add the 1000 closest Locations in that Map. Filter the Move selectors so it never tries to connect 2 locations which are not in each other's Maps. This might affect the quality of the result though.

C)预计算距离并将其存储在磁盘上并将其缓存在内存中

与B)相同，但是由于距离矩阵太大，因此将其存储在磁盘上.如果最近没有要求使用缓存，则仅从磁盘中获取值.

Same as B), but because the distance matrix is too big, store it on disk. Use caching to only fetch a value from the disk if it hasn't been asked recently.

更新2019:只需从 optaweb-vehicle-routing

Update 2019: Just start from optaweb-vehicle-routing

这篇关于OptaPlanner VRP边缘权重需要使用实际GPS数据而不是欧几里得距离的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！