CVRPD Visit Node Constraints

[burbot48]

Hi ,

We developed a CVRPD with TW model in python platform and we would like to put a constraint on a model about visiting rule of nodes. The rule is that the vehicle should not visit another specific pick-up point, unless it delivers a demands of a specific pickup point where the vehicle has already visited before.
Let me try to explain with an example :

• I have 6 nodes , 3 of them are pick-up points and rest 3 points are delivery points.
• According to the below model the vehicle visit point 1. before point 3. , the vehicle should not visit point 3. without visiting point 4. ( Delivery point of point 1.) or visa-versa the vehicle should have to visit point 3. before point 1. , the vehicle should not visit point 1. without visiting point 6. ( Delivery point of point 3.).

This constrain does not seem manageable by time matrix due that there are two possibilities. Of course this constraint will be valid incase that these two nodes (point1 and Point2 ) are assigned to the same vehicle.

Could you give me an advise to manage this constraint.

Thanks in advance

    from ortools.constraint_solver import routing_enums_pb2
    from ortools.constraint_solver import pywrapcp
    def create_data_model():    
        data = {}
        data['pickups_deliveries']=[[1, 4], [2, 5], [3, 6]]
        data['demands']=[0, 975, 1450, 975, -975, -1450, -975]
        data['num_vehicles']=1
        data['vehicle_capacities']=[3000]
        data['time_matrix']=[[0.0, 105.0, 56.0, 87.0, 1500.0, 1500.0, 1500.0],
        [0.0, 40.0, 1575.0, 73.0, 97.0, 83.0, 79.0],
        [0.0, 1590.0, 25.0, 1563.0, 63.0, 49.0, 36.0],
        [0.0, 88.0, 1563.0, 25.0, 94.0, 80.0, 68.0],
        [0.0, 115.0, 66.0, 97.0, 22.0, 26.0, 26.0],
        [0.0, 101.0, 52.0, 83.0, 26.0, 22.0, 26.0],
        [0.0, 97.0, 39.0, 71.0, 26.0, 26.0, 22.0]]
        data['time_windows']=[(0, 5000), (0, 1200), (0, 1200), (0, 1380), (0, 1200), (0, 1200), (0, 1380)]
        data['depot'] = 0
        return data
    
    
    def print_solution(data, manager, routing, solution):
    
        time_dimension = routing.GetDimensionOrDie('Time')
        total_time = 0
        for vehicle_id in range(data['num_vehicles']):
            index = routing.Start(vehicle_id)
            plan_output = 'Route for vehicle {}:\n'.format(vehicle_id)
            while not routing.IsEnd(index):
                time_var = time_dimension.CumulVar(index)
                plan_output += '{0} Time({1},{2}) -> '.format(
                    manager.IndexToNode(index), solution.Min(time_var),
                    solution.Max(time_var))
                index = solution.Value(routing.NextVar(index))
            time_var = time_dimension.CumulVar(index)
            plan_output += '{0} Time({1},{2})\n'.format(manager.IndexToNode(index),
                                                        solution.Min(time_var),
                                                        solution.Max(time_var))
            plan_output += 'Time of the route: {}min\n'.format(
                solution.Min(time_var))
            print(plan_output)
            total_time += solution.Min(time_var)
        print('Total time of all routes: {}min'.format(total_time))
    
    
    def main():
      
        data = create_data_model()
    
        manager = pywrapcp.RoutingIndexManager(len(data['time_matrix']),
                                               data['num_vehicles'], data['depot'])
    
        routing = pywrapcp.RoutingModel(manager)
    
        def time_callback(from_index, to_index):
            from_node = manager.IndexToNode(from_index)
            to_node = manager.IndexToNode(to_index)
            return data['time_matrix'][from_node][to_node]
    
        transit_callback_index = routing.RegisterTransitCallback(time_callback)
    
        routing.SetArcCostEvaluatorOfAllVehicles(transit_callback_index)
    
        time = 'Time'
        routing.AddDimension(
            transit_callback_index,
            3000,  # allow waiting time
            3000,  # maximum time per vehicle
            False,  # Don't force start cumul to zero.
            time)
        time_dimension = routing.GetDimensionOrDie(time)
        
    
        for location_idx, time_window in enumerate(data['time_windows']):
            if location_idx == 0:
                continue
            index = manager.NodeToIndex(location_idx)
            time_dimension.CumulVar(index).SetRange(time_window[0], time_window[1])
    
        for vehicle_id in range(data['num_vehicles']):
            index = routing.Start(vehicle_id)
            time_dimension.CumulVar(index).SetRange(data['time_windows'][0][0],
                                                    data['time_windows'][0][1])
    
        for i in range(data['num_vehicles']):
            routing.AddVariableMinimizedByFinalizer(
                time_dimension.CumulVar(routing.Start(i)))
            routing.AddVariableMinimizedByFinalizer(
                time_dimension.CumulVar(routing.End(i)))
        
        for request in data['pickups_deliveries']:
            pickup_index = manager.NodeToIndex(request[0])
            delivery_index = manager.NodeToIndex(request[1])
            routing.AddPickupAndDelivery(pickup_index, delivery_index)
            routing.solver().Add(
                routing.VehicleVar(pickup_index) == routing.VehicleVar(
                    delivery_index))
            routing.solver().Add(
                time_dimension.CumulVar(pickup_index) <= time_dimension.CumulVar(delivery_index))
        
        def demand_callback(from_index):
            from_node = manager.IndexToNode(from_index)
            return data['demands'][from_node]
    
        demand_callback_index = routing.RegisterUnaryTransitCallback(
            demand_callback)
        routing.AddDimensionWithVehicleCapacity(
            demand_callback_index,
            0,  # null capacity slack
            data['vehicle_capacities'],  # vehicle maximum capacities
            True,  # start cumul to zero
            'Capacity')
    
        search_parameters = pywrapcp.DefaultRoutingSearchParameters()
        search_parameters.first_solution_strategy = (
            routing_enums_pb2.FirstSolutionStrategy.PATH_CHEAPEST_ARC)
    
        solution = routing.SolveWithParameters(search_parameters)
    
        if solution:
            print_solution(data, manager, routing, solution)
    
    
    if __name__ == '__main__':
        main()`

[Mizux]

Don't get it, sorry, did you try to play with PD policy ? (FIFO in your case aka First In First Out)
https://github.com/google/or-tools/blob/stable/ortools/constraint_solver/doc/PDP.md

or do you mean you have 4 < 3 or 6 < 1 I.e. no interleaved pickup delivery ?

1. simply create a vehicle capacity of 1, i.e. vehicle need to deliver before be able to pickup something else

2. Playing with constraint

solver = routing.solver()

cond = routing.VehicleVar(1) == routing.VehicleVar(3)
non_cond = routing.VehicleVar(1) != routing.VehicleVar(3)
expr_1 = time_dimension.CumulVar(four) <= time_dimension.CumulVar(three)
expr_2 = time_dimension.CumulVar(six) <= time_dimension.CumulVar(one)
solver.Add(solver.Sum[non_cond, cond * expr_1, cond * expr_2] == 1)

[burbot48]

I studied PD policy but as I understood this policy is valid for all Pick up delivery nodes.

routing.SetPickupAndDeliveryPolicyOfAllVehicles(pywrapcp.RoutingModel.PICKUP_AND_DELIVERY_FIFO)

Let me explain much more easy:
Please suppose that there are two node groups as below and all the nodes are performed by one vehicle. So the vehicle must pick up and deliver based on node groups without switching between node groups.

First Group nodes [1,4] , [2,5]
Second Group nodes [3,6]

I mean that the vehicle should complete pick up & delivery for first group nodes then go to second group nodes or should complete second group nodes firstly then go to first group nodes.

Do you have any idea to solve this problem.

Thank you