【纠错】遗传算法求解VRP计算车辆容量限制的代码有bug

关联文章

关联的博客文章为：《遗传算法求解带时间窗的VRP问题（python）》

原出错函数

源程序代码如下：

def vehicle_capacity_restraint(chrom):
    # 计算一条染色体的车辆容量限制
    individual = copy.deepcopy(chrom)
    split_flag_node = True
    total_path_list = []
    while split_flag_node:
        vehicle_load_list = demand_quantity[0, individual]
        cumsum_list = np.cumsum(vehicle_load_list)
        if len(np.where(cumsum_list > vehicle_capacity_max)[0]) != 0: # 累加值大于车辆容量的位置
            split_flag_node = np.where(cumsum_list > vehicle_capacity_max)[0][0]
        else:
            # 生成的染色体刚好够一辆车运输
            split_flag_node = False
            path_list = [0] * (len(individual) + 2)  # 前后两个配送中心节点
            path_list[1:-1] = copy.deepcopy(individual)
            total_path_list.append(path_list)
        if split_flag_node:
            path_list = [0] * (split_flag_node + 2)  # 前后两个配送中心节点
            path_list[1:-1] = copy.deepcopy(individual[:split_flag_node])
            total_path_list.append(path_list)
            individual = individual[split_flag_node:]
    return total_path_list
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

运行其他的算例发现如下错误：

total_path_list [[0, 1, 2, 0], [0, 4, 0], [0, 8, 5, 0], [0, 6, 0], [0, 7, 0]]
total_path_list [[0, 5, 0]]
population [[ 1  2  4  8  5  6  7  3  9 10]
 [ 5 10  3  7  6  9  4  1  2  8]]
total_path_list [[0, 1, 2, 0], [0, 4, 0], [0, 8, 5, 0], [0, 6, 0], [0, 7, 0]]
routes [1, 2, 4, 8, 5, 6, 7]
1
2
3
4
5
6

分析错误表象为：使用函数vehicle_capacity_restraint()不能很好的根据车辆的最大容量限制切割染色体，根据容量限制插入配送中心节点0。

如下为算例10个需求服务点的需求配送量：

车辆的最大载重量vehicle_capacity_max = 3。

在某些场景下该函数切出来的车辆路径是正确的，需要车辆的载重量扩大点

vehicle_capacity_max = 5的场景下计算是可行的，如下：

total_path_list [[0, 10, 0], [0, 4, 1, 2, 0], [0, 9, 3, 0], [0, 8, 5, 0], [0, 6, 7, 0]]
total_path_list [[0, 8, 5, 0], [0, 10, 0], [0, 7, 6, 0], [0, 2, 3, 0], [0, 1, 4, 9, 0]]
population [[10  4  1  2  9  3  8  5  6  7]
 [ 8  5 10  7  6  2  3  1  4  9]]
total_path_list [[0, 10, 0], [0, 4, 1, 2, 0], [0, 9, 3, 0], [0, 8, 5, 0], [0, 6, 7, 0]]
routes [10, 4, 1, 2, 9, 3, 8, 5, 6, 7]
1
2
3
4
5
6

当vehicle_capacity_max = 3的场景，函数vehicle_capacity_restraint()计算会出现错误，不能正确的根据车辆容量限制切割配送路线，如下：

chrom [ 8  2  7  5  4 10  9  6  1  3]
split_flag_node 2
split_flag_node 2
split_flag_node 1
total_path_list [[0, 8, 2, 0], [0, 7, 5, 0], [0, 4, 0]]
1
2
3
4
5

代码捉虫

修改代码如下：

def vehicle_capacity_restraint(chrom):
    print("chrom", chrom)
    # 计算一条染色体的车辆容量限制
    individual = copy.deepcopy(chrom)
    split_node_flag = True
    split_node_index = -1
    total_path_list = []
    while split_node_flag:
        vehicle_load_list = demand_quantity[0, individual]
        cumsum_list = np.cumsum(vehicle_load_list)
        print("cumsum_list", cumsum_list)
        if len(np.where(cumsum_list > vehicle_capacity_max)[0]) != 0:  # 累加值大于车辆容量的位置
            print("111", np.where(cumsum_list > vehicle_capacity_max)[0])
            split_node_index = np.where(cumsum_list > vehicle_capacity_max)[0][0]
        else:
            if len(cumsum_list) == 0:
                split_node_flag = False
                continue
            else:
                if split_node_index == -1:
                    print("222")
                    split_node_flag = False
                    # 生成的染色体刚好够一辆车运输
                    path_list = [0] * (len(individual) + 2)  # 前后两个配送中心节点
                    path_list[1:-1] = copy.deepcopy(individual)
                    total_path_list.append(path_list)
        if (split_node_index) != 0 and (split_node_index != -1):
            print("split_node_index", split_node_index)
            path_list = [0] * (split_node_index + 2)  # 前后两个配送中心节点
            path_list[1:-1] = copy.deepcopy(individual[:split_node_index])
            total_path_list.append(path_list)
            individual = individual[split_node_index:]
        elif len(cumsum_list) == 0:
            split_node_flag = False
            continue
        elif split_node_index != -1:
            print("333", split_node_index)
            path_list = [0] * (1 + 2)  # 前后两个配送中心节点
            path_list[1] = copy.deepcopy(individual[0])
            total_path_list.append(path_list)
            individual = individual[1:]
        else:
            pass
    print("total_path_list", total_path_list)
    return total_path_list
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

