algorithm - Jsprit 的解决方案如果 cargo 有多个尺寸的尺寸是不正确的-6ren

algorithm - Jsprit 的解决方案如果 cargo 有多个尺寸的尺寸是不正确的

转载作者：塔克拉玛干更新时间：2023-11-03 05:13:33

我是 Jsprit 的新手。我试图在我的发货 list 中使用多种尺寸的尺寸。例如，我在 createJob() 中使用 WHEELCHAIRSPACE_INDEX 添加了一些货件的尺寸大小，而一些货件使用了 PASSENGERSEATS_INDEX。但是输出似乎是错误的。

public class Test {

static int WHEELCHAIRSPACE_INDEX = 0;

static int PASSENGERSEATS_INDEX = 1;

private VehicleType vehicleType_wheelchair;

private VehicleType vehicleType_solelypassenger;

private VehicleImpl vehicle1,vehicle1_2,vehicle2,vehicle2_2;

private VehicleRoutingProblem.Builder vrpBuilder;

private HardRouteConstraint wheelchair_bus_passenger_pickup_constraint;

private VehicleRoutingAlgorithm algorithm;

private VehicleRoutingProblem problem;

private VehicleRoutingTransportCosts costMatrix;

private static final String FILENAME = "C:\\Users\\admin\\Desktop\\test.txt";

public static void main(String[] args) {
    // TODO Auto-generated method stub
    Examples.createOutputFolder();
    Test test = new Test();
    test.createVehicleType();
    test.createVehicle();
    test.createJob();
    test.createConstraint();
    test.createProblem();
    test.searchSolution();
}

private void searchSolution() {
    Collection<VehicleRoutingProblemSolution> solutions = algorithm.searchSolutions();
    VehicleRoutingProblemSolution bestSolution = Solutions.bestOf(solutions);
    SolutionPrinter.print(problem, bestSolution, SolutionPrinter.Print.VERBOSE);

    Plotter problemPlotter = new Plotter(problem);
    problemPlotter.plotShipments(true);
    problemPlotter.setLabel(Plotter.Label.SIZE);
    problemPlotter.plot("output/transportOfDisabledPeopleExample_problem.png", "disabled people tp");

    Plotter solutionPlotter = new Plotter(problem, Solutions.bestOf(solutions));
    solutionPlotter.plotShipments(true);
    solutionPlotter.setLabel(Plotter.Label.SIZE);
    solutionPlotter.plot("output/transportOfDisabledPeopleExample_solution.png", "disabled people tp");


}

private void createProblem() {


    StateManager stateManager = new StateManager(problem);

    ConstraintManager constraintManager = new ConstraintManager(problem, stateManager);
    constraintManager.addConstraint(wheelchair_bus_passenger_pickup_constraint);


    algorithm = Jsprit.Builder.newInstance(problem).setStateAndConstraintManager(stateManager,constraintManager).buildAlgorithm();
    algorithm.setPrematureAlgorithmTermination(new IterationWithoutImprovementTermination(100));
}

private void createConstraint() {
    wheelchair_bus_passenger_pickup_constraint = new HardRouteConstraint() {

        @Override
        public boolean fulfilled(JobInsertionContext insertionContext) {

            return true;
        }
    };
}

private void createJob() {
    com.graphhopper.jsprit.core.problem.job.Shipment.Builder builder1 = Shipment.Builder.newInstance("1");
    builder1.addSizeDimension(WHEELCHAIRSPACE_INDEX, 1);
    builder1.setPickupLocation(Location.newInstance("1a"));
    builder1.setDeliveryLocation(Location.newInstance("1b"));
    builder1.setDeliveryServiceTime(0);

    Shipment shipment1 = builder1.build();

    com.graphhopper.jsprit.core.problem.job.Shipment.Builder builder2 = Shipment.Builder.newInstance("2");
    builder2.addSizeDimension(PASSENGERSEATS_INDEX, 1);
    builder2.setPickupLocation(Location.newInstance("2a"));
    builder2.setDeliveryLocation(Location.newInstance("2b"));
    builder2.setDeliveryServiceTime(0);

    Shipment shipment2 = builder2.build();

    com.graphhopper.jsprit.core.problem.job.Shipment.Builder builder3 = Shipment.Builder.newInstance("3");
    builder3.addSizeDimension(WHEELCHAIRSPACE_INDEX, 1);
    builder3.setPickupLocation(Location.newInstance("3a"));
    builder3.setDeliveryLocation(Location.newInstance("3b"));
    builder3.setDeliveryServiceTime(0);

    Shipment shipment3 = builder3.build();

    com.graphhopper.jsprit.core.problem.job.Shipment.Builder builder4 = Shipment.Builder.newInstance("4");
    builder4.addSizeDimension(PASSENGERSEATS_INDEX, 1);
    builder4.setPickupLocation(Location.newInstance("4a"));
    builder4.setDeliveryLocation(Location.newInstance("4b"));
    builder4.setDeliveryServiceTime(0);

    Shipment shipment4 = builder4.build();

    com.graphhopper.jsprit.core.problem.job.Shipment.Builder builder5 = Shipment.Builder.newInstance("5");
    builder5.addSizeDimension(WHEELCHAIRSPACE_INDEX, 1);
    builder5.setPickupLocation(Location.newInstance("5a"));
    builder5.setDeliveryLocation(Location.newInstance("5b"));
    builder5.setDeliveryServiceTime(0);

    Shipment shipment5 = builder5.build();

    setTransportCost();

    vrpBuilder = VehicleRoutingProblem.Builder.newInstance();
    vrpBuilder.addVehicle(vehicle1);
    vrpBuilder.addVehicle(vehicle2);
    vrpBuilder.addVehicle(vehicle1_2);
    vrpBuilder.addVehicle(vehicle2_2);
    vrpBuilder.addJob(shipment1).addJob(shipment2).addJob(shipment3).addJob(shipment4);
    vrpBuilder.addJob(shipment5);

    vrpBuilder.setFleetSize(FleetSize.FINITE);
    vrpBuilder.setRoutingCost(costMatrix);
    problem = vrpBuilder.build();

}

private void setTransportCost() {
    // TODO Auto-generated method stub
    VehicleRoutingTransportCostsMatrix.Builder costMatrixBuilder = VehicleRoutingTransportCostsMatrix.Builder.newInstance(true);

    costMatrixBuilder.addTransportTime("0", "0", 0.0);
    costMatrixBuilder.addTransportTime("0", "1a", 2.0);
    costMatrixBuilder.addTransportTime("0", "1b", 3.3);
    costMatrixBuilder.addTransportTime("0", "2a", 2.0);
    costMatrixBuilder.addTransportTime("0", "2b", 4.3);
    costMatrixBuilder.addTransportTime("0", "3a", 3.5);
    costMatrixBuilder.addTransportTime("0", "3b", 3.0);
    costMatrixBuilder.addTransportTime("0", "4a", 1.5);
    costMatrixBuilder.addTransportTime("0", "4b", 2.7);
    costMatrixBuilder.addTransportTime("0", "5a", 1.2);
    costMatrixBuilder.addTransportTime("0", "5b", 3.5);

    costMatrixBuilder.addTransportTime("1a", "0", 2.0);
    costMatrixBuilder.addTransportTime("1a", "1a", 0.0);
    costMatrixBuilder.addTransportTime("1a", "1b", 2.5);
    costMatrixBuilder.addTransportTime("1a", "2a", 2.3);
    costMatrixBuilder.addTransportTime("1a", "2b", 4.4);
    costMatrixBuilder.addTransportTime("1a", "3a", 4.0);
    costMatrixBuilder.addTransportTime("1a", "3b", 4.0);
    costMatrixBuilder.addTransportTime("1a", "4a", 2.3);
    costMatrixBuilder.addTransportTime("1a", "4b", 4.5);
    costMatrixBuilder.addTransportTime("1a", "5a", 3.2);
    costMatrixBuilder.addTransportTime("1a", "5b", 1.5);

    costMatrixBuilder.addTransportTime("1b", "0", 3.3);
    costMatrixBuilder.addTransportTime("1b", "1a", 2.5);
    costMatrixBuilder.addTransportTime("1b", "1b", 0.0);
    costMatrixBuilder.addTransportTime("1b", "2a", 1.7);
    costMatrixBuilder.addTransportTime("1b", "2b", 2.2);
    costMatrixBuilder.addTransportTime("1b", "3a", 2.5);
    costMatrixBuilder.addTransportTime("1b", "3b", 3.4);
    costMatrixBuilder.addTransportTime("1b", "4a", 4.5);
    costMatrixBuilder.addTransportTime("1b", "4b", 5.0);
    costMatrixBuilder.addTransportTime("1b", "5a", 4.5);
    costMatrixBuilder.addTransportTime("1b", "5b", 2.2);

    costMatrixBuilder.addTransportTime("2a", "0", 2.0);
    costMatrixBuilder.addTransportTime("2a", "1a", 2.3);
    costMatrixBuilder.addTransportTime("2a", "1b", 1.7);
    costMatrixBuilder.addTransportTime("2a", "2a", 0.0);
    costMatrixBuilder.addTransportTime("2a", "2b", 2.3);
    costMatrixBuilder.addTransportTime("2a", "3a", 1.7);
    costMatrixBuilder.addTransportTime("2a", "3b", 1.8);
    costMatrixBuilder.addTransportTime("2a", "4a", 3.3);
    costMatrixBuilder.addTransportTime("2a", "4b", 3.2);
    costMatrixBuilder.addTransportTime("2a", "5a", 3.0);
    costMatrixBuilder.addTransportTime("2a", "5b", 2.9);

    costMatrixBuilder.addTransportTime("2b", "0", 4.3);
    costMatrixBuilder.addTransportTime("2b", "1a", 4.4);
    costMatrixBuilder.addTransportTime("2b", "1b", 2.2);
    costMatrixBuilder.addTransportTime("2b", "2a", 2.3);
    costMatrixBuilder.addTransportTime("2b", "2b", 0.0);
    costMatrixBuilder.addTransportTime("2b", "3a", 1.2);
    costMatrixBuilder.addTransportTime("2b", "3b", 2.8);
    costMatrixBuilder.addTransportTime("2b", "4a", 5.7);
    costMatrixBuilder.addTransportTime("2b", "4b", 4.5);
    costMatrixBuilder.addTransportTime("2b", "5a", 5.2);
    costMatrixBuilder.addTransportTime("2b", "5b", 4.3);

    costMatrixBuilder.addTransportTime("3a", "0", 3.5);
    costMatrixBuilder.addTransportTime("3a", "1a", 4.0);
    costMatrixBuilder.addTransportTime("3a", "1b", 2.5);
    costMatrixBuilder.addTransportTime("3a", "2a", 1.7);
    costMatrixBuilder.addTransportTime("3a", "2b", 1.2);
    costMatrixBuilder.addTransportTime("3a", "3a", 0.0);
    costMatrixBuilder.addTransportTime("3a", "3b", 1.5);
    costMatrixBuilder.addTransportTime("3a", "4a", 5.0);
    costMatrixBuilder.addTransportTime("3a", "4b", 3.3);
    costMatrixBuilder.addTransportTime("3a", "5a", 4.2);
    costMatrixBuilder.addTransportTime("3a", "5b", 4.3);

    costMatrixBuilder.addTransportTime("3b", "0", 3.0);
    costMatrixBuilder.addTransportTime("3b", "1a", 4.0);
    costMatrixBuilder.addTransportTime("3b", "1b", 3.4);
    costMatrixBuilder.addTransportTime("3b", "2a", 1.8);
    costMatrixBuilder.addTransportTime("3b", "2b", 2.8);
    costMatrixBuilder.addTransportTime("3b", "3a", 1.5);
    costMatrixBuilder.addTransportTime("3b", "3b", 0.0);
    costMatrixBuilder.addTransportTime("3b", "4a", 4.3);
    costMatrixBuilder.addTransportTime("3b", "4b", 1.8);
    costMatrixBuilder.addTransportTime("3b", "5a", 2.8);
    costMatrixBuilder.addTransportTime("3b", "5b", 5.0);

    costMatrixBuilder.addTransportTime("4a", "0", 1.5);
    costMatrixBuilder.addTransportTime("4a", "1a", 2.3);
    costMatrixBuilder.addTransportTime("4a", "1b", 4.5);
    costMatrixBuilder.addTransportTime("4a", "2a", 3.3);
    costMatrixBuilder.addTransportTime("4a", "2b", 5.7);
    costMatrixBuilder.addTransportTime("4a", "3a", 5.0);
    costMatrixBuilder.addTransportTime("4a", "3b", 4.3);
    costMatrixBuilder.addTransportTime("4a", "4a", 0.0);
    costMatrixBuilder.addTransportTime("4a", "4b", 3.6);
    costMatrixBuilder.addTransportTime("4a", "5a", 1.7);
    costMatrixBuilder.addTransportTime("4a", "5b", 3.8);

    costMatrixBuilder.addTransportTime("4b", "0", 2.7);
    costMatrixBuilder.addTransportTime("4b", "1a", 4.5);
    costMatrixBuilder.addTransportTime("4b", "1b", 5.0);
    costMatrixBuilder.addTransportTime("4b", "2a", 3.2);
    costMatrixBuilder.addTransportTime("4b", "2b", 4.5);
    costMatrixBuilder.addTransportTime("4b", "3a", 3.3);
    costMatrixBuilder.addTransportTime("4b", "3b", 1.8);
    costMatrixBuilder.addTransportTime("4b", "4a", 3.6);
    costMatrixBuilder.addTransportTime("4b", "4b", 0.0);
    costMatrixBuilder.addTransportTime("4b", "5a", 1.9);
    costMatrixBuilder.addTransportTime("4b", "5b", 5.7);

    costMatrixBuilder.addTransportTime("5a", "0", 1.2);
    costMatrixBuilder.addTransportTime("5a", "1a", 3.2);
    costMatrixBuilder.addTransportTime("5a", "1b", 4.5);
    costMatrixBuilder.addTransportTime("5a", "2a", 3.0);
    costMatrixBuilder.addTransportTime("5a", "2b", 5.2);
    costMatrixBuilder.addTransportTime("5a", "3a", 4.2);
    costMatrixBuilder.addTransportTime("5a", "3b", 2.8);
    costMatrixBuilder.addTransportTime("5a", "4a", 1.7);
    costMatrixBuilder.addTransportTime("5a", "4b", 1.9);
    costMatrixBuilder.addTransportTime("5a", "5a", 0.0);
    costMatrixBuilder.addTransportTime("5a", "5b", 4.7);

    costMatrixBuilder.addTransportTime("5b", "0", 3.5);
    costMatrixBuilder.addTransportTime("5b", "1a", 1.5);
    costMatrixBuilder.addTransportTime("5b", "1b", 2.2);
    costMatrixBuilder.addTransportTime("5b", "2a", 2.9);
    costMatrixBuilder.addTransportTime("5b", "2b", 4.3);
    costMatrixBuilder.addTransportTime("5b", "3a", 4.3);
    costMatrixBuilder.addTransportTime("5b", "3b", 5.0);
    costMatrixBuilder.addTransportTime("5b", "4a", 3.8);
    costMatrixBuilder.addTransportTime("5b", "4b", 5.7);
    costMatrixBuilder.addTransportTime("5b", "5a", 4.7);
    costMatrixBuilder.addTransportTime("5b", "5b", 0.0);

    costMatrix = costMatrixBuilder.build();
}

private void createVehicle() {
    Builder vehicleBuilder1 = VehicleImpl.Builder.newInstance("wheelchair_bus");
    vehicleBuilder1.setStartLocation(Location.newInstance("0")).setEndLocation(Location.newInstance("0"));
    vehicleBuilder1.setType(vehicleType_wheelchair);
    vehicleBuilder1.setEarliestStart(0);
    vehicleBuilder1.setLatestArrival(10);
    vehicle1 = vehicleBuilder1.build();

    Builder vehicleBuilder1_2 = VehicleImpl.Builder.newInstance("wheelchair_bus_2");
    vehicleBuilder1_2.setStartLocation(Location.newInstance("0")).setEndLocation(Location.newInstance("0"));
    vehicleBuilder1_2.setType(vehicleType_wheelchair);
    vehicleBuilder1_2.setEarliestStart(0);
    vehicleBuilder1_2.setLatestArrival(10);
    vehicle1_2 = vehicleBuilder1_2.build();

    Builder vehicleBuilder2 = VehicleImpl.Builder.newInstance("passenger_bus");
    vehicleBuilder2.setStartLocation(Location.newInstance("0")).setEndLocation(Location.newInstance("0"));
    vehicleBuilder2.setType(vehicleType_solelypassenger);
    vehicleBuilder2.setEarliestStart(0);
    vehicleBuilder2.setLatestArrival(10);
    vehicle2 = vehicleBuilder2.build();

    Builder vehicleBuilder2_2 = VehicleImpl.Builder.newInstance("passenger_bus_2");
    vehicleBuilder2_2.setStartLocation(Location.newInstance("0")).setEndLocation(Location.newInstance("0"));
    vehicleBuilder2_2.setType(vehicleType_solelypassenger);
    vehicleBuilder2_2.setEarliestStart(0);
    vehicleBuilder2_2.setLatestArrival(10);
    vehicle2_2 = vehicleBuilder2_2.build();
}

private void createVehicleType() {
    VehicleTypeImpl.Builder wheelChairTypeBuilder = VehicleTypeImpl.Builder.newInstance("wheelChairBusType");
    wheelChairTypeBuilder.addCapacityDimension(WHEELCHAIRSPACE_INDEX, 2);
    wheelChairTypeBuilder.addCapacityDimension(PASSENGERSEATS_INDEX, 4);
    //wheelChairTypeBuilder.setCostPerDistance(1);
    wheelChairTypeBuilder.setCostPerTransportTime(2);
    vehicleType_wheelchair = wheelChairTypeBuilder.build();

    VehicleTypeImpl.Builder soleyPassengerTypeBuilder = VehicleTypeImpl.Builder.newInstance("passengerBusType");
    soleyPassengerTypeBuilder.addCapacityDimension(PASSENGERSEATS_INDEX, 6);
    //soleyPassengerTypeBuilder.setCostPerDistance(1);
    soleyPassengerTypeBuilder.setCostPerTransportTime(2);
    vehicleType_solelypassenger = soleyPassengerTypeBuilder.build();
}

private static Location loc(Coordinate coordinate) {
    return Location.Builder.newInstance().setCoordinate(coordinate).build();
}

这是输出

装运 1 和装运 5 未分配到作业列表。但是，如果我将所有维度的大小更改为 PASSENGERSEATS_INDEX，则所有作业都会正确分配。这是否意味着该算法不支持多个维度？

当我在 Debug模式下进入代码时，我发现有一个分配 4 个作业的解决方案。然而，它被认为是 Jsprit 中不被接受的解决方案。从逻辑上看，这个解决方案应该是正确的解决方案，因为它最大限度地减少了未分配的工作(与原始解决方案相比，只分配 3 个工作)。

最佳答案

当您构建成本矩阵时，您只指定了旅行时间，而不是距离。

默认情况下，未分配任务的成本取决于取货地点和送货地点之间的(最大)距离。由于未设置距离，因此未分配的工作不会受到惩罚。

一个简单的解决方案是在构建成本矩阵时添加一些合理的距离度量:

     private void setTransportCost() {
        VehicleRoutingTransportCostsMatrix.Builder costMatrixBuilder = VehicleRoutingTransportCostsMatrix.Builder.newInstance(true);

        String[] locationIds = new String[] {"0", "1a", "1b", "2a", "2b", "3a", "3b", "4a", "4b", "5a", "5b"};
        for (String l1: locationIds) {
            for (String l2: locationIds) {
                if (!l1.equals(l2)) {
                    costMatrixBuilder.addTransportDistance(l1, l2, 5);
                }
            }
        }

       // ... on with original implementation ...

关于algorithm - Jsprit 的解决方案如果 cargo 有多个尺寸的尺寸是不正确的，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/54015998/

文章推荐： java - 检查混音器线路中的音频播放电平？

文章推荐： java - Java 包名中的下划线——不好吗？

文章推荐： java - 检查单元测试是否委托(delegate)了所有方法

jsprit - jsprit TSP 和 VRP 求解器是否允许提供点之间的时间和距离限制？
有谁知道 jsprit 求解器是否默认使用路径中两点之间的“像乌鸦一样”的几何距离？如果是这样，是否可以通过向 jsprit 提供预先计算的时间/相邻点之间的距离的参数来限制这一点，例如由Google
jsprit - 如何将jsprit与时间窗口一起使用？
我不明白如何在 jsprit 中使用时间窗口。我知道这是您通过以下方法赋予车辆的值(value): setLatestArrival(1236); 对于像这样的服务: setTimeWindow(T
jsprit - 车辆路线规划服务的自动分配
我正在使用 Jsprit对于车辆路由，我对现有解决方案中新服务的自动分配感到震惊，是否有任何解决方法。最佳答案赋予所有车辆独特的技能。任何预先解决的订单都必须在新问题中根据最初分配到的车辆的技能要
java - JSprit:如何最大化可用车辆的数量以减少时间
我正在尝试解决一个由取货和送货组成的 vrp。我有 73 辆车，我想使用所有可用的车辆来减少整体流程时间。我观察到结果是 24 辆车从未使用过，而其他人则获得了多项工作。问题是一些分配的车辆实际上回到
jobs - JSprit 中的相关职位
是否可以在 jsprit 中处理作业(在本例中为服务)之间的关系？例如，一项工作必须与一项或多项其他工作同时开始。或者一项工作不得在另一项工作结束之前开始(正常顺序)。如果没有，您知道可以处理此类
jsprit 入门 : conceptional advice
对不起，这不是一个具体的问题。因为我是 Jsprit 的新手，所以我需要一些关于如何开始解决问题的概念性帮助。我的例子: 我开始时只有一辆车带有开始和结束位置。有多个优先取货位置，只有一个仓库位置用
java - 无法通过使用 Jsprit 向服务提供时间窗口来获得正确的优化路线
我正在尝试使用Jsprit来获得优化的路线。我有三个工作，每个工作都有自己的时间窗口。现在是这样的 VehicleTypeImpl.Builder vehicleTypeBui
java - 在 jsprit 中使用带有日期的时间窗口
我正在使用 VRP 做一个学校项目。我试图解决的问题是生成具有多个点的路线，每个点必须在一个时间窗口中执行。我的问题是如何将日期(unix 时间戳)转换为 jsprit 中的时间窗口，因为算法从 0
java - 由于时间问题，JSprit 不使用更近的车辆
两辆车的单一作业时间表。一辆车从靠近工作地点的地方出发，另一辆车从远离工作地点的地方出发。似乎它应该更喜欢使用距离较近的车辆，因为按距离计算费用。但如果 setCostPerWaitingTime()
algorithm - Jsprit 的解决方案如果 cargo 有多个尺寸的尺寸是不正确的
我是 Jsprit 的新手。我试图在我的发货 list 中使用多种尺寸的尺寸。例如，我在 createJob() 中使用 WHEELCHAIRSPACE_INDEX 添加了一些货件的尺寸大小，而一些货
java - JSPRIT 中的 CapacityDimension 是什么？
VehicleTypeImpl.Builder.newInstance("vehicleType").addCapacityDimension(0, 2) 中 jsprit 中的尺寸是多少？我们可以
java - 使用 GraphHopper 和 jsprit 构建矩阵
我正在 Java 中构建一个路由服务，其中包含用于生成点之间路线的 graphhopper 等路由工具，以及通过 Maven 嵌入到应用程序中的用于解决车辆路由问题的 jsprit。在jsprit中
java - Jsprit : Can't add multiple related jobs
我正在使用 JSPRIT 来解决路由和旅行者问题。它实际上适用于简单的约束(时间、容量等)。但我试图实现“相关工作”约束。对于像第 7 个工作在列表中的第 1 个之前服务的简单案例，我成功了。我想对
java - jsprit 作为 php web 应用程序的后端
由于我没有 Java 编程经验，所以我在这里可能找错了树。我遇到了 jsprit，一个基于 java 的 VRP 求解器，它看起来非常令人印象深刻，我想知道它是否可以用于基于 php 的网络应用程序

塔克拉玛干

个人简介

我是一名优秀的程序员,十分优秀！

作者热门文章

滴滴打车优惠券免费领取

全站热门文章

首页

博学

6Ren·AI

商城

algorithm - Jsprit 的解决方案如果 cargo 有多个尺寸的尺寸是不正确的