java - Optaplanner 和链接

Question

我正在尝试使用 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 生成任务，其中插入了(随机)基边，而该基边又被链接到其他任务。

如何实现预期的行为？

Answer 1

不要使用 OptaPlanner 来找到从 A 到 B 的最佳路径。这不是 NP 困难。使用A*搜索算法(= Dijkstra 的更好形式)。为什么？这不是解决人工智能问题的约束。

但是，如果您需要找到访问多个位置(例如 TSP 或 VRP)的最佳路线，那么它是 NP 困难的，然后请使用 OptaPlanner。