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
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
|
import numpy as np
import copy
class Node:
def __init__(self, id: int, x: float, y: float, demand: float, ready_time: float, due_time: float, service_time: float):
super()
self.id = id
if id == 0:
self.is_depot = True
else:
self.is_depot = False
self.x = x
self.y = y
self.demand = demand
self.ready_time = ready_time
self.due_time = due_time
self.service_time = service_time
class VrptwGraph:
"""VRPTW instance container class
Attributes
----------
rho : float
Pheromone volatilization rate
nodes : list
Nodes of the graph (depot + customers)
node_num : float
Number of nodes
node_dist_mat : list
Distance matrix
pheromone_mat : list
Pheromone matrix
heuristic_info_mat : list
Heuristic information matrix
"""
def __init__(self, file_path, rho=0.1):
super()
self.node_num, self.nodes, self.node_dist_mat, self.vehicle_num, self.vehicle_capacity \
= self.create_from_file(file_path)
self.rho = rho
self.nnh_travel_path, nnh_travel_path_dist, _ = self.nearest_neighbor_heuristic()
self.init_pheromone_val = 1 / (nnh_travel_path_dist * self.node_num)
self.pheromone_mat = np.ones((self.node_num, self.node_num)) * self.init_pheromone_val
self.heuristic_info_mat = 1 / self.node_dist_mat
def copy(self, init_pheromone_val):
new_graph = copy.deepcopy(self)
# 信息素
new_graph.init_pheromone_val = init_pheromone_val
new_graph.pheromone_mat = np.ones((new_graph.node_num, new_graph.node_num)) * init_pheromone_val
return new_graph
def create_from_file(self, file_path):
"""Read input file. Set parameters, nodes and distance matrix.
从文件中读取服务点、客户的位置
お前はもう死んでいる。なに〜！
"""
# Create nodes
node_list = []
with open(file_path, 'rt') as f:
count = 1
for line in f:
if count == 5:
vehicle_num, vehicle_capacity = line.split()
vehicle_num = int(vehicle_num)
vehicle_capacity = int(vehicle_capacity)
elif count >= 10:
node_list.append(line.split())
count += 1
node_num = len(node_list)
nodes = [Node(
int(item[0]), # id
float(item[1]), float(item[2]), # coords.
float(item[3]), # demand
float(item[4]), float(item[5]), # time window
float(item[6]) # service time
) for item in node_list]
# Create distance matrix
node_dist_mat = np.zeros((node_num, node_num))
for i in range(node_num):
node_a = nodes[i]
node_dist_mat[i][i] = 1e-8
for j in range(i+1, node_num):
node_b = nodes[j]
node_dist_mat[i][j] = VrptwGraph.calculate_dist(node_a, node_b)
node_dist_mat[j][i] = node_dist_mat[i][j]
return node_num, nodes, node_dist_mat, vehicle_num, vehicle_capacity
@staticmethod
def calculate_dist(node_a, node_b):
"""Euclidean distance"""
return np.linalg.norm((node_a.x - node_b.x, node_a.y - node_b.y))
def local_update_pheromone(self, start_ind, end_ind):
self.pheromone_mat[start_ind][end_ind] = (1-self.rho) * self.pheromone_mat[start_ind][end_ind] + \
self.rho * self.init_pheromone_val
def global_update_pheromone(self, best_path, best_path_distance):
"""Update pheromone trail on best path (T+)
Ant Colony System offline pheromone trail update
"""
self.pheromone_mat = (1-self.rho) * self.pheromone_mat
current_index = best_path[0]
for next_index in best_path[1:]:
self.pheromone_mat[current_index][next_index] += self.rho/best_path_distance
current_index = next_index
def nearest_neighbor_heuristic(self, max_vehicle_num=None):
"""Generate route plan using Nearest Neighbor (NN) heuristic
Returns
-------
list
route plan, travel_distance, vehicle_num
"""
index_to_visit = list(range(1, self.node_num)) # 0 is depot
# route plan begins at depot
current_index = 0
current_load = 0
current_time = 0
travel_distance = 0
travel_path = [0]
if max_vehicle_num is None:
max_vehicle_num = self.node_num
while len(index_to_visit) > 0 and max_vehicle_num > 0:
# While there are nodes left to visit, or vehicle_num reaches 1;
# find NN to visit next in travel_path
nn_index = self._cal_nearest_next_index(index_to_visit,
current_index, current_load, current_time)
if nn_index is None:
# Finish current vehicle route (return to depot)
travel_distance += self.node_dist_mat[current_index][0]
current_load = 0
current_time = 0 # all vehicles depart at t=0 ?
travel_path.append(0)
current_index = 0
max_vehicle_num -= 1
else:
# Add nearest neighbour node to vehicle route
current_load += self.nodes[nn_index].demand
dist = self.node_dist_mat[current_index][nn_index]
wait_time = max(self.nodes[nn_index].ready_time - current_time - dist, 0)
service_time = self.nodes[nn_index].service_time
current_time += dist + wait_time + service_time
index_to_visit.remove(nn_index)
travel_distance += self.node_dist_mat[current_index][nn_index]
travel_path.append(nn_index)
current_index = nn_index
# Finish route plan (final return to depot)
travel_distance += self.node_dist_mat[current_index][0]
travel_path.append(0)
vehicle_num = travel_path.count(0) - 1
return travel_path, travel_distance, vehicle_num
def _cal_nearest_next_index(self, index_to_visit, current_index, current_load, current_time):
"""Find nearest reachable next_index
Parameters
----------
index_to_visit : list
Remaining node indices to visit
"""
nearest_index = None
nearest_distance = None
for next_index in index_to_visit:
if current_load + self.nodes[next_index].demand > self.vehicle_capacity:
# Homogenous vehicle capacity constraint
continue
dist = self.node_dist_mat[current_index][next_index]
wait_time = max(self.nodes[next_index].ready_time - current_time - dist, 0)
service_time = self.nodes[next_index].service_time
return_time = current_time + dist * 1 + wait_time + service_time \
+ self.node_dist_mat[next_index][0]
if return_time > self.nodes[0].due_time:
# Depot time window constraint
continue
if current_time + dist > self.nodes[next_index].due_time:
# Time window constraint
continue
if nearest_distance is None or dist < nearest_distance:
nearest_distance = dist
nearest_index = next_index
return nearest_index
class PathMessage:
"""Deep copy of travel_path?"""
def __init__(self, path, distance):
if path is not None:
self.path = copy.deepcopy(path)
self.distance = copy.deepcopy(distance)
self.used_vehicle_num = self.path.count(0) - 1
else:
self.path = None
self.distance = None
self.used_vehicle_num = None
def get_path_info(self):
return self.path, self.distance, self.used_vehicle_num
|
