蚁群算法解决CVRP
程序员文章站
2022-05-20 23:36:34
...
蚁群算法解决CVRP
问题
通过实际案例描述,根据配送点和业务需求量,进行最优路线的计算。由物流中心点出发,配送多个客户点后再回到起点,根据车辆数量,承载限制,不同车辆服务成本、运行里程限制等条件选择最优运输路径(总里程最短),使成本最小化,配送订单最大化,满载率最大化(如由一个配送中心向各个销售点配送货物,通过算法确定配送中心每辆车的配送方案,包括配送至哪个客户,配送量,下一个配送目的地)。
问题数据及说明
某物流中心有5台配送车辆,车辆的最大载重均为8T,一次配送的最大行驶距离都为50KM,需要向20个客户送货,物流中心和20个客户的坐标及其客户的需求量随机产生,其中,物流中心的坐标为(14.2KM,13.1km),要求合理安排车辆的配送路线和载重量,使配送总里程最短
客户点 | 横坐标x(km) | 纵坐标y(km) | 需求量q(t) |
---|---|---|---|
1 | 12.8 | 8.5 | 0.1 |
2 | 18.4 | 3.4 | 0.4 |
3 | 15.4 | 16.6 | 1.2 |
4 | 18.9 | 15.2 | 1.5 |
5 | 15.5 | 11.6 | 0.8 |
6 | 3.9 | 10.6 | 1.3 |
7 | 10.6 | 7.6 | 1.7 |
8 | 8.6 | 8.4 | 0.6 |
9 | 12.5 | 2.1 | 1.2 |
10 | 13.8 | 5.2 | 0.4 |
11 | 6.7 | 16.9 | 0.9 |
12 | 14.8 | 2.6 | 1.3 |
13 | 1.8 | 8.7 | 1.3 |
14 | 17.1 | 11 | 1.9 |
15 | 7.4 | 1 | 1.7 |
16 | 0.2 | 2.8 | 1.1 |
17 | 11.9 | 19.8 | 1.5 |
18 | 13.2 | 15.1 | 1.6 |
19 | 6.4 | 5.6 | 1.7 |
20 | 9.6 | 14.8 | 1.5 |
说明:各客户相互之间和物流中心与客户之间的距离均采用直线距离
python代码(辣鸡代码仅供参考)
import random
import copy
import sys
'''
ALPHA:信息启发因子,值越大,则蚂蚁选择之前走过的路径可能性就越大
,值越小,则蚁群搜索范围就会减少,容易陷入局部最优
BETA:Beta值越大,蚁群越就容易选择局部较短路径,这时算法收敛速度会
加快,但是随机性不高,容易得到局部的相对最优
RH0:挥发率
Q : 每条路径上释放的信息素Q / 路径长度
'''
(ALPHA, BETA, RHO, Q) = (0.7, 2.5, 0.20, 100.0)
# 城市数,蚁群
(city_num, ant_num) = (21, 21)
distance_x = [14.2,12.8, 18.4, 15.4,18.9,15.5,3.9,10.6,8.6,12.5,13.8,6.7,14.8,1.8,17.1,7.4,0.2,11.9,13.2,6.4,9.6]
distance_y = [13.1,8.5, 3.4, 16.6, 15.2, 11.6, 10.6, 7.6, 8.4, 2.1, 5.2, 16.9, 2.6, 8.7, 11, 1, 2.8, 19.8, 15.1, 5.6, 14.8]
need = [0,0.1,0.4,1.2,1.5,0.8,1.3,1.7,0.6,1.2,0.4,0.9,1.3,1.3,1.9,1.7,1.1,1.5,1.6,1.7,1.5] #需求量
# 城市距离和信息素
distance_graph = [[0.0 for col in range(city_num)] for raw in range(city_num)]
pheromone_graph = [[1.0 for col in range(city_num)] for raw in range(city_num)]
class Ant(object):
# 初始化
def __init__(self, ID):
self.ID = ID # ID
self.__clean_data() # 随机初始化出生点
# 初始数据
def __clean_data(self):
self.path = [] # 当前蚂蚁的路径
self.total_distance = 0.0 # 当前路径的总距离
self.move_count = 0 # 移动次数
self.current_city = -1 # 当前停留的城市
self.open_table_city = [True for i in range(city_num)] # 探索城市的状态
city_index = 0 # 随机初始出生点
self.current_city = city_index
self.path.append(city_index)
self.open_table_city[city_index] = False
self.move_count = 1
# 选择下一个城市
def __choice_next_city(self):
next_city = -1
select_citys_prob = [0.0 for i in range(city_num)] # 存储去下个城市的概率
total_prob = 0.0
# 获取去下一个城市的概率
for i in range(city_num):
if self.open_table_city[i]:
try:
# 计算概率:与信息素浓度成正比,与距离成反比
select_citys_prob[i] = pow(pheromone_graph[self.current_city][i], ALPHA) * pow(
(1.0 / distance_graph[self.current_city][i]), BETA)
total_prob += select_citys_prob[i]
except ZeroDivisionError as e:
print('Ant ID: {ID}, current city: {current}, target city: {target}'.format(ID=self.ID,
current=self.current_city,
target=i))
sys.exit(1)
# 轮盘选择城市
if total_prob > 0.0:
# 产生一个随机概率,0.0-total_prob
temp_prob = random.uniform(0.0, total_prob)
for i in range(city_num):
if self.open_table_city[i]:
# 轮次相减
temp_prob -= select_citys_prob[i]
if temp_prob < 0.0:
next_city = i
break
if (next_city == -1):
next_city = random.randint(1, city_num)
while ((self.open_table_city[next_city]) == False): # if==False,说明已经遍历过了
next_city = random.randint(1, city_num)
# 返回下一个城市序号
return next_city
# 计算路径总距离
def __cal_total_distance(self):
temp_distance = 0.0
for i in range(1, city_num):
start, end = self.path[i-1], self.path[i]
temp_distance += distance_graph[start][end]
# 回路
start = self.path[0]
temp_distance += distance_graph[start][end]
self.total_distance = temp_distance
# 移动操作
def __move(self, next_city):
self.path.append(next_city)
self.open_table_city[next_city] = False
self.total_distance += distance_graph[self.current_city][next_city]
self.current_city = next_city
self.move_count += 1
# 搜索路径
def search_path(self):
# 初始化数据
self.__clean_data()
# 搜素路径,遍历完所有城市为止
while self.move_count < city_num:
# 移动到下一个城市
next_city = self.__choice_next_city()
self.__move(next_city)
# 计算路径总长度
self.__cal_total_distance()
class VRP(object):
def __init__(self,n=city_num):
self.n = n
# 计算城市之间的距离
for i in range(city_num):
for j in range(city_num):
temp_distance = pow((distance_x[i] - distance_x[j]), 2) + pow((distance_y[i] - distance_y[j]), 2)
temp_distance = pow(temp_distance, 0.5)
#distance_graph[i][j] = float(int(temp_distance + 0.5))
distance_graph[i][j] = temp_distance
self.ants = [Ant(ID) for ID in range(ant_num)] # 初始蚁群
self.best_ant = Ant(-1) # 初始最优解
self.best_ant.total_distance = 1 << 31 # 初始最大距离
self.iter = 1 # 初始化迭代次数
# 开始搜索
def search_path(self):
while self.iter < 2000:
# 遍历每一只蚂蚁
for ant in self.ants:
# 搜索一条路径
ant.search_path()
# 与当前最优蚂蚁比较
if ant.total_distance < self.best_ant.total_distance:
# 更新最优解
self.best_ant = copy.deepcopy(ant)
# 更新信息素
self.__update_pheromone_gragh()
self.iter += 1
# 更新信息素
def __update_pheromone_gragh(self):
# 获取每只蚂蚁在其路径上留下的信息素
temp_pheromone = [[0.0 for col in range(city_num)] for raw in range(city_num)]
for ant in self.ants:
for i in range(1, city_num):
start, end = ant.path[i - 1], ant.path[i]
# 在路径上的每两个相邻城市间留下信息素,与路径总距离反比
temp_pheromone[start][end] += Q / ant.total_distance
temp_pheromone[end][start] = temp_pheromone[start][end]
# 更新所有城市之间的信息素,旧信息素衰减加上新迭代信息素
for i in range(city_num):
for j in range(city_num):
pheromone_graph[i][j] = pheromone_graph[i][j] * (1-RHO) + RHO * temp_pheromone[i][j]
if __name__ == '__main__':
vrp = VRP()
vrp.search_path()
best_path = vrp.best_ant.path #得出的最优TSP路径
print('最优路径:', best_path)
top_height = 8 #最大载重量
top_distance = 50 #最远行驶距离
final_way = [0] #记录最终路径
now_height = 0 #当前车的当前载重量
now_distance = 0 #当前车的当前行驶的距离
k = 1 #记录用几辆车
all_distance = 0 #所有车合起来行驶的距离
for i in range(1,21): #分解TSP路径为VRP路径
if(now_height==0): #判断是否是从头开始
now_height = now_height + need[best_path[i]]
now_distance = distance_graph[0][best_path[i]]
final_way.append(best_path[i])
# 可以到达下一地点并且回来
elif(now_height+need[best_path[i]] <=top_height and
(now_distance + distance_graph[best_path[i-1]][best_path[i]] + distance_graph[0][best_path[i]]) <= top_distance):
final_way.append(best_path[i])
now_height = now_height + need[best_path[i]]
now_distance = now_distance + distance_graph[best_path[i-1]][best_path[i]]
else:
#让上一辆车返回,并开始新的一辆
final_way.append(0)
now_distance = now_distance + distance_graph[0][best_path[i-1]]
print('第{}辆车的路径为{},载重{},行驶距离{}'.format(k,final_way,now_height,now_distance))
all_distance = all_distance + now_distance
k += 1
now_height = need[best_path[i]]
now_distance = distance_graph[0][best_path[i]]
final_way = [0,best_path[i]]
if (i == 20):
final_way.append(0)
now_distance = now_distance + distance_graph[0][best_path[i]]
print('第{}辆车的路径为{},载重{},行驶距离{}'.format(k, final_way, now_height, now_distance))
all_distance = all_distance + now_distance
print(all_distance)
上一篇: ai选择工具怎么给图形变形并拖动复制?
下一篇: 设计理论:《刀锋铁骑》新品首发总结