Solve salesman problem, Shortest Path through Points, by using Python 3

I need to share
how to use Python3 to solve salesman problem, Shortest Path through Points,

Shortest Path.dyn (26.4 KB)

I use eploy Python genetic algorithm library as shown in the below link

import sys
import clr
import System
clr.AddReference('ProtoGeometry')
from Autodesk.DesignScript.Geometry import *
dirAppLoc = System.Environment.GetFolderPath(System.Environment.SpecialFolder.LocalApplicationData) 
sys.path.append(dirAppLoc + r'\python-3.8.3-embed-amd64\Lib\site-packages')

clr.AddReference('System.Drawing')
import System.Drawing
from System.Drawing import *
from System.Drawing.Imaging import *
from System.IO import MemoryStream

import numpy as np
import matplotlib.pyplot as plt
from PIL import Image
import io
import math




import numpy as np
from scipy import spatial
import matplotlib.pyplot as plt



def plt2arr(fig):
    """
    need to draw if figure is not drawn yet
    """
    fig.canvas.draw()
    rgba_buf = fig.canvas.buffer_rgba()
    (w,h) = fig.canvas.get_width_height()
    rgba_arr = np.frombuffer(rgba_buf, dtype=np.uint8).reshape((h,w,4))
    return rgba_arr

def convertToBitmap2(npImgArray):
    bitmap_ = None
    # remove alpha
    if npImgArray.ndim == 3 and npImgArray.shape[-1] == 4:
        npImgArray = npImgArray[:, :, :-1]
    # convert to PIL Image
    if npImgArray.ndim == 3:
        image = Image.fromarray(npImgArray, "RGB")
    else:
        image = Image.fromarray(npImgArray, "L")
    # convert to Python ByteArray
    byteIO = io.BytesIO()
    image.save(byteIO, format='BMP')
    byteArr = byteIO.getvalue()
    # convert to Net ByteArray
    netBytes = System.Array[System.Byte](byteArr)
    with MemoryStream(netBytes) as ms:
        bitmap_ = Bitmap(ms)
    return bitmap_


#num_points = 10


X=IN[0]
num_points=IN[1]
#points_coordinate = np.random.rand(num_points, 2)  # generate coordinate of points
#points_coordinate = np.array([[50 , 6],[100, 0.23430645],[0.26308841, 0.25977513],[53 , 600]])

#points_coordinate = np.array([[pt[0],pt[1]] for pt in IN[0]], dtype=np.float32) 


points_coordinate = np.array([[pt.X, pt.Y] for pt in IN[0]], dtype=np.float32) 

distance_matrix = spatial.distance.cdist(points_coordinate, points_coordinate, metric='euclidean')


def cal_total_distance(routine):
    '''The objective function. input routine, return total distance.
    cal_total_distance(np.arange(num_points))
    '''
    num_points, = routine.shape
    return sum([distance_matrix[routine[i % num_points], routine[(i + 1) % num_points]] for i in range(num_points)])


from sko.GA import GA_TSP

ga_tsp = GA_TSP(func=cal_total_distance, n_dim=num_points, size_pop=50, max_iter=5000, prob_mut=1)
best_points, best_distance = ga_tsp.run()

points_coordinate

fig, ax = plt.subplots(1, 2)
best_points_ = np.concatenate([best_points, [best_points[0]]])
best_points_
best_points_coordinate = points_coordinate[best_points_, :]
ax[0].plot(best_points_coordinate[:, 0], best_points_coordinate[:, 1], 'o-r')
ax[1].plot(ga_tsp.generation_best_Y)
plt.show()


image_from_plot = plt2arr(fig)
bitmap1 = convertToBitmap2(image_from_plot)



OUT = bitmap1,best_points_coordinate.tolist()
16 Likes

Hello RMohareb:
Do you know if there is a way to create the shortest path but with ortogonal angles only. Because i want to draw a pipe layout across few street blocks to connect some buildings and i want to design it with generative design to optimise the layout.

3 Likes

Hi @Rlucki

you can look to the AU class @Cesare_Caoduro3. He show how to fined the shortest path for the cable. i think it may be help you. see in 33:00 min in the class video

3 Likes

thank you so much, now i will apply these and adapt it to my problem.

1 Like

i think that the problem with this algorithm is that we do not have cable trays on the model, there are just nodes that i want to connect with the shortest network possible and a starting point or a main branch with a starting point that needs to be included in the connection tree.

1 Like

https://skieffer.info/publications/kieffer2016hola.pdf in this paper talks about creating connections between nodes

1 Like

Awesome work @RMohareb ,
Have you tried different case with another algorithm? such as PSO/ Ant colony/ SOS?
I am currently working for this kind of technique to optimize BIM. Looking forward if you have done previous work/ reference to be followed :slight_smile: