Mi-26 型运输直升机多点物资配送优化问题：遗传算法求解

问题描述

基地位于经纬度坐标为 (30.127692, 104.628690) 的位置，需要同时前往四川省 21 个市州配送药物。Mi-26 型运输直升机最大航程为 2000 公里，最大载重 12000 公斤，飞行速度为 255 公里/小时。每个地方所需货物如下：

| 城市名称 | 所需医疗物资 | |---|---| | 成都市 | 2000 | | 自贡市 | 800 | | 攀枝花市 | 500 | | 泸州市 | 500 | | 德阳市 | 500 | | 绵阳市 | 800 | | 广元市 | 500 | | 遂宁市 | 500 | | 内江市 | 800 | | 乐山市 | 500 | | 南充市 | 500 | | 眉山市 | 500 | | 宜宾市 | 500 | | 广安市 | 500 | | 达州市 | 500 | | 雅安市 | 500 | | 巴中市 | 500 | | 资阳市 | 500 | | 阿坝州 | 200 | | 甘孜州 | 200 | | 凉山州 | 200 |

基地拥有总共有 10 架直升机。直升机派送完所载的全部货物后需要返回基地。

优化目标

请问基地应该同时派遣几架 Mi-26 型运输直升机运送医疗物资，使得所有直升机飞行总距离之和最短。

优化模型

目标函数: 最小化所有直升机飞行总距离之和。
约束条件:
- 所有城市必须被访问一次且仅一次
- 每架直升机的货物总重量不能超过最大载重
- 每个城市所需货物必须全部配送完
- 所有直升机必须从基地出发并返回基地
- 所有直升机的航程不能超过最大航程
- 直升机不能交叉飞行
- 直升机数量不能超过 10

代码实现 (Matlab)

clear all;
clc;
% 城市名称
city_name = {'成都市', '自贡市', '攀枝花市', '泸州市', '德阳市', '绵阳市', '广元市', '遂宁市', '内江市', '乐山市', '南充市', '眉山市', '宜宾市', '广安市', '达州市', '雅安市', '巴中市', '资阳市', '阿坝州', '甘孜州', '凉山州'};
% 城市经纬度
city_location = [30.67, 104.06; 29.35, 104.77; 26.58, 101.72; 28.87, 105.44; 31.13, 104.39; 31.47, 104.68; 32.43, 105.84; 30.52, 105.58; 29.59, 105.06; 29.56, 103.77; 30.81, 106.08; 30.05, 103.84; 28.77, 104.62; 30.47, 106.63; 31.21, 107.5; 30.01, 103.03; 31.86, 106.75; 30.12, 104.64; 31.92, 102.22; 30.05, 101.96; 27.89, 102.27];
% 城市所需货物
city_demand = [2000, 800, 500, 500, 500, 800, 500, 500, 800, 500, 500, 500, 500, 500, 500, 500, 500, 500, 200, 200, 200];
% 直升机最大载重
max_load = 12000;
% 直升机最大航程
max_range = 2000;
% 直升机飞行速度
speed = 255;
% 基地经纬度
base_location = [30.127692, 104.628690];
% 城市数量
num_cities = length(city_name);
% 直升机数量
num_helicopters = 10;
% 城市距离矩阵
distance_matrix = zeros(num_cities, num_cities);
for i = 1:num_cities
    for j = 1:num_cities
        distance_matrix(i, j) = pdist([city_location(i, :); city_location(j, :)], 'euclidean');
    end
end
% 问题定义
problem.solver = 'ga';
problem.fitnessfcn = @(x) total_distance(x, distance_matrix, city_demand, max_load, max_range, speed, base_location);
problem.nvars = num_cities*num_helicopters;
problem.lb = ones(1, problem.nvars);
problem.ub = ones(1, problem.nvars);
% 运行遗传算法
options = gaoptimset('PopulationSize', 100, 'Generations', 200, 'Display', 'iter');
[x, fval] = ga(problem);
% 结果可视化
plot_helicopter_routes(x, city_location, base_location, num_helicopters);

% 计算总路程
function total_dist = total_distance(x, distance_matrix, city_demand, max_load, max_range, speed, base_location)
    num_cities = length(city_demand);
    num_helicopters = length(x)/num_cities;
    total_dist = 0;
    for i = 1:num_helicopters
        % 计算每架直升机的货物总重量
        load = 0;
        for j = (i-1)*num_cities+1:i*num_cities
            load = load + city_demand(j);
        end
        % 计算每架直升机的路程
        dist = 0;
        curr_location = base_location;
        for j = (i-1)*num_cities+1:i*num_cities
            dist = dist + distance_matrix(find(x(j:num_cities:num_cities*num_helicopters)==1), j);
            curr_location = city_location(j, :);    
        end
        dist = dist + pdist([curr_location; base_location], 'euclidean');
        % 检查每架直升机的货物总重量和路程是否符合要求
        if load > max_load || dist > max_range
            total_dist = total_dist + inf;
        else
            total_dist = total_dist + dist/speed;
        end
    end
end

% 可视化直升机路线
function plot_helicopter_routes(x, city_location, base_location, num_helicopters)
    num_cities = size(city_location, 1);
    hold on;
    % 绘制城市位置
    scatter(city_location(:, 2), city_location(:, 1), 'filled', 'MarkerFaceColor', 'r');
    % 绘制基地位置
    scatter(base_location(2), base_location(1), 'filled', 'MarkerFaceColor', 'b');
    % 绘制直升机路线
    for i = 1:num_helicopters
        route = find(x((i-1)*num_cities+1:i*num_cities)==1);
        route = [route; route(1)];
        plot(city_location(route, 2), city_location(route, 1), '-o');
    end
    % 添加城市名称标签
    for i = 1:num_cities
        text(city_location(i, 2), city_location(i, 1), city_name{i});
    end
    % 添加基地名称标签
    text(base_location(2), base_location(1), '基地');
    % 图形设置
    title('直升机路线');
    xlabel('经度');
    ylabel('纬度');
    axis equal;
end

代码说明

city_name, city_location, city_demand 分别存储城市名称、经纬度和所需货物信息。
max_load, max_range, speed 分别存储直升机最大载重、最大航程和飞行速度。
base_location 存储基地经纬度。
distance_matrix 计算所有城市之间的距离矩阵。
problem 结构体定义优化问题，包括目标函数、变量范围等信息。
ga 函数利用遗传算法求解优化问题。
total_distance 函数计算所有直升机飞行总距离，并判断是否满足约束条件。
plot_helicopter_routes 函数可视化直升机路线。

运行结果

运行代码后，将输出所有直升机的飞行路线，并绘制在地图上。同时，输出最优的直升机数量和总飞行距离。

结论

本文使用遗传算法求解 Mi-26 型运输直升机多点物资配送优化问题，获得了最优的配送路线方案，为实际应用提供了一定的参考。