Building a VRP Solution with Constraints - Help Needed

[patrick-aragao]

Hello all! Hope I can have some guidance on a problem I'm facing for a couple days. My objective is to have a VRP solver that can read a file with a 84 x 84 Distance Matrix (DC is the first in this list), a 2nd file with Demand for 83 Locations and the First Location again the DC with Demand = Zero, and a 3rd File that Capture by Location the Lat and Long to Further plot in a Map.

The result I'm getting is:

Route for Vehicle 0 = All locations in the same truck with no distance being calculated
Routes 1 to 17 = No Volume and No Distance.

Any help would be very much appreciated....

Code:

import math
from ortools.constraint_solver import pywrapcp
from ortools.constraint_solver import routing_enums_pb2
import pandas as pd
import numpy as np
import heapq

MIN_EFFICIENCY = 0.3  # %
MAX_STOPS = 5  # Number of Drops
MAX_TRAILER_PALLET = 33  # Pallet Capacity
MAX_DISTANCE_VEHICLE = 10000
NUM_DAYS = 2
END_NODES = []

def transforming_columns(df):
    df_temp = df.copy()
    df_temp.columns = df_temp.columns.str.lower()
    df_temp.columns = df_temp.columns.str.replace("[#,@,&]", "")
    df_temp.columns = df_temp.columns.str.replace(" ", "_")
    return df_temp

def find_highest_distances(distance_matrix, num_highest):
    distances = [(i, max(row[1:])) for i, row in enumerate(distance_matrix[1:])]
    top_distances = heapq.nlargest(num_highest, distances, key=lambda x: x[1])
    return [index for index, _ in top_distances]

def create_data_model(df_demands, df_distance_matrix):
    data = {}
    demands = df_demands["demand"].tolist()
    data["demands"] = [float(item) for item in demands]
    data["distance_matrix"] = df_distance_matrix.values.tolist()
    data["num_vehicles"] = math.ceil((df_demands["demand"].sum() / MAX_TRAILER_PALLET))
    data["vehicle_cpt_pallets"] = [MAX_TRAILER_PALLET] * data["num_vehicles"]
    data["max_loc_vehicle"] = [MAX_STOPS] * data["num_vehicles"]
    data["locations"] = list(zip(df_demands["latitude"], df_demands["longitude"]))
    data["starts"] = [0] * data["num_vehicles"]
    data["ends"] = [0] * data["num_vehicles"]
    return data

def visualize_routes(data, df, manager, routing, solution, output_path):
    output_data = []
    DROPPED_NODES = []
    for node in range(routing.Size()):
        if routing.IsStart(node):
            continue
        if solution.Value(routing.NextVar(node)) == node:
            DROPPED_NODES.append(manager.IndexToNode(node))

    route_stops = []
    pallets = []
    distance = []
    counter_dim = routing.GetDimensionOrDie("Counter")
    for vehicle_id in range(data["num_vehicles"]):
        index = routing.Start(vehicle_id)
        counter = 0
        ROUTE_DISTANCE = 0
        PALLETS = 0
        while not routing.IsEnd(index):
            node_index = manager.IndexToNode(index)
            total_count = counter_dim.CumulVar(index)
            counter = solution.Value(total_count)
            previous_index = index
            index = solution.Value(routing.NextVar(index))
            PALLETS += data["demands"][node_index]
            if routing.IsEnd(index):
                continue

            ROUTE_DISTANCE += routing.GetArcCostForVehicle(previous_index, index, vehicle_id)

        route_stops.append(counter + 1)
        distance.append(ROUTE_DISTANCE)
        pallets.append(PALLETS)

    for vehicle_id in range(data["num_vehicles"]):
        route_coords = []
        previous_index = 0
        ROUTE_NUMBER = vehicle_id
        ROUTE_DISTANCE = 0
        STOP_DISTANCE = 0
        ROUTE_PALLETS = 0
        STOPS = 0
        TOTAL_COUNT = route_stops[vehicle_id]
        index = routing.Start(vehicle_id)
        index_end = routing.IsEnd(index)
        while not routing.IsEnd(index):
            node_index = manager.IndexToNode(index)
            route_coords.append(data["locations"][node_index])
            row_values = df.iloc[node_index].values
            LOCATION_ID = int(row_values[0])
            LOCATION_NAME = row_values[1]
            LATITUDE = row_values[2]
            LONGITUDE = row_values[3]
            node_index_previous = manager.IndexToNode(previous_index)
            row_values_previous = df.iloc[node_index_previous].values
            LOCATION_ORIG_ID = row_values_previous[0]
            LOCATION_ORIG_NAME = row_values_previous[1]
            total_count = counter_dim.CumulVar(index)
            counter = solution.Value(total_count)
            previous_index = index
            index = solution.Value(routing.NextVar(index))

            ROUTE_PALLETS += data["demands"][node_index]

            if index_end == index:
                continue

            popup_text = (
                f"Route Number: {ROUTE_NUMBER}<br>"
                f"Destination Name: {LOCATION_NAME}<br>"
                f"Stop Number: {STOPS}/{TOTAL_COUNT}<br>"
                f"Total Pallets: {ROUTE_PALLETS} <br>"
                f"Total Distance: {ROUTE_DISTANCE} miles<br>"
                f"Route Efficiency Pallet: {(ROUTE_PALLETS/MAX_TRAILER_PALLET) * 100:.2f}%<br>"
            )

            print(popup_text)
            output_data.append(
                {
                    "Route Number": ROUTE_NUMBER,
                    "Stop Sequence": STOPS,
                    "Number of Stops": TOTAL_COUNT,
                    "Stop ID": LOCATION_ID,
                    "Origin ID": "" if STOPS == 0 else LOCATION_ORIG_ID,
                    "Origin Name": "" if STOPS == 0 else LOCATION_ORIG_NAME,
                    "Destination Name": "" if STOPS == 0 else LOCATION_NAME,
                    "Distance to Drop": round(STOP_DISTANCE, 2),
                    "Pallets of Drop": data["demands"][node_index],
                    "Partial Distance to Drop (miles)": round(ROUTE_DISTANCE, 2),
                    "Partial Pallet to Drop": ROUTE_PALLETS,
                    "Total Distance of Route (miles)": distance[vehicle_id],
                    "Total Pallets of Route": pallets[vehicle_id],
                    "End of Route": "Yes" if STOPS == TOTAL_COUNT else "No",
                    "Route Efficiency Pallets (%)": f"{(ROUTE_PALLETS/MAX_TRAILER_PALLET) * 100:.2f}%",
                    "Latitude": LATITUDE,
                    "Longitude": LONGITUDE,
                }
            )
            ROUTE_DISTANCE += routing.GetArcCostForVehicle(previous_index, index, vehicle_id)
            STOP_DISTANCE = routing.GetArcCostForVehicle(previous_index, index, vehicle_id)
            STOPS += 1

    df_dropped = df.iloc[:, -2:]
    df_dropped = df_dropped.iloc[DROPPED_NODES]
    df_dropped.to_csv(output_path + "/dropped.csv", index=False)
    df_result = pd.DataFrame(output_data)
    df_result.to_csv(output_path + "/result.csv", index=False)

