Travelling Salesperson Problem using Google OR Tools

Posted By :Vikas Kumar |31st August 2021

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.

 


About Author

Vikas Kumar

Vikas is a seasoned backend developer with a strong expertise in Python.He possesses a wide range of skills such as Python, Django, Flask, HTML, CSS, Celery, Git, and AWS services and a solid understanding of various databases including MongoDB, PostgreSQL, MySQL, and DynamoDB. He has worked on several notable projects such as English-Chinese Language Translation, i_infinitytransformation, Political Content Moderation, Optical Character Recognition, Palmadoc: Document content extraction, Hey, Kaido, and ViralNation. Given his extensive experience and diverse skillset, he is adept at developing robust backend solutions.

Request For Proposal

[contact-form-7 404 "Not Found"]

Ready to innovate ? Let's get in touch

Chat With Us