Vehicle's load constraint - Help

[Pablo Hernán Giménez]

Hi everyone,

I'm trying to solve a CVRPTW problem and I have a constraint that's giving me a headache: Each vehicle's load must be 85% or higher. Otherwise the vehicle should stay at the depot.

- All the nodes are optional (I create a disjunction for each node).

- I have a volume dimension for vehicles [0.. MaxVolume].

I thought that a constraint for each vehicle's end node should do the trick but isn't working:

I iterate over the vehicles array (idx) and set:

routing.CumulVar(routing.End(idx), dimensionVolume).SetMin((long)(((decimal)vehicles[idx].getMaxVolume()) * 0.85));

Whenever I set this constraint to the model, the solver only finds the first solution (all nodes remain unvisited) with a 10 minutes time limit.

I assume that this happens because the solver can't find any intermediate solution to improve.

Is there another way I can model this? Maybe with a soft constraint? 

I'm using the following routing parameters:

            parameters.no_lns = true;

            parameters.first_solution = RoutingModel.RoutingStrategyName(RoutingModel.ROUTING_GLOBAL_CHEAPEST_ARC);

            parameters.guided_local_search = true;

Thanks

[Vincent Furnon]

This constraint is a bit tricky to enforce due to its "non-monotonicity": a short route may be unfeasible but adding extra nodes might make it feasible, The solver is highly geared towards constructive heuristics which explains the failures you are getting.

A possible workaround is to penalize under-loaded vehicles (with a high penalty) using the SetEndCumulVarSoftLowerBound of RoutingDimension. First solutions won't be great but local search should clean them up.

BTW I would try using "insertion" heuristics with the new model, instead of RoutingModel.ROUTING_GLOBAL_CHEAPEST_ARC.

Vincent

--
You received this message because you are subscribed to the Google Groups "or-tools-discuss" group.
To unsubscribe from this group and stop receiving emails from it, send an email to or-tools-discu...@googlegroups.com.
For more options, visit https://groups.google.com/d/optout.

[Pablo Hernán Giménez]

Vincent,

Thanks for the quick response. Do I have a way to remove penalties when a vehicle is not leaving the depot?

I want to penalize only a vehicle loaded between 1% and 85%.

Thanks

You received this message because you are subscribed to a topic in the Google Groups "or-tools-discuss" group.
To unsubscribe from this topic, visit https://groups.google.com/d/topic/or-tools-discuss/zSCWi88ugsA/unsubscribe.
To unsubscribe from this group and all its topics, send an email to or-tools-discu...@googlegroups.com.

[Vincent Furnon]

You're right, I missed that part. A possible trick would be to put a dummy load when the vehicle is empty; to do that have the "load" callback return the capacity for (route start, route end) pairs.