-
Notifications
You must be signed in to change notification settings - Fork 0
/
TSPDL.py
91 lines (75 loc) · 3.43 KB
/
TSPDL.py
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
import random
import copy
import itertools
from collections import namedtuple
MOST_EXPENSIVE_ROUTE = 10000000000
Neighbor = namedtuple('Neighbor', 'solution swap')
class TSPDL:
def __init__(self, instance):
self.instance = instance
def generate_initial_solution(self):
all_ports = range(0, int(self.instance["number_of_ports"]))
solution = []
solution.append(0)
# Starting from garage
current_demand = self.get_total_demand()
print(f'Current demand: {current_demand}')
eligible_ports = self.find_eligible_ports(current_demand, [x for x in all_ports if x not in solution])
next_port = self.find_cheapest_route(0, eligible_ports)
solution.append(next_port)
current_demand = current_demand - int(self.instance['demand'][next_port])
# Finding intermiate route
for i in range(1, int(self.instance['number_of_ports']) - 1):
eligible_ports = self.find_eligible_ports(current_demand, [x for x in all_ports if x not in solution])
next_port = self.find_cheapest_route(solution[-1], eligible_ports)
solution.append(next_port)
current_demand = current_demand - int(self.instance['demand'][next_port])
# Going back to garage
solution.append(0)
return solution
def get_total_demand(self):
total = 0
for value in self.instance['demand']:
total = total + int(value)
return total
def find_eligible_ports(self, needed_draft, candidates):
eligible_drafts = []
for i in candidates:
if int(self.instance['draft'][i]) >= needed_draft:
eligible_drafts.append(i)
return eligible_drafts
def find_cheapest_route(self, origin, candidates):
#print(f'Origin: {origin}, candidates: {candidates}')
cheapest_route = MOST_EXPENSIVE_ROUTE
cheapest_route_index = -1
for i in candidates:
if int(self.instance['cost'][origin][i]) < cheapest_route:
cheapest_route = int(self.instance['cost'][origin][i])
cheapest_route_index = i
return cheapest_route_index
def get_cost_from_solution(self, solution):
total_cost = 0
for i in range(0, len(solution) - 1):
total_cost = total_cost + int(self.instance['cost'][solution[i]][solution[i+1]])
return total_cost
def get_all_valid_neighbors(self, solution, ilegal_moves):
swap_candidates = list(itertools.combinations(range(1, len(solution) - 1), 2))
for move in ilegal_moves:
if move is not None:
swap_candidates.remove(move)
neighbors = []
for i in range(0, len(swap_candidates)):
new_neighbor = copy.deepcopy(solution)
aux = new_neighbor[swap_candidates[i][0]]
new_neighbor[swap_candidates[i][0]] = new_neighbor[swap_candidates[i][1]]
new_neighbor[swap_candidates[i][1]] = aux
if self.is_valid(new_neighbor):
neighbors.append(Neighbor(new_neighbor, swap_candidates[i]))
return neighbors
def is_valid(self, solution):
current_demand = self.get_total_demand()
for i in range(1, len(solution)):
if int(self.instance['draft'][solution[i]]) < current_demand:
return False
current_demand = current_demand - int(self.instance['demand'][solution[i]])
return True