Unassigned Job Issue

jsprit
1

Hi,
I am trying to model a scenario where there are 2 shipments having same pickup and destination locations and pickup time window.

Shipment S1 required capacity : 4500
Shipment S2 required capacity : 2500

There are 2 vehicles(V1,V2) available at pickup location(same coordinates) with capacity of 5000 and 3000 respectively.

In this scenario, S1 should get assigned to V1 and S2 to V2.

However, S2 is getting assigned to V1 keeping S1 in unassigned state. Not sure if I am missing something. I am using version 1.6.3-SNAPSHOT

Regards,
Amit

Code:
public class MultipleShipmentMultipleVehicles {

public static void main(String[] args) {

	Location.Builder locBuilder = Location.Builder.newInstance();
	Coordinate coordinate1 = Coordinate.newInstance(5, 7);
	locBuilder.setId("VL1").setCoordinate(coordinate1);
	Location VL1 = locBuilder.build();

	Location.Builder locBuilder1 = Location.Builder.newInstance();
	locBuilder1.setId("PL1").setCoordinate(coordinate1);
	Location PL1 = locBuilder1.build();

	Location.Builder locBuilder2 = Location.Builder.newInstance();
	Coordinate coordinate2 = Coordinate.newInstance(6, 9);
	locBuilder2.setId("DL1").setCoordinate(coordinate2);
	Location DL1 = locBuilder2.build();

	VehicleTypeImpl.Builder vehicleType1Builder = VehicleTypeImpl.Builder.newInstance("vehicleType1")
			.addCapacityDimension(0, 5000);
	VehicleType vehicleType1 = vehicleType1Builder.build();

	Builder vehicleBuilder1 = VehicleImpl.Builder.newInstance("V1");
	vehicleBuilder1.setStartLocation(VL1);
	vehicleBuilder1.setType(vehicleType1);
	VehicleImpl vehicle1 = vehicleBuilder1.build();

	
	VehicleTypeImpl.Builder vehicleType2Builder = VehicleTypeImpl.Builder.newInstance("vehicleType2")
			.addCapacityDimension(0, 3000);
	VehicleType vehicleType2 = vehicleType2Builder.build();
	
	Builder vehicleBuilder2 = VehicleImpl.Builder.newInstance("V2");
	vehicleBuilder2.setStartLocation(VL1);
	vehicleBuilder2.setType(vehicleType2);
	VehicleImpl vehicle2 = vehicleBuilder2.build();

	VehicleRoutingTransportCostsMatrix.Builder costMatrixBuilder = com.graphhopper.jsprit.core.util.VehicleRoutingTransportCostsMatrix.Builder
			.newInstance(true);

	costMatrixBuilder.addTransportDistance("PL1", "DL1", 10.0);
	costMatrixBuilder.addTransportTime("PL1", "DL1", 60.0);

	costMatrixBuilder.addTransportDistance("VL1", "DL1", 25.0);
	costMatrixBuilder.addTransportTime("VL1", "DL1", 150.0);

	costMatrixBuilder.addTransportDistance("VL1", "PL1", 0);
	costMatrixBuilder.addTransportTime("VL1", "PL1", 0);

	VehicleRoutingTransportCosts costMatrix = costMatrixBuilder.build();

	Shipment shipment1 = Shipment.Builder.newInstance("S1").addSizeDimension(0, 4500).setPickupLocation(PL1)
			.setDeliveryLocation(DL1).setPickupTimeWindow(new TimeWindow(200.0, 200.00)).build();

	Shipment shipment2 = Shipment.Builder.newInstance("S2").addSizeDimension(0, 2500).setPickupLocation(PL1)
			.setDeliveryLocation(DL1).setPickupTimeWindow(new TimeWindow(200.0, 200.00)).build();

	VehicleRoutingProblem.Builder vrpBuilder = VehicleRoutingProblem.Builder.newInstance();

	vrpBuilder.addVehicle(vehicle1).addVehicle(vehicle2);
	vrpBuilder.addJob(shipment1).addJob(shipment2);

	vrpBuilder.setFleetSize(FleetSize.FINITE);

	VehicleRoutingProblem problem = vrpBuilder.setRoutingCost(costMatrix).build();

	StateManager stateManager = new StateManager(problem);

	stateManager.addStateUpdater(new StateVisitor(stateManager));
	VehicleRoutingAlgorithm algorithm = Jsprit.Builder.newInstance(problem).addCoreStateAndConstraintStuff(true)
			.setProperty(Jsprit.Parameter.VEHICLE_SWITCH, "true").buildAlgorithm();

	algorithm.setMaxIterations(2000);
	Collection<VehicleRoutingProblemSolution> solutions = algorithm.searchSolutions();

	VehicleRoutingProblemSolution bestSolution = Solutions.bestOf(solutions);

	SolutionPrinter.print(problem, bestSolution, SolutionPrinter.Print.VERBOSE);

}

}

