How can I forbid certain vehicles to go from node A to B ?

[angelo manzatto]

I am trying to model a constraint that works okay for small scenarios but when it grow up it simply explodes in time.

Let's say I would like to forbid vehicle 1 to go from node A to node B, but it can go from C do B, D to B and so one. How can I model that ?

I am modeling a constraint where a vehicle can travel from A to B empty just in cases where the maximum distance is below max_empty_distance.

distance_dimension = routing.GetDimensionOrDie("distance")

weight_dimension = routing.GetDimensionOrDie("weight")

# For each pair of possible node combinations

 for i in range(routing.nodes()):

        

       for j in range(routing.nodes()):

                

                current_index = manager.NodeToIndex(i)

                next_index  = manager.NodeToIndex(j)

                # Check if after node A comes B

                next_node_condition = routing.NextVar(current_index) == next_index

                    

                # Check if vehicle is travel without load

               empty_load_condition = weight_dimension.CumulVar(next_index) == 0

                # Condition

                combined_condition = next_node_condition * empty_load_condition 

                        

                # Expression

                 max_empty_distance_constraint = distance_dimension.TransitVar(current_index) < max_empty_distance

                        

                        # The constraint will be evaluated only for this particular vehicle

                        expression = routing.solver().ConditionalExpression(

                            combined_condition,

                            max_empty_distance_constraint,

                            1)

                

                        # Add constraint to the solver

                        routing.solver().AddConstraint(

                            expression >= 1

                            )

The code above works ok , but when the number of nodes grow to up > 200 the time to find a solution just slows down a lot.

[Laurent Perron]

Have a different node evaluator for each class of vehicle.

Remove (put a very high price) on the forbidden arc for the given vehicle.

Laurent Perron | Operations Research | lpe...@google.com | (33) 1 42 68 53 00

--
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.
To view this discussion on the web visit https://groups.google.com/d/msgid/or-tools-discuss/ab3fcf95-11a2-4b7a-bd5e-7dc183d95fb3n%40googlegroups.com.

[angelo manzatto]

The first part I solved using a different node evaluator for each vehicle. The problem is the second part where I need to take into consideration the cumulvar from weight dimension to check if is zero to apply the constraint. Do you have any idea on how can I optimize this code:

        distance_dimension = routing.GetDimensionOrDie("distance")

        weight_dimension = routing.GetDimensionOrDie("weight")

        

        # Empty load max travel distance

        max_empty_load_travel_distance = self.data['max_empty_load_travel_distance']

        

        logging.info("Applying max travel distance between nodes constraint with emtpy load distance as: {}"

                     .format(max_empty_load_travel_distance))

        

        # For each pair of possible node combinations

        for i in range(routing.nodes()):

        

            for j in range(routing.nodes()):

                

                    current_index = manager.NodeToIndex(i)

                    next_index  = manager.NodeToIndex(j)

                

                    # Check if after node A comes B

                    next_node_condition = self.routing.NextVar(current_index) == next_index

                    

                    # Check if vehicle is travel without load

                    # This line I can't put into a evaluator

                    empty_load_condition = weight_dimension.CumulVar(next_index) == 0

                    

                    # Condition

                    combined_condition = next_node_condition * empty_load_condition 

                    

                    # Expression

                    max_empty_distance_constraint = distance_dimension.TransitVar(current_index) < max_empty_load_travel_distance

                    

                    # The constraint will be evaluated only for this particular vehicle

                    expression = routing.solver().ConditionalExpression(

                        combined_condition,

                        max_empty_distance_constraint,

                        1)

            

                    # Add constraint to the solver

                    routing.solver().AddConstraint(

                        expression >= 1

                        )