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 生成任务，其中插入了（随机）基础边缘，作为回报，它被链接到其他任务。

我怎样才能达到预期的行为？

标签： javaoptaplanner

Answer 1

不要使用 OptaPlanner 找到从 A 到 B 的最佳路径。这不是 NP 难的。使用A* 搜索算法（= Dijkstra 的更好形式）。为什么？这不是解决 AI 问题的约束。

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