is Jsprit.createAlgorithm(problem) equivalent to ... ?

[He Huang]

Hi,

I have read in multiple posts (e.g., Walkthrough---Algorithm and playground/wiki) that

VehicleRoutingAlgorithm vra = VehicleRoutingAlgorithms.readAndCreateAlgorithm(routingProblem, "yourAlgorithmConfig");

is equivalent to (Skill is not present because, I guess, it was not implemented at the time of those posts)

VehicleRoutingAlgorithmBuilder vraBuilder = new VehicleRoutingAlgorithmBuilder(routingProblem, "yourAlgorithmConfig");

StateManager stateManager = new StateManager(problem.getTransportCosts());

stateManager.updateLoadStates();

stateManager.updateTimeWindowStates();

ConstraintManager constraintManager = new ConstraintManager(problem, stateManager);

constraintManager.addLoadConstraint();

constraintManager.addTimeWindowConstraint();

vraBuilder.setStateAndConstraintManager(stateManager, constraintManager);

vraBuilder.addDefaultCostCalculators();

VehicleRoutingAlgorithm vra = vraBuilder.build();

I have not found any similar statement about the Jsprit algorithm, so my question is:

is

VehicleRoutingAlgorithm algorithm = Jsprit.createAlgorithm(problem);

equivalent to the following (Skill is also not present)?

Jsprit.Builder algorithmBuilder = Jsprit.Builder.newInstance(problem);

algorithmBuilder.addCoreStateAndConstraintStuff(false);

StateManager stateManager = new StateManager(problem);

ConstraintManager constraintManager = new ConstraintManager(problem, stateManager);

constraintManager.addLoadConstraint();

stateManager.updateLoadStates();

constraintManager.addTimeWindowConstraint();

stateManager.updateTimeWindowStates();

UpdateVehicleDependentPracticalTimeWindows vra = new UpdateVehicleDependentPracticalTimeWindows(stateManager, problem.getTransportCosts());

vra.setVehiclesToUpdate(new UpdateVehicleDependentPracticalTimeWindows.VehiclesToUpdate() {

Map<VehicleTypeKey, Vehicle> uniqueTypes = new HashMap();

public Collection<Vehicle> get(VehicleRoute vehicleRoute) {

if (uniqueTypes.isEmpty()) {

Iterator vehicles = problem.getVehicles().iterator();

while (vehicles.hasNext()) {

Vehicle v = (Vehicle) vehicles.next(); 

if (!uniqueTypes.containsKey(v.getVehicleTypeIdentifier())) {

uniqueTypes.put(v.getVehicleTypeIdentifier(), v);

}

}

}

 

ArrayList vehicles1 = new ArrayList();

vehicles1.addAll(uniqueTypes.values());

return vehicles1;

}

});

stateManager.addStateUpdater(vra);

stateManager.addStateUpdater(new UpdateEndLocationIfRouteIsOpen());

stateManager.addStateUpdater(new UpdateActivityTimes(problem.getTransportCosts(), ActivityTimeTracker.ActivityPolicy.AS_SOON_AS_TIME_WINDOW_OPENS));

stateManager.addStateUpdater(new UpdateVariableCosts(problem.getActivityCosts(), problem.getTransportCosts(), stateManager));

algorithmBuilder.setStateAndConstraintManager(stateManager, constraintManager);

algorithmBuilder.setObjectiveFunction(new SolutionCostCalculator() {

@Override

public double getCosts(VehicleRoutingProblemSolution solution) {

double c = 0.0; 

for (VehicleRoute r : solution.getRoutes()) { 

c += (stateManager.getRouteState(r, InternalStates.COSTS, Double.class)).doubleValue(); 

c += r.getVehicle().getType().getVehicleCostParams().fix; 

} 

c += solution.getUnassignedJobs().size() * c * .1; 

return c; 

}

});

algorithm = algorithmBuilder.buildAlgorithm();

I have conducted tests on Solomon C1 instances and the results show that they are not equivalent, as they return different results for instances C102, C106 and C108.

inst	runs	res*	veh*	Jsprit.createAlgorithm(problem)			Jsprit (second implementation)
				iterations	totalDistance	numRoutes	iterations	totalDistance	numRoutes
C101	1	828.94	10	10000	828.94	10	10000	828.94	10
C102	1	828.94	10	10000	829.7	10	10000	828.94	10
C103	1	828.06	10	10000	831.07	10	10000	831.07	10
C104	1	824.78	10	10000	848.44	10	10000	848.44	10
C105	1	828.94	10	10000	828.94	10	10000	828.94	10
C106	1	828.94	10	10000	828.94	10	10000	829.38	10
C107	1	828.94	10	10000	828.94	10	10000	828.94	10
C108	1	828.94	10	10000	829.7	10	10000	828.94	10
C109	1	828.94	10	10000	828.94	10	10000	828.94	10

What am I missing in the second implementation?

Best regards,

He

[He Huang]

