I’m trying to implement a particular TSP (VRP with only one vehicle). I’ve used the standard distance matrix provided in the examples of the VRP on Google OR-Tools page (which has a total of 16 locations, 17 including the depot).
For my purposes, I have removed many connections in the graph. Specifically, from index 0 (index corresponding to the depot), I can only go to nodes (9 10 11 12 13 14 15 16). From nodes (1 2 3 4 5 6 7 8), I can only go to node i + 8 or to the depot (index number 17). Finally, from nodes (9 10 11 12 13 14 15 16), I cannot return to the depot (removed the connection between these nodes and index 17), and I cannot go to node i – 8 (e.g., from node 10, I cannot go to node 2). This is related to my previous question about the need to remove the depot (if interested, you can go back and read it).

My goal is to define a series of nodes to visit, respecting the constraints defined above, in such a way as to get as close as possible to a maximum distance of the route provided as input. This maximum distance is less than the minimum distance required to visit all nodes, so some of them cannot be visited.
To achieve this goal, I first thought of adding a constraint related to the maximum distance that the vehicle can travel within routing.AddDimension. Then, to allow not visiting all nodes, I considered using routing.AddDisjunction. For now, I have set an equal penalty for all nodes. However, my goal would be to ensure that some nodes are necessarily visited (as long as the sum of the distances is below the limit) while other nodes are “optional,” meaning they can be visited or not depending on the maximum distance. If I don’t include the constraint related to the maximum distance, the solver finds a solution. However, when this constraint is in place, the solver fails to find a solution, despite the disjunctions being present. I don’t understand why the solver fails to find a solution. It’s worth mentioning that “no solution found” is printed even before the time limit for the search is reached. If anyone could help me, I would be grateful.
I post my code below, maybe it can help you.

"""Capacited Vehicles Routing Problem (CVRP)."""

from ortools.constraint_solver import routing_enums_pb2
from ortools.constraint_solver import pywrapcp


def create_data_model():
    """Stores the data for the problem."""
    data = {}
    data["distance_matrix"] = [
        # fmt: off
      [0, 548, 776, 696, 582, 274, 502, 194, 308, 194, 536, 502, 388, 354, 468, 776, 662],
      [548, 0, 684, 308, 194, 502, 730, 354, 696, 742, 1084, 594, 480, 674, 1016, 868, 1210],
      [776, 684, 0, 992, 878, 502, 274, 810, 468, 742, 400, 1278, 1164, 1130, 788, 1552, 754],
      [696, 308, 992, 0, 114, 650, 878, 502, 844, 890, 1232, 514, 628, 822, 1164, 560, 1358],
      [582, 194, 878, 114, 0, 536, 764, 388, 730, 776, 1118, 400, 514, 708, 1050, 674, 1244],
      [274, 502, 502, 650, 536, 0, 228, 308, 194, 240, 582, 776, 662, 628, 514, 1050, 708],
      [502, 730, 274, 878, 764, 228, 0, 536, 194, 468, 354, 1004, 890, 856, 514, 1278, 480],
      [194, 354, 810, 502, 388, 308, 536, 0, 342, 388, 730, 468, 354, 320, 662, 742, 856],
      [308, 696, 468, 844, 730, 194, 194, 342, 0, 274, 388, 810, 696, 662, 320, 1084, 514],
      [194, 742, 742, 890, 776, 240, 468, 388, 274, 0, 342, 536, 422, 388, 274, 810, 468],
      [536, 1084, 400, 1232, 1118, 582, 354, 730, 388, 342, 0, 878, 764, 730, 388, 1152, 354],
      [502, 594, 1278, 514, 400, 776, 1004, 468, 810, 536, 878, 0, 114, 308, 650, 274, 844],
      [388, 480, 1164, 628, 514, 662, 890, 354, 696, 422, 764, 114, 0, 194, 536, 388, 730],
      [354, 674, 1130, 822, 708, 628, 856, 320, 662, 388, 730, 308, 194, 0, 342, 422, 536],
      [468, 1016, 788, 1164, 1050, 514, 514, 662, 320, 274, 388, 650, 536, 342, 0, 764, 194],
      [776, 868, 1552, 560, 674, 1050, 1278, 742, 1084, 810, 1152, 274, 388, 422, 764, 0, 798],
      [662, 1210, 754, 1358, 1244, 708, 480, 856, 514, 468, 354, 844, 730, 536, 194, 798, 0],
        # fmt: on
    ]

    data["num_vehicles"] = 1
    data["depot"] = 0
    return data


