summaryrefslogtreecommitdiffstats
diff options
context:
space:
mode:
Diffstat
-rw-r--r--ant.py262
-rw-r--r--example1.py7
-rw-r--r--multiple_ant_colony_system.py187
-rw-r--r--odiparpack/pedidosperu195.txt205
-rw-r--r--sols/c208_v3_d81115
-rw-r--r--sols/pedidosperu78.txt7
-rw-r--r--vrptw_base.py15
7 files changed, 519 insertions, 179 deletions
diff --git a/ant.py b/ant.py
index f07c664..9887847 100644
--- a/ant.py
+++ b/ant.py
@@ -5,6 +5,26 @@ from threading import Event
class Ant:
+ """Instancia de agente en Ant Colony System. Paralelizable.
+
+ Attributes
+ ----------
+ graph : VrptwGraph
+ VRPTW problem instance (parameters + graph + pheromones)
+ current_index : int
+ Current route's vehicle's location
+ vehicle_load : float
+ Current route's vehicle's spare capacity
+ vehicle_travel_time : float
+ Current route's vehicle's travel time
+ travel_path : list
+ Representation of the solution. A sequence of node indeces.
+ arrival_time : list
+ ?
+ index_to_visit : list
+ Remaining node indices not yet included in travel_path
+ total_travel_distance : float
+ """
def __init__(self, graph: VrptwGraph, start_index=0):
super()
self.graph = graph
@@ -20,28 +40,31 @@ class Ant:
self.total_travel_distance = 0
def clear(self):
+ """Restart Ant solution (Kill)"""
self.travel_path.clear()
self.index_to_visit.clear()
def move_to_next_index(self, next_index):
- # 更新蚂蚁路径
+ """Update ant path + "current simulated vehicle route parameters"."""
self.travel_path.append(next_index)
- self.total_travel_distance += self.graph.node_dist_mat[self.current_index][next_index]
-
dist = self.graph.node_dist_mat[self.current_index][next_index]
- self.arrival_time.append(self.vehicle_travel_time + dist)
+ self.total_travel_distance += dist
+
+ self.arrival_time.append(self.vehicle_travel_time + dist * 1)
if self.graph.nodes[next_index].is_depot:
- # 如果一下个位置为服务器点，则要将车辆负载等清空
+ # If the next location is a depot, the vehicle load, etc., must be cleared
+ # (start next vehicle route)
self.vehicle_load = 0
self.vehicle_travel_time = 0
else:
- # 更新车辆负载、行驶距离、时间
+ # Update vehicle load, distance traveled, time
self.vehicle_load += self.graph.nodes[next_index].demand
- # 如果早于客户要求的时间窗(ready_time)，则需要等待
-
- self.vehicle_travel_time += dist + max(self.graph.nodes[next_index].ready_time - self.vehicle_travel_time - dist, 0) + self.graph.nodes[next_index].service_time
+ # If it is earlier than the time window (ready_time) requested by the client, you need to wait
+ self.vehicle_travel_time += dist * 1 \
+ + max(self.graph.nodes[next_index].ready_time - self.vehicle_travel_time - dist * 1, 0) \
+ + self.graph.nodes[next_index].service_time
self.index_to_visit.remove(next_index)
self.current_index = next_index
@@ -53,75 +76,102 @@ class Ant:
return self.travel_path.count(0)-1
def check_condition(self, next_index) -> bool:
- """
- 检查移动到下一个点是否满足约束条件
- :param next_index:
- :return:
+ """Check if moving to next point satisfies constraints
+
+ Returns
+ -------
+ bool
+ Conditions satisfied.
"""
if self.vehicle_load + self.graph.nodes[next_index].demand > self.graph.vehicle_capacity:
+ # Capacity is not enough to serve whole customer demand
return False
- dist = self.graph.node_dist_mat[self.current_index][next_index]
- wait_time = max(self.graph.nodes[next_index].ready_time - self.vehicle_travel_time - dist, 0)
+ # Time that takes traversing the arc ("tramo") (vehicle mean speed may vary)
+ dist_time = self.graph.node_dist_mat[self.current_index][next_index] * 1
+ wait_time = max(self.graph.nodes[next_index].ready_time - self.vehicle_travel_time - dist_time, 0)
service_time = self.graph.nodes[next_index].service_time
- # 检查访问某一个旅客之后，能否回到服务店
- if self.vehicle_travel_time + dist + wait_time + service_time + self.graph.node_dist_mat[next_index][0] > self.graph.nodes[0].due_time:
+ # Check whether a traveler can return to the service shop after visiting a certain traveler
+ if self.vehicle_travel_time + dist_time + wait_time + service_time \
+ + self.graph.node_dist_mat[next_index][0] > self.graph.nodes[0].due_time:
return False
- # 不可以服务due time之外的旅客
- if self.vehicle_travel_time + dist > self.graph.nodes[next_index].due_time:
+ # Passengers outside the due time cannot be served
+ if self.vehicle_travel_time + dist_time > self.graph.nodes[next_index].due_time:
return False
return True
def cal_next_index_meet_constrains(self):
- """
- 找出所有从当前位置（ant.current_index）可达的customer
- :return:
+ """Find all customers reachable from the current location (ant.current_index)
+
+ Returns
+ -------
+ list
+ Neighbor nodes' indices that satisfy constraints
"""
next_index_meet_constrains = []
- for next_ind in self.index_to_visit:
- if self.check_condition(next_ind):
- next_index_meet_constrains.append(next_ind)
+ for next_index in self.index_to_visit:
+ if self.check_condition(next_index):
+ next_index_meet_constrains.append(next_index)
return next_index_meet_constrains
def cal_nearest_next_index(self, next_index_list):
"""
- 从待选的customers中选择，离当前位置（ant.current_index）最近的customer
+ Select from the available customers, the customer closest to the current
+ location (ant.current_index)
- :param next_index_list:
- :return:
+ Parameters
+ ----------
+ next_index_list : list
+ ???
+
+ Returns
+ -------
+ int
"""
- current_ind = self.current_index
+ current_index = self.current_index
- nearest_ind = next_index_list[0]
- min_dist = self.graph.node_dist_mat[current_ind][next_index_list[0]]
+ nearest_index = next_index_list[0]
+ min_dist = self.graph.node_dist_mat[current_index][nearest_index]
- for next_ind in next_index_list[1:]:
- dist = self.graph.node_dist_mat[current_ind][next_ind]
+ for next_index in next_index_list[1:]:
+ dist = self.graph.node_dist_mat[current_index][next_index]
if dist < min_dist:
min_dist = dist
- nearest_ind = next_ind
+ nearest_index = next_index
- return nearest_ind
+ return nearest_index
@staticmethod
def cal_total_travel_distance(graph: VrptwGraph, travel_path):
+ """
+ (Update to ignore depot-to-depot distances later)
+ """
distance = 0
- current_ind = travel_path[0]
- for next_ind in travel_path[1:]:
- distance += graph.node_dist_mat[current_ind][next_ind]
- current_ind = next_ind
+ current_index = travel_path[0]
+ for next_index in travel_path[1:]:
+ distance += graph.node_dist_mat[current_index][next_index]
+ current_index = next_index
return distance
def try_insert_on_path(self, node_id, stop_event: Event):
"""
- 尝试性地将node_id插入当前的travel_path中
- 插入的位置不能违反载重，时间，行驶距离的限制
- 如果有多个位置，则找出最优的位置
- :param node_id:
- :return:
+ Attempt to insert node_id into current travel_path. Inserted locations
+ cannot violate load, time, travel distance restrictions. If there are
+ multiple positions, find the best position.
+
+ Parameters
+ ----------
+
+ Returns
+ -------
+
+ Note
+ ----
+ Seems like at least one vehicle route (depot-to-depot substring) in
+ travel_path is required. This is OK since
"""
best_insert_index = None
best_distance = None
@@ -135,85 +185,92 @@ class Ant:
if self.graph.nodes[self.travel_path[insert_index]].is_depot:
continue
- # 找出insert_index的前面的最近的depot
- front_depot_index = insert_index
- while front_depot_index >= 0 and not self.graph.nodes[self.travel_path[front_depot_index]].is_depot:
- front_depot_index -= 1
- front_depot_index = max(front_depot_index, 0)
+ # Find the nearest depot before insert_index
+ last_depot_index = insert_index
+ while last_depot_index > 0 and not self.graph.nodes[self.travel_path[last_depot_index]].is_depot:
+ last_depot_index -= 1
- # check_ant从front_depot_index出发
- check_ant = Ant(self.graph, self.travel_path[front_depot_index])
+ # check_ant starts from last_depot_index
+ check_ant = Ant(self.graph, self.travel_path[last_depot_index])
- # 让check_ant 走过 path中下标从front_depot_index开始到insert_index-1的点
- for i in range(front_depot_index+1, insert_index):
+ # Let check_ant walk through the point in the path from
+ # last_depot_index to insert_index-1
+ for i in range(last_depot_index+1, insert_index):
+ # (only one depot, so no start point needs to be passed)
check_ant.move_to_next_index(self.travel_path[i])
- # 开始尝试性地对排序后的index_to_visit中的结点进行访问
+ # Begin to tentatively visit the nodes in the sorted index_to_visit
if check_ant.check_condition(node_id):
check_ant.move_to_next_index(node_id)
else:
continue
- # 如果可以到node_id，则要保证vehicle可以行驶回到depot
- for next_ind in self.travel_path[insert_index:]:
-
+ # If you can get to the node_id, make sure that the vehicle can drive back to the depot
+ for next_index in self.travel_path[insert_index:]:
if stop_event.is_set():
# print('[try_insert_on_path]: receive stop event')
return
- if check_ant.check_condition(next_ind):
- check_ant.move_to_next_index(next_ind)
+ if check_ant.check_condition(next_index):
+ check_ant.move_to_next_index(next_index)
- # 如果回到了depot
- if self.graph.nodes[next_ind].is_depot:
- temp_front_index = self.travel_path[insert_index-1]
- temp_back_index = self.travel_path[insert_index]
+ # If back to the depot, then it means the vehicle whose
+ # route would be modified is over *and valid*. So now,
+ # compute the new total_travel_distance if node_id where
+ # added just before travel_path[insert_index]
+ if self.graph.nodes[next_index].is_depot:
+ insert_node_id_prev = self.travel_path[insert_index-1]
+ insert_node_id = self.travel_path[insert_index]
- check_ant_distance = self.total_travel_distance - self.graph.node_dist_mat[temp_front_index][temp_back_index] + \
- self.graph.node_dist_mat[temp_front_index][node_id] + self.graph.node_dist_mat[node_id][temp_back_index]
+ check_ant_distance = self.total_travel_distance \
+ - self.graph.node_dist_mat[insert_node_id_prev][insert_node_id] \
+ + self.graph.node_dist_mat[insert_node_id_prev][node_id] \
+ + self.graph.node_dist_mat[node_id][insert_node_id]
if best_distance is None or check_ant_distance < best_distance:
best_distance = check_ant_distance
best_insert_index = insert_index
break
- # 如果不可以回到depot，则返回上一层
+ # If you can't go back to the depot, simmulated route was invalid
else:
break
return best_insert_index
- def insertion_procedure(self, stop_even: Event):
+ def insertion_procedure(self, stop_event: Event):
"""
- 为每个未访问的结点尝试性地找到一个合适的位置，插入到当前的travel_path
- 插入的位置不能违反载重，时间，行驶距离的限制
+ Try to find a suitable location for each unvisited node, insert into the
+ current travel_path and insert the location without violating load,
+ time, travel distance constraints
:return:
"""
if self.index_to_visit_empty():
return
success_to_insert = True
- # 直到未访问的结点中没有一个结点可以插入成功
+ # Until none of the unvisited nodes can be inserted successfully
while success_to_insert:
success_to_insert = False
- # 获取未访问的结点
+ # Get unvisited nodes
ind_to_visit = np.array(copy.deepcopy(self.index_to_visit))
- # 获取为访问客户点的demand，降序排序
+ # Sort ind_to_visit by customer demand in descending order
demand = np.zeros(len(ind_to_visit))
for i, ind in zip(range(len(ind_to_visit)), ind_to_visit):
demand[i] = self.graph.nodes[ind].demand
- arg_ind = np.argsort(demand)[::-1]
- ind_to_visit = ind_to_visit[arg_ind]
+ arg_index = np.argsort(demand)[::-1]
+ ind_to_visit = ind_to_visit[arg_index]
+ # Try to insert at least one from the ordered list
for node_id in ind_to_visit:
- if stop_even.is_set():
+ if stop_event.is_set():
# print('[insertion_procedure]: receive stop event')
return
- best_insert_index = self.try_insert_on_path(node_id, stop_even)
+ best_insert_index = self.try_insert_on_path(node_id, stop_event)
if best_insert_index is not None:
self.travel_path.insert(best_insert_index, node_id)
self.index_to_visit.remove(node_id)
@@ -229,26 +286,36 @@ class Ant:
@staticmethod
def local_search_once(graph: VrptwGraph, travel_path: list, travel_distance: float, i_start, stop_event: Event):
+ """
- # 找出path中所有的depot的位置
- depot_ind = []
+ Returns
+ -------
+ list
+ None, None, None
+ """
+
+ # Find the locations of all depots in the path
+ depot_index = []
for ind in range(len(travel_path)):
if graph.nodes[travel_path[ind]].is_depot:
- depot_ind.append(ind)
+ depot_index.append(ind)
- # 将self.travel_path分成多段，每段以depot开始，以depot结束，称为route
- for i in range(i_start, len(depot_ind)):
- for j in range(i + 1, len(depot_ind)):
+ # Divide self.travel_path into multiple segments, each segment starts
+ # with depot and ends with depot, called route
+ for i in range(i_start, len(depot_index)):
+ for j in range(i + 1, len(depot_index)):
if stop_event.is_set():
return None, None, None
- for start_a in range(depot_ind[i - 1] + 1, depot_ind[i]):
- for end_a in range(start_a, min(depot_ind[i], start_a + 6)):
- for start_b in range(depot_ind[j - 1] + 1, depot_ind[j]):
- for end_b in range(start_b, min(depot_ind[j], start_b + 6)):
+ for start_a in range(depot_index[i - 1] + 1, depot_index[i]):
+ for end_a in range(start_a, min(depot_index[i], start_a + 6)):
+ for start_b in range(depot_index[j - 1] + 1, depot_index[j]):
+ for end_b in range(start_b, min(depot_index[j], start_b + 6)):
if start_a == end_a and start_b == end_b:
continue
+ # Create new travel_path changing swaping routes
+ # a and b
new_path = []
new_path.extend(travel_path[:start_a])
new_path.extend(travel_path[start_b:end_b + 1])
@@ -256,13 +323,13 @@ class Ant:
new_path.extend(travel_path[start_a:end_a])
new_path.extend(travel_path[end_b + 1:])
- depot_before_start_a = depot_ind[i - 1]
+ depot_before_start_a = depot_index[i - 1]
- depot_before_start_b = depot_ind[j - 1] + (end_b - start_b) - (end_a - start_a) + 1
+ depot_before_start_b = depot_index[j - 1] + (end_b - start_b) - (end_a - start_a) + 1
if not graph.nodes[new_path[depot_before_start_b]].is_depot:
raise RuntimeError('error')
- # 判断发生改变的route a是否是feasible的
+ # Determine whether the changed route a is feasible
success_route_a = False
check_ant = Ant(graph, new_path[depot_before_start_a])
for ind in new_path[depot_before_start_a + 1:]:
@@ -277,7 +344,7 @@ class Ant:
check_ant.clear()
del check_ant
- # 判断发生改变的route b是否是feasible的
+ # Determine whether the changed route b is feasible
success_route_b = False
check_ant = Ant(graph, new_path[depot_before_start_b])
for ind in new_path[depot_before_start_b + 1:]:
@@ -296,10 +363,10 @@ class Ant:
if new_path_distance < travel_distance:
# print('success to search')
- # 删除路径中连在一起的depot中的一个
- for temp_ind in range(1, len(new_path)):
- if graph.nodes[new_path[temp_ind]].is_depot and graph.nodes[new_path[temp_ind - 1]].is_depot:
- new_path.pop(temp_ind)
+ # Delete one of the depots linked together in the path
+ for temp_index in range(1, len(new_path)):
+ if graph.nodes[new_path[temp_index]].is_depot and graph.nodes[new_path[temp_index - 1]].is_depot:
+ new_path.pop(temp_index)
break
return new_path, new_path_distance, i
else:
@@ -309,8 +376,7 @@ class Ant:
def local_search_procedure(self, stop_event: Event):
"""
- 对当前的已经访问完graph中所有节点的travel_path使用cross进行局部搜索
- :return:
+ Use cross to perform a local search on the current travel_path that has visited all nodes in the graph
"""
new_path = copy.deepcopy(self.travel_path)
new_path_distance = self.total_travel_distance
@@ -326,7 +392,7 @@ class Ant:
new_path = temp_path
new_path_distance = temp_distance
- # 设置i_start
+ # set i_start
i_start = (i_start + 1) % (new_path.count(0)-1)
i_start = max(i_start, 1)
else:
@@ -334,4 +400,4 @@ class Ant:
self.travel_path = new_path
self.total_travel_distance = new_path_distance
- print('[local_search_procedure]: local search finished') \ No newline at end of file
+ print('[local_search_procedure]: local search finished')
diff --git a/example1.py b/example1.py
index 165e7ff..c867f44 100644
--- a/example1.py
+++ b/example1.py
@@ -2,10 +2,11 @@ from vrptw_base import VrptwGraph
from multiple_ant_colony_system import MultipleAntColonySystem
def main():
- file_path = './solomon-100/c208.txt'
+ file_path = './solomon-100/c101.txt'
+ #file_path = './odiparpack/pedidosperu78.txt'
ants_num = 10
- beta = 2
- q0 = 0.1
+ beta = 2 # 5
+ q0 = 0.1 # 0.5 ?
show_figure = True
graph = VrptwGraph(file_path)
diff --git a/multiple_ant_colony_system.py b/multiple_ant_colony_system.py
index 751a441..45c896a 100644
--- a/multiple_ant_colony_system.py
+++ b/multiple_ant_colony_system.py
@@ -13,17 +13,30 @@ from multiprocessing import Queue as MPQueue
class MultipleAntColonySystem:
+ """
+ Attributes
+ ----------
+ graph : VrptwGraph
+ ants_num : int
+ max_load : int
+ beta : float
+ Heuristic information importance (relative to pheromones)
+ q0 : float
+ Probability of directly selecting the next point with highest
+ probability ??
+ """
def __init__(self, graph: VrptwGraph, ants_num=10, beta=1, q0=0.1, whether_or_not_to_show_figure=True):
super()
- # graph 结点的位置、服务时间信息
+ # The location and service time information of graph nodes
self.graph = graph
- # ants_num 蚂蚁数量
+ # ants_num number of ants
self.ants_num = ants_num
- # vehicle_capacity 表示每辆车的最大载重
+ # vehicle_capacity represents the maximum load per vehicle
self.max_load = graph.vehicle_capacity
- # beta 启发性信息重要性
+ # beta heuristic information importance
self.beta = beta
- # q0 表示直接选择概率最大的下一点的概率
+ # q0 represents the probability of directly selecting the next point
+ # with the highest probability
self.q0 = q0
# best path
self.best_path_distance = None
@@ -35,7 +48,7 @@ class MultipleAntColonySystem:
@staticmethod
def stochastic_accept(index_to_visit, transition_prob):
"""
- 轮盘赌
+ Roulette
:param index_to_visit: a list of N index (list or tuple)
:param transition_prob:
:return: selected index
@@ -55,41 +68,60 @@ class MultipleAntColonySystem:
return index_to_visit[ind]
@staticmethod
- def new_active_ant(ant: Ant, vehicle_num: int, local_search: bool, IN: np.numarray, q0: float, beta: int, stop_event: Event):
+ def new_active_ant(ant: Ant, vehicle_num: int, local_search: bool,
+ IN: np.numarray, q0: float, beta: int, stop_event: Event):
"""
- 按照指定的vehicle_num在地图上进行探索，所使用的vehicle num不能多于指定的数量，acs_time和acs_vehicle都会使用到这个方法
- 对于acs_time来说，需要访问完所有的结点（路径是可行的），尽量找到travel distance更短的路径
- 对于acs_vehicle来说，所使用的vehicle num会比当前所找到的best path所使用的车辆数少一辆，要使用更少的车辆，尽量去访问结点，如果访问完了所有的结点（路径是可行的），就将通知macs
- :param ant:
- :param vehicle_num:
- :param local_search:
- :param IN:
- :param q0:
- :param beta:
- :param stop_event:
- :return:
+ Explore the map according to the specified vehicle_num. The vehicle num
+ used cannot be more than the specified number. This method is used by
+ both acs_time and acs_vehicle
+
+ For acs_time, it is necessary to visit all nodes (the path is
+ feasible), and try to find a path with a shorter travel distance
+
+ For acs_vehicle, the vehicle num used will be one less vehicle than the
+ number of vehicles used by the currently found best path. To use fewer
+ vehicles, try to visit the nodes. If all nodes are visited (the path is
+ feasible), it will notify macs
+
+ Parameters
+ ----------
+ ant : Ant
+ vehicle_num : int
+ local_search : bool
+ IN : numpy.numarray
+ ??? (variable compartida entre acs_vehicle y acs_time a traves de
+ macs. Pero que info tiene???
+ q0 : float
+ beta : int
+ stop_event : threading.Event
+
+ Returns
+ -------
"""
# print('[new_active_ant]: start, start_index %d' % ant.travel_path[0])
- # 在new_active_ant中，最多可以使用vehicle_num个车，即最多可以包含vehicle_num+1个depot结点，由于出发结点用掉了一个，所以只剩下vehicle个depot
+ # In new_active_ant, up to vehicle_num vehicles can be used, that is, it
+ # can contain up to vehicle_num+1 depot nodes. Since one departure node
+ # is used up, only vehicle depots are left.
unused_depot_count = vehicle_num
- # 如果还有未访问的结点，并且还可以回到depot中
+ # If there are still unvisited nodes, and you can also return to the depot
while not ant.index_to_visit_empty() and unused_depot_count > 0:
if stop_event.is_set():
# print('[new_active_ant]: receive stop event')
return
- # 计算所有满足载重等限制的下一个结点
+ # Calculate all next nodes that satisfy constraints such as load
next_index_meet_constrains = ant.cal_next_index_meet_constrains()
- # 如果没有满足限制的下一个结点，则回到depot中
+ # If there is no next node that meets the limit, go back to the depot
if len(next_index_meet_constrains) == 0:
ant.move_to_next_index(0)
unused_depot_count -= 1
continue
- # 开始计算满足限制的下一个结点，选择各个结点的概率
+ # Start calculating the next node that satisfies the constraints,
+ # and select the probability of each node
length = len(next_index_meet_constrains)
ready_time = np.zeros(length)
due_time = np.zeros(length)
@@ -98,38 +130,39 @@ class MultipleAntColonySystem:
ready_time[i] = ant.graph.nodes[next_index_meet_constrains[i]].ready_time
due_time[i] = ant.graph.nodes[next_index_meet_constrains[i]].due_time
- delivery_time = np.maximum(ant.vehicle_travel_time + ant.graph.node_dist_mat[ant.current_index][next_index_meet_constrains], ready_time)
+ delivery_time = np.maximum(ant.vehicle_travel_time \
+ + ant.graph.node_dist_mat[ant.current_index][next_index_meet_constrains], ready_time)
delta_time = delivery_time - ant.vehicle_travel_time
distance = delta_time * (due_time - ant.vehicle_travel_time)
- distance = np.maximum(1.0, distance-IN[next_index_meet_constrains])
+ distance = np.maximum(1.0, distance - IN[next_index_meet_constrains])
closeness = 1/distance
transition_prob = ant.graph.pheromone_mat[ant.current_index][next_index_meet_constrains] * \
np.power(closeness, beta)
transition_prob = transition_prob / np.sum(transition_prob)
- # 按照概率直接选择closeness最大的结点
+ # Directly select the node with the largest closeness according to the probability
if np.random.rand() < q0:
max_prob_index = np.argmax(transition_prob)
next_index = next_index_meet_constrains[max_prob_index]
else:
- # 使用轮盘赌算法
+ # Use the roulette algorithm
next_index = MultipleAntColonySystem.stochastic_accept(next_index_meet_constrains, transition_prob)
- # 更新信息素矩阵
+ # update pheromone matrix
ant.graph.local_update_pheromone(ant.current_index, next_index)
ant.move_to_next_index(next_index)
- # 如果走完所有的点了，需要回到depot
+ # If you finish all the points, you need to go back to the depot
if ant.index_to_visit_empty():
ant.graph.local_update_pheromone(ant.current_index, 0)
ant.move_to_next_index(0)
- # 对未访问的点进行插入，保证path是可行的
+ # Insert unvisited points to ensure that the path is feasible
ant.insertion_procedure(stop_event)
- # ant.index_to_visit_empty()==True就是feasible的意思
+ # ant.index_to_visit_empty()==True means Feasible
if local_search is True and ant.index_to_visit_empty():
ant.local_search_procedure(stop_event)
@@ -137,7 +170,8 @@ class MultipleAntColonySystem:
def acs_time(new_graph: VrptwGraph, vehicle_num: int, ants_num: int, q0: float, beta: int,
global_path_queue: Queue, path_found_queue: Queue, stop_event: Event):
"""
- 对于acs_time来说，需要访问完所有的结点（路径是可行的），尽量找到travel distance更短的路径
+ For acs_time, it is necessary to visit all nodes (the path is feasible),
+ and try to find a path with a shorter travel distance
:param new_graph:
:param vehicle_num:
:param ants_num:
@@ -216,16 +250,17 @@ class MultipleAntColonySystem:
def acs_vehicle(new_graph: VrptwGraph, vehicle_num: int, ants_num: int, q0: float, beta: int,
global_path_queue: Queue, path_found_queue: Queue, stop_event: Event):
"""
- 对于acs_vehicle来说，所使用的vehicle num会比当前所找到的best path所使用的车辆数少一辆，要使用更少的车辆，尽量去访问结点，如果访问完了所有的结点（路径是可行的），就将通知macs
- :param new_graph:
- :param vehicle_num:
- :param ants_num:
- :param q0:
- :param beta:
- :param global_path_queue:
- :param path_found_queue:
- :param stop_event:
- :return:
+ For acs_vehicle, the vehicle num used will be one less vehicle than the
+ number of vehicles used by the currently found best path. To use fewer
+ vehicles, try to visit the nodes. If all nodes are visited (the path is
+ feasible), it will notify macs
+
+ Parameters
+ ----------
+ new_graph : VrptwGraph
+ global_path_queue : queue.Queue
+ path_found_queue : queue.Queue
+ stop_event : threading.Event
"""
# vehicle_num设置为比当前的best_path少一个
print('[acs_vehicle]: start, vehicle_num %d' % vehicle_num)
@@ -253,13 +288,14 @@ class MultipleAntColonySystem:
for k in range(ants_num):
ant = Ant(new_graph, 0)
- thread = ants_pool.submit(MultipleAntColonySystem.new_active_ant, ant, vehicle_num, False, IN, q0,
+ thread = ants_pool.submit(MultipleAntColonySystem.new_active_ant,
+ ant, vehicle_num, False, IN, q0,
beta, stop_event)
ants_thread.append(thread)
ants.append(ant)
- # 这里可以使用result方法，等待线程跑完
+ # Here you can use the result method to wait for the thread to finish running
for thread in ants_thread:
thread.result()
@@ -271,20 +307,21 @@ class MultipleAntColonySystem:
IN[ant.index_to_visit] = IN[ant.index_to_visit]+1
- # 蚂蚁找出来的路径与current_path进行比较，是否能使用vehicle_num辆车访问到更多的结点
+ # Compare the path found by the ants with the current_path,
+ # whether it can use vehicle_num vehicles to visit more nodes
if len(ant.index_to_visit) < len(current_index_to_visit):
current_path = copy.deepcopy(ant.travel_path)
current_index_to_visit = copy.deepcopy(ant.index_to_visit)
current_path_distance = ant.total_travel_distance
- # 并且将IN设置为0
+ # and set IN to 0
IN = np.zeros(new_graph.node_num)
- # 如果这一条路径是feasible的话，就要发到macs_vrptw中
+ # If this path is feasible, it should be sent to macs_vrptw
if ant.index_to_visit_empty():
print('[acs_vehicle]: found a feasible path, send path info to macs')
path_found_queue.put(PathMessage(ant.travel_path, ant.total_travel_distance))
- # 更新new_graph中的信息素，global
+ # Update pheromone in new_graph, global
new_graph.global_update_pheromone(current_path, current_path_distance)
if not global_path_queue.empty():
@@ -304,14 +341,13 @@ class MultipleAntColonySystem:
def run_multiple_ant_colony_system(self, file_to_write_path=None):
"""
- 开启另外的线程来跑multiple_ant_colony_system， 使用主线程来绘图
- :return:
+ Start another thread to run multiple_ant_colony_system, use the main thread for drawing
"""
path_queue_for_figure = MPQueue()
multiple_ant_colony_system_thread = Process(target=self._multiple_ant_colony_system, args=(path_queue_for_figure, file_to_write_path, ))
multiple_ant_colony_system_thread.start()
- # 是否要展示figure
+ # Whether to show figure
if self.whether_or_not_to_show_figure:
figure = VrptwAcoFigure(self.graph.nodes, path_queue_for_figure)
figure.run()
@@ -319,7 +355,7 @@ class MultipleAntColonySystem:
def _multiple_ant_colony_system(self, path_queue_for_figure: MPQueue, file_to_write_path=None):
"""
- 调用acs_time 和 acs_vehicle进行路径的探索
+ Call acs_time and acs_vehicle for path exploration
:param path_queue_for_figure:
:return:
"""
@@ -330,14 +366,18 @@ class MultipleAntColonySystem:
start_time_total = time.time()
- # 在这里需要两个队列，time_what_to_do、vehicle_what_to_do， 用来告诉acs_time、acs_vehicle这两个线程，当前的best path是什么，或者让他们停止计算
+ # Two queues are needed here, time_what_to_do, vehicle_what_to_do, to
+ # tell the two threads acs_time and acs_vehicle what the current best
+ # path is, or let them stop computing
global_path_to_acs_time = Queue()
global_path_to_acs_vehicle = Queue()
- # 另外的一个队列， path_found_queue就是接收acs_time 和acs_vehicle计算出来的比best path还要好的feasible path
+ # Another queue, path_found_queue, is to receive acs_time and
+ # acs_vehicle calculated by acs_vehicle that is even better than the
+ # best path. Feasible path
path_found_queue = Queue()
- # 使用近邻点算法初始化
+ # Initialize using the nearest neighbor algorithm
self.best_path, self.best_path_distance, self.best_vehicle_num = self.graph.nearest_neighbor_heuristic()
path_queue_for_figure.put(PathMessage(self.best_path, self.best_path_distance))
@@ -345,25 +385,28 @@ class MultipleAntColonySystem:
print('[multiple_ant_colony_system]: new iteration')
start_time_found_improved_solution = time.time()
- # 当前best path的信息，放在queue中以通知acs_time和acs_vehicle当前的best_path是什么
+ # The information of the current best path is placed in the queue to
+ # inform acs_time and acs_vehicle what the current best_path is
global_path_to_acs_vehicle.put(PathMessage(self.best_path, self.best_path_distance))
global_path_to_acs_time.put(PathMessage(self.best_path, self.best_path_distance))
stop_event = Event()
- # acs_vehicle，尝试以self.best_vehicle_num-1辆车去探索，访问更多的结点
+ # acs_vehicle, try to explore with self.best_vehicle_num-1 vehicles, visit more nodes
graph_for_acs_vehicle = self.graph.copy(self.graph.init_pheromone_val)
acs_vehicle_thread = Thread(target=MultipleAntColonySystem.acs_vehicle,
args=(graph_for_acs_vehicle, self.best_vehicle_num-1, self.ants_num, self.q0,
self.beta, global_path_to_acs_vehicle, path_found_queue, stop_event))
- # acs_time 尝试以self.best_vehicle_num辆车去探索，找到更短的路径
+ # acs_time try to explore with self.best_vehicle_num vehicles to find a shorter path
graph_for_acs_time = self.graph.copy(self.graph.init_pheromone_val)
acs_time_thread = Thread(target=MultipleAntColonySystem.acs_time,
args=(graph_for_acs_time, self.best_vehicle_num, self.ants_num, self.q0, self.beta,
global_path_to_acs_time, path_found_queue, stop_event))
- # 启动acs_vehicle_thread和acs_time_thread，当他们找到feasible、且是比best path好的路径时，就会发送到macs中来
+ # Start acs_vehicle_thread and acs_time_thread, when they find a
+ # feasible and better path than the best path, they will be sent to
+ # macs
print('[macs]: start acs_vehicle and acs_time')
acs_vehicle_thread.start()
acs_time_thread.start()
@@ -372,7 +415,7 @@ class MultipleAntColonySystem:
while acs_vehicle_thread.is_alive() and acs_time_thread.is_alive():
- # 如果在指定时间内没有搜索到更好的结果，则退出程序
+ # Exit the program if no better results are found within the specified time
given_time = 10
if time.time() - start_time_found_improved_solution > 60 * given_time:
stop_event.set()
@@ -384,7 +427,7 @@ class MultipleAntColonySystem:
self.print_and_write_in_file(file_to_write, 'best path distance is %f, best vehicle_num is %d' % (self.best_path_distance, self.best_vehicle_num))
self.print_and_write_in_file(file_to_write, '*' * 50)
- # 传入None作为结束标志
+ # Pass in None as the end flag
if self.whether_or_not_to_show_figure:
path_queue_for_figure.put(PathMessage(None, None))
@@ -408,10 +451,11 @@ class MultipleAntColonySystem:
if vehicle_num < found_path_used_vehicle_num:
found_path, found_path_distance, found_path_used_vehicle_num = path, distance, vehicle_num
- # 如果找到的路径（which is feasible）的距离更短，则更新当前的最佳path的信息
+ # If the distance of the found path (which is feasible) is
+ # shorter, update the current best path information
if found_path_distance < self.best_path_distance:
- # 搜索到更好的结果，更新start_time
+ # Better search results, update start_time
start_time_found_improved_solution = time.time()
self.print_and_write_in_file(file_to_write, '*' * 50)
@@ -425,19 +469,21 @@ class MultipleAntColonySystem:
self.best_vehicle_num = found_path_used_vehicle_num
self.best_path_distance = found_path_distance
- # 如果需要绘制图形，则要找到的best path发送给绘图程序
+ # If you need to draw graphics, send the best path to be found to the drawing program
if self.whether_or_not_to_show_figure:
path_queue_for_figure.put(PathMessage(self.best_path, self.best_path_distance))
- # 通知acs_vehicle和acs_time两个线程，当前找到的best_path和best_path_distance
+ # Notify the two threads of acs_vehicle and acs_time, the
+ # currently found best_path and best_path_distance
global_path_to_acs_vehicle.put(PathMessage(self.best_path, self.best_path_distance))
global_path_to_acs_time.put(PathMessage(self.best_path, self.best_path_distance))
- # 如果，这两个线程找到的路径用的车辆更少了，就停止这两个线程，开始下一轮迭代
- # 向acs_time和acs_vehicle中发送停止信息
+ # If the paths found by the two threads use fewer vehicles, stop
+ # the two threads and start the next iteration
+ # Send stop messages to acs_time and acs_vehicle
if found_path_used_vehicle_num < best_vehicle_num:
- # 搜索到更好的结果，更新start_time
+ # Better search results, update start_time
start_time_found_improved_solution = time.time()
self.print_and_write_in_file(file_to_write, '*' * 50)
self.print_and_write_in_file(file_to_write, '[macs]: vehicle num of found path (%d) better than best path\'s (%d), found path distance is %f'
@@ -454,9 +500,10 @@ class MultipleAntColonySystem:
if self.whether_or_not_to_show_figure:
path_queue_for_figure.put(PathMessage(self.best_path, self.best_path_distance))
- # 停止acs_time 和 acs_vehicle 两个线程
+ # Stop the acs_time and acs_vehicle threads
print('[macs]: send stop info to acs_time and acs_vehicle')
- # 通知acs_vehicle和acs_time两个线程，当前找到的best_path和best_path_distance
+ # Notify the two threads of acs_vehicle and acs_time, the
+ # currently found best_path and best_path_distance
stop_event.set()
@staticmethod
diff --git a/odiparpack/pedidosperu195.txt b/odiparpack/pedidosperu195.txt
new file mode 100644
index 0000000..651ec69
--- /dev/null
+++ b/odiparpack/pedidosperu195.txt
@@ -0,0 +1,205 @@
+Pedidos Peru 195 provincias
+
+VEHICLE
+NUMBER CAPACITY
+ 40 500
+
+CUSTOMER
+CUST NO. XCOORD. YCOORD. DEMAND READY TIME DUE DATE SERVICE TIME
+
+0 -166.922 712.41 96 0 5433 60
+1 -85.354 682.914 22 0 5615 60
+2 -93.619 646.767 88 0 5592 60
+3 -92.734 828.799 85 0 5355 60
+4 -102.462 656.816 69 0 5292 60
+5 -50.227 628.253 3 0 5455 60
+6 -156.975 699.583 66 0 5734 60
+7 -64.518 251.936 81 0 5391 60
+8 1.52 327.456 71 0 5701 60
+9 -37.311 320.667 31 0 5343 60
+10 -14.044 210.587 76 0 5627 60
+11 -68.474 307.36 3 0 5688 60
+12 -33.207 328.199 57 0 5467 60
+13 -141.768 285.753 76 0 5272 60
+14 -96.467 386.458 86 0 5737 60
+15 -55.416 279.76 50 0 5601 60
+16 -15.619 300.062 37 0 5556 60
+17 -124.736 219.856 9 0 5328 60
+18 -86.684 333.288 9 0 5277 60
+19 -36.36 353.708 63 0 5388 60
+20 -40.73 182.633 20 0 5269 60
+21 -108.806 406.196 52 0 5663 60
+22 -47.787 358.647 25 0 5499 60
+23 -47.33 258.399 34 0 5612 60
+24 -173.806 330.402 6 0 5343 60
+25 -66.798 388.218 35 0 5468 60
+26 -79.439 323.136 64 0 5384 60
+27 461.639 -176.959 85 0 5731 60
+28 404.815 -179.078 41 0 5353 60
+29 461.76 -257.843 66 0 5493 60
+30 421.009 -250.054 34 0 5378 60
+31 367.799 -163.691 6 0 5405 60
+32 539.968 -211.301 4 0 5411 60
+33 480.68 -229.002 37 0 5525 60
+34 610.847 -484.02 17 0 5736 60
+35 480.238 -509.161 17 0 5559 60
+36 407.539 -414.337 78 0 5602 60
+37 504.648 -448.192 60 0 5647 60
+38 603.623 -399.281 25 0 5657 60
+39 486.926 -421.798 71 0 5641 60
+40 557.648 -554.124 32 0 5459 60
+41 460.607 -352.153 72 0 5734 60
+42 321.0 -176.067 15 0 5259 60
+43 311.871 -123.91 21 0 5334 60
+44 299.85 -208.375 96 0 5640 60
+45 309.412 -99.408 91 0 5535 60
+46 339.076 -107.497 37 0 5678 60
+47 323.166 -294.458 91 0 5521 60
+48 361.339 -330.367 27 0 5388 60
+49 409.879 -359.488 12 0 5471 60
+50 354.896 -218.536 60 0 5590 60
+51 329.603 -189.758 78 0 5738 60
+52 342.105 -178.702 46 0 5424 60
+53 -112.919 491.724 47 0 5421 60
+54 -165.35 543.615 21 0 5664 60
+55 -123.99 576.033 26 0 5683 60
+56 -180.108 609.831 57 0 5547 60
+57 -197.274 520.369 49 0 5433 60
+58 -198.796 630.316 78 0 5374 60
+59 -165.53 596.714 46 0 5480 60
+60 -197.63 704.655 10 0 5287 60
+61 -219.552 767.208 51 0 5523 60
+62 -126.759 523.712 69 0 5645 60
+63 -202.479 561.031 85 0 5291 60
+64 -199.359 547.922 18 0 5710 60
+65 -212.815 602.652 25 0 5330 60
+66 -12.252 -1.604 98 0 5604 60
+67 594.559 -208.3 72 0 5590 60
+68 542.821 -158.528 80 0 5598 60
+69 564.253 -141.866 63 0 5270 60
+70 622.521 -241.407 61 0 5492 60
+71 645.375 -247.639 60 0 5584 60
+72 550.239 -267.34 56 0 5544 60
+73 561.727 -163.544 95 0 5309 60
+74 624.65 -305.475 63 0 5723 60
+75 482.321 -90.891 48 0 5714 60
+76 576.329 -190.744 54 0 5597 60
+77 604.208 -141.427 15 0 5468 60
+78 600.999 -182.575 89 0 5575 60
+79 546.468 -140.107 53 0 5274 60
+80 273.463 -88.779 75 0 5622 60
+81 257.077 -104.204 96 0 5708 60
+82 190.293 -137.595 43 0 5394 60
+83 293.881 -77.096 76 0 5450 60
+84 228.772 -82.426 90 0 5719 60
+85 186.521 -173.297 65 0 5512 60
+86 240.412 -39.238 81 0 5634 60
+87 91.851 213.126 86 0 5533 60
+88 25.485 246.562 43 0 5598 60
+89 8.66 334.48 86 0 5303 60
+90 23.898 277.533 75 0 5421 60
+91 87.939 235.33 52 0 5607 60
+92 44.354 218.816 14 0 5683 60
+93 114.554 305.512 22 0 5455 60
+94 -13.216 382.68 47 0 5410 60
+95 115.22 238.896 65 0 5719 60
+96 229.568 296.508 65 0 5523 60
+97 46.936 243.203 99 0 5563 60
+98 99.841 -152.523 77 0 5593 60
+99 144.697 -224.393 77 0 5559 60
+100 232.781 -309.304 45 0 5678 60
+101 205.195 -276.634 39 0 5384 60
+102 91.99 -185.026 82 0 5603 60
+103 189.286 110.076 18 0 5272 60
+104 193.799 -1.756 71 0 5314 60
+105 190.981 14.173 84 0 5393 60
+106 202.424 -2.451 21 0 5451 60
+107 170.125 30.101 92 0 5532 60
+108 115.356 98.394 62 0 5658 60
+109 266.144 88.068 16 0 5401 60
+110 149.304 69.608 44 0 5289 60
+111 125.701 58.858 12 0 5642 60
+112 -230.954 481.711 10 0 5367 60
+113 -74.739 543.971 77 0 5540 60
+114 -266.772 535.807 90 0 5509 60
+115 -198.92 507.768 77 0 5726 60
+116 -161.915 445.157 3 0 5252 60
+117 -170.707 460.727 23 0 5285 60
+118 -275.072 513.038 37 0 5407 60
+119 -29.558 419.203 38 0 5322 60
+120 -113.211 470.395 18 0 5647 60
+121 -127.071 433.722 58 0 5286 60
+122 -222.189 437.458 0 0 5544 60
+123 -191.447 403.82 20 0 5702 60
+124 -312.254 586.488 9 0 5268 60
+125 -306.625 601.197 0 0 5551 60
+126 -319.765 593.982 46 0 5639 60
+127 -81.206 143.652 10 0 5493 60
+128 71.506 -114.734 28 0 5436 60
+129 4.169 174.936 28 0 5731 60
+130 45.118 64.371 94 0 5399 60
+131 -19.647 61.214 83 0 5615 60
+132 71.658 22.367 37 0 5463 60
+133 -64.483 104.23 65 0 5366 60
+134 0.0 0.0 71 0 5362 60
+135 28.625 153.206 10 0 5386 60
+136 123.627 -46.014 19 0 5283 60
+137 102.977 683.921 32 0 5514 60
+138 52.927 802.199 24 0 5590 60
+139 384.183 838.332 21 0 5353 60
+140 724.291 905.119 40 0 5699 60
+141 420.998 922.537 39 0 5694 60
+142 485.059 1067.329 45 0 5560 60
+143 352.945 776.388 41 0 5279 60
+144 224.773 522.105 6 0 5434 60
+145 630.652 -87.873 52 0 5479 60
+146 828.745 122.423 4 0 5656 60
+147 873.352 -60.968 76 0 5369 60
+148 673.89 -514.611 54 0 5578 60
+149 632.164 -622.681 53 0 5540 60
+150 677.822 -572.419 81 0 5449 60
+151 57.14 172.862 58 0 5492 60
+152 180.789 163.639 42 0 5386 60
+153 86.1 151.476 73 0 5742 60
+154 -298.529 823.476 46 0 5563 60
+155 -269.106 756.895 90 0 5586 60
+156 -348.08 772.735 45 0 5631 60
+157 -454.028 774.005 46 0 5395 60
+158 -399.863 761.547 12 0 5658 60
+159 -421.627 721.474 41 0 5250 60
+160 -406.627 795.697 21 0 5351 60
+161 -471.614 830.207 48 0 5571 60
+162 760.034 -318.307 19 0 5593 60
+163 733.791 -224.895 6 0 5607 60
+164 841.886 -463.394 32 0 5366 60
+165 821.941 -449.333 9 0 5480 60
+166 808.282 -351.175 78 0 5448 60
+167 740.886 -369.029 6 0 5484 60
+168 716.14 -315.339 8 0 5442 60
+169 837.365 -368.588 78 0 5321 60
+170 778.641 -421.951 30 0 5609 60
+171 796.371 -318.934 72 0 5442 60
+172 766.684 -383.324 57 0 5685 60
+173 841.065 -253.202 2 0 5491 60
+174 882.657 -466.835 85 0 5504 60
+175 49.57 553.645 32 0 5358 60
+176 37.32 604.011 21 0 5257 60
+177 28.76 568.151 6 0 5486 60
+178 57.189 625.369 40 0 5537 60
+179 33.809 541.02 17 0 5559 60
+180 6.208 668.421 1 0 5384 60
+181 77.858 569.905 93 0 5344 60
+182 -15.264 665.314 51 0 5401 60
+183 74.576 618.044 94 0 5468 60
+184 57.842 428.909 19 0 5561 60
+185 753.912 -580.69 92 0 5721 60
+186 696.981 -619.124 66 0 5642 60
+187 753.868 -663.587 85 0 5502 60
+188 778.184 -603.655 58 0 5334 60
+189 -405.393 930.174 61 0 5366 60
+190 -381.296 942.387 4 0 5571 60
+191 -360.775 950.187 70 0 5564 60
+192 364.237 146.354 51 0 5295 60
+193 277.793 407.271 29 0 5464 60
+194 169.224 334.59 97 0 5497 60
+195 702.797 252.808 40 0 5367 60
diff --git a/sols/c208_v3_d811 b/sols/c208_v3_d811
index 0f8eac6..a3d7b6c 100644
--- a/sols/c208_v3_d811
+++ b/sols/c208_v3_d811
@@ -4,10 +4,23 @@ solmon c208
time is up: cannot find a better solution in given time(10 minutes)
it takes 607.824 second from multiple_ant_colony_system running
the best path have found is:
-[0, 93, 5, 75, 2, 20, 22, 24, 30, 29, 6, 32, 33, 31, 35, 37, 38, 39, 36, 34, 28, 26, 23, 18, 19, 16, 14, 12, 15, 17, 13, 25, 9, 11, 10, 21, 0, 67, 63, 61, 62, 72, 74, 69, 66, 64, 68, 65, 55, 49, 54, 53, 56, 59, 58, 60, 57, 40, 44, 46, 45, 51, 50, 52, 47, 42, 41, 43, 48, 8, 90, 0, 27, 1, 99, 100, 97, 92, 94, 95, 98, 7, 3, 4, 89, 88, 91, 86, 84, 83, 82, 76, 71, 85, 73, 70, 79, 80, 78, 77, 87, 96, 81, 0]
+[0, 93, 5, 75, 2, 20, 22, 24, 30, 29, 6, 32, 33, 31, 35, 37, 38, 39, 36, 34, 28,
+26, 23, 18, 19, 16, 14, 12, 15, 17, 13, 25, 9, 11, 10, 21, 0, 67, 63, 61, 62,
+72, 74, 69, 66, 64, 68, 65, 55, 49, 54, 53, 56, 59, 58, 60, 57, 40, 44, 46, 45,
+51, 50, 52, 47, 42, 41, 43, 48, 8, 90, 0, 27, 1, 99, 100, 97, 92, 94, 95, 98, 7,
+
+3, 4, 89, 88, 91, 86, 84, 83, 82, 76, 71, 85, 73, 70, 79, 80, 78, 77, 87, 96,
+81, 0]
best path distance is 810.973266, best vehicle_num is 3
**************************************************
Optimum C208.100 v=3 d=585.8 method=KLM
+node_id 80
+travel_path[insert_index] 57
+travel_path[next_index] 0
+temp_front_index 60
+temp_back_index 0
+travel_path = ..., 60, 57, ...
+check_ant_distance = ..., 60, 80, 57, ...
diff --git a/sols/pedidosperu78.txt b/sols/pedidosperu78.txt
new file mode 100644
index 0000000..cecaafb
--- /dev/null
+++ b/sols/pedidosperu78.txt
@@ -0,0 +1,7 @@
+**************************************************
+time is up: cannot find a better solution in given time(10 minutes)
+it takes 600.063 second from multiple_ant_colony_system running
+the best path have found is:
+[0, 6, 60, 61, 155, 154, 156, 158, 160, 157, 161, 159, 125, 124, 112, 122, 116, 180, 0, 4, 2, 1, 5, 182, 176, 178, 183, 181, 177, 144, 11, 190, 0, 58, 56, 59, 55, 62, 53, 120, 121, 21, 25, 18, 32, 0, 65, 63, 64, 57, 115, 54, 117, 123, 24, 13, 17, 7, 127, 0, 3, 138, 137, 175, 179, 113, 119, 94, 19, 22, 12, 173, 0, 126, 114, 118, 14, 26, 9, 16, 8, 23, 146, 0, 191, 189, 184, 89, 90, 88, 97, 92, 129, 0, 15, 10, 20, 135, 151, 153, 108, 111, 110, 107, 0, 93, 194, 96, 193, 95, 91, 87, 152, 103, 109, 31, 0, 143, 139, 141, 142, 140, 195, 145, 77, 69, 79, 68, 163, 0, 133, 131, 66, 134, 132, 130, 136, 128, 0, 192, 105, 104, 106, 86, 84, 81, 167, 0, 98, 102, 99, 85, 82, 80, 83, 0, 45, 43, 46, 42, 51, 52, 50, 44, 28, 49, 0, 75, 27, 33, 29, 30, 48, 47, 100, 101, 35, 168, 0, 73, 76, 67, 78, 70, 71, 74, 0, 72, 41, 39, 37, 36, 38, 34, 148, 186, 0, 147, 171, 166, 169, 172, 170, 165, 164, 188, 0, 162, 174, 185, 150, 149, 40, 187, 0]
+best path distance is 50696.719561, best vehicle_num is 19
+**************************************************
diff --git a/vrptw_base.py b/vrptw_base.py
index e7e55bd..b92db7b 100644
--- a/vrptw_base.py
+++ b/vrptw_base.py
@@ -107,16 +107,16 @@ class VrptwGraph:
self.rho * self.init_pheromone_val
def global_update_pheromone(self, best_path, best_path_distance):
- """
- 更新信息素矩阵
- :return:
+ """Update pheromone trail on best path (T+)
+
+ Ant Colony System offline pheromone trail update
"""
self.pheromone_mat = (1-self.rho) * self.pheromone_mat
- current_ind = best_path[0]
- for next_ind in best_path[1:]:
- self.pheromone_mat[current_ind][next_ind] += self.rho/best_path_distance
- current_ind = next_ind
+ 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
@@ -212,6 +212,7 @@ class VrptwGraph:
class PathMessage:
+ """Deep copy of travel_path?"""
def __init__(self, path, distance):
if path is not None:
self.path = copy.deepcopy(path)
generated by cgit v1.2.3 (git 2.25.1) at 2025-10-28 13:37:49 +0000