import numpy as np # Function to calculate distance between two points def distance(a, b): return np.sqrt((a[0] - b[0]) ** 2 + (a[1] - b[1]) ** 2) locations = [ (54.1391723668124,10.1630144708565), (5.16311785475916,18.3713689888664), (58.1077341232713,97.325872003479), (16.6066387616466,73.6752906752222), (10.9215147296463,26.9026260431418), (40.2830425950062,49.0059611185157), (95.9067950103118,31.2537921390593), (38.8068853736467,61.8496341187066), (50.7736281603872,41.7122988413166), (16.1210451723109,4.17415211185698), (30.5725260368337,25.6641613944403), (88.6541848293903,28.6034058450262), (76.1583329812348,52.0601020081577), (57.9907902884404,58.2901693224847), (80.1180100459334,80.7424210060046), (90.879027610417,90.9769056531731), (2.58720752188314,45.8084939684228), (74.0498005304951,2.98613115772289), (71.7091166549543,37.2581705831028), (22.3719171429327,94.5307472331531), (24.1011220595671,11.0665812260669), (42.2780005223912,9.14186038530076), (58.3280585995255,76.1590760811723), (71.2535984441914,18.2126848196072), (57.2421947321968,82.6687611686287), ] # Calculate distances matrix n = len(locations) distances = np.zeros((n, n)) for i in range(n): for j in range(n): distances[i, j] = distance(locations[i], locations[j]) # Dynamic programming solution for the VRP def vrp(warehouses, max_stops, costs): all_stores = frozenset(range(1, 25)) def dp(state): pos, visited, (trucks, lorries) = state if visited == all_stores: return distances[pos, warehouses[0]] + trucks * costs[0] + lorries * costs[1], [pos], (trucks, lorries) state_key = (pos, visited, (trucks, lorries)) if state_key in memo: return memo[state_key] min_cost, min_route, min_vehicles = float('inf'), [], (0, 0) for next_pos in all_stores - visited: next_state = (next_pos, visited | {next_pos}, (trucks + (pos in warehouses), lorries + (pos not in warehouses))) next_cost, next_route, next_vehicles = dp(next_state) next_cost += distances[pos, next_pos] if next_cost < min_cost: min_cost, min_route, min_vehicles = next_cost, [pos] + next_route, next_vehicles memo[state_key] = min_cost, min_route, min_vehicles return min_cost, min_route, min_vehicles memo = {} state = (warehouses[0], frozenset(), (0, 0)) cost, route, (num_trucks, num_lorries) = dp(state) return cost, route, (num_trucks, num_lorries) # Test the VRP solution for the given problem warehouses = [22, 23] max_stops = [4, 16] costs = [1, 2] total_cost, best_route, (num_trucks, num_lorries) = vrp(warehouses, max_stops, costs) output = f"""Best route: {best_route} Total cost: {total_cost} Number of trucks: {num_trucks} Number of lorries: {num_lorries} """ # Print the result in the console print(output) # Save the result to the file with open("info.txt", "w") as f: f.write(output)
# The result  # Running tests 