2022电工杯B题思路模型分析

B题思路分析

B题是一道路径优化类的题目,我们可以知道:

目标函数:完成一次整体配送所需要的时间最短

决策变量:物资集中地点,配送目标地点,各点之间路线情况,各点之间距离,各点当日物资需求量,配送车辆最大载重量。

常量包括:配送车辆的数量(每个物资集中点一辆)和行驶速度,无人机数量(每个物资集中点一台)、最大载重量、行驶速度和最长飞行时间。

约束条件:

  1. 配送车辆可在某地点释放无人机,再前往其他地点配送
  2. 配送车辆可先于无人机到达某地点等待接收无人机,也可比无人机晚到某地点再回收无人机。为了配送时间最短,应尽量让无人机先到达某地,而后配送车辆到达进行回收。
  3. 无人机在一次飞行过程中可对一个地点进行配送,也可根据实际情况对多个地点进行配送。
  4. 无人机完成一次飞行后可返回配送车辆换装电池,然后再次进行配送。

更多思路:gzh【UST数模社】

可以梳理题目中的假设

  1. 5G网络能够覆盖整个配送区域;
  2. 每个应急物资集中地点限配送一辆车,只能携带一辆无人机;
  3. 不考虑配送车辆及无人机装卸物资的时间;
  4. 不考虑配送车辆及无人机在各个配送点的停留时间。

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

2022电工杯B题思路模型分析_第1张图片

共给出14个地点,相互之间距离如下表:

2022电工杯B题思路模型分析_第2张图片

空白的位置即代表无法通行。

14个地点当日物资需求量也给出了,如下表:

所有物资总重量为762kg,车辆最大载重量为1000kg,不考虑配送车辆还需要返回应急物资集中地点的情况。

整个配送物资的流程是配送车辆从第9个地点出发,满载物资游走于各个地点之间,知道满足所有所有地点的物资配送需求并回到第9个地点。

第一问就是旅行商问题,求从第9个地点出发遍历14个地点,最终又返回第9个地点的最短路径,进而算出所需消耗的时间。

可使用穷举法,也可使用免疫算法、蚁群算法、遗传算法等进行求解。

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

2022电工杯B题思路模型分析_第3张图片

问题2还是14个地点,但相互之间增加了无人机的路径,如下表:

2022电工杯B题思路模型分析_第4张图片

红色即表示仅无人机可以飞行的路径,黑色是无人机和车辆均可通行。14个地点当日所需物资与问题一相同。

整个配送物资的流程是配送车辆从第9个地点出发,满载物资游走于各个地点之间,与此同时可以分配一些地点的物资配送任务给无人机,直到满足所有地点的物资配送需求后回到第9个地点。

此时可以先根据点与点之间距离、无人机续航和平均速度初步计算出哪些地点可以使用无人机配送,将其纳入可行解构范围。而后根据问题一算法求解。

问题三,若问题2中的配送车辆的最大载重量为500千克,其他条件不变。请结合附件2,建立完成一次整体配送的数学模型,并给出最优方案。 

问题三将配送车辆的最大载重变成了500kg,因所有地点所需救援物资总重为762kg,所以至少需要配送两次。

第一种,先使用聚类的方式将所有地点分为两类(=所需物资总重/最大载重量,进一制),聚类时还需考虑每一类的所需物质之和小于最大载重量500kg。而后使用与问题一一致的高级优化算法进行求解。

问题四,图3中有30个地点,计划设置两个应急物资集中地点,若配送车辆的最大载重量为 500 千克,采取“配送车辆+无人机”的配送模式。请结合附件3,建立完成一次整体配送的数学模型,确定两个应急物资集中地点的最佳位置。

2022电工杯B题思路模型分析_第5张图片

给出一共30个地点,相互之间距离如下表:

2022电工杯B题思路模型分析_第6张图片

30个地点当日物资需求量也给出了,如下表:

2022电工杯B题思路模型分析_第7张图片

所有物资总重为1568kg,车辆最大载重量为500kg,所以至少要分为4辆车运输(=所需物资总重/最大载重量,进一制)。

题目要求确定两个应急物资集中地点的最佳位置。

本问应该使用聚类的方式将所有地点分为两类,在每一类中单独运用问题三中的算法计算最短时间,总的最短配送时间为这两类地点各自配送时间中较长的哪一个。

可以多试几种聚类方式,比较哪种聚类方式可以得到更短的配送时间。

部分代码

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))

你可能感兴趣的