One of my IoT students has been exploring the classical Travelling Salesman Problem and came across an excellent write-up produced by a graduate at the University of Pittsburgh.
The document contains a substantial amount of mathematical theory; however, from page 15 onwards it presents a fully worked example showing how the problem can be solved manually. This example uses the Nearest Neighbour heuristic, which is relatively straightforward to model programmatically. I therefore encouraged the student to implement this approach in Python as a practical exercise (as shown below).
dist = [
[0, 8, 8, 6, 7],
[8, 0, 12, 10, 11],
[8, 12, 0, 5, 9],
[6, 10, 5, 0, 15],
[7, 11, 9, 15, 0]
]
N = len(dist)
current = 0
visited = [False] * N
visited[current] = True
path = [current]
total_distance = 0
for _ in range(N - 1):
next_city = None
min_dist = 1e9
for city in range(N):
if not visited[city] and dist[current][city] < min_dist:
min_dist = dist[current][city]
next_city = city
visited[next_city] = True
path.append(next_city)
total_distance += min_dist
current = next_city
total_distance += dist[current][path[0]]
path.append(path[0])
print("Greedy distance:", total_distance)
print("Path:", path)
As a personal challenge, I took his Python script, converted it to JavaScript using an online Python-to-JavaScript tool, and then placed the converted code into a Node-RED function node. This resulted in the simple flow shown below.
[{"id":"24eb715b6b856fce","type":"tab","label":"Travelling_Salesman_Problem","disabled":false,"info":"","env":[]},{"id":"140e2b6541a0e6fc","type":"function","z":"24eb715b6b856fce","name":"Travelling Salesman calcs","func":"const dist = [\n [0, 8, 8, 6, 7],\n [8, 0, 12, 10, 11],\n [8, 12, 0, 5, 9],\n [6, 10, 5, 0, 15],\n [7, 11, 9, 15, 0]\n];\n\nconst N = dist.length;\nlet current = 0;\nconst visited = Array(N).fill(false);\nvisited[current] = true;\n\nconst path = [current];\nlet total_distance = 0;\n\nfor (let i = 0; i < N - 1; i++) {\n let next_city = null;\n let min_dist = 1e9;\n\n for (let city = 0; city < N; city++) {\n if (!visited[city] && dist[current][city] < min_dist) {\n min_dist = dist[current][city];\n next_city = city;\n }\n }\n\n visited[next_city] = true;\n path.push(next_city);\n total_distance += min_dist;\n current = next_city;\n}\n\n// Return to start\ntotal_distance += dist[current][path[0]];\npath.push(path[0]);\n\nmsg.payload =\n \"Greedy distance: \" + total_distance +\n \"\\nPath: \" + JSON.stringify(path);\n\nreturn msg;\n","outputs":1,"timeout":0,"noerr":0,"initialize":"","finalize":"","libs":[],"x":310,"y":240,"wires":[["4d0947a041ac8a6f"]]},{"id":"5aa55d037231cd41","type":"inject","z":"24eb715b6b856fce","name":"Trigger","props":[{"p":"payload"}],"repeat":"","crontab":"","once":false,"onceDelay":0.1,"topic":"","payload":"1","payloadType":"num","x":110,"y":240,"wires":[["140e2b6541a0e6fc"]]},{"id":"4d0947a041ac8a6f","type":"debug","z":"24eb715b6b856fce","name":"Show results","active":true,"tosidebar":true,"console":true,"tostatus":false,"complete":"payload","targetType":"msg","statusVal":"","statusType":"auto","x":540,"y":240,"wires":[]}]
Hope you have fun trying it out with Node-RED and/or Python.
