How the costs affects the assignment of the fleet?

jsprit
1

Hi there

I have 3 vehicles (each one with different capacity) and 3 services (each service dimension matches one vehicle capacity).

If we set the fleet size to INFITE vrpBuilder.setFleetSize(FleetSize.INFINITE) and the cost per distance with any value .setCostPerDistance(10) then jsprit shows the results as it is expected: one service is assigned to each vehicle

Pasted image1073×449 7.75 KB

The problem is that when we set the fleet size to FINITE vrpBuilder.setFleetSize(FleetSize.FINITE) and the cost per distance is different from zero, jsprit leaves one job unassigned…

Pasted image1072×463 7.11 KB

If we set a finite fleet and zero cost then it assigns all the fleet.

Pasted image1081×457 6.99 KB

Why does the cost affect the use of the fleet?

2

Would you mind to post the entire problem so that we can reproduce it?

3

Hello,

Here is the code. Thanks for your attention.

`public class PR_CostMatrix_Fleet {

public static void main(String[] args) {
    /*
     * some preparation - create output folder
	 */
    Examples.createOutputFolder();
   
    VehicleTypeImpl type1 = VehicleTypeImpl.Builder.newInstance("type1").addCapacityDimension(0,150).setCostPerDistance(0).build();
    VehicleTypeImpl type2 = VehicleTypeImpl.Builder.newInstance("type2").addCapacityDimension(0,250).setCostPerDistance(0).build();
    VehicleTypeImpl type3 = VehicleTypeImpl.Builder.newInstance("type3").addCapacityDimension(0,350).setCostPerDistance(0).build();
    
    VehicleImpl vehicle1 = VehicleImpl.Builder.newInstance("vehicle1").setStartLocation(Location.newInstance("0")).setType(type1).build();
    VehicleImpl vehicle2 = VehicleImpl.Builder.newInstance("vehicle2").setStartLocation(Location.newInstance("0")).setType(type2).build();
    VehicleImpl vehicle3 = VehicleImpl.Builder.newInstance("vehicle3").setStartLocation(Location.newInstance("0")).setType(type3).build();

    Service s1 = Service.Builder.newInstance("1").addSizeDimension(0, 150).setLocation(Location.newInstance("1")).build();
    Service s2 = Service.Builder.newInstance("2").addSizeDimension(0, 250).setLocation(Location.newInstance("2")).build();
    Service s3 = Service.Builder.newInstance("3").addSizeDimension(0, 350).setLocation(Location.newInstance("3")).build();

    //define a matrix-builder building a matrix
    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", "0", 12.0);
    costMatrixBuilder.addTransportDistance("1", "2", 4.0);
    costMatrixBuilder.addTransportDistance("1", "3", 1.0);
    costMatrixBuilder.addTransportDistance("2", "0", 22.0);
    costMatrixBuilder.addTransportDistance("2", "1", 6.0);
    costMatrixBuilder.addTransportDistance("2", "3", 2.0);
    costMatrixBuilder.addTransportDistance("3", "0", 7.0);
    costMatrixBuilder.addTransportDistance("3", "1", 2.0);
    costMatrixBuilder.addTransportDistance("3", "2", 4.0);



    VehicleRoutingTransportCosts costMatrix = costMatrixBuilder.build();

    VehicleRoutingProblem.Builder vrpBuilder = VehicleRoutingProblem.Builder.newInstance();
    vrpBuilder.addVehicle(vehicle1);
    vrpBuilder.addVehicle(vehicle2);
    vrpBuilder.addVehicle(vehicle3);
    vrpBuilder.setFleetSize(FleetSize.FINITE);
    vrpBuilder.setRoutingCost(costMatrix);
    vrpBuilder.addJob(s1)
    		.addJob(s2)
    		.addJob(s3)
    		.build();

    VehicleRoutingProblem problem = vrpBuilder.build();
    VehicleRoutingAlgorithm algorithm = Jsprit.createAlgorithm(problem);

    Collection<VehicleRoutingProblemSolution> solutions = algorithm.searchSolutions();
    VehicleRoutingProblemSolution  bestSolution = Solutions.bestOf(solutions);

    //SolutionPrinter.print(Solutions.bestOf(solutions));      
    SolutionPrinter.print(problem, bestSolution, SolutionPrinter.Print.VERBOSE);

}

}`

4

Hi @pajaro5,

It seems that the default penalty for unassigned jobs is too small compared with the transport cost (especially considering that you set cost per distance as 10).

Therefore, you can

  1. set a smaller cost per distance; or

  2. set a higher penalty for unassigned jobs when building Jsprit algorithm, either by setting Jsprit.Parameter.MAX_TRANSPORT_COSTS to a larger value, or by constructing a custom objective function with a larger maxCosts.

Btw, your cost matrix builder should be with .newInstance(false) since the matrix is not symmetric.

Best regards,
He

1 Like