2

Hi Amit,

A quick way to get the expected solution is to add the following to your Jsprit algorithm builder:

.setProperty(Jsprit.Parameter.MAX_TRANSPORT_COSTS, Double.toString(1.0E8))

Best regards,
He

3

Hi He,
Your recommendation worked. Thanks for timely help.

I would like to know core reason behind the issue. Can you please explain.

Thanks once again.

Regards,
Amit

4

Hi Amit,

A short answer is that the penalty for unassigned jobs is not high enough.

More detailed answer is as follows:

Jspirt’s default objective function uses the following as the penalty for unassigned jobs (note that, in version 1.6.3-SNAPSHOT, 11 was 4):

costs += maxCosts * 2 * (11 - j.getPriority());

By default, maxCosts is the max average distance between jobs:

maxCosts = jobNeighborhoods.getMaxDistance();

In your problem, the value of maxCosts is not high enough, therefore the total cost is lower when it unassigns S1 than when it does not unassign any job.

What I suggested increased maxCosts to a very high level so that the penalty for unassigned jobs would be very high.

Considering that maxCosts is also used in other places, e.g., noise makers, a more decent way would be to create a custom objective function and increase the penalty for unassigned jobs directly there.

Best regards,
He

5

Thanks He for sharing insightful details.
Regards,
Amit

7

Hi,

I’m having a similar issue as the original poster where services are being unassigned even though there is a vehicle available to service them. I’d like to try the advised solution regarding setting MAX_TRANSPORT_COSTS, but I am unsure how to do that in my existing code.

I’m currently making the algorithm with:
VehicleRoutingAlgorithm algorithm = Jsprit.createAlgorithm(problem);

I’d essentially like to run
.setProperty(Jsprit.Parameter.MAX_TRANSPORT_COSTS, Double.toString(1.0E8))

on the resulting algorithm to get the default algorithm with the MAX_TRANSPORT_COSTS set. That doesn’t work though since it’s not an AlgorithmBuilder.

Yet, I’m not clear how to make the same algorithm manually using a builder… The examples I know (like docs/Walkthrough—Algorithm.md) use a VehicleRoutingAlgorithmBuilder, but I don’t have that anywhere in my code base. I can see a PrettyAlgorithmBuilder, but I have no idea how to use that and don’t see documetation around that. Either way, if I build an algorithm manually using a builder, how will I know it will behave the same as the one created with Jsprit.createAlgorithm(problem)?

Did the code get updated without the documentation catching up? Is there some secret documentation someone can expose me to?

I’m new to Java programming, and OOP in general. I really appreciate the help.

Sincerely,
Andy

8

Hi Andy,

You will need to work with Jsprit.Builder like the following:

Jsprit.Builder algorithmBuilder = Jsprit.Builder.newInstance(vrp);
algorithmBuilder.setProperty(Jsprit.Parameter.MAX_TRANSPORT_COSTS, Double.toString(1.0E8));
// and other algo config, including adding state updaters and constraints, etc.
VehicleRoutingAlgorithm algorithm = algorithmBuilder.buildAlgorithm();

Best regards,
He

9

Hi Andy,
Hope this helps,
Jsprit.Builder builder = Jsprit.Builder.newInstance(problem).addCoreStateAndConstraintStuff(true)
.setStateAndConstraintManager(stateManager, constraintManager)
.setProperty(Jsprit.Parameter.MAX_TRANSPORT_COSTS, Double.toString(1.0E8));

VehicleRoutingAlgorithm algorithm = builder.buildAlgorithm();

Regards,
Amit
Note: This code compatible with v 1.6.3-SNAPSHOT

1 Like
10

Thank you so much, amit_ak!

Can you confirm that this will give me the exact same algorithm settings,
except for MAX_TRANSPORT_COST?

Cheers,
Andy

11

Yes Andy. It works for me.

Regards,
Amit

12

Hi @amit_ak @jie31best @andromodon Can you please help me out in same? I tried with the latest code. And even though i have more vehicles left, some of the jobs are still unassigned. i have even tried bumping up penalty costs of unassigned jobs. but it increased overall cost of the solution but still jobs remained unassigned. pl help.

Thanks
Rishabh