欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

蚁群算法解决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)