基于OptaPlanner的多旅行商问题：如何均衡任务分配？

要实现最小化所有地点访问完成的最晚时间（即Makespan），让多个Actor并行分摊任务，核心是直接以每个Actor的路径总耗时（或总距离，假设速度固定）的最大值作为主要优化目标，而非通过任务数量的二次惩罚间接调整。以下是具体实现步骤和约束代码：

1. 给Actor添加路径总耗时计算方法 #

首先在Actor类中实现计算完整路径总时间的方法（若时间与距离成正比，也可直接用总距离替代），需覆盖从起点到首个任务点、任务点间移动，以及最后一个任务点返回起点的时间（根据业务需求选择是否保留返程）：

public Long getTotalRouteTime() {
    long totalTime = 0;
    Sector previousSector = null;
    // 假设sectors列表已按访问顺序排序（OptaPlanner的车辆路径规划逻辑通常会维护该顺序）
    for (Sector sector : sectors) {
        if (previousSector == null) {
            // 计算Actor起点到第一个任务点的时间
            totalTime += calculateTimeFromActorStart(sector);
        } else {
            // 用上一个任务点到当前点的移动时间（若getCostFromPreviousSector是距离，需转成时间：距离/速度）
            totalTime += sector.getCostFromPreviousSector();
        }
        previousSector = sector;
    }
    // 若需要返回起点，加上最后一个任务点到起点的时间
    if (previousSector != null) {
        totalTime += calculateTimeToActorStart(previousSector);
    }
    return totalTime;
}

2. 编写核心约束：最小化最晚完工时间 #

直接针对所有Actor的路径总耗时最大值进行惩罚，OptaPlanner会自动调整任务分配，让该最大值尽可能小，从而迫使任务分摊到多个Actor：

protected Constraint minimizeMakespan(ConstraintFactory factory) {
    return factory.forEach(Actor.class)
            // 聚合出所有Actor中最大的路径总耗时
            .groupBy(ConstraintCollectors.max(Actor::getTotalRouteTime))
            // 对最大值进行惩罚，设置为最高优先级
            .penalizeLong(HardSoftLongScore.ONE_SOFT, maxFinishTime -> maxFinishTime)
            .asConstraint("Minimize latest actor finish time (makespan)");
}

3. 调整原有总距离约束的优先级 #

若仍希望兼顾总行驶距离（但优先级低于完工时间），可保留原约束并降低其权重：

protected Constraint totalTravelDistance(ConstraintFactory factory) {
    return factory.forEach(Sector.class)
            .filter(sector -> sector.getActor() != null)
            // 权重设为较小值，确保优先级低于完工时间约束
            .penalizeLong(HardSoftLongScore.ofSoft(10), Sector::getCostFromPreviousSector)
            .asConstraint("Total travel distance");
}

为什么之前的二次惩罚效果不佳？ #

你之前使用的100 * sectors.size()²是基于任务数量的二次惩罚，但任务数量与实际路径耗时并非直接等价——少量远距离任务点的总耗时可能远多于多个近距离任务点。直接优化完工时间的最大值是更精准的目标，能直接引导OptaPlanner将任务分摊给多个Actor，避免单个Actor承担过长路径导致整体完工时间延迟。

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