Multiple Pick, Load and Drop Nodes with Outsourcing Component

[nielsneerhoff]

Dear,

This is the first issue I post on Github so please let me know if I am doing things according to the rules.

I have a CVRPTW with PD, but instead of the usual PD constraint something more complicated. In my model, drivers of trucks are also warehouse pickers. This imposes a non-regular time constraint on the time trucks are available to actually load, travel, and deliver:

• Picking means getting the item from the stock and preparing it for delivery (e.g. by wrapping its pallet in plastic). The picking time varies per order.
• Loading is literally the process of loading the picked orders onto the vehicle. Also the loading time is varies per order.
• Orders can be picked and loaded by different vehicles, but the vehicle that loads the order must deliver it.

I noticed this problem is similar to #968. To model the situation described above, I have created a node for each order, where that order can be picked, and a node for each order, where that order can be loaded.

I would like the possibility to outsource some orders if that is profitable. If an order is outsourced, all a vehicle (driver) needs to do is pick the order from the warehouse (the outsource company will load and deliver the order). I have added a disjunction to every load node with penalty equal to the cost of outsourcing the corresponding order (which varies per order). The outsourcing cost for an order node is 0, since the price for outsourcing was already paid at the load node.

This is part of my code for the situation above:

def add_precedence_constraints(routing_model, nodes, manager, primary_network_size, precedence_pair_callback):
    time_dimension = routing_model.GetDimensionOrDie('time')
    for i in range(primary_network_size):
        pair = precedence_pair_callback(i)
        if pair:
            pick_node_server_id = pair[0]
            load_node_server_id = pair[1]

            # Get the or tools id's of the nodes in this pair
            pick_node_id = manager.NodeToIndex(pick_node_server_id)
            load_node_id = manager.NodeToIndex(load_node_server_id)

            # Load job nodes can be visited, or we pay outsource cost
            routing_model.AddDisjunction([load_node_id], maxsize)

            # Get the variables indicating node activity
            pick_active_var = [routing_model.ActiveVar(pick_node_id)]
            load_active_var = [routing_model.ActiveVar(load_node_id)]

            # Get the time variables
            pick_time = [time_dimension.CumulVar(pick_node_id)]
            load_time = [time_dimension.CumulVar(load_node_id)]
                
            # Get the product of the active variables with the time variables
            pick_cross_active = [p * a for p, a in zip(pick_time, pick_active_var)]
            load_cross_active = [l * a for l, a in zip(load_active_var, load_time)]

            # Orders need to be picked before they are loaded
            solver = routing_model.solver()
            solver.AddConstraint(solver.Max(pick_cross_active) <= solver.Max(load_cross_active))

            # Get the relevant solver variables that we need to constrain
            load_vehicle = [routing_model.VehicleVar(load_node_id)]
            load_active_var = [routing_model.ActiveVar(load_node_id)]

            # Get the id of the node that corresponds to the order to be delivered
            id_to_deliver = manager.NodeToIndex(i)
                
            # Get the (vehicle) variables of the node that needs to be delivered
            deliver_vehicle = [routing_model.VehicleVar(id_to_deliver)]
            deliver_active_var = [routing_model.ActiveVar(id_to_deliver)]

            # The vehicle that loads the order must deliver the order
            solver = routing_model.solver()
            solver.AddConstraint(solver.Max(load_vehicle) == solver.Max(deliver_vehicle))
            
            # Get the time variables
            load_time = [time_dimension.CumulVar(load_node_id)]
            deliver_time = [time_dimension.CumulVar(id_to_deliver)]

            # A vehicle must load the order before it is delivered
            load_cross_active = [p * a for (p, a) in zip(load_time, load_active_var)]
            deliver_cross_active = [d * a for (d, a) in zip(deliver_time, deliver_active_var)]
            solver.AddConstraint(solver.Max(load_cross_active) <= solver.Max(deliver_cross_active))

            # Add pickup and delivery constraint (required in OR tools v7.+)
            routing_model.AddPickupAndDelivery(load_node_id, id_to_deliver)

With this code I only get solutions where the load node is always visited, even if I set the penalty at the disjunction of load nodes very low. In fact, when I set the outsource cost (the penalty) to 0, the solver did not find any solution.

How can this happen, and how can I solve it? Many thanks in advance!

[nielsneerhoff]

I fixed this by replacing
solver.AddConstraint(solver.Max(pick_cross_active) <= solver.Max(load_cross_active))
with
solver.AddConstraint(time_dimension.CumulVar(pick_node_id) + (duration of picking) <= time_dimension.CumulVar(load_node_id)). Now it works fine!