满足第一种场景，vehicle_capacity_max = 22 # 车辆的最大载重量，即刚好使用一辆车可以装满所有10个需求节点的货物，运输路线只有一条，即total_path_list [[0, 2, 3, 4, 5, 6, 7, 8, 9, 10, 1, 0]]：

chrom [2, 3, 4, 5, 6, 7, 8, 9, 10, 1]
cumsum_list [ 1.   4.5  6.5  7.5 10.5 12.5 14.5 16.  20.  21.5]
222
total_path_list [[0, 2, 3, 4, 5, 6, 7, 8, 9, 10, 1, 0]]

Process finished with exit code 0

1
2
3
4
5
6
7

满足第二种场景，vehicle_capacity_max = 1 # 车辆的最大载重量，车辆的运输能力极小时，函数vehicle_capacity_restraint()也能正确的工作，得到极大值，也就是派10辆车完成运输任务，如下结果total_path_list [[0, 2, 0], [0, 3, 0], [0, 4, 0], [0, 5, 0], [0, 6, 0], [0, 7, 0], [0, 8, 0], [0, 9, 0], [0, 10, 0], [0, 1, 0]]

chrom [2, 3, 4, 5, 6, 7, 8, 9, 10, 1]
cumsum_list [ 1.   4.5  6.5  7.5 10.5 12.5 14.5 16.  20.  21.5]
111 [1 2 3 4 5 6 7 8 9]
split_node_index 1
cumsum_list [ 3.5  5.5  6.5  9.5 11.5 13.5 15.  19.  20.5]
111 [0 1 2 3 4 5 6 7 8]
333 0
cumsum_list [ 2.   3.   6.   8.  10.  11.5 15.5 17. ]
111 [0 1 2 3 4 5 6 7]
333 0
cumsum_list [ 1.   4.   6.   8.   9.5 13.5 15. ]
111 [1 2 3 4 5 6]
split_node_index 1
cumsum_list [ 3.   5.   7.   8.5 12.5 14. ]
111 [0 1 2 3 4 5]
333 0
cumsum_list [ 2.   4.   5.5  9.5 11. ]
111 [0 1 2 3 4]
333 0
cumsum_list [2.  3.5 7.5 9. ]
111 [0 1 2 3]
333 0
cumsum_list [1.5 5.5 7. ]
111 [0 1 2]
333 0
cumsum_list [4.  5.5]
111 [0 1]
333 0
cumsum_list [1.5]
111 [0]
333 0
cumsum_list []
total_path_list [[0, 2, 0], [0, 3, 0], [0, 4, 0], [0, 5, 0], [0, 6, 0], [0, 7, 0], [0, 8, 0], [0, 9, 0], [0, 10, 0], [0, 1, 0]]

Process finished with exit code 0

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

满足第三种场景，vehicle_capacity_max = 5 # 车辆的最大载重量，也就是没有修改函数前，函数能实现的计算功能。

chrom [2, 3, 4, 5, 6, 7, 8, 9, 10, 1]
cumsum_list [ 1.   4.5  6.5  7.5 10.5 12.5 14.5 16.  20.  21.5]
111 [2 3 4 5 6 7 8 9]
split_node_index 2
cumsum_list [ 2.   3.   6.   8.  10.  11.5 15.5 17. ]
111 [2 3 4 5 6 7]
split_node_index 2
cumsum_list [ 3.   5.   7.   8.5 12.5 14. ]
111 [2 3 4 5]
split_node_index 2
cumsum_list [2.  3.5 7.5 9. ]
111 [2 3]
split_node_index 2
cumsum_list [4.  5.5]
111 [1]
split_node_index 1
cumsum_list [1.5]
split_node_index 1
cumsum_list []
total_path_list [[0, 2, 3, 0], [0, 4, 5, 0], [0, 6, 7, 0], [0, 8, 9, 0], [0, 10, 0], [0, 1, 0]]

Process finished with exit code 0

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

满足第四种场景，vehicle_capacity_max = 100 # 车辆的最大载重量，当车辆最大载重量即运输能力极大时，函数也能够很好的计算配送路线，total_path_list [[0, 2, 3, 4, 5, 6, 7, 8, 9, 10, 1, 0]]

chrom [2, 3, 4, 5, 6, 7, 8, 9, 10, 1]
cumsum_list [ 1.   4.5  6.5  7.5 10.5 12.5 14.5 16.  20.  21.5]
222
total_path_list [[0, 2, 3, 4, 5, 6, 7, 8, 9, 10, 1, 0]]

Process finished with exit code 0

1
2
3
4
5
6
7

运用实例

vehicle_capacity_max = 5 # 车辆的最大载重量

目标函数如下：

# 目标函数：使用车辆数量最少+车辆的总行驶距离最小。
# 约束条件：车辆载重量限制+硬时间窗限制
# 由于出动一辆车的固定成本远远大于车辆的行驶成本，
# 所以，本文将车辆数最小作为最小总成本的主要目标 ，而将路程最小作为次要目标 。

def main_target_func(chrom):
    # 使用车辆数量最少
    vehice_num = 0
    routes = get_feasible_route(chrom)
    print("routes", routes)
    for path in routes:
        for node in path[1:-1]:
            if node == 0:
                vehice_num += 1
    return vehice_num


def minor_target_func(chrom):
    # 车辆的总行驶距离最小
    # 适应度函数是总路线长度最小
    routes = get_feasible_route(chrom)
    total_length = 0
    for route in routes:
        total_length += get_route_length(route)
    target_value = total_length
    return target_value


def calculate_fitness(chrom):
    target_value = 0.6*main_target_func(chrom) + 0.4*minor_target_func(chrom)
    return target_value
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

遗传算法计算得到如下的结果即算法迭代图形：