TSP with node having various cost

tsp_node_with_various_cost.py

#!/usr/bin/env python3
"""
Having a cost different if a node is visited last or along the route
"""

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["costs"] = [
        {"part": 0, "final": 0},  # 0
        {"part": 2, "final": 3},  # 1 (part) / 4 (final)
        {"part": 4, "final": 2},  # 2 (part) / 5 (final)
        {"part": 1, "final": 3},  # 3 (part) / 6 (final)
    ]
    data["depot"] = 0
    data["num_vehicles"] = 1
    return data


def print_solution(data, manager, routing, solution):
    """Prints solution on console."""
    print(f"Objective: {solution.ObjectiveValue()}")
    # Display dropped nodes.
    dropped_nodes = "Dropped nodes:"
    for node in range(routing.Size()):
        if routing.IsStart(node) or routing.IsEnd(node):
            continue
        if solution.Value(routing.NextVar(node)) == node:
            dropped_nodes += f" {manager.IndexToNode(node)}"
    print(dropped_nodes)
    # Display routes
    max_route_distance = 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
        while not routing.IsEnd(index):
            node = manager.IndexToNode(index)
            plan_output += f" {node}"
            if node > len(data["costs"]):
                plan_output += f'({node-len(data["costs"])+1})'
            plan_output += f" -> "
            previous_index = index
            index = solution.Value(routing.NextVar(index))
            route_distance += routing.GetArcCostForVehicle(
                previous_index, index, vehicle_id
            )
        plan_output += "{}\n".format(manager.IndexToNode(index))
        plan_output += "Distance of the route: {}m\n".format(route_distance)
        print(plan_output)
        max_route_distance = max(route_distance, max_route_distance)
    print("Maximum of the route distances: {}m".format(max_route_distance))


def main():
    """Entry point of the program."""
    # Instantiate the data problem.
    data = create_data_model()

    # Create the routing index manager.
    manager = pywrapcp.RoutingIndexManager(
        2 * len(data["costs"]) - 1,
        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)

        # part node shouldn't be final
        #if from_node in [1, 2, 3] and to_node is 0:
        #    return 9999
        return 1

    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
       1024,  # vehicle maximum travel distance
       True,  # start cumul to zero
       dimension_name)
    #distance_dimension = routing.GetDimensionOrDie(dimension_name)
    #distance_dimension.SetGlobalSpanCostCoefficient(100)

    # Compute the indices list of vehicle end nodes.
    end_indices = []
    for vehicle_id in range(manager.GetNumberOfVehicles()):
        end_indices.append(routing.End(vehicle_id))

    # Part nodes can't have end node as next
    for part_node in range(1, len(data["costs"])):
        part_index = manager.NodeToIndex(part_node)
        print(f"Remove end indices from NextVar({part_index})")
        routing.NextVar(part_index).RemoveValues(end_indices)

    # Final nodes only have end nodes as next
    offset = len(data["costs"]) - 1
    for final_node in range(1+offset, len(data["costs"])+offset):
        final_index = manager.NodeToIndex(final_node)
        print(f"Only allow end indices for NextVar({final_index})")
        routing.NextVar(final_index).SetValues(end_indices + [final_index])

    # Allow to drop part nodes with a penalty of "final" cost.
    for i in range(1, len(data["costs"])):
        index = manager.NodeToIndex(i)
        penalty = data["costs"][i]["final"]
        print(f"Allow to drop index {index} for penalty {penalty}")
        routing.AddDisjunction([index], penalty)

    # Allow to drop final nodes, with a penalty of "part" cost.
    for i in range(1, len(data["costs"])):
        index = manager.NodeToIndex(i+offset)
        penalty = data["costs"][i]["part"]
        print(f"Allow to drop index {index} for penalty {penalty}")
        routing.AddDisjunction([index], penalty)


    # Only allow one node to be visited between the part and the final duplicate.
    for i in range(1, len(data["costs"])):
        part_index = manager.NodeToIndex(i)
        final_index = manager.NodeToIndex(i+offset)
        routing.solver().Add(routing.ActiveVar(part_index)+routing.ActiveVar(final_index) <= 1)


    # 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(2)
    #search_parameters.log_search = True

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

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


if __name__ == "__main__":
    main()

zz.md

Possible output:

%./build/python/venv/bin/python ~/work/tmp/tsp_node_with_various_cost.py 
Remove end indices from NextVar(1)
Remove end indices from NextVar(2)
Remove end indices from NextVar(3)
Only allow end indices for NextVar(4)
Only allow end indices for NextVar(5)
Only allow end indices for NextVar(6)
Allow to drop index 1 for penalty 3
Allow to drop index 2 for penalty 2
Allow to drop index 3 for penalty 3
Allow to drop index 4 for penalty 2
Allow to drop index 5 for penalty 4
Allow to drop index 6 for penalty 1
Objective: 9
Dropped nodes: 2 4 6
Route for vehicle 0:
 0 ->  3 ->  1 ->  5(2) -> 0
Distance of the route: 4m

Maximum of the route distances: 4m