Timefold VRP中使用规划列表变量时，替代值范围提供者的搜索限制方法

核心结论 #

规划列表变量（Planning List Variable）确实无法搭配值范围提供者（Value Range Provider），无法直接在Vehicle或Visit实体中通过该方式实现技能匹配过滤。以下是可行的替代方案：

替代方案1：优化硬约束配置 #

如果你暂时不想改造变量类型，可以强化现有约束的严格性，确保不符合技能要求的分配被彻底禁止，同时通过约束优先级让Timefold在搜索过程中尽早剪枝：

// 在约束定义类中
private Constraint vehicleSkillMatch(ConstraintFactory factory) {
    return factory.forEach(Visit.class)
            .join(Vehicle.class, Joiners.equal(Visit::getAssignedVehicle))
            .filter((visit, vehicle) -> !vehicle.getSkills().containsAll(visit.getRequiredSkills()))
            // 用forbid直接排除不符合的分配，比penalize更严格
            .forbid();
}

这种方式能保证结果正确性，但无法提前过滤候选值，搜索效率提升有限。

替代方案2：改用链式规划变量（Chained Variable） #

这是更高效的方案，链式变量天然支持值范围过滤，适配VRP的路线结构。具体实现步骤如下：

1. 定义共同父类Standstill #

用于统一锚点（Vehicle）和节点（Visit）的类型，让链式变量可以在两者间跳转：

public interface Standstill {
    Visit getNextVisit();
    void setNextVisit(Visit nextVisit);
}

2. 改造Vehicle实体作为链式锚点 #

@PlanningEntity
public class Vehicle implements Standstill {
    private Visit nextVisit;
    private Set<String> skills; // 车辆具备的技能

    // 实现Standstill接口
    @Override
    public Visit getNextVisit() {
        return nextVisit;
    }

    @Override
    public void setNextVisit(Visit nextVisit) {
        this.nextVisit = nextVisit;
    }

    // 技能相关getter/setter
    public Set<String> getSkills() {
        return skills;
    }
}

3. 改造Visit实体添加链式规划变量 #

@PlanningEntity
public class Visit implements Standstill {
    private Standstill previousStandstill; // 指向车辆或前一个Visit
    private Visit nextVisit;
    private Set<String> requiredSkills; // 该Visit需要的技能

    // 链式规划变量配置
    @PlanningVariable(
            graphType = PlanningVariableGraphType.CHAINED,
            nullable = false,
            valueRangeProviderRefs = {"standstillRange"},
            filter = SkillMatchingFilter.class // 关键：添加技能过滤规则
    )
    public Standstill getPreviousStandstill() {
        return previousStandstill;
    }

    public void setPreviousStandstill(Standstill previousStandstill) {
        this.previousStandstill = previousStandstill;
    }

    // 实现Standstill接口
    @Override
    public Visit getNextVisit() {
        return nextVisit;
    }

    @Override
    public void setNextVisit(Visit nextVisit) {
        this.nextVisit = nextVisit;
    }

    // 技能相关getter/setter
    public Set<String> getRequiredSkills() {
        return requiredSkills;
    }
}

4. 实现技能匹配过滤器 #

自定义过滤器，确保每个Visit的候选值仅包含符合技能要求的车辆或同属合规车辆的Visit：

public class SkillMatchingFilter implements SelectionFilter<Visit, Standstill> {
    @Override
    public boolean accept(ScoreDirector<VehicleRoutingSolution> scoreDirector, Visit visit, Standstill standstill) {
        // 检查车辆是否具备所需技能
        if (standstill instanceof Vehicle vehicle) {
            return vehicle.getSkills().containsAll(visit.getRequiredSkills());
        }
        // 检查前一个Visit所属的车辆是否具备技能（链式继承车辆技能）
        if (standstill instanceof Visit previousVisit) {
            Standstill current = previousVisit;
            while (current instanceof Visit) {
                current = ((Visit) current).getPreviousStandstill();
            }
            Vehicle parentVehicle = (Vehicle) current;
            return parentVehicle.getSkills().containsAll(visit.getRequiredSkills());
        }
        return false;
    }
}

5. 在Solution类中定义值范围提供者 #

@PlanningSolution
public class VehicleRoutingSolution {
    private List<Vehicle> vehicles;
    private List<Visit> visits;
    // 其他属性（如score）

    @ValueRangeProvider(id = "standstillRange")
    public List<Standstill> getStandstillRange() {
        List<Standstill> standstills = new ArrayList<>();
        standstills.addAll(vehicles);
        standstills.addAll(visits);
        return standstills;
    }

    // 其他getter/setter
}

方案对比 #

• 优化约束：实现简单，无需改造实体结构，但搜索效率提升有限。
• 链式变量：需要调整实体结构，但能提前过滤候选值，大幅提升搜索效率，同时从根源避免错误分配。

内容的提问来源于stack exchange，提问作者user24852323