OR-Tools is an open-source optimization suite that provides constraint-programming and routing solvers. It turns a problem’s data, constraints, and costs into a model that can search for feasible or low-cost solutions. section 6.5 section 2.1.2
A typical OR-Tools workflow includes:
- Represent distances, vehicles, and depots in a data model. section 6.5
- Create an index manager and routing model, then register a distance callback. section 6.5
- Set an arc-cost evaluator and choose a search strategy such as tabu search. section 6.5
- Solve, print the route and objective value, and visualize the resulting path. section 6.5
Berlin52 traveling-salesman problem
A Python model loads 52 Berlin locations, converts pairwise distances to integers, defines one vehicle and depot 0, and runs tabu search for 30 seconds. One reported route has an objective of 7,884 meters. section 6.5
Listing 6.3 Solving Belin52 TSP using OR-Tools tabu search
import numpy as np from optalgotools.problems import TSP #1 from ortools.constraint_solver import pywrapcp #2 from ortools.constraint_solver import routing_enums_pb2 #3 import matplotlib.pyplot as plt berlin52_tsp_url = 'https://raw.githubusercontent.com/coin-or/jorlib/ b3a41ce773e9b3b5b73c149d4c06097ea1511680/jorlib-core/src/test/resources/ tspLib/tsp/berlin52.tsp' #4 berlin52_tsp = TSP(load_tsp_url=berlin52_tsp_url, gen_method='mutate', init_method='random') #5 cities = berlin52_tsp.cities #6 tsp_dist=berlin52_tsp.eval_distances_from_cities(cities) #6 tsp_dist_int=list(np.array(tsp_dist).astype(int)) #6 #1 Import the TSP problem class from optalgotools. #2 Import the Python wrapper for the C++ constraint programming solver in OR-Tools. #3 Import the protocol buffer module. #4 Get berlin52 from a permalink. #5 Create a different tsp object from the problem class. #6 Define the problem parameters.
Browse the complete Python listing for loading Berlin52, constructing the routing model, solving with tabu search, and plotting the route. section 6.5