The problem seems to be the objective function, which was copied from Stefan's example in this post and VariablePlusFixedSolutionCostCalculatorFactory.

When I delete that part, it returns the same results as Jsprit.createAlgorithm(problem).

When I compare the objective function with the default one in Jsprit, the difference is in the transport costs (ignoring the activity cost and break activity), i.e., stateManager.getRouteState(r, InternalStates.COSTS, Double.class) does not return the correct route transport costs in this case.

[Stefan Schroeder]

Thanks for you in-depth analysis. I really appreciate it. BTW: if you think smth should not be, you can always open an issue in jsprit's issue tracker. We can then - together - try to erase the problem.

Am 13/10/15 um 11:55 schrieb He Huang:

The problem seems to be the objective function, which was copied from Stefan's example in this post and VariablePlusFixedSolutionCostCalculatorFactory.

When I delete that part, it returns the same results as Jsprit.createAlgorithm(problem).

When I compare the objective function with the default one in Jsprit, the difference is in the transport costs (ignoring the activity cost and break activity), i.e., stateManager.getRouteState(r, InternalStates.COSTS, Double.class) does not return the correct route transport costs in this case.

--
You received this message because you are subscribed to the Google Groups "jsprit-mailing-list" group.
To unsubscribe from this group and stop receiving emails from it, send an email to jsprit-mailing-...@googlegroups.com.
To post to this group, send email to jsprit-ma...@googlegroups.com.
Visit this group at http://groups.google.com/group/jsprit-mailing-list.
For more options, visit https://groups.google.com/d/optout.

[He Huang]

Hi Stefan,

Thanks for your replies to my multiple posts. It is a pity you do not have much time for soft time windows constraint at the moment.

I have a further question about the Jsprit algorithm:

In VehicleRoutingAlgorithmBuilder, one can deactivate the default activity insertion cost calculator (which is LocalActivityInsertionCostsCalculator, right?) by not using "vraBuilder.addDefaultCostCalculators();". In this way, the activity insertion cost is entirely calculated by soft constraints.

But I cannot find a similar setting for the Jsprit algorithm. Can I assume that LocalActivityInsertionCostsCalculator is by default embedded? Or the opposite?

Please kindly advise. Thank you.

Best regards,

He

[Stefan Schroeder]

Hi He,

Thanks for your replies to my multiple posts. It is a pity you do not have much time for soft time windows constraint at the moment.

Yes, it is. BTW: As you correctly analysed, one should go throught the whole route to evaluate the impact of an insertion. Think about an estimation function that estimates the impact on the whole route. The estimation function might then be updated everytime a route change. This will probably be much faster then going through the whole route every time when calculating insertion costs.

But I cannot find a similar setting for the Jsprit algorithm. Can I assume that LocalActivityInsertionCostsCalculator is by default embedded? Or the opposite?

Yes, it is embedded by default. However, you can override it by your own calculator, just use this. If you set an ActivityInsertionCostCalc that always return 0 then it only depends on your soft constraints.

Best,
Stefan

Please kindly advise. Thank you.

Best regards,

He

[He Huang]

Hi Stefan,

Thanks for your reply.

Yes, it is. BTW: As you correctly analysed, one should go throught the whole route to evaluate the impact of an insertion. Think about an estimation function that estimates the impact on the whole route. The estimation function might then be updated everytime a route change. This will probably be much faster then going through the whole route every time when calculating insertion costs.

But can we find such estimation function? As in my analysis, the change in totalActivityLate can only be calculated by going through the whole route. Moreover, if the penalty function is not additive (i.e., f(x) + f(y) != f(x+y)), we cannot use totalActivityEarly and totalActivityLate, and, instead, will need to go through every individual activity to calculate their penalties individually.

Yes, it is embedded by default. However, you can override it by your own calculator, just use this. If you set an ActivityInsertionCostCalc that always return 0 then it only depends on your soft constraints.

I see. Just to confirm: if I do not override it, then in the soft constraints I should not calculate the addition in the transport cost, i.e., c_ik + c_kj - c_ij, right?

Best regards,

He 

[Stefan Schroeder]

Correct!

Am 14/10/15 um 12:01 schrieb He Huang:

[He Huang]

Thanks! :-)

Btw, is this a bug?

[Stefan Schroeder]

No, it is not. The calculus here is that if the route end time is bigger than latest break time (route.getEnd().getArrTime() > route.getVehicle().getBreak().getTimeWindow().getEnd()), the driver needs a break.
Thus, it is penalyzed then. If not the break is not necessary since the driver can
make the break at home. In this case, an unassigned break should not be penalyzed. However, every unassigned job (incl. break)
will be penalyzed here. This is just neutralized by this. Make sense?

Am 14/10/15 um 13:32 schrieb He Huang:

Thanks! :-)

Btw, is this a bug?

[He Huang]

I see. Thanks.

Just wondering: if a break is unassigned, then why is it in route.getActivities()?

[He Huang]

Ah, I see. It is "if (!hasBreak)"... Sorry about that.