本代码设计由B站up主'全糖奶茶屋'提供, 可以直接在我们讲解思路的视频下发评论区进行留言. 我们收到留言后会将问题在这里汇总, 与技术小哥商议之后, 给大家更准确的答复. 大家也可以添加我们的人工客服微信: quantangnaichawu (如遇暂时加满了, 无法添加, 请后面再尝试).

代码背景

随着城市化进程的加速，城市生活垃圾产量呈现爆发式增长，对城市环境治理和可持续发展构成严峻挑战。数据显示，我国垃圾清运量从2004年的全球最大产量起步，2016年超过2亿吨，2019年突破3.43亿吨，至2023年已达4亿吨。庞大的垃圾产生量逼近城市处理能力极限，垃圾收集、运输和处理的效率提升成为亟待解决的关键问题。  

垃圾分类运输作为城市环境治理的核心环节，面临多重复杂性：需区分厨余垃圾、可回收物、有害垃圾、其他垃圾等不同类型，每种垃圾对应专用运输车辆，受载重、容积、运输成本等约束；同时需考虑中转站处理能力、时间窗口限制，以及运输成本与碳排放控制的平衡。在此背景下，通过数学建模优化运输路径与调度，提升效率并降低成本，成为城市管理领域的重要研究课题。  

代码围绕单一车辆、多车辆协同、含中转站选址的综合优化等场景，要求建立数学模型并设计算法，解决不同维度下的路径规划与调度问题，为城市垃圾分类运输提供科学的决策支持。

第一部分:最小化每日行驶距离

import pandas as pd
import numpy as np
import matplotlib.pyplot as plt
from matplotlib.patches import Circle
# 设置图片清晰度
plt.rcParams['figure.dpi'] = 300
# 读取文件
excel_file = pd.ExcelFile('C:\\Users\\Administrator\\PyCharmMiscProject\\电工杯\\附件1.xlsx')
# 获取指定工作表中的数据，设置表头行为1
df = excel_file.parse('附件130个垃圾分类收集点坐标及总垃圾量', header=1)
# 重新设置列名
df.columns = ['Collection Point ID', 'X-coordinate (km)', 'Y-coordinate (km)', 'Garbage Volume (tons)', 'Remark']
# 提取坐标数据
coordinates = df[['X-coordinate (km)', 'Y-coordinate (km)']].values
num_points = len(coordinates)
distance_matrix = np.zeros((num_points, num_points))
# 计算距离矩阵（四舍五入取整）
for i in range(num_points):
    for j in range(num_points):
        # 计算欧氏距离并四舍五入取整
        distance = np.sqrt(((coordinates[i] - coordinates[j]) ** 2).sum())
        distance_matrix[i, j] = round(distance)  # 四舍五入取整
# 将距离矩阵转换为 DataFrame
distance_df = pd.DataFrame(distance_matrix, dtype=int)  # 指定整数类型
# 保存到 Excel 文件
distance_df.to_excel('C:\\Users\\Administrator\\PyCharmMiscProject\\电工杯\\distance_matrix_rounded.xlsx', index=False)
# 绘制收集点分布图
plt.figure(figsize=(10, 8))
# 处理厂（编号0）用红色五角星标记，其他收集点用蓝色圆点标记
for i in range(num_points):
    if df['Collection Point ID'][i] == 0:
        plt.scatter(coordinates[i, 0], coordinates[i, 1], c='red', marker='*', s=200,
                    label='Waste Treatment Plant' if i == 0 else '')
        # 添加处理厂标签
        plt.annotate(f'0', (coordinates[i, 0]+0.2, coordinates[i, 1]+0.2),
                     fontsize=12, fontweight='bold')
    else:
        plt.scatter(coordinates[i, 0], coordinates[i, 1], c='blue', marker='o', s=80,
                    label='Collection Point' if i == 1 else '')
        # 添加收集点编号标签
        plt.annotate(f'{df['Collection Point ID'][i]}',
                     (coordinates[i, 0]+0.2, coordinates[i, 1]+0.2),
                     fontsize=9)
