java - Optaplanner和链接

我正在尝试使用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的一种更好形式）。为什么？这不是解决AI问题的约束。

但是，如果您需要找到访问多个位置的最佳路线（例如TSP或VRP），则它是NP难的，然后使用OptaPlanner。