Optaplanner返回非最优解问题排查与优化咨询

架构老林

2026-8-10

OptaPlanner SKU分配问题：求解器受实体顺序影响未寻得最优解

问题背景

使用OptaPlanner解决SKU仓库分配问题：将指定需求量的SKU发往容量有限的仓库，硬约束为总发送量不超过仓库容量，软约束为最大化销售额（代码中为ventes）。但求解器优先满足低单价的SKU1需求，即便高单价的SKU2能带来更高销售额。示例中，求解器分配10个SKU1和10个SKU2（总销售额30），而非将全部20容量分配给SKU2（总销售额40）。仅调换初始化deploiementlist的顺序（先SKU2后SKU1）才能得到最优解，说明求解器受实体列表顺序影响，未完成全局寻优。

问题原因分析

这并非OptaPlanner的异常表现，而是默认启发式算法的特性导致：

构造启发式（CH）阶段：默认使用First Fit类策略，实体处理顺序直接影响初始解质量。当SKU1先被处理时，会优先占用容量，后续SKU2只能分配剩余容量。
局部搜索（LS）阶段：默认移动策略可能无法有效跳出局部最优。从日志可见，LS阶段仅在初始解附近微调，未尝试将SKU1的容量完全转移给SKU2的操作。

代码调整方案

1. 优化构造启发式的实体排序

让高单价SKU优先被处理，避免初始解陷入局部最优：

// 在SolverConfig中指定构造启发式的实体排序规则
SolverFactory<planingsolution> solverFactory = SolverFactory.create(new SolverConfig()
        .withSolutionClass(planingsolution.class)
        .withEntityClasses(deploiement.class)
        .withConstraintProviderClass(Contraintes.class)
        .withTerminationSpentLimit(Duration.ofSeconds(10))
        .withPhaseConfigList(List.of(
                new ConstructionHeuristicPhaseConfig()
                        .withConstructionHeuristicType(ConstructionHeuristicType.FIRST_FIT_DECREASING)
                        .withEntitySortComparator((d1, d2) -> Integer.compare(d2.getPrix(), d1.getPrix()))
        )));

2. 修复容量约束的逻辑错误

原约束中join(deploiement.class)会导致同一约束被重复计算，建议将仓库单独作为ProblemFact，简化约束逻辑：

// 定义仓库ProblemFact
public class Agence {
    private String id;
    private int capacity;
    // getter/setter
}

// 调整deploiement实体，关联Agence
@PlanningEntity
public class deploiement {
    private Agence agence;
    private String SKU;
    private int prix;
    private int prevision;
    
    @PlanningVariable(valueRangeProviderRefs = "DeploiementRange")
    private Integer Deploiement;
    
    @ValueRangeProvider(id = "DeploiementRange")
    public CountableValueRange<Integer> getTransportedRange() {
        return ValueRangeFactory.createIntValueRange(0, prevision +1);
    }
    // ... 其他getter/setter ...
}

// 优化容量约束
private Constraint maxCapacity(ConstraintFactory cf) {
    return cf.forEach(deploiement.class)
            .groupBy(deploiement::getAgence, ConstraintCollectors.sum(deploiement::getDeploiement))
            .filter((agence, totalDep) -> totalDep > agence.getCapacity())
            .penalize("Maximum capacite agence", HardSoftScore.ONE_HARD,
                    (agence, totalDep) -> totalDep - agence.getCapacity());
}

3. 增强局部搜索的移动策略

添加更灵活的移动类型，让求解器能探索更大的解空间：

SolverFactory<planingsolution> solverFactory = SolverFactory.create(new SolverConfig()
        // ... 原有配置 ...
        .withPhaseConfigList(List.of(
                new ConstructionHeuristicPhaseConfig(),
                new LocalSearchPhaseConfig()
                        .withLocalSearchType(LocalSearchType.TABU_SEARCH)
                        .withMoveSelectorConfigList(List.of(
                                new ChangeMoveSelectorConfig(),
                                new SwapMoveSelectorConfig()
                        ))
        )));

4. 简化销售额计算（替代Shadow Variable）

无需使用自定义Shadow Variable，直接在约束中计算销售额，减少复杂度：

private Constraint maxsales(ConstraintFactory constraintFactory) {
    return constraintFactory.forEach(deploiement.class)
            .reward("max Sales Day", HardSoftScore.ONE_SOFT,
                    dep -> Math.min(dep.getDeploiement(), dep.getPrevision()) * dep.getPrix());
}

原相关代码与日志

Planning Entity代码

@PlanningEntity
public class deploiement {
    private String Agence;
    private int capacityagence;
    
    @PlanningId
    private String SKU;
    private int prix;
    private int prevision;
    
