代码之家 › 专栏 › 技术社区 › Henry

Optaplanner和链接

optaplanner java

0

Henry · 技术社区 · 5 年前

我们想从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不会返回任何任务,因为这些任务尚未生成。

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

0 回复 | 直到 5 年前

1

Geoffrey De Smet 5 年前

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

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