如何在Jsprit Shipment中实现灵活的多取件多派送？

核心结论 #

Jsprit原生的Shipment模块仅支持1个取件点+1个派送点的标准模式，不直接支持多取多派场景，但可以通过两种方案实现需求：

方案一：拆分任务为标准Pickup/Delivery并添加关联约束 #

这是最快捷的实现方式，无需修改Jsprit核心代码，通过将多取多派任务拆分为独立的取件（Pickup）和派送（Delivery）任务，再通过自定义约束确保同一原始任务的取件全部完成后才执行派送。

步骤1：拆分任务并标记归属 #

为每个取件点创建独立Pickup任务，每个派送点创建独立Delivery任务，通过自定义属性标记它们属于同一个原始Shipment：

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import jsprit.core.problem.Location;
import jsprit.core.problem.job.Delivery;
import jsprit.core.problem.job.Pickup;

public class ShipmentSplitter {
    public static void main(String[] args) {
        String originalShipmentId = "SHIPMENT_001";
        // 模拟5个取件点、2个派送点
        List<Location> pickupLocations = Arrays.asList(
            Location.newInstance(1, 1), Location.newInstance(2, 2),
            Location.newInstance(3, 3), Location.newInstance(4, 3),
            Location.newInstance(5, 2)
        );
        List<Location> deliveryLocations = Arrays.asList(
            Location.newInstance(10, 5), Location.newInstance(12, 6)
        );

        // 创建取件任务
        List<Pickup> pickups = new ArrayList<>();
        for (int i = 0; i < pickupLocations.size(); i++) {
            Pickup pickup = Pickup.Builder.newInstance("PICKUP_" + originalShipmentId + "_" + i)
                .setLocation(pickupLocations.get(i))
                .addSizeDimension(0, 20) // 单批货物尺寸，根据实际调整
                .setAttribute("originalShipmentId", originalShipmentId)
                .build();
            pickups.add(pickup);
        }

        // 创建派送任务
        List<Delivery> deliveries = new ArrayList<>();
        for (int i = 0; i < deliveryLocations.size(); i++) {
            Delivery delivery = Delivery.Builder.newInstance("DELIVERY_" + originalShipmentId + "_" + i)
                .setLocation(deliveryLocations.get(i))
                .addSizeDimension(0, 20)
                .setAttribute("originalShipmentId", originalShipmentId)
                .build();
            deliveries.add(delivery);
        }

        // 将这些任务添加到VehicleRoutingProblem中
        // VehicleRoutingProblem.Builder vrpBuilder = ...
        // pickups.forEach(vrpBuilder::addJob);
        // deliveries.forEach(vrpBuilder::addJob);
    }
}

步骤2：添加硬约束确保取件优先于派送 #

自定义HardJobConstraint，检查同一原始Shipment的所有取件任务是否已被执行，未完成则禁止执行派送任务：

import jsprit.core.problem.job.Delivery;
import jsprit.core.problem.job.Job;
import jsprit.core.problem.job.Pickup;
import jsprit.core.problem.solution.route.activity.PickupActivity;
import jsprit.core.problem.solution.route.activity.TourActivity;
import jsprit.core.problem.vehicle.Vehicle;
import jsprit.core.problem.VehicleRoutingProblem;
import jsprit.core.problem.constraint.HardJobConstraint;
import jsprit.core.problem.constraint.ConstraintsStatus;
import jsprit.core.problem.solution.VehicleRoutingProblemSolution;
import jsprit.core.problem.solver.VehicleRoutingProblemSolver;

public class PickupBeforeDeliveryConstraint implements HardJobConstraint {
    @Override
    public ConstraintsStatus fulfilled(Job job, Vehicle vehicle, TourActivity prevActivity, TourActivity nextActivity, VehicleRoutingProblemSolution solution, VehicleRoutingProblemSolver solver) {
        if (job instanceof Delivery) {
            String originalShipmentId = (String) job.getAttribute("originalShipmentId");
            // 验证所有同归属的取件任务已被安排到路线中
            boolean allPickupsCompleted = solution.getRoutes().stream()
                .flatMap(route -> route.getActivities().stream())
                .filter(act -> act instanceof PickupActivity)
                .map(act -> (PickupActivity) act)
                .map(PickupActivity::getJob)
                .filter(p -> p instanceof Pickup)
                .map(p -> (Pickup) p)
                .anyMatch(p -> originalShipmentId.equals(p.getAttribute("originalShipmentId")));
            
            // 如果存在未完成的取件，约束不满足
            if (!allPickupsCompleted) {
                return ConstraintsStatus.NOT_FULFILLED;
            }
        }
        return ConstraintsStatus.FULFILLED;
    }
}

// 将约束添加到求解器
// VehicleRoutingProblemSolver.Builder solverBuilder = VehicleRoutingProblemSolver.Builder.newInstance(vrp);
// solverBuilder.addHardJobConstraint(new PickupBeforeDeliveryConstraint(), "pickup_before_delivery");

方案二：扩展Jsprit核心模型（自定义多取多送任务） #

如果业务场景复杂，拆分法无法满足需求（比如需要严格的取派顺序、统一的货物跟踪），可以自定义MultiPickupMultiDeliveryShipment类实现Job接口，同时修改Jsprit的求解器组件来支持自定义任务类型。

步骤1：自定义Job类型 #

import jsprit.core.problem.Location;
import jsprit.core.problem.job.Job;
import jsprit.core.problem.solution.route.activity.TourActivity;
import jsprit.core.problem.vehicle.Vehicle;
import jsprit.core.problem.Dimension;

import java.util.List;

public class MultiPickupMultiDeliveryShipment implements Job {
    private final String id;
    private final List<Location> pickupLocations;
    private final List<Location> deliveryLocations;
    private final Dimension size;

    private MultiPickupMultiDeliveryShipment(Builder builder) {
        this.id = builder.id;
        this.pickupLocations = builder.pickupLocations;
        this.deliveryLocations = builder.deliveryLocations;
        this.size = builder.size;
    }

    // 实现Job接口的所有方法
    @Override
    public String getId() { return id; }
    @Override
    public Dimension getSize() { return size; }
    // 其他方法如getLocation()可返回第一个取件点或自定义逻辑

    // Builder模式简化创建
    public static class Builder {
        private String id;
        private List<Location> pickupLocations;
        private List<Location> deliveryLocations;
        private Dimension size = Dimension.Builder.newInstance().build();

        public Builder setId(String id) {
            this.id = id;
            return this;
        }

        public Builder setPickupLocations(List<Location> pickupLocations) {
            this.pickupLocations = pickupLocations;
            return this;
        }

        public Builder setDeliveryLocations(List<Location> deliveryLocations) {
            this.deliveryLocations = deliveryLocations;
            return this;
        }

        public Builder setSize(Dimension size) {
            this.size = size;
            return this;
        }

        public MultiPickupMultiDeliveryShipment build() {
            return new MultiPickupMultiDeliveryShipment(this);
        }
    }
}

步骤2：扩展求解器组件 #

需要修改以下核心组件：

• VehicleRoutingProblemBuilder：支持添加自定义MultiPickupMultiDeliveryShipment任务
• RouteStateUpdater：处理多取件/派送时的车辆装载状态变化
• CostCalculator：计算多取多送任务的路径成本和时间成本
• ActivityFactory：将自定义任务转换为可执行的TourActivity实例

这种方式需要深入理解Jsprit的内部执行逻辑，适合有一定源码基础的开发者。

方案对比 #

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