如何使用Jsprit中的成本矩阵解决取货和送货问题

Question

我尝试使用 Jsprit 通过成本矩阵来解决取货和送货问题。但是，解决方案不起作用。有谁知道哪里出了问题吗？

package com.graphhopper.jsprit.examples;

import java.util.Collection;

import com.graphhopper.jsprit.analysis.toolbox.GraphStreamViewer;
import com.graphhopper.jsprit.analysis.toolbox.Plotter;
import com.graphhopper.jsprit.analysis.toolbox.GraphStreamViewer.Label;
import com.graphhopper.jsprit.core.algorithm.VehicleRoutingAlgorithm;
import com.graphhopper.jsprit.core.algorithm.box.Jsprit;
import com.graphhopper.jsprit.core.algorithm.state.StateManager;
import com.graphhopper.jsprit.core.algorithm.termination.IterationWithoutImprovementTermination;
import com.graphhopper.jsprit.core.problem.Location;
import com.graphhopper.jsprit.core.problem.VehicleRoutingProblem;
import com.graphhopper.jsprit.core.problem.VehicleRoutingProblem.FleetSize;
import com.graphhopper.jsprit.core.problem.constraint.ConstraintManager;
import com.graphhopper.jsprit.core.problem.constraint.HardRouteConstraint;
import com.graphhopper.jsprit.core.problem.cost.VehicleRoutingTransportCosts;
import com.graphhopper.jsprit.core.problem.job.Shipment;
import com.graphhopper.jsprit.core.problem.misc.JobInsertionContext;
import com.graphhopper.jsprit.core.problem.solution.VehicleRoutingProblemSolution;
import com.graphhopper.jsprit.core.problem.solution.route.activity.TimeWindow;
import com.graphhopper.jsprit.core.problem.vehicle.VehicleImpl;
import com.graphhopper.jsprit.core.problem.vehicle.VehicleType;
import com.graphhopper.jsprit.core.problem.vehicle.VehicleTypeImpl;
import com.graphhopper.jsprit.core.problem.vehicle.VehicleImpl.Builder;
import com.graphhopper.jsprit.core.reporting.SolutionPrinter;
import com.graphhopper.jsprit.core.util.Coordinate;
import com.graphhopper.jsprit.core.util.Solutions;
import com.graphhopper.jsprit.core.util.VehicleRoutingTransportCostsMatrix;
import com.graphhopper.jsprit.util.Examples;

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;

    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");

        //new GraphStreamViewer(problem).labelWith(Label.ID).setRenderDelay(100).setRenderShipments(true).display();
        //new GraphStreamViewer(problem, Solutions.bestOf(solutions)).labelWith(Label.ACTIVITY).setRenderDelay(100).setRenderShipments(true).display();
    }

    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) {
                /*
                Shipment shipment2insert = ((Shipment) insertionContext.getJob());
                if (insertionContext.getNewVehicle().getId().equals("wheelchair_bus")) {
                    if (shipment2insert.getSize().get(PASSENGERSEATS_INDEX) > 0) {
                        if (shipment2insert.getPickupLocation().getCoordinate().getX() > 15. || shipment2insert.getDeliveryLocation().getCoordinate().getX() > 15.) {
                            return false;
                        }
                    }
                }
                */
                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);
        //builder1.setPickupTimeWindow(new TimeWindow(0,1));
        //builder1.setDeliveryTimeWindow(new TimeWindow(0,1));
        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);
        //builder2.setPickupTimeWindow(new TimeWindow(0,1));
        //builder2.setDeliveryTimeWindow(new TimeWindow(0,1));
        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);
        //builder3.setPickupTimeWindow(new TimeWindow(0,1));
        //builder3.setDeliveryTimeWindow(new TimeWindow(0,1));
        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);
        //builder4.setPickupTimeWindow(new TimeWindow(0,1));
        //builder4.setDeliveryTimeWindow(new TimeWindow(0,1));
        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);
        //builder5.setPickupTimeWindow(new TimeWindow(0,1));
        //builder5.setDeliveryTimeWindow(new TimeWindow(0,1));
        Shipment shipment5 = builder5.build();

        setTransportCost();

        vrpBuilder = VehicleRoutingProblem.Builder.newInstance();
        vrpBuilder.addVehicle(vehicle1).addVehicle(vehicle2).addVehicle(vehicle1_2).addVehicle(vehicle2_2);
        vrpBuilder.addJob(shipment1).addJob(shipment2).addJob(shipment3).addJob(shipment4);
        vrpBuilder.addJob(shipment5);
        /*.addJob(shipment6).addJob(shipment7).addJob(shipment8);
        vrpBuilder.addJob(shipment9).addJob(shipment10).addJob(shipment11).addJob(shipment12);
        vrpBuilder.addJob(shipment13).addJob(shipment14).addJob(shipment15).addJob(shipment16);
        vrpBuilder.addJob(shipment17).addJob(shipment18).addJob(shipment19).addJob(shipment20);*/

        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.addTransportDistance("0", "1", 10.0);
        costMatrixBuilder.addTransportDistance("0", "2", 20.0);
        costMatrixBuilder.addTransportDistance("0", "3", 5.0);
        costMatrixBuilder.addTransportDistance("1", "2", 4.0);
        costMatrixBuilder.addTransportDistance("1", "3", 1.0);
        costMatrixBuilder.addTransportDistance("2", "3", 2.0);
         */
        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"));
        vehicleBuilder1.setType(vehicleType_wheelchair);
        vehicle1 = vehicleBuilder1.build();

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

        Builder vehicleBuilder2 = VehicleImpl.Builder.newInstance("passenger_bus");
        vehicleBuilder2.setStartLocation(Location.newInstance("0"));
        vehicleBuilder2.setType(vehicleType_solelypassenger);
        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);
        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);
        vehicleType_wheelchair = wheelChairTypeBuilder.build();

        VehicleTypeImpl.Builder soleyPassengerTypeBuilder = VehicleTypeImpl.Builder.newInstance("passengerBusType");
        soleyPassengerTypeBuilder.addCapacityDimension(PASSENGERSEATS_INDEX, 6);
        vehicleType_solelypassenger = soleyPassengerTypeBuilder.build();
    }

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

我使用了 Jsprit TransportOfDisabledPeople and costMatrixExample 中的示例来创建我的 problem.However，我的代码似乎无法正常工作。如果我遗漏了代码中的任何内容，请告诉我。我试图弄清楚但失败了。

Answer 1

我找到了解决方案。我必须为每种车辆类型设置每次运输时间的成本。

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();
}

如何使用Jsprit中的成本矩阵解决取货和送货问题

How to solve pick up and delivery problem using cost matrix in Jsprit

routing

jsprit

vehicle-routing