Confusion about Google OR-Tools' CVRP solver

Question

I am using the Google OR-Tools' CVRP solver to solve CVRP instances (using different (meta)heuristics). I am, however, having some confusion and questions about the entirety of the code. Namely:

• It is unclear to me what the code minimizes.
• I am confused as to what data["depot"] = 0 does.

First of all, this is my code:

def create_data_model():
    data = {}
    data["distance_matrix"] = createDistanceMatrix(customers).tolist()
    data["demands"] = customers['Demand'].astype(int).tolist()
    data["vehicle_capacities"] = [1000]
    data["num_vehicles"] = 1
    data["depot"] = 0
    return data

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

def main():
    """Solve the CVRP problem."""
    # Instantiate the data problem.
    data = create_data_model()

    # Create the routing index manager.
    manager = pywrapcp.RoutingIndexManager(
        len(data["distance_matrix"]), data["num_vehicles"], data["depot"]
    )

    # Create Routing Model.
    routing = pywrapcp.RoutingModel(manager)

    # Create and register a transit callback.
    def distance_callback(from_index, to_index):
        """Returns the distance between the two nodes."""
        # Convert from routing variable Index to distance matrix NodeIndex.
        from_node = manager.IndexToNode(from_index)
        to_node = manager.IndexToNode(to_index)
        return data["distance_matrix"][from_node][to_node]

    transit_callback_index = routing.RegisterTransitCallback(distance_callback)

    # Define cost of each arc.
    routing.SetArcCostEvaluatorOfAllVehicles(transit_callback_index)

    # Add Capacity constraint.
    def demand_callback(from_index):
        """Returns the demand of the node."""
        # Convert from routing variable Index to demands NodeIndex.
        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",
    )

    # Setting first solution heuristic.
    search_parameters = pywrapcp.DefaultRoutingSearchParameters()
    search_parameters.first_solution_strategy = (
        routing_enums_pb2.FirstSolutionStrategy.PATH_CHEAPEST_ARC
    )
    search_parameters.local_search_metaheuristic = (
        routing_enums_pb2.LocalSearchMetaheuristic.GUIDED_LOCAL_SEARCH
    )
    search_parameters.time_limit.FromSeconds(5)

    # Solve the problem.
    solution = routing.SolveWithParameters(search_parameters)

    # Print solution on console.
    if solution:
        print_solution(data, manager, routing, solution)

Now, the first thing I was confused about is what exactly the code minimizes. I saw online (on the normal VRP-variant: https://developers.google.com/optimization/routing/vrp) that the command SetGlobalSpanCostCoefficient() causes the code to minimize the distance of the longest route. However, this command is not contained in the code for the CVRP-variant. Moreover, I am looking to minimize the total distance of all routes (note that my code currently has only 1 vehicle, but I am planning on using more). Additionally, as I understand it now, different heuristics minimize different things. So, how does thing combine with the rest of the code and how do I make the code minimize the total distance of all routes (if it doesn't do that already).

The second thing I was confused about, was the data["depot"] = 0 part in the code:

def create_data_model():
    data = {}
    data["distance_matrix"] = createDistanceMatrix(customers).tolist()
    data["demands"] = customers['Demand'].astype(int).tolist()
    data["vehicle_capacities"] = [1000]
    data["num_vehicles"] = 1
    data["depot"] = 0
    return data

The way that I use the code now is: I generate location of customers (and a nonzero location for a depot!) and use the function createDistanceMatrix(customers).tolist() for the (Euclidian) distances. I am however uncertain as to what exactly data["depot"] = 0 does, since I have a nonzero location for the depot. I am aware that I could redefine all locations such that the depot is centered at (0,0), but would really rather not, as it would make other things way more complicated.

Thanks in advance!

Answer 1

1. the main cost is defined by the SetArcCostEvaluatorOfAllVehicles() call. So in your case, it means minimizing the total distance travelled.

2. It indicates that the depot is located at the node with index 0 (w.r.t. the distance matrix).