Travelling Salesperson Problem using Google OR Tools

OR-Tools is great download for combinatorial optimization, which tries to determine the optimum solution to a problem among a huge number of options. Here are some difficulties that OR-Tools can help with:

Vehicle routing: Determine the best routes for vehicle fleets that pick up and deliver packages based on limits (e.g., "this truck can't carry more than 20,000 pounds" or "all deliveries must be made by this truck under two hours of windows").

Scheduling:Finding the best timetable for a large number of jobs, some of which must be completed before others, on a limited number of machines or other resources.

Bin packing:Problems like these typically have a large number of viable solutions—too numerous for a computer to sort through. OR-Tools overcomes this by narrowing the search set with cutting-edge algorithms in order to obtain an optimal (or near-optimal) answer.

OR-Tools includes solvers for:

• Constraint Programming
• Linear and Mixed-Integer Programming
• Routing
• Graph Algorithms

Here let's discuss about few points of a very big topic Routing:

First we create data and then create routing model. Following are the main section of programs creates the index manager.

manager = pywrapcp.RoutingIndexManager(len(data['distance_matrix']),
                                       data['num_vehicles'], data['depot'])
routing = pywrapcp.RoutingModel(manager)

The following are the inputs to RoutingIndexManager:

• The distance matrix's number of rows, or the number of locations (including the depot).
• The number of automobiles involved in the issue.
• The depot's related node.

Set the cost of travel

routing.SetArcCostEvaluatorOfAllVehicles(transit_callback_index)

Set search parameters

search_parameters = pywrapcp.DefaultRoutingSearchParameters()
search_parameters.first_solution_strategy = (
    routing_enums_pb2.FirstSolutionStrategy.PATH_CHEAPEST_ARC)

Add the solution printer

def print_solution(manager, routing, solution):
    """Prints solution on console."""
    print('Objective: {} miles'.format(solution.ObjectiveValue()))
    index = routing.Start(0)
    plan_output = 'Route for vehicle 0:\n'
    route_distance = 0
    while not routing.IsEnd(index):
        plan_output += ' {} ->'.format(manager.IndexToNode(index))
        previous_index = index
        index = solution.Value(routing.NextVar(index))
        route_distance += routing.GetArcCostForVehicle(previous_index, index, 0)
    plan_output += ' {}\n'.format(manager.IndexToNode(index))
    print(plan_output)
    plan_output += 'Route distance: {}miles\n'.format(route_distance)

Solve and print the solution

solution = routing.SolveWithParameters(search_parameters)
if solution:
    print_solution(manager, routing, solution)

Conclusion: -

OR-TOOL will help to find solution for complex problems. This has the advantage of preserving the routes in case you want to use them again later.