    @PlanningVariable(valueRangeProviderRefs = "DeploiementRange")
    private Integer Deploiement;
    @ValueRangeProvider(id = "DeploiementRange")
    public CountableValueRange<Integer> getTransportedRange() {
    return ValueRangeFactory.createIntValueRange(0, prevision +1);
    }
    
    @CustomShadowVariable(variableListenerClass = varlistener.class,
            sources = {@PlanningVariableReference(entityClass=deploiement.class ,variableName = "Deploiement")})
    private Integer ventes;
... (constructor + getters and setters)

Variable Listener代码

if(deploiment.getDeploiement()!=null) {
        int ventes =Math.min(deploiment.getDeploiement(),deploiment.getPrevision())*deploiment.getPrix();
        
        scoreDirector.beforeVariableChanged(deploiment, "ventes");
        deploiment.setVentes(ventes);
        scoreDirector.afterVariableChanged(deploiment, "ventes");
        }

Constraint Provider代码

public class Contraintes implements ConstraintProvider {

    @Override
    public Constraint[] defineConstraints(ConstraintFactory constraintFactory) {
        return new Constraint[] {
                 maxCapacity(constraintFactory), 
                 maxsales(constraintFactory),
                 
         };
     }
    
    
     private Constraint maxCapacity(ConstraintFactory cf) {
         return cf.forEach(deploiement.class)
                 .groupBy(deploiement::getAgence, ConstraintCollectors.sum(deploiement::getDeploiement))
                 .join(deploiement.class)
                 .filter((agence, totaldep, dep) -> totaldep > dep.getCapacityagence())
                 .penalize("Maximum capacite agence" ,HardSoftScore.ONE_HARD ,(agence, totaldep, dep) -> totaldep - dep.getCapacityagence());
     }
     
     private Constraint maxsales(ConstraintFactory constraintFactory) {
            return constraintFactory.forEach(deploiement.class)
                    .reward("max Sales Day ", HardSoftScore.ONE_SOFT ,deploiement::getVentes);
        }
    
}

Main方法代码

public class Mainmethod {

    public static void main(String[] args) {
        
        SolverFactory<planingsolution> solverFactory = SolverFactory.create(new SolverConfig()
                .withSolutionClass(planingsolution.class)
                .withEntityClasses(deploiement.class)
                .withConstraintProviderClass(Contraintes.class)
                .withTerminationSpentLimit(Duration.ofSeconds(10)));
        
    
        planingsolution problem = inputdata();
        
        Solver<planingsolution> solver=solverFactory.buildSolver();
        
        planingsolution solution = solver.solve(problem);

        // display results
        
         System.out.println("solution: " + "\n" + "\n" + "score: " + solution.getScore());
        
         print(solution);

    }
    
