2022电工杯AB题思路分析

将在本文更新电工杯AB题思路

2022电工杯AB题思路分析_第1张图片

A题:高比例风电电力系统储能运行及配置分析
A题是一个风力系统储能问题,需要相关的专业知识,本题考量的是风力发电接入容量、供电成本,储能容量等;需要考虑建立多目标优化模型来求解,后面会更新相对应的详细思路

B 题 5G 网络环境下应急物资配送问题
B题是一个典型的路径优化问题,考察的是“配送车辆+无人机”的配送模式下的路径规划问题,我们可以用到模拟退火算法、遗传算法、粒子群算法来解决该问题。

我们首先可以将其配送路径设置为如下图所示:

2022电工杯AB题思路分析_第2张图片

下面放一种可供参考的VRP模型来解决问题:
首先我们对模型参数和决策变量进行设定

模型参数:

参数 含义
N 所有点的集合
M 可以使用无人机配送的点的集合
O 起止点
wi 点i的配送重量
W 配送车辆的载重上限
dij 点i到点j的距离
c 无人机配送的距离成本系数
B 一个充分大的数

决策变量:

变量 类型 含义
xi,j 0-1 卡车是否经过从点 i 到点 j 的路径
yi,j 0-1 无人机是否经过从点 i 到点 j 的路径
si 0-1 点 i 是否由卡车配送
zi,j R0+ 从点 i 到点 j 的路径上的卡车载重,可用于消除子回路we

问题1 图 1给出 14 个地点,其中实线代表各地点之间的路线情况。若目前所有应急物资集中在第 9 个地点,配送车辆的最大载重量为 1000 千克,采取配送车辆(无人机不参与)的配送模式。请结合附件 1,建立完成一次整体配送的数学模型,并给出最优方案。

针对问题一,我们的约束条件为

(1) 流入/流出
(1a) 只能使用车辆配送的点,最大载重量为1000kg

\sum_{j\epsilon N}x_{i,j}=1 \forall i\epsilon N/(o)M \sum_{j\epsilon N}y_{i,j}=1 \forall i\epsilon N/(o)M

物资都集合在了第 9 个点,车辆配送最大载重为 1000kg,那么我们可以设计程序步骤:

Step1:设置优化算法基本参数,设置最大路线数N,设置惩罚系数(该系数后面问通用)

Step2:生成初始个体,每个个体长度为n(地点数),通过randi([1,N])得到k条路线,通过randi([1,N],1,n)随机赋予每个点所在的路线编号,并检验是否存在没有经过点的路线(检验时排除第9个点),否则重新randi([1,N],1,n),然后通过randperm(n)随机赋予各点一个顺序,这样就可以得到不同路线的不同路径

Step3:计算初始个体的目标函数,有了前面的距离矩阵,可以直接调用计算出总时间(肯定要算完整的路线从出发点到终点),同时计算每条路线的运载量(需求量之和),超载部分乘以惩罚系数作为额外的成本

Step4:迭代,这里遗传算法的交叉变异函数需要自己写,交叉过程就是rand<交叉率时,随便选择两个点的顺序交换或者路线编号交换,变异过程就建议重新用randperm(n)生成下路径顺序,或者用randi([1,N],1,n)重新给予路线编号都可以,但交叉和变异过程都得进行检验

Step5:最后输出最优路线及路径

(最短路径还有模拟退火、禁忌搜索、蚁群等算法都可以实现)

问题2 图 2 中实线代表车辆和无人机都可以走的路线,虚线代表只有无人机可以走的路线。应急物资仍然集中在第 9 个地点,配送车辆的最大载重量为 1000 千克,采取“配送车辆+无人机”的配送模式。请结合附件 2,建立完成一次整体配送的数学模型,并给出最优方案。

第二问就在第一问程序基础上增加条件就可以了,逻辑给同学们理一理哈,无人机的速度是优先于车辆的,所以只要满足无人机配送条件的都可以直接通过无人机配送,程序添加第一问Step2最后,针对每条路线中,判断无人机可以连续配送多少个点,配送完了后就到达下一个点等待车辆或者车辆先到达等待无人机,车辆就直接前往无人机配送完后将抵达的下一个点,这里一定要考虑无人机的航程和续航时间,必须到达点上才行,都这只配送一个点或者不配送。

建议同学们增加一个0-1矩阵,维度就是所有点数,用来记录那些点是无人机配送的就行,第二问主要是加个0-1矩阵,然后重新换算下配送时间,第一问整体程序框架未做大改

(1b) 可以使用无人机配送的点

2022电工杯AB题思路分析_第3张图片

 (2) 去除自循环

2022电工杯AB题思路分析_第4张图片

(3) 是否由车辆配送

(4) 子回路去除

2022电工杯AB题思路分析_第5张图片

 (5) 无人机配送的流入点和流出点,符合车辆路径的先后关系

 (6每辆车只有一架无人机

2022电工杯AB题思路分析_第6张图片

目标函数

最小化,加权距离成本

2022电工杯AB题思路分析_第7张图片

from datetime import datetime
import random
import math

from utils.logger import log_vrp as log


dts = datetime.now()


# nodes
NUM_NODE = 50
NUM_NODE_NAV = 10
LIST_NODE_UAV = list(range(NUM_NODE - NUM_NODE_NAV + 1, NUM_NODE + 1))

# coordinates
random.seed(2021)
RANGE_COORDINATE = (0, 100)
LIST_COORDINATE = [(random.randint(RANGE_COORDINATE[0], RANGE_COORDINATE[1]),
                    random.randint(RANGE_COORDINATE[0], RANGE_COORDINATE[1])) for _ in range(NUM_NODE)]

# distance
ORIGIN = (round((RANGE_COORDINATE[1] - RANGE_COORDINATE[0]) / 2),
          round((RANGE_COORDINATE[1] - RANGE_COORDINATE[0]) / 2))
LIST_COORDINATE_ = [ORIGIN] + LIST_COORDINATE
MAT_DISTANCE = [[0.0 for _ in range(0, NUM_NODE + 1)] for _ in range(0, NUM_NODE + 1)]
range_wave = (0.8, 1.2)
for i in range(0, NUM_NODE + 1):
    for j in range(0, NUM_NODE + 1):
        distance = round(math.sqrt((LIST_COORDINATE_[i][0] - LIST_COORDINATE_[j][0]) ** 2
                                   + (LIST_COORDINATE_[i][1] - LIST_COORDINATE_[j][1]) ** 2)
                         * (range_wave[0] + random.random() * (range_wave[1] - range_wave[0])), 4)
        MAT_DISTANCE[i][j] = distance

# cost
COST_UAV = 0.1

# weight, load
upper_weight_item = 20
LIST_WEIGHT = [random.randint(0, upper_weight_item) for _ in range(NUM_NODE)]
UPPER_LOAD = 100
log.info(msg="total weight:  {}".format(sum(LIST_WEIGHT)))


dte = datetime.now()
tm = round((dte - dts).seconds + (dte - dts).microseconds / (10 ** 6), 3)
log.info(msg="random data generating time:  {} s".format(tm))

 更多思路:

2022电工杯AB题思路分析_第8张图片

你可能感兴趣的