基于Timefold的电动车辆VRP充电行程建模技术咨询

核心思路 #

针对带充电需求的电动车辆VRP，核心是将充电行为转化为求解器可识别的规划元素，同时满足续航约束与多趟行程需求。以下是两种评估方案的落地建议，以及更优实践方向：

方案1：将充电建模为可选行程（推荐） #

把母站/充电站的充电操作定义为特殊的Visit（行程节点），标记为可选未分配状态（isUnassigned=true），通过约束控制其分配时机：

• 模型定义：
  • 给车辆类扩展currentMileage（当前已行驶里程）、maxMileage（最大续航）属性；
  • 创建ChargingVisit子类继承基础行程节点，绑定充电站（母站）位置、固定充电时长（如30分钟），默认设为未分配。
• 约束实现：
  • 硬约束：当车辆当前里程 + 下一段行程预估里程 > 最大续航时，必须插入充电行程；
  • 硬约束：充电行程完成后，重置车辆currentMileage为0；
  • 软约束：尽量减少充电次数（优化运营成本）。
• 优势：直接复用Timefold VRP原有行程分配逻辑，求解器可自动调整充电节点插入位置，天然适配多趟行程场景（每趟行程结束后若续航不足，可插入充电再开启下一趟）。

方案2：将充电建模为带位置的预约 #

把充电视为车辆在特定条件下必须执行的“强制预约任务”，通过约束确保触发时机：

• 模型定义：
  • 给车辆添加needsCharging布尔属性，续航即将耗尽时标记为true；
  • 定义ChargingAppointment实体，关联充电站位置与固定时长，与车辆绑定。
• 约束实现：
  • 硬约束：若needsCharging=true，车辆必须优先前往充电站完成充电，才能继续服务客户；
  • 硬约束：充电完成后重置needsCharging为false，同时重置续航。
• 注意点：需额外维护车辆续航状态判断逻辑，求解器灵活性弱于方案1，适合充电点固定、规则简单的场景。

关键建模细节 #

• 续航计算：实时跟踪车辆行驶里程，每完成一段行程更新currentMileage，充电后重置为0；
• 多趟行程支持：允许车辆完成一趟客户服务行程后，插入充电行程再开启下一趟，不限制行程次数；
• Timefold适配：扩展原有的VehicleRoutingConstraintProvider，添加充电相关硬/软约束，比如在arrivalTime计算中纳入充电时长。

实践示例（伪代码） #

车辆类扩展 #

public class ElectricVehicle extends Vehicle {
    private int maxMileage; // 最大续航里程
    private int currentMileage; // 当前已行驶里程
    // 原有属性...
}

充电行程节点 #

public class ChargingVisit extends Visit {
    private static final int CHARGING_DURATION = 30; // 固定充电时长（分钟）
    public ChargingVisit() {
        super(DepotLocation.getInstance()); // 绑定母站位置
        setUnassigned(true);
    }
    @Override
    public int getDuration() {
        return CHARGING_DURATION;
    }
}

约束示例 #

public class ElectricVrpConstraintProvider implements ConstraintProvider {
    @Override
    public Constraint[] defineConstraints(ConstraintFactory constraintFactory) {
        return new Constraint[] {
            enforceChargingWhenLow(constraintFactory),
            resetMileageAfterCharging(constraintFactory),
            minimizeChargingStops(constraintFactory)
        };
    }

    private Constraint enforceChargingWhenLow(ConstraintFactory constraintFactory) {
        return constraintFactory.from(ElectricVehicle.class)
                .join(Visit.class, Joiners.equal(Vehicle::getId, Visit::getVehicleId))
                .filter((vehicle, nextVisit) -> 
                    vehicle.getCurrentMileage() + calculateDistance(vehicle.getLastLocation(), nextVisit.getLocation()) > vehicle.getMaxMileage())
                .penalize("Enforce charging when mileage is low", HardSoftScore.ONE_HARD)
                .asConstraint();
    }

    // 其他约束实现...
}

内容的提问来源于stack exchange，提问作者Ayush Kumar Srivastava 0223-19