# 添加网格线
plt.grid(True, linestyle='--', alpha=0.7)
# 添加图标题和坐标轴标签
plt.title('Distribution of Garbage Collection Points', fontsize=14)
plt.xlabel('X-coordinate (km)', fontsize=12)
plt.ylabel('Y-coordinate (km)', fontsize=12)
# 设置图例位置
plt.legend(loc='upper right')
# 保存图片
plt.savefig('C:\\Users\\Administrator\\PyCharmMiscProject\\电工杯\\collection_points_distribution_rounded.png')
# 显示图形
plt.show()
# 输出统计信息
print(f'距离矩阵已保存至 'distance_matrix_rounded.xlsx'')
print(f'收集点分布图已保存至 'collection_points_distribution_rounded.png'')
print(f'总收集点数: {num_points-1} (编号1~{num_points-1})')
print(f'处理厂编号: 0')

步骤2: 计算最短总路径

import math
import random
import pandas as pd
import matplotlib.pyplot as plt
from matplotlib.pylab import mpl
import numpy as np
mpl.rcParams['font.sans-serif'] = ['SimHei']  # 添加这条可以让图形显示中文
def calDistance(CityCoordinates):
    '''
    计算城市间距离
    输入：CityCoordinates-城市坐标；
    输出：城市间距离矩阵-dis_matrix
    '''
    dis_matrix = pd.DataFrame(data=None, columns=range(len(CityCoordinates)), index=range(len(CityCoordinates)))
    for i in range(len(CityCoordinates)):
        xi, yi = CityCoordinates[i][0], CityCoordinates[i][1]
        for j in range(len(CityCoordinates)):
            xj, yj = CityCoordinates[j][0], CityCoordinates[j][1]
            dis_matrix.iloc[i, j] = round(math.sqrt((xi - xj) ** 2 + (yi - yj) ** 2), 5)
    return dis_matrix
def greedy(CityCoordinates, dis_matrix):
    '''
    贪婪策略构造初始解,初始化时将VRP简化为TSP进行构造。
    输入：CityCoordinates-节点坐标,dis_matrix-距离矩阵
    输出：初始解-line
    '''
    # 修改dis_matrix以适应求解需要
    dis_matrix = dis_matrix.astype('float64')
    for i in range(len(CityCoordinates)): dis_matrix.loc[i, i] = math.pow(10, 10)
    dis_matrix.loc[:, 0] = math.pow(10, 10)  # 0不在编码内
    line = []  # 初始化
    now_city = random.randint(1, len(CityCoordinates) - 1)  # 随机生成出发城市
    line.append(now_city)  # 添加当前城市到路径
    dis_matrix.loc[:, now_city] = math.pow(10, 10)  # 更新距离矩阵，已经过城市不再被取出
    for i in range(1, len(CityCoordinates) - 1):
        next_city = dis_matrix.loc[now_city, :].idxmin()  # 距离最近的城市
        line.append(next_city)  # 添加进路径
        dis_matrix.loc[:, next_city] = math.pow(10, 10)  # 更新距离矩阵
        now_city = next_city  # 更新当前城市
    return line
