如何让OptaPlanner在异构车队VRP中选最优车辆而非按列表顺序分配

我正使用OptaPlanner求解车辆路径规划问题（VRP），代码运行正常，但发现一个问题：我的车队为异构类型，包含多种车型（如A类大型卡车、B类小型卡车等），虽已正确构建模型，但求解器会按PlanningEntityCollectionProperty列表中的车辆顺序优先分配，而非根据实际条件选择最优车辆。我的目标不仅是在不违反载重、容积约束的前提下分配订单，更要让求解器根据成本、距离、时间等条件选择最优车辆，最小化整体得分（不同车型的行驶距离成本存在差异）。

模型示例如下：

@PlanningSolution
public class VehicleRoutingSolution {
    @ProblemFactCollectionProperty
    protected List<Location> locationList;

    @ProblemFactCollectionProperty
    protected List<Depot> depotList;

    @PlanningEntityCollectionProperty
    protected List<Vehicle> vehicleList;

    @ProblemFactCollectionProperty
    @ValueRangeProvider
    protected List<Customer> customerList;
    
    @PlanningScore
    protected HardSoftLongScore score;
}

@PlanningEntity
public class Vehicle {
    private int weight; // 车辆载重上限
    private int volume; // 车辆容积上限
    private float costPerKm; // 每公里行驶成本（建议明确属性含义）

    @PlanningListVariable
    private List<Customer> customers = new ArrayList<>();
}

调整方案 #

1. 完善软得分规则，纳入车辆成本与行驶成本 #

求解器的核心决策依据是评分函数，必须把车辆的成本差异明确纳入软得分计算，让求解器能识别“选择低成本车辆更优”。

使用OptaPlanner的Constraint Streams实现评分规则示例：

public class VehicleRoutingConstraintProvider implements ConstraintProvider {
    @Override
    public Constraint[] defineConstraints(ConstraintFactory constraintFactory) {
        return new Constraint[] {
            // 硬约束：车辆载重不超限
            vehicleWeightLimit(constraintFactory),
            // 硬约束：车辆容积不超限
            vehicleVolumeLimit(constraintFactory),
            // 软约束：最小化总行驶成本（每公里成本×行驶距离）
            minimizeTotalTravelCost(constraintFactory)
        };
    }

    private Constraint vehicleWeightLimit(ConstraintFactory constraintFactory) {
        return constraintFactory.from(Vehicle.class)
                .filter(vehicle -> vehicle.getCustomers().stream()
                        .mapToInt(Customer::getWeight)
                        .sum() > vehicle.getWeight())
                .penalizeLong("Vehicle weight exceeded", HardSoftLongScore.ONE_HARD);
    }

    private Constraint vehicleVolumeLimit(ConstraintFactory constraintFactory) {
        return constraintFactory.from(Vehicle.class)
                .filter(vehicle -> vehicle.getCustomers().stream()
                        .mapToInt(Customer::getVolume)
                        .sum() > vehicle.getVolume())
                .penalizeLong("Vehicle volume exceeded", HardSoftLongScore.ONE_HARD);
    }

    private Constraint minimizeTotalTravelCost(ConstraintFactory constraintFactory) {
        return constraintFactory.from(Vehicle.class)
                .filter(vehicle -> !vehicle.getCustomers().isEmpty())
                .penalizeLong("Total travel cost",
                        HardSoftLongScore.ONE_SOFT,
                        vehicle -> calculateTotalTravelDistance(vehicle) * vehicle.getCostPerKm())
                .asConstraint();
    }

    // 辅助方法：计算车辆的总行驶距离（从仓库出发，遍历客户，返回仓库）
    private long calculateTotalTravelDistance(Vehicle vehicle) {
        Depot depot = vehicle.getDepot();
        long totalDistance = 0;
        Location previousLocation = depot.getLocation();
        for (Customer customer : vehicle.getCustomers()) {
            totalDistance += getDistance(previousLocation, customer.getLocation());
            previousLocation = customer.getLocation();
        }
        totalDistance += getDistance(previousLocation, depot.getLocation());
        return totalDistance;
    }

    private long getDistance(Location a, Location b) {
        // 实际项目中可使用预计算的距离矩阵或坐标计算（如曼哈顿距离、欧氏距离）
        return Math.abs(a.getX() - b.getX()) + Math.abs(a.getY() - b.getY());
    }
}

2. 消除初始解的顺序依赖 #

默认的初始解生成策略可能会按vehicleList的顺序分配订单，可通过以下两种方式优化：

方式一：自定义初始解生成器

public class CustomVehicleRoutingInitialSolution implements InitialSolutionInitializer<VehicleRoutingSolution> {
    @Override
    public void initializeSolution(VehicleRoutingSolution solution) {
        List<Vehicle> sortedVehicleList = solution.getVehicleList().stream()
                .sorted(Comparator.comparing(Vehicle::getCostPerKm)) // 按每公里成本升序排序
                .collect(Collectors.toList());
        List<Customer> remainingCustomers = new ArrayList<>(solution.getCustomerList());

        for (Vehicle vehicle : sortedVehicleList) {
            List<Customer> assignableCustomers = findAssignableCustomers(vehicle, remainingCustomers);
            vehicle.getCustomers().addAll(assignableCustomers);
            remainingCustomers.removeAll(assignableCustomers);
            if (remainingCustomers.isEmpty()) break;
        }
    }

    // 找到当前车辆可承载的客户（不违反载重、容积约束）
    private List<Customer> findAssignableCustomers(Vehicle vehicle, List<Customer> remainingCustomers) {
        List<Customer> assignable = new ArrayList<>();
        int currentWeight = 0;
        int currentVolume = 0;
        for (Customer customer : remainingCustomers) {
            if (currentWeight + customer.getWeight() <= vehicle.getWeight()
                    && currentVolume + customer.getVolume() <= vehicle.getVolume()) {
                assignable.add(customer);
                currentWeight += customer.getWeight();
                currentVolume += customer.getVolume();
            }
        }
        return assignable;
    }
}

在求解器配置中指定初始解生成器：

<solver>
    <initialSolutionInitializerClass>com.yourpackage.CustomVehicleRoutingInitialSolution</initialSolutionInitializerClass>
    <!-- 其他配置 -->
</solver>

方式二：调整内置初始解策略

如果不想自定义，可先对车辆列表按成本升序排序，再使用内置的FIRST_FIT_DECREASING策略，让初始解优先分配低成本车辆：

// 构建solution前，先对车辆列表排序
solution.setVehicleList(solution.getVehicleList().stream()
        .sorted(Comparator.comparing(Vehicle::getCostPerKm))
        .collect(Collectors.toList()));

3. 确保约束的完整性 #

检查所有硬约束是否覆盖了车辆的使用限制（如载重、容积、车辆可用性等），确保求解器不会将订单分配给不符合条件的车辆，无论列表顺序如何。

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