第十四届全国大学生电工杯数学建模竞赛

时隔一年，记录下，实在懒，没有什么内容好更了。

没有哪次竞赛比这次更累了，建模、编程、论文三合一，加班加点的通宵，比完直接躺了两天。当然，对于自己各方面的提升也是巨大的，最后也是不负众望，和室友、班长共同努力下取得了一等奖。

B 题如下

第一问很简单是可重复访问的 TSP 问题，有多种方法，例如多次 Dijkstra + 剪枝优化，暴力枚举 + 剪枝优化（$O(n!)$），遗传算法，状压 DP（状态压缩动态规划，$O(n^{2}\cdot 2^{n})$）等等。由于数量级问题，遗传算法大概 2 分钟，其他算法不推荐。
状压 DP 代码如下：

import sys

def tsp(dp, mask, pos, dist, n):
    # 如果所有城市都访问过，返回当前位置到起点的距离
    if mask == (1 << n) - 1:
        return dist[pos][0]
    
    # 如果这个状态已经计算过，直接返回结果
    if dp[mask][pos] != -1:
        return dp[mask][pos]
    
    ans = sys.maxsize
    # 尝试访问每个城市
    for i in range(n):
        # 如果这个城市还没有被访问过
        if (mask & (1 << i)) == 0:
            # 计算通过这个城市到下一个城市的新路径长度
            newAns = dist[pos][i] + tsp(dp, mask | (1 << i), i, dist, n)
            ans = min(ans, newAns)
    
    # 记录并返回当前状态的最短路径长度
    dp[mask][pos] = ans
    return ans

第二问复杂的多，改进遗传算法，增加一条代表无人机路径的染色体并且由于无人机载重限制，同一地点可能需要重复飞行，将配送地点当日物资需求量利用阶跃函数和取整函数进行分界设置为无人机染色体中该地点基因的权重，由此控制变异之后该地点基因出现概率。得出完成一次整体配送的最优方案时间。

第三问延续第二问进行二次改进，设置配送车辆染色体 9 号基因的权重为较大值，即可使配送车辆染色体以较大的变异概率出现 9 号基因，即中途返回出发地，得出完成一次整体配送最优方案时间。

第四问由于计划设置两个应急物资集中地点，因此使用 K-median 聚类方法进行聚类，同时，将各地点当日物资需求量作为聚类点集权重，聚类得出两个应急物资中心点为地点 5 和地点 25，且将图分为两部分，之后使用问题三中改进的遗传算法计算两次，分别得出两个应急物资点完成一次整体配送的最优方案。