def calFitness(birdPop, Demand, dis_matrix, CAPACITY, DISTABCE, C0, C1):
    '''
    贪婪策略分配车辆（解码），计算路径距离（评价函数）
    输入：birdPop-路径，Demand-客户需求,dis_matrix-城市间距离矩阵，CAPACITY-车辆最大载重,DISTABCE-车辆最大行驶距离,C0-车辆启动成本,C1-车辆单位距离行驶成本；
    输出：birdPop_car-分车后路径,fits-适应度
    '''
    birdPop_car, fits = [], []  # 初始化
    for j in range(len(birdPop)):
        bird = birdPop[j]
        lines = []  # 存储线路分车
        line = [0]  # 每辆车服务客户点
        dis_sum = 0  # 线路距离
        dis, d = 0, 0  # 当前客户距离前一个客户的距离、当前客户需求量
        i = 0  # 指向配送中心
        while i < len(bird):
            if line == [0]:  # 车辆未分配客户点
                dis += dis_matrix.loc[0, bird[i]]  # 记录距离
                line.append(bird[i])  # 为客户点分车
                d += Demand[bird[i]]  # 记录需求量
                i += 1  # 指向下一个客户点
            else:  # 已分配客户点则需判断车辆载重和行驶距离
                if (dis_matrix.loc[line[-1], bird[i]] + dis_matrix.loc[bird[i], 0] + dis <= DISTABCE) & (
                        d + Demand[bird[i]]  croBird
    list2 = list(range(0, start_pos))
    list1 = list(range(end_pos + 1, len(parent2)))
    list_index = list1 + list2  # croBird从后往前填充
    j = -1
    for i in list_index:
        for j in range(j + 1, len(parent2) + 1):
            if parent2[j] not in croBird:
                croBird[i] = parent2[j]
                break
    return croBird
def draw_path(car_routes, CityCoordinates):
    '''
    #画路径图
    输入：line-路径，CityCoordinates-城市坐标；
    输出：路径图
    '''
    for route in car_routes:
        x, y = [], []
        for i in route:
            Coordinate = CityCoordinates[i]
            x.append(Coordinate[0])
            y.append(Coordinate[1])
        x.append(x[0])
        y.append(y[0])
        plt.plot(x, y, 'o-', alpha=0.8, linewidth=0.8)
    plt.xlabel('x')
    plt.ylabel('y')
    plt.show()
if __name__ == '__main__':
    random.seed(0)
    # 车辆参数
    CAPACITY = 5 # 车辆最大容量
    DISTABCE = 999 # 车辆最大行驶距离
    C0 = 0  # 车辆启动成本
    C1 = 1# 车辆单位距离行驶成本
    # PSO参数
    birdNum = 100  # 粒子数量
    w = 0.2  # 惯性因子
    c1 = 0.4  # 自我认知因子
    c2 = 0.4  # 社会认知因子
    pBest, pLine = 0, []  # 当前最优值、当前最优解，（自我认知部分）
    gBest, gLine = 0, []  # 全局最优值、全局最优解，（社会认知部分）
    # 其他参数
    iterMax = 1000  # 迭代次数
    iterI = 1  # 当前迭代次数
    bestfit = []  # 记录每代最优值
    # 读入数据,
    # DistributionCenter = #配送中心
    Customer =pd.read_excel(r'..\附件1坐标与垃圾.xlsx').values[:,[1,2]]
    Demand =  pd.read_excel(r'..\附件1坐标与垃圾.xlsx').values[:,-1]
    dis_matrix = calDistance(Customer)  # 计算城市间距离
    birdPop = [greedy(Customer, dis_matrix) for i in range(birdNum)]  # 贪婪算法构造初始解
    # birdPop = [random.sample(range(1,len(Customer)),len(Customer)-1) for i in range(birdNum)]#客户点编码，随机初始化生成种群
    birdPop_car, fits = calFitness(birdPop, Demand, dis_matrix, CAPACITY, DISTABCE, C0, C1)  # 分配车辆，计算种群适应度
    gBest = pBest = min(fits)  # 全局最优值、当前最优值
    gLine = pLine = birdPop[fits.index(min(fits))]  # 全局最优解、当前最优解
    gLine_car = pLine_car = birdPop_car[fits.index(min(fits))]
    bestfit.append(gBest)
    while iterI '.join([str(i) for i in all_road]))
    print(r'总路程:',al)
    draw_path(gLine_car, Customer)  # 画路径图

第二部分: 垃圾分类回收

考虑 4 类垃圾（厨余、可回收物、有害垃圾、其他垃圾），每类由专用车辆运输（载重、容积、单位距离成本不同），且收集点可能产生多种垃圾。需建立以最小化总运输成本为目标的多车辆协同模型；将问题一算法扩展至多类型车辆场景（考虑类型、载重与容积约束）并求解；若增加车辆每日最大行驶时间约束，需修改模型并举例说明其对路径规划（如任务拆分）的影响。

import math
import random
import pandas as pd
import matplotlib.pyplot as plt
from matplotlib.pylab import mpl
import numpy as np
mpl.rcParams['font.sans-serif'] = ['SimHei']  # 添加这条可以让图形显示中文
def calDistance(CityCoordinates):
    '''
    计算城市间距离
    输入：CityCoordinates-城市坐标；
    输出：城市间距离矩阵-dis_matrix
    '''
    dis_matrix = pd.DataFrame(data=None, columns=range(len(CityCoordinates)), index=range(len(CityCoordinates)))
    for i in range(len(CityCoordinates)):
        xi, yi = CityCoordinates[i][0], CityCoordinates[i][1]
        for j in range(len(CityCoordinates)):
            xj, yj = CityCoordinates[j][0], CityCoordinates[j][1]
            dis_matrix.iloc[i, j] = round(math.sqrt((xi - xj) ** 2 + (yi - yj) ** 2), 5)
    return dis_matrix
def greedy(CityCoordinates, dis_matrix):
    '''
    贪婪策略构造初始解,初始化时将VRP简化为TSP进行构造。
    输入：CityCoordinates-节点坐标,dis_matrix-距离矩阵
    输出：初始解-line
    '''
    # 修改dis_matrix以适应求解需要
    dis_matrix = dis_matrix.astype('float64')
    for i in range(len(CityCoordinates)): dis_matrix.loc[i, i] = math.pow(10, 10)
    dis_matrix.loc[:, 0] = math.pow(10, 10)  # 0不在编码内
    line = []  # 初始化
    now_city = random.randint(1, len(CityCoordinates) - 1)  # 随机生成出发城市
    line.append(now_city)  # 添加当前城市到路径
    dis_matrix.loc[:, now_city] = math.pow(10, 10)  # 更新距离矩阵，已经过城市不再被取出
    for i in range(1, len(CityCoordinates) - 1):
        next_city = dis_matrix.loc[now_city, :].idxmin()  # 距离最近的城市
        line.append(next_city)  # 添加进路径
        dis_matrix.loc[:, next_city] = math.pow(10, 10)  # 更新距离矩阵
        now_city = next_city  # 更新当前城市
    return line
def calFitness(birdPop, Demand, dis_matrix, CAPACITY, DISTABCE, C0, C1):
    '''
    贪婪策略分配车辆（解码），计算路径距离（评价函数）
    输入：birdPop-路径，Demand-客户需求,dis_matrix-城市间距离矩阵，CAPACITY-车辆最大载重,DISTABCE-车辆最大行驶距离,C0-车辆启动成本,C1-车辆单位距离行驶成本；
    输出：birdPop_car-分车后路径,fits-适应度
    '''
    birdPop_car, fits = [], []  # 初始化
    for j in range(len(birdPop)):
        bird = birdPop[j]
        lines = []  # 存储线路分车
        line = [0]  # 每辆车服务客户点
        dis_sum = 0  # 线路距离
        dis, d = 0, 0  # 当前客户距离前一个客户的距离、当前客户需求量
        i = 0  # 指向配送中心
        while i < len(bird):
            if line == [0]:  # 车辆未分配客户点
                dis += dis_matrix.loc[0, bird[i]]  # 记录距离
                line.append(bird[i])  # 为客户点分车
                d += Demand[bird[i]]  # 记录需求量
                i += 1  # 指向下一个客户点
            else:  # 已分配客户点则需判断车辆载重和行驶距离
                if (dis_matrix.loc[line[-1], bird[i]] + dis_matrix.loc[bird[i], 0] + dis <= DISTABCE) & (
                        d + Demand[bird[i]] <= CAPACITY):
                    dis += dis_matrix.loc[line[-1], bird[i]]
                    line.append(bird[i])
                    d += Demand[bird[i]]
                    i += 1
                else:
                    dis += dis_matrix.loc[line[-1], 0]  # 当前车辆装满
                    line.append(0)
                    dis_sum += dis
                    lines.append(line)
                    # 下一辆车
                    dis, d = 0, 0
                    line = [0]
        # 最后一辆车
        dis += dis_matrix.loc[line[-1], 0]
        line.append(0)
        dis_sum += dis
        lines.append(line)
        birdPop_car.append(lines)
        fits.append(round(C1 * dis_sum + C0 * len(lines), 5))
    return birdPop_car, fits
def crossover(bird, pLine, gLine, w, c1, c2):
    '''
    采用顺序交叉方式；交叉的parent1为粒子本身，分别以w/(w+c1+c2),c1/(w+c1+c2),c2/(w+c1+c2)
    的概率接受粒子本身逆序、当前最优解、全局最优解作为parent2,只选择其中一个作为parent2；
    输入：bird-粒子,pLine-当前最优解,gLine-全局最优解,w-惯性因子,c1-自我认知因子,c2-社会认知因子；
    输出：交叉后的粒子-croBird；
    '''
    croBird = [None] * len(bird)  # 初始化
    parent1 = bird  # 选择parent1
    # 选择parent2（轮盘赌操作）
    randNum = random.uniform(0, sum([w, c1, c2]))
    if randNum <= w:
        parent2 = [bird[i] for i in range(len(bird) - 1, -1, -1)]  # bird的逆序
    elif randNum  croBird
    start_pos = random.randint(0, len(parent1) - 1)
    end_pos = random.randint(0, len(parent1) - 1)
    if start_pos > end_pos: start_pos, end_pos = end_pos, start_pos
    croBird[start_pos:end_pos + 1] = parent1[start_pos:end_pos + 1].copy()
    # parent2 -> croBird
    list2 = list(range(0, start_pos))
    list1 = list(range(end_pos + 1, len(parent2)))
    list_index = list1 + list2  # croBird从后往前填充
    j = -1
    for i in list_index:
        for j in range(j + 1, len(parent2) + 1):
            if parent2[j] not in croBird:
                croBird[i] = parent2[j]
                break
    return croBird
def draw_path(car_routes, CityCoordinates):
    '''
    #画路径图
    输入：line-路径，CityCoordinates-城市坐标；
    输出：路径图
    '''
    for route in car_routes:
        x, y = [], []
        for i in route:
            Coordinate = CityCoordinates[i]
            x.append(Coordinate[0])
            y.append(Coordinate[1])
        x.append(x[0])
        y.append(y[0])
        plt.plot(x, y, 'o-', alpha=0.8, linewidth=0.8)
    plt.xlabel('x')
    plt.ylabel('y')
    plt.show()
if __name__ == '__main__':
    random.seed(0)
    # 车辆参数
    CAPACITY = 8 # 车辆最大容量
    DISTABCE = 9999# 车辆最大行驶距离
    C0 = 0  # 车辆启动成本
    C1 = 1# 车辆单位距离行驶成本
    # PSO参数
    birdNum = 100  # 粒子数量
    w = 0.2  # 惯性因子
    c1 = 0.4  # 自我认知因子
    c2 = 0.4  # 社会认知因子
    pBest, pLine = 0, []  # 当前最优值、当前最优解，（自我认知部分）
    gBest, gLine = 0, []  # 全局最优值、全局最优解，（社会认知部分）
    # 其他参数
    iterMax = 1000  # 迭代次数
    iterI = 1  # 当前迭代次数
    bestfit = []  # 记录每代最优值
    # 读入数据,
    # DistributionCenter = #配送中心
    Customer =pd.read_excel(r'..\附件1坐标与垃圾.xlsx').values[:,[1,2]]
    Demand =  pd.read_excel(r'..\附件3垃圾.xlsx',index_col=0).values[:,0]
    dis_matrix = calDistance(Customer)  # 计算城市间距离
    birdPop = [greedy(Customer, dis_matrix) for i in range(birdNum)]  # 贪婪算法构造初始解
    # birdPop = [random.sample(range(1,len(Customer)),len(Customer)-1) for i in range(birdNum)]#客户点编码，随机初始化生成种群
    birdPop_car, fits = calFitness(birdPop, Demand, dis_matrix, CAPACITY, DISTABCE, C0, C1)  # 分配车辆，计算种群适应度
    gBest = pBest = min(fits)  # 全局最优值、当前最优值
    gLine = pLine = birdPop[fits.index(min(fits))]  # 全局最优解、当前最优解
    gLine_car = pLine_car = birdPop_car[fits.index(min(fits))]
    bestfit.append(gBest)
    while iterI <= iterMax:  # 迭代开始
        for i in range(birdNum):
            birdPop[i] = crossover(birdPop[i], pLine, gLine, w, c1, c2)
        birdPop_car, fits = calFitness(birdPop, Demand, dis_matrix, CAPACITY, DISTABCE, C0, C1)  # 分配车辆，计算种群适应度
        pBest, pLine, pLine_car = min(fits), birdPop[fits.index(min(fits))], birdPop_car[fits.index(min(fits))]
        if min(fits) <= gBest:
            gBest, gLine, gLine_car = min(fits), birdPop[fits.index(min(fits))], birdPop_car[fits.index(min(fits))]
        bestfit.append(gBest)
        print(iterI, gBest)  # 打印当前代数和最佳适应度值
        iterI += 1  # 迭代计数加一
    print(gLine_car)  # 路径顺序
    aw= 0
    all_road = []
    al = 0
    for i in range(len(gLine_car)):
        print(f'车辆 {i+1} 路径','->'.join([str(gLine_car[i][k])for k in range(len(gLine_car[i]))]),
             f'载重w ={np.sum(Demand[gLine_car[i]])}',f'路程:{np.sum([dis_matrix.values[gLine_car[i][k-1],gLine_car[i][k]]for k in range(1,len(gLine_car[i]))])}')
        al += np.sum([dis_matrix.values[gLine_car[i][k-1],gLine_car[i][k]]for k in range(1,len(gLine_car[i]))])
        aw += np.sum(Demand[gLine_car[i]])
        if i ==0:
            all_road += gLine_car[i]
        else:
            all_road += gLine_car[i][1:]
    print(r'总载重:',aw)
    print(r'总路径:'+'->'.join([str(i) for i in all_road]))
    print(r'总路程:',al)
    draw_path(gLine_car, Customer)  # 画路径图

代码演示与讲解视频

整体思路视频: https://www.bilibili.com/video/BV1M6jEzdECb/

第一二问详细细节: https://www.bilibili.com/video/BV1M6jEzdECb/

针对智能优化算法有什么需要注意的地方?

这里还是给大家强调几点: 

1. 不要上来就说这是一个TSP问题, 然后就直接略过TSP里面所有的内容, 然后就开始了一大堆求解, 这个是骗子博主的老套路了, 使用看不懂的名词, 就跳过基础的模型解释. TSP只是因为隶属于线性规划, 并且有明确的约束条件组成, 而被大家定下来一个新的名字. 就像是你给人家介绍电风扇, 你需要把你的扇叶, 电路板, 控制器, 电源通通介绍清楚, 而不是我这是一个电风扇, 这是不被认可的, 具体可以看我们的B站视频讲解.
   
2. 所有的规划模型, 决策变量, 目标函数, 约束条件是三个最重要的组成部分, 也是得分点. 如果没有得分点, 该区域的分数会直接丢失, 如果国赛跳过这些, 那么你的奖项会直接掉入省一以下. 所以, 请不要相信书写这是一个TSP, 然后开始模拟退火进行操作, 就可以写这一小问了, 这种都是非常明确的不踩得分点的失分.
   
3. 本问没有非常明确的要求或者思路一定要使用智能算法, 非必要, 不得使用智能算法, 请收起你的粒子群, 遗传, 模拟退火, 至少你先把基础的规划模型写清楚, 然后写清楚你的理由, 比如收敛速度慢, 比如在合理时间内逼近最优解，适用于大规模复杂问题这样的理由, 然后再开始书写. 还是强调, 先把基础的规划模型三块写清楚.
   

关于各部分结果具体值应该是多少?

    按照我们目前的计算结果, 第一小问的总路程为 1113.73236, 第二问的总成本为 3001.81628元. 类似的规划问题实际上标准答案都会允许一定的波动范围存在, 一般为5%左右, 只要答案基本上在标准附近都是正确的.

垃圾车是否要满载?是否需要一个回收站的垃圾可以分多次运输, 完成相关的垃圾回收?为什么需要限制每个回收站点只能进出一次?

    按照现实的情况来说, 回收站的居民其实并不愿意垃圾每天都分很多批次进行处理, 造成的生活影响是比较大的. 另外, 在越来越机械化的时代, 垃圾处理由机器代替人工, 肯定是更愿意进行一次性处理的, 否则机器还需要判断是否满载, 现实情况更加复杂. 所以我们在模型假设中安排了对应的假设, 让每个回收站的每一种垃圾仅由一辆车处理.

完整助攻文章展示

代码文件展示

代码结果展示