def print_solution(data, manager, routing, assignment):
    """Prints assignment on console."""
    print(f"Objective: {assignment.ObjectiveValue()}")
    # Display dropped nodes.
    dropped_nodes = "Dropped nodes:"
    for node in range(routing.Size()):
        if routing.IsStart(node) or routing.IsEnd(node):
            continue
        if assignment.Value(routing.NextVar(node)) == node:
            dropped_nodes += f" {manager.IndexToNode(node)}"
    print(dropped_nodes)
    # Display routes
    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
        while not routing.IsEnd(index):
            node_index = manager.IndexToNode(index)
            plan_output += f" {node_index} -> "
            previous_index = index
            index = assignment.Value(routing.NextVar(index))
            route_distance += routing.GetArcCostForVehicle(
                previous_index, index, vehicle_id
            )
        plan_output += f" {manager.IndexToNode(index)}n"
        plan_output += f"Distance of the route: {route_distance}mn"
        print(plan_output)
        total_distance += route_distance
    print(f"Total Distance of all routes: {total_distance}m")


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 Distance constraint.
    dimension_name = "Distance"
    routing.AddDimension(
        transit_callback_index,
        0,  # no slack
        7000,  # vehicle maximum travel distance
        True,  # start cumul to zero
        dimension_name,
    )
    
    # Allow to drop nodes.
    
    for node in range(1, len(data["distance_matrix"])):
        routing.AddDisjunction([manager.NodeToIndex(node)], 100)
        
    N = 8
    time_dimension = routing.GetDimensionOrDie(dimension_name)
    
    # Definisco una nuova variabile da minimizzare per l'algoritmo
    for vehicle_id in range(data["num_vehicles"]):
        duration = 5000 - (time_dimension.CumulVar(routing.End(vehicle_id)) - time_dimension.CumulVar(routing.Start(vehicle_id)))
        routing.AddVariableMinimizedByFinalizer(duration)
        
    # elimino gli archi che non possono essere percorsi
    connessioni_eliminate = {}
    for i in range(0, 2*N + 1 + 2*(data["num_vehicles"]) - 1):
        connessioni_eliminate[i] = []
        
    for risorsa in range(data["num_vehicles"]):  
        nodo_considerato = manager.GetStartIndex(risorsa)
        connessioni_eliminate[nodo_considerato] = []
        for j in range(1, N + 1):
            nodo_da_eliminare = manager.NodeToIndex(j)
            routing.NextVar(nodo_considerato).RemoveValue(nodo_da_eliminare)
            connessioni_eliminate[nodo_considerato].append(nodo_da_eliminare)
            
    for risorsa in range(data["num_vehicles"]):     
        nodo_considerato = manager.GetEndIndex(risorsa)
        for j in range(N + 1,2*N + 1):
            nodo_precedente = manager.NodeToIndex(j)
            routing.NextVar(nodo_precedente).RemoveValue(nodo_considerato)
            connessioni_eliminate[nodo_considerato].append(nodo_precedente)
     
    for i in range(1,2*N + 1):
        nodo_considerato = manager.NodeToIndex(i)
        if nodo_considerato <= N:
            for j in range(1,2*N + 1):
                nodo_da_eliminare = manager.NodeToIndex(j)
                if nodo_da_eliminare == i + N:
                    continue
                else:
                    routing.NextVar(nodo_considerato).RemoveValue(nodo_da_eliminare)
                    connessioni_eliminate[nodo_considerato].append(nodo_da_eliminare)
        else:
            nodo_da_eliminare = manager.NodeToIndex(i - N + 1)
            routing.NextVar(nodo_considerato).RemoveValue(nodo_da_eliminare)
            connessioni_eliminate[nodo_considerato].append(nodo_da_eliminare)
            for j in range(N + 1,2*N + 1):
                nodo_da_eliminare = manager.NodeToIndex(j)
                routing.NextVar(nodo_considerato).RemoveValue(nodo_da_eliminare)
                connessioni_eliminate[nodo_considerato].append(nodo_da_eliminare)

    # 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(10)

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

    # Print solution on console.
    if assignment:
        print_solution(data, manager, routing, assignment)
    else:
        print("No solution found!")


if __name__ == "__main__":
    main()