CODEWITHSUNDEEP
python-3.xtraveling-salesmanor-tools
shabnam Aghaei
shabnam Aghaei

Reputation: 13

or-tools setting custom cost for tsp

I'm working on a project that needs to solve a TSP in the process. I found or-tools for this purpose. as I understood, or-tools for tsp uses distance as cost this means the cost of travel between any two locations is just the distance between them. I need to set my costs manually as I want the cost to be affected by some other factors than only distance. this is the code that sets the cost for TSP in or-tools.

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)
routing.SetArcCostEvaluatorOfAllVehicles(transit_callback_index)

I have 2 questions regarding this code:
1- distance_callback is a function. how come the function is called without it's parametrs in routing.RegisterTransitCallback(distance_callback)?
2- How can I change this code to set my custom cost?

I have a matrix of my custom costs and I tried to replace return data['distance_matrix'][from_node][to_node] with my own cost matrix return data['cost_matrix'][from_node][to_node], but it didnt work corectly.

Upvotes: 1

Views: 1405

Answers (2)

Mizux
Mizux

Reputation: 9301

  1. This callback will be call by the C++ library, the python package is a native package which wrap the C++ library using SWIG.

  2. technically the solver only need you to register function (or lambda) taking two parameters (int64 from_index, int64 to_index) and returning an integer (int64).

  3. A good starting point

cost_callback_indices = []
for vehicle_idx in range(data['vehicle_number']):
    def vehicle_cost_callback(from_index, to_index, i=vehicle_idx):
        from_node = manager.IndexToNode(from_index)
        to_node = manager.IndexToNode(to_index)
        return data['distance_matrix'][i][from_node][to_node]
    cost_callback_index = routing.RegisterTransitCallback(vehicle_cost_callback)
    cost_callback_indices.append(cost_callback_index)
    routing.SetArcCostEvaluatorOfVehicle(cost_callback_index, vehicle_idx)

see: https://github.com/google/or-tools/issues/1795#issue-540774218

Upvotes: 0

Laurent Perron
Laurent Perron

Reputation: 11034

You can register on distance callback per vehicle.

See: the SetArcCostEvaluatorOfVehicle method

Upvotes: 1

Related Questions