    public static planingsolution inputdata() {
    
        String Agence="Agence1";
        int CapacitéAgence = 20;
        
        String SKU1 = "SKU1";
        int PrevisionsParJoursku1 = 10;     
        int PrixSku1= 1;
        
        String SKU2 = "SKU2";
        int PrevisionsParJoursku2 = 30;     
        int PrixSku2= 2;
        
        
        List<deploiement> deploimentlist = new ArrayList<>();
                
        deploimentlist.add(new deploiement(Agence, CapacitéAgence, SKU1, PrixSku1, PrevisionsParJoursku1));
        
        deploimentlist.add(new deploiement(Agence, CapacitéAgence, SKU2, PrixSku2, PrevisionsParJoursku2)); 
        
    
    
        return new planingsolution(deploimentlist);
        
    }
    
    
public static void print(planingsolution solution) {
        
        List<deploiement> deploimentlist = solution.getDeplist();
        
        
        
        System.out.println("Agence" + " |   " + "capacité Agence" + "   |   " + 
        "SKU" + "   |   " + "previsions" + "    |   " + "Prix SKU" + "  |   "  
         +  "Deploiement" +"    |   " + "Ventes" + "\n");
        
        for(deploiement dep : deploimentlist) {
            
            System.out.println(dep.getAgence() + "  |   " + dep.getCapacityagence() + " |   " + 
                    dep.getSKU() + "    |   " + dep.getPrevision() + "  |   " + dep.getPrix() + "   |   "  
                     +  dep.getDeploiement() +" |   " + dep.getVentes() + "\n");
        }
        
    }

}

正常求解日志（调换SKU顺序后）

00:51:06.287 [main ] INFO Solving started: time spent (79),
best score (-2init/0hard/0soft), environment mode (REPRODUCIBLE), move
thread count (NONE), random (JDK with seed 0). 00:51:06.342 [main
] DEBUG CH step (0), time spent (134), score (-1init/0hard/8soft),
selected move count (11), picked move (domain.deploiement@2c0b4c83
{null -> 8}). 00:51:06.363 [main ] DEBUG CH step (1), time
spent (156), score (0hard/8soft), selected move count (31), picked
move (domain.deploiement@4acb2510 {null -> 0}). 00:51:06.363 [main
] INFO Construction Heuristic phase (0) ended: time spent (156), best
score (0hard/8soft), score calculation speed (623/sec), step total
(2). 00:51:06.383 [main ] DEBUG LS step (0), time spent
(176), score (0hard/16soft), new best score (0hard/16soft),
accepted/selected move count (1/1), picked move
(domain.deploiement@760245e1 {8} <-> domain.deploiement@31ceba99 {0}).
00:51:06.386 [main ] DEBUG LS step (1), time spent (179),
score (0hard/8soft), best score (0hard/16soft), accepted/selected
move count (1/2), picked move (domain.deploiement@31ceba99 {8} <->
domain.deploiement@760245e1 {0}). 00:51:06.393 [main ] DEBUG
LS step (2), time spent (186), score (0hard/16soft), best score
(0hard/16soft), accepted/selected move count (1/6), picked move
(domain.deploiement@31ceba99 {0} <-> domain.deploiement@760245e1 {8}).
00:51:06.398 [main ] DEBUG LS step (3), time spent (191),
score (0hard/8soft), best score (0hard/16soft), accepted/selected
move count (1/4), picked move (domain.deploiement@760245e1 {0} <->
domain.deploiement@31ceba99 {8}). 00:51:06.401 [main ] DEBUG
LS step (4), time spent (194), score (0hard/16soft), best score
(0hard/16soft), accepted/selected move count (1/2), picked move
(domain.deploiement@760245e1 {8} <-> domain.deploiement@31ceba99 {0}).
00:51:06.406 [main ] DEBUG LS step (5), time spent (199),
score (0hard/8soft), best score (0hard/16soft), accepted/selected
move count (1/3), picked move (domain.deploiement@760245e1 {0} <->
domain.deploiement@31ceba99 {8}). 00:51:06.409 [main ] DEBUG
LS step (6), time spent (202), score (0hard/16soft), best score
(0hard/16soft), accepted/selected move count (1/1), picked move
(domain.deploiement@31ceba99 {0} <-> domain.deploiement@760245e1 {8}).
. . . 00:51:16.207 [main ] INFO Local Search phase (1) ended:
time spent (10000), best score (0hard/16soft), score calculation speed
(171781/sec), step total (415). 00:51:16.210 [main ] INFO
Solving ended: time spent (10001), best score (0hard/16soft), score
calculation speed (168969/sec), phase total (2), environment mode
(REPRODUCIBLE), move thread count (NONE). solution:
score: 0hard/16soft

异常求解日志（原SKU顺序）

00:50:28.084 [main ] INFO Solving started: time spent (79),
best score (-2init/0hard/0soft), environment mode (REPRODUCIBLE), move
thread count (NONE), random (JDK with seed 0). 00:50:28.146 [main
] DEBUG CH step (0), time spent (142), score
(-1init/0hard/10soft), selected move count (11), picked move
(domain.deploiement@2c0b4c83 {null -> 10}). 00:50:28.171 [main
] DEBUG CH step (1), time spent (167), score (0hard/30soft),
selected move count (31), picked move (domain.deploiement@4acb2510
{null -> 10}). 00:50:28.172 [main ] INFO Construction
Heuristic phase (0) ended: time spent (168), best score
(0hard/30soft), score calculation speed (544/sec), step total (2).
00:50:38.004 [main ] DEBUG LS step (0), time spent (10000),
score (0hard/29soft), best score (0hard/30soft), accepted/selected
move count (0/2249955), picked move (domain.deploiement@7569ea63 {10
-> 9}). 00:50:38.006 [main ] INFO Local Search phase (1) ended: time spent (10002), best score (0hard/30soft), score
calculation speed (229003/sec), step total (1). 00:50:38.008 [main
] INFO Solving ended: time spent (10002), best score (0hard/30soft),
score calculation speed (224955/sec), phase total (2), environment
mode (REPRODUCIBLE), move thread count (NONE). solution: score:
0hard/30soft

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

Optaplanner返回非最优解问题排查与优化咨询

问题背景 #

问题原因分析 #

代码调整方案 #

1. 优化构造启发式的实体排序 #

2. 修复容量约束的逻辑错误 #

3. 增强局部搜索的移动策略 #

4. 简化销售额计算（替代Shadow Variable） #

原相关代码与日志 #

Planning Entity代码 #

Variable Listener代码 #

Constraint Provider代码 #

Main方法代码 #

正常求解日志（调换SKU顺序后） #

异常求解日志（原SKU顺序） #