Solving the Traveling Salesperson Problem Google OR-Tools with Python for AutoCAD

 

OR-Tools has a bunch of NP-complete, NP-hard algorithms that could be useful in the CAD industry, TSP, Packing, Linear Optimization. This is a sample of using OR-Tools inside AutoCAD. It’s a bit hard to use, but these are the world's toughest. As a side note, this was a hot challenge over at TheSwamp. 

Here’s the Traveling SalespersonProblem, this drawing has about 200 points, the runtime is instant 

import PyRx as Rx

import PyGe as Ge

import PyGi as Gi

import PyDb as Db

import PyAp as Ap

import PyEd as Ed

import traceback

# OR-Tools imports

from ortools.constraint_solver import routing_enums_pb2

from ortools.constraint_solver import pywrapcp

# define our command

def PyRxCmd_doit():

    try:

        #build a selectionset of points

        db = Db.curDb()

        filter = [(Db.DxfCode.kDxfStart, "POINT")]

        ssres: tuple[Ed.PromptStatus,

                     Ed.SelectionSet] = Ed.Editor.select(filter)

        if ssres[0] != Ed.PromptStatus.eOk:

            return

        # this is the distance map

        locs = []

        for id in ssres[1].objectIds():

            pntObj = Db.Point(id)

            locs.append(pntObj.position())

        manager = pywrapcp.RoutingIndexManager(len(locs), 1, 0)

        routing = pywrapcp.RoutingModel(manager)

        # not really optimal as this gets called a lot

        # could build a cache like google shows

        def dist_func(from_index, to_index):

            # scale and convert to int

            from_node = manager.IndexToNode(from_index)

            to_node = manager.IndexToNode(to_index)

            return int(locs[from_node].

                       distanceTo(locs[to_node]) * 100)

        #add the callback

        dist_callback = routing.RegisterTransitCallback(dist_func)

        # Define cost of each arc.

        routing.SetArcCostEvaluatorOfAllVehicles(dist_callback)

        # Setting first solution heuristic.

        search_parameters = pywrapcp.DefaultRoutingSearchParameters()

        search_parameters.first_solution_strategy = (

            # you can change the algorithm here

            # https://developers.google.com/optimization/routing/routing_options#first_solution_strategy

            routing_enums_pb2.FirstSolutionStrategy.PATH_CHEAPEST_ARC

        )

        solution = routing.SolveWithParameters(search_parameters)

        if solution:

            draw_solution(manager, routing, solution, locs, db)

    except Exception as err:

        traceback.print_exception(err)

# get the point indexes from the solution

def draw_solution(manager, routing, solution, locs, db):

    pnts = []

    index = routing.Start(0)

    while not routing.IsEnd(index):

        pnts.append(locs[manager.IndexToNode(index)])

        index = solution.Value(routing.NextVar(index))

        pnts.append(locs[manager.IndexToNode(index)])

       

    # create a polyline

    model = Db.BlockTableRecord(db.modelSpaceId(), Db.OpenMode.kForWrite)

    model.appendAcDbEntity(Db.Polyline(pnts))