OR-Tools VRPTW - Solving multi-depot usage with different loading points

24 Views Asked by At

I am currently working on a project that involves utilizing Google OR-Tools for solving a multi-depot vehicle routing problem. I am facing a specific challenge related to the application of time windows for loading, unloading, and depot usages.

Taking the tutorial at https://developers.google.com/optimization/routing/cvrptw_resources as a starting point, I would like to know how to modify the depot constraints to configure different capacities for each of them. For example, depot 0 has 1 loading point and depot 1 has 5 loading points.

When using the code in the tutorial, these constraints are applied at the global level of the solution so I am getting results that are not correct for my problem:

Route for vehicle 0:
 depot_0 Cumul(06:00,06:00)
Route for vehicle 1:
 depot_0 Cumul(06:05,06:05)
Route for vehicle 2:
 depot_1 Cumul(06:10,06:10) 
Route for vehicle 3:
 depot_1 Cumul(06:15,06:15)

As you can see, if I set a single loading point, vehicle 2 should start at 06:00 as it starts in a different main depot than vehicles 0 and 1.

Given the next data to the model:

data['num_vehicles'] = 4
data['starts`] = [0, 0, 1, 1]
data['ends`] = [0, 0, 1, 1]
data['loading_points'] = 1 --> using here a list of loading points would be ideal
data['vehicle_load_time'] = 5

The expected output should be:

Route for vehicle 0:
 depot_0 Cumul(06:00,06:00)
Route for vehicle 1:
 depot_0 Cumul(06:05,06:05)
Route for vehicle 2:
 depot_1 Cumul(06:00,06:00) 
Route for vehicle 3:
 depot_1 Cumul(06:05,06:05)

The current code for these restrictions is as follows:

# Add time windows for loading and unloading
    # Add resource constraints at the depot.
    solver = routing.solver()
    intervals = []
    intervals_rmx = []
    for i in range(data['num_vehicles']):
        # Add time windows at start of routes
        intervals.append(
            solver.FixedDurationIntervalVar(
                time_dimension.CumulVar(routing.Start(i)),
                data["vehicle_load_time"],
                "depot_load_interval"
            )
        )
        # Add time windows at end of routes
        intervals.append(
            solver.FixedDurationIntervalVar(
                time_dimension.CumulVar(routing.End(i)),
                data["vehicle_unload_time"],
                "depot_unload_interval"
            )
        )

    for location_idx, time_window in enumerate(data['time_windows']):
        if location_idx in data['reloading_depots_indices']:
            index = manager.NodeToIndex(location_idx)
            intervals.append(
                solver.FixedDurationIntervalVar(
                    time_dimension.CumulVar(index),
                    data["vehicle_load_time"],
                    "depot_load_interval"
                )
            )

    # Unload constraints for each location except depots
    for location_idx, time_window in enumerate(data['time_windows']):
        if location_idx not in data['depots_indices']:
            index = manager.NodeToIndex(location_idx)
            intervals_rmx.append(
                solver.FixedDurationIntervalVar(
                    time_dimension.CumulVar(index),
                    data["vehicle_unload_time"],
                    "rmx_unload_interval"
                )
            )

    depot_usage = [1 for _ in range(len(intervals))]
    solver.Add(solver.Cumulative(intervals, depot_usage, data["depot_loading_points"], "depot"))

    rmx_usage = [1 for _ in range(len(intervals_rmx))]
    solver.Add(solver.Cumulative(intervals_rmx, rmx_usage, data["rmx_unloading_points"], "rmx_unloading"))

Thank you all for your time and consideration. I look forward to any insights or suggestions you may have.

0

There are 0 best solutions below