def print_solution(data, manager, routing, assignment):
    total_distance = 0
    total_load = 0
    for vehicle_id in range(data["num_vehicles"]):
        index = routing.Start(vehicle_id)
        plan_output = "Route for vehicle {}:\n".format(vehicle_id)
        route_distance = 0
        route_load = 0
        while not routing.IsEnd(index):
            node_index = manager.IndexToNode(index)
            route_load += data["demands"][node_index]
            plan_output += " {0} Load({1}) -> ".format(node_index, route_load)
            previous_index = index
            index = assignment.Value(routing.NextVar(index))
            route_distance += routing.GetArcCostForVehicle(previous_index, index, vehicle_id)
        plan_output += "Route Finished \n"
        plan_output += "Distance of the route: {}m\n".format(route_distance)
        plan_output += "Load of the route: {}\n".format(route_load)
        print(plan_output)
        total_distance += route_distance
        total_load += route_load
    print("Total distance of all routes: {}m".format(total_distance))
    print("Total load of all routes: {}".format(total_load))

def add_count_constraints(routing, manager, data):
    def demand_count_evaluator(from_index):
        from_node = manager.IndexToNode(from_index)
        return 1 if (from_node != 0) else 0

    demand_evaluator_index = routing.RegisterUnaryTransitCallback(demand_count_evaluator)

    routing.AddDimensionWithVehicleCapacity(
        demand_evaluator_index,
        0,
        data["max_loc_vehicle"],
        True,
        "Counter",
    )

def add_capacity_pallets(routing, manager, data):
    def demand_evaluator_pounds(from_index):
        from_node = manager.IndexToNode(from_index)
        return data["demands"][from_node]

    demand_evaluator_index = routing.RegisterUnaryTransitCallback(demand_evaluator_pounds)

    capacity = "Pallets"
    routing.AddDimensionWithVehicleCapacity(
        demand_evaluator_index,
        0,
        data["vehicle_cpt_pallets"],
        True,
        capacity,
    )

def main():
    output_folder = "/Users/Desktop"
    file_path_matrix = "/Users/matrix.csv"
    df_distance_matrix = transforming_columns(pd.read_csv(file_path_matrix))
    if df_distance_matrix.empty:
        print("No distance matrix file selected.")
        return

    file_path_demand = "/Users/demand.csv"
    df_demand = transforming_columns(pd.read_csv(file_path_demand))
    if df_demand.empty:
        print("No Demand file selected.")
        return

    file_path_loc = "/Users/gps.csv"
    df_locations = transforming_columns(pd.read_csv(file_path_loc))
    if df_locations.empty:
        print("No Location file selected.")
        return

    df_distance_matrix = df_distance_matrix.rename(columns={"origin": "ID"})
    df_demand = df_demand.rename(columns={"volume_pallets": "demand"})
    selected_columns = ["id", "latitude", "longitude", "name"]
    df_locations = df_locations[selected_columns]

    result_df = pd.merge(
        df_distance_matrix, df_demand, left_on="ID", right_on="destination", how="left"
    )
    result_df.to_csv(output_folder + "/result_join.csv", index=False)
    
    cols_to_drop = result_df[
        (result_df["demand"].isnull()) & (result_df["ID"] != "550052")
    ]["ID"].tolist()
    
    cols_to_drop = [str(item) for item in cols_to_drop]
    
    column_name = "ID"
    matrix_cleaned = result_df.drop(columns=cols_to_drop)
    cols_to_drop = [int(item) for item in cols_to_drop]
    matrix_cleaned = matrix_cleaned[~matrix_cleaned[column_name].isin(cols_to_drop)]
    
    matrix_cleaned = matrix_cleaned.reset_index(drop=True)

    columns_to_drop = ["ID", "destination", "demand"]
    df_distance_matrix = matrix_cleaned.drop(columns=columns_to_drop)
    
    df_distance_matrix = matrix_cleaned.reset_index(drop=True)

    matrix_cleaned = pd.merge(
        matrix_cleaned, df_locations, left_on="ID", right_on="id", how="left"
    )
    
    matrix_cleaned.to_csv(output_folder + "/ss.csv", index=False)
    columns_names = matrix_cleaned.columns.tolist()
    columns_names.remove("latitude")
    columns_names.remove("longitude")
    columns_names.remove("name")
    columns_names.insert(1, "name")
    columns_names.insert(2, "latitude")
    columns_names.insert(3, "longitude")
    matrix_cleaned = matrix_cleaned[columns_names]
    
    matrix_cleaned = matrix_cleaned.reset_index(drop=True)
    
    data = create_data_model(matrix_cleaned, df_distance_matrix)

    print("Distance Matrix:", data["distance_matrix"])
    
    manager = pywrapcp.RoutingIndexManager(
        len(data["distance_matrix"]),
        data["num_vehicles"],
        data["starts"],
        data["ends"]
    )
    
    routing = pywrapcp.RoutingModel(manager)
    
    def distance_callback(from_index, to_index):
        from_node = manager.IndexToNode(from_index)
        to_node = manager.IndexToNode(to_index)
        print(f"From: {from_node}, To: {to_node}, Distance: {data['distance_matrix'][from_node][to_node]}")
        return data['distance_matrix'][from_node][to_node]

    transit_callback_index = routing.RegisterTransitCallback(distance_callback)
    routing.SetArcCostEvaluatorOfAllVehicles(transit_callback_index)

    add_capacity_pallets(routing, manager, data)
    add_count_constraints(routing, manager, data)
    
    penalty = 1000
    for node in range(1, len(data['distance_matrix'])):
        try:
            idx = manager.NodeToIndex(node)
            if idx == -1:
                print(f"Skipping invalid node: {node}")
                continue
            print(f"Node: {node}, Index: {idx}")
            routing.AddDisjunction([idx], penalty)
            print(f"Added disjunction for node: {node}")
        except Exception as e:
            print(f"Failed to add disjunction for node: {node}, Error: {e}")

    search_parameters = pywrapcp.DefaultRoutingSearchParameters()
    search_parameters.first_solution_strategy = (
        routing_enums_pb2.FirstSolutionStrategy.PARALLEL_CHEAPEST_INSERTION
    )
    search_parameters.local_search_metaheuristic = (
        routing_enums_pb2.LocalSearchMetaheuristic.GUIDED_LOCAL_SEARCH
    )
    search_parameters.time_limit.seconds = 60
    search_parameters.log_search = True

    solution = routing.SolveWithParameters(search_parameters)
    if solution:
        print_solution(data, manager, routing, solution)
        visualize_routes(
            data, matrix_cleaned, manager, routing, solution, output_folder
        )
    else:
        print("No solution found!")

if __name__ == "__main__":
    main()

[Mizux]

is return data['distance_matrix'][from_node][to_node] returns a python int ?

[patrick-aragao]

Yes it returns! ☹️

[Mizux]

at least here data["demands"] = [float(item) for item in demands] is definitively not an int()...

To debug, you can try to disable "Counter" and "pallets" dimension
also you may want to display the value of all dimension in your print function...

[patrick-aragao]

You are 100% correct on this part. the demand the goes on each destination is definitely a float number (partial pallets). In this case it can't be?

[Mizux]

internally the c++ solver want a int64_t and the swig machinery will copy the python "float" bytes verbatim i.e. undefined
behaviour...