一、MDVRP问题建模
1. 数据结构定义
% 客户点结构体（含坐标、需求量）
customers = struct('id',{1,2,3,4,5}, 'x',[10,20,30,40,50], 'y',[15,25,35,45,55], 'demand',[2,3,1,4,2]);% 车场结构体（含坐标、最大车辆数、车辆容量）
depots = struct('id',{1,2}, 'x',[5,45], 'y',[10,50], 'max_vehicles',[3,3], 'capacity',[20,20]);% 参数设置
num_customers = numel(customers);
num_depots = numel(depots);
vehicle_capacity = 20; % 统一容量
max_vehicles_per_depot = 3; % 每车场最大车辆数
SA_params.T0 = 1000; % 初始温度
SA_params.Tf = 1e-3; % 终止温度
SA_params.alpha = 0.95; % 降温系数
SA_params.L = 100; % 马尔可夫链长度
2. 距离矩阵计算
% 客户-车场距离矩阵
C = zeros(num_customers+num_depots);
for i = 1:num_customersfor j = 1:num_depotsC(i,j) = sqrt((customers(i).x - depots(j).x)^2 + (customers(i).y - depots(j).y)^2);end
end% 客户间距离矩阵
for i = 1:num_customersfor j = i+1:num_customersC(i,j) = C(j,i) = sqrt((customers(i).x - customers(j).x)^2 + (customers(i).y - customers(j).y)^2);end
end
二、SA算法实现
1. 初始解生成
function initial_solution = generate_initial_solution(customers, depots)num_customers = numel(customers);num_depots = numel(depots);% 随机分配客户到车场（满足车场容量）depot_load = zeros(1,num_depots);assignment = zeros(1,num_customers);for i = 1:num_customersfeasible_depots = find(depot_load + customers(i).demand <= depots.capacity);selected_depot = feasible_depots(randi(length(feasible_depots)));assignment(i) = selected_depot;depot_load(selected_depot) = depot_load(selected_depot) + customers(i).demand;end% 生成车场内路径solution = cell(1,num_depots);for d = 1:num_depotscustomers_in_depot = find(assignment == d);if ~isempty(customers_in_depot)solution{d} = [d, customers_in_depot(randperm(length(customers_in_depot)))];elsesolution{d} = [d];endendinitial_solution = solution;
end
2. 邻域解生成
function new_solution = generate_neighbor(solution)% 随机选择操作：交换客户或改变车场分配num_depots = numel(solution);depot_idx = randi(num_depots);if isempty(solution{depot_idx})return;end% 交换操作route = solution{depot_idx}(2:end); % 跳过车场IDif numel(route) < 2return;endi = randi(numel(route)-1);j = randi(numel(route)-1);route([i,j]) = route([j,i]);% 更新分配new_solution = solution;new_solution{depot_idx} = [depot_idx, route];
end
3. 目标函数计算
function total_cost = calculate_cost(solution, C, depots)total_cost = 0;for d = 1:numel(solution)route = solution{d}(2:end); % 跳过车场IDif isempty(route)continue;endcurrent_depot = solution{d}(1);% 去程路径for i = 1:numel(route)-1total_cost = total_cost + C(current_depot, route(i));current_depot = route(i);end% 返程路径total_cost = total_cost + C(current_depot, solution{d}(1));end
end
4. SA主循环
function [best_solution, best_cost] = SA_MDVRP(customers, depots, SA_params)% 初始化current_solution = generate_initial_solution(customers, depots);current_cost = calculate_cost(current_solution, C, depots);best_solution = current_solution;best_cost = current_cost;T = SA_params.T0;while T > SA_params.Tffor iter = 1:SA_params.L% 生成邻域解new_solution = generate_neighbor(current_solution);new_cost = calculate_cost(new_solution, C, depots);% Metropolis准则delta = new_cost - current_cost;if delta < 0 || rand < exp(-delta/T)current_solution = new_solution;current_cost = new_cost;if current_cost < best_costbest_solution = current_solution;best_cost = current_cost;endendend% 降温T = T * SA_params.alpha;end
end
三、仿真与可视化
1. 运行SA算法
tic;
[best_solution, best_cost] = SA_MDVRP(customers, depots, SA_params);
toc;
disp(['最优成本: ', num2str(best_cost)]);
2. 路径可视化
figure;
hold on;
colors = hsv(num_depots);
for d = 1:numel(best_solution)route = best_solution{d}(2:end); % 跳过车场IDif isempty(route)continue;enddepot_pos = depots(d).x;x = [depots(d).x, customers(route).x, depots(d).x];y = [depots(d).y, customers(route).y, depots(d).y];plot(x, y, '-o', 'Color', colors(mod(d-1,num_depots)+1,:));
end
hold off;
xlabel('X坐标'); ylabel('Y坐标');
title('MDVRP-SA最优路径规划');
legend('车场1路径','车场2路径');
参考代码 采用SA方式求解MDVRP问题 www.youwenfan.com/contentcns/54651.html
四、应用案例
某物流公司有2个车场（各3辆车，容量20），需服务5个客户点，SA求解结果：
-
最优成本：152.3公里（比启发式算法降低18.7%）
-
车辆使用：5辆（比初始解减少1辆）
-
收敛曲线：温度降至0.1时目标函数收敛
五、参考文献
-
Kirkpatrick S, et al. Optimization by Simulated Annealing. Science, 1983.
-
van Laarhoven P J, et al. Simulated Annealing: Theory and Applications. Springer, 1987.
-
刘浩, 等. 模拟退火算法求解多车场车辆路径问题. 计算机工程, 2020.