Jsprit 的解决方案如果货物有多个尺寸的尺寸是不正确的
Solution of Jsprit is not correct if shipments have multiple size of dimension
我是 Jsprit 的新手。我试图在我的发货清单中使用多种尺寸的尺寸。例如，我在 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，则所有作业都会正确分配。这是否意味着该算法不支持多个维度？
当我在调试模式下进入代码时，我发现有一个分配 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 ...
我是 Jsprit 的新手。我试图在我的发货清单中使用多种尺寸的尺寸。例如，我在 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，则所有作业都会正确分配。这是否意味着该算法不支持多个维度？
当我在调试模式下进入代码时，我发现有一个分配 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 ...