我正在尝试使用 OptaPlanner 实现以下场景的解决方案:
- 我们想从 A 点到达 B 点
- 我们可以采用一组有限的边(我们的事实;每条边都有出发地和目的地)
- 我们希望找到从 A 到 B 的最佳边连续,以便最小化边之间的总距离
- 因此,任何最佳结果都由一组边组成,其中第一个边从 A 点开始,最后一个边在 B 点结束,并且它们都是直接连接的
我当前的模型如下所示:
@PlanningSolution
@Getter
@Setter
@NoArgsConstructor
public class TaskAssigningSolution {
// Our facts: We'd like to go from A to B
private GeoPoint departureLocation;
private GeoPoint destinationLocation;
// Available edges, i.e., database contents
@ProblemFactCollectionProperty
@ValueRangeProvider(id = "edgeRange")
private List<Edge> availableEdges;
@PlanningEntityCollectionProperty
@ValueRangeProvider(id = "taskRange")
private List<Task> tasks = new ArrayList<>();
@PlanningScore
private HardSoftScore score;
public TaskAssigningSolution(GeoPoint departureLocation, GeoPoint destinationLocation,
List<Edge> availableEdges) {
this.departureLocation = departureLocation;
this.destinationLocation = destinationLocation;
this.availableEdges = availableEdges;
}
@Getter
@Setter
@NoArgsConstructor
@PlanningEntity
public class Task {
@AnchorShadowVariable(sourceVariableName = "previousTask")
private Edge edge;
// FIXME: the problem lies here, as I cannot use the edgeRange provider and the taskRange is empty.
@PlanningVariable(valueRangeProviderRefs = {"taskRange"}, graphType = PlanningVariableGraphType.CHAINED)
private Task previousTask;
// Shadow variables
@InverseRelationShadowVariable(sourceVariableName = "previousTask")
private Task nextTask;
}
但是,这不起作用,因为生成的解决方案是空的。 taskRange-ValueProvider 不返回任何任务,因为这些任务尚未生成。
我认为任务是优势的实现。因此,我期望 OptaPlanner 生成任务,其中插入了(随机)基边,而该基边又被链接到其他任务。
如何实现预期的行为?
最佳答案
不要使用 OptaPlanner 来找到从 A 到 B 的最佳路径。这不是 NP 困难。使用A*搜索算法(= Dijkstra 的更好形式)。为什么?这不是解决人工智能问题的约束。
但是,如果您需要找到访问多个位置(例如 TSP 或 VRP)的最佳路线,那么它是 NP 困难的,然后请使用 OptaPlanner。
关于java - Optaplanner 和链接,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/58857027/