CVRPTW. How to deliver items to a location if demand exceeds capacity of a single vehicle?

[drozdd80]

Hello everyone.

I am working in python with ortools.
I am solving a CVRPTW problem and trying to deal with cases when items requiring delivery to a location are exceeding capacity of any vehicle. 

To fit items on several vehicles I am using item-based split creating virtual locations for each of the items. However this raises a different issue that 2 or more vehicles can now visit the same real location (in different virtual locations) at the same time (unloading of each item requires certain fixed time). And this is not supposed to be happening.

Is there a way to set constrains on a group of nodes that no more than 1 vehicle can be at a group of nodes at once?

[Mizux]

you can use ressource constraint: see https://developers.google.com/optimization/routing/cvrptw_resources

[drozdd80]

Thank you for your response and for the guide.

It is a similar problem however I still have troubles with applying it to the case of multiple nodes.
My understanding was that for each group of nodes you should loop through all the vehicles and nodes and create intervals for the nodes in the list of intervals for a given group. And then add a cumulative constrain the same way it is done in the guide with depots.

It doesn't give solutions in the different datasets I tried, so I assume the logic is incorrect. Do I need to create some kind of merged node and create intervals for it instead? Or to transform the intervals afterwards but before setting the constrains?

Sorry for the basic questions, I am quite new to ortools.

Here is what I was trying. Used the code from the guide with Depot constrains and was trying to add constrains for each group of nodes.

    data["depot_capacity"] = 1
    data['location_capacity'] = 1
    data['location_groups'] = (['depot'] 
                               + ['group_1']*((len(data["time_matrix"])-1)//2) 
                               + ['group_2']*(len(data["time_matrix"]) - ((len(data["time_matrix"])-1)//2)-1)
    )

    group_location_map = {value: [i for i, v in enumerate(data['location_groups']) if v == value] for value in set(data['location_groups'])}

    # Add resource constraints at the depot.
    solver = routing.solver()
    intervals = {}
    for gr in set(data['location_groups']):
        intervals[gr] = []
        if gr == 'depot':
            for i in range(data["num_vehicles"]):
                # Add time windows at start of routes
                intervals[gr].append(
                    solver.FixedDurationIntervalVar(
                        time_dimension.CumulVar(routing.Start(i)),
                        data["vehicle_load_time"],
                        gr,
                    )
                )
                # Add time windows at end of routes.
                intervals[gr].append(
                    solver.FixedDurationIntervalVar(
                        time_dimension.CumulVar(routing.End(i)),
                        data["vehicle_unload_time"],
                        gr,
                    )
                )
        else:
            for i in range(data["num_vehicles"]):
                for loc in group_location_map[gr]:
                    node_ind = manager.NodeToIndex(loc)
                    intervals[gr].append(
                        solver.FixedDurationIntervalVar(
                            time_dimension.CumulVar(node_ind),
                            data["vehicle_unload_time"],
                            gr
                        )
                    )

    for gr in set(data['location_groups']):
        loc_usage = [1 for _ in range(len(intervals[gr]))]
        if gr == 'depot':
            solver.Add(
                solver.Cumulative(intervals[gr], loc_usage, data["depot_capacity"], gr)
            )
        else:
            solver.Add(
                solver.Cumulative(intervals[gr], loc_usage, data["location_capacity"], gr)
            )

[Mizux]

why keeping the for i in range(data["num_vehicles"]): for regular nodes ? i.e. In your else: you don't need this extra loop

[drozdd80]

My thinking here was the same as with Depot. But vehicles cannot visit the same node except depot so I guess it is not needed.

Thank you. After removing this part and fiddling with the settings the code started working. However only on some specific time windows and other settings. Maybe it is more constraining than I thought.