-
-
Save phabee/e71890b984d8f92190ee86e6c7a81998 to your computer and use it in GitHub Desktop.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
# Samplescript with Nearest Neighbor C-Heuristic + 2-opt Local Search | |
import math | |
import pytest | |
def calculate_distance(coord1, coord2): | |
return math.sqrt((coord1[0] - coord2[0]) ** 2 + (coord1[1] - coord2[1]) ** 2) | |
def nearest_neighbor_tsp(start_node, nodes): | |
unvisited = set(nodes.keys()) | |
tour = [start_node] | |
unvisited.remove(start_node) | |
total_distance = 0.0 | |
current_node = start_node | |
while unvisited: | |
next_node = min(unvisited, key=lambda node: calculate_distance(nodes[current_node], nodes[node])) | |
distance = calculate_distance(nodes[current_node], nodes[next_node]) | |
total_distance += distance | |
tour.append(next_node) | |
unvisited.remove(next_node) | |
current_node = next_node | |
# Add distance back to the start to complete the tour | |
total_distance += calculate_distance(nodes[current_node], nodes[start_node]) | |
return tour, total_distance | |
def read_tsp_file(file_path): | |
""" | |
read TSPlib input file and return a nodes-dictionary | |
:param file_path: | |
:return: dict containing nodes with tupels representing x, y coordinates | |
""" | |
nodes = {} | |
with open(file_path, 'r') as file: | |
lines = file.readlines() | |
node_section = False | |
for line in lines: | |
line = line.strip() | |
if line.startswith("NODE_COORD_SECTION"): | |
node_section = True | |
continue | |
if line.startswith("EOF"): | |
break | |
if node_section: | |
parts = line.split() | |
if len(parts) == 3: | |
node_id, x, y = parts | |
nodes[int(node_id)] = (float(x), float(y)) | |
return nodes | |
def total_tour_distance(tour, nodes): | |
distance = 0.0 | |
for i in range(len(tour) - 1): | |
distance += calculate_distance(nodes[tour[i]], nodes[tour[i + 1]]) | |
distance += calculate_distance(nodes[tour[-1]], nodes[tour[0]]) # Return to start | |
return distance | |
def two_opt_swap(tour, i, k): | |
new_tour = tour[0:i] + tour[i:k + 1][::-1] + tour[k + 1:] | |
return new_tour | |
def tsp_local_search(nodes, initial_solution): | |
# Initialize the best solution and its distance | |
best_solution = initial_solution | |
best_distance = total_tour_distance(best_solution, nodes) | |
improvement = True | |
# Continue searching for improvements while possible | |
while improvement: | |
improvement = False | |
for i in range(1, len(best_solution) - 1): | |
for k in range(i + 1, len(best_solution)): | |
# Generate a new solution by performing a 2-opt swap | |
new_solution = two_opt_swap(best_solution, i, k) | |
# Calculate the distance of the new solution | |
new_distance = total_tour_distance(new_solution, nodes) | |
# Check if the new solution is better | |
if new_distance < best_distance: | |
best_solution = new_solution | |
best_distance = new_distance | |
improvement = True | |
return best_solution, best_distance | |
# ******************************************************************************************************************* | |
# * Testcases to validate if code is working as expected * | |
# ******************************************************************************************************************* | |
def test_tsp_test_1(): | |
""" | |
Test, whether test4.tsp returns a tour with length 80 | |
:return: | |
""" | |
file_path = './data/test4.tsp' | |
nodes = read_tsp_file(file_path) | |
start_node = 1 | |
_, total_distance = nearest_neighbor_tsp(start_node, nodes) | |
assert total_distance == 80.0, f"Expected distance to be 80, but got {total_distance}" | |
def test_tsp_test_2(): | |
""" | |
Test, whether test8.tsp returns a tour with length 4*5 + 4*5*sqrt(2) = 20*(1+sqrt(2))=48.28 | |
:return: | |
""" | |
file_path = './data/test8.tsp' | |
nodes = read_tsp_file(file_path) | |
start_node = 1 | |
tour, total_distance = nearest_neighbor_tsp(start_node, nodes) | |
# make sure, tour follows the points in counter clockwise direction onthe octagon | |
assert tour == [1, 2, 3, 4, 5, 6, 7, 8], f"Expected tour to be the sequence of 1-8, but got {tour}" | |
# make sure, tour distance summary equals to the 4x5 units pieces + 4x5xsqrt(2) units pieces | |
assert total_distance == pytest.approx(4 * 5 + 4 * 5 * math.sqrt(2), | |
rel=1e-4), f"Expected distance to be 48.2842, but got {total_distance}." | |
# ******************************************************************************************************************* | |
# * Main Program * | |
# ******************************************************************************************************************* | |
def main(): | |
file_paths = ['./data/berlin52.tsp', './data/u1817.tsp', './data/u2319.tsp'] | |
start_nodes = [1, 257, 2319] | |
optimal_cost = [7542, 57201, 234256] | |
for id, file in enumerate(file_paths): | |
nodes = read_tsp_file(file) | |
# Call k-heuristic to create initial tsp solution | |
tour, dist = nearest_neighbor_tsp(start_nodes[id], nodes) | |
print(f"*** File {file}, with start node {id}:") | |
print(f"Tour: {tour[:5]}") | |
print(f"Dist: {round(dist)}") | |
print(f"Opt.Gap: {round(100 * (dist / optimal_cost[id] - 1), 2)}") | |
# Call local-search to improve initial tsp solution | |
print(f"*** Improving tour with local search ***") | |
tour, dist = tsp_local_search(nodes, tour) | |
print(f"Tour: {tour[:5]}") | |
print(f"Dist: {round(dist)}") | |
print(f"Opt.Gap: {round(100 * (dist / optimal_cost[id] - 1), 2)}") | |
if __name__ == "__main__": | |
main() |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment