1. 选址-路径问题LRP基础与建模选址-路径问题Location-Routing Problem, LRP是物流优化中的经典难题它需要同时考虑仓库选址和配送路径规划两个关键决策。想象一下你是一家连锁超市的物流经理既要决定在哪些城市建立配送中心又要规划卡车如何高效送货到各个门店——这就是典型的LRP应用场景。LRP的数学模型包含三个核心要素候选设施点集合I、客户需求点集合J和车辆集合K。我常用一个简单的类比帮助学生理解把设施点看作水源客户点是需要浇灌的植物车辆就是输水管道。目标是用最少的管道铺设成本固定成本和输水能耗运输成本让所有植物都得到充分灌溉。在MATLAB中建模时目标函数通常表示为function total_cost objective_function(x) % x(1:I): 设施选址决策变量 % x(I1:IJ): 客户分配决策变量 % x(IJ1:end): 路径规划决策变量 fixed_cost sum(facility_cost .* x(1:I)); transport_cost calculate_routing_cost(x(I1:end)); total_cost fixed_cost transport_cost; end这个目标函数需要满足几个关键约束每个客户必须被唯一设施服务、车辆不能超载、路径必须形成闭合环路等。我在第一次实现时曾忽略车辆容量约束结果算法给出了用摩托车运集装箱的荒谬方案这个教训让我深刻理解了约束条件的重要性。2. 遗传算法设计要点遗传算法解决LRP的核心在于染色体编码设计。经过多次实践我发现双层编码方案最有效第一层用二进制串表示设施选址1选/0不选第二层用排列编码表示客户访问顺序。例如对于5个候选设施和10个客户的问题染色体可能长这样选址部分[1,0,1,0,1] 路径部分[3,7,2,9,4,1,8,5,6,10]这表示选择第1、3、5号设施客户访问顺序为3→7→2→...→10。适应度函数设计直接影响算法效果。我推荐使用惩罚函数法处理约束function fitness evaluate_fitness(chromosome) [cost, violations] decode_chromosome(chromosome); penalty 1e6 * sum(violations); % 重大约束违反惩罚 fitness 1/(cost penalty eps); % 最小化问题转换为最大化 end在交叉操作上对于路径部分建议采用顺序交叉(OX)它能保持客户访问的排列有效性。变异则可以随机交换两个客户位置或翻转一段路径。实测表明保持约5%的变异率能在探索和开发间取得良好平衡。3. MATLAB实现详解让我们从种群初始化开始。这段代码创建包含pop_size个个体的初始种群function population initialize_population(pop_size, num_facilities, num_customers) population cell(pop_size, 1); for i 1:pop_size % 随机选择30-70%的设施 facility_part rand(1,num_facilities) 0.5; % 随机排列客户访问顺序 route_part randperm(num_customers); population{i} [facility_part, route_part]; end end核心进化循环的关键代码如下for gen 1:max_generations % 评估适应度 fitness arrayfun((x) evaluate_fitness(population{x}), 1:pop_size); % 锦标赛选择 selected tournament_selection(population, fitness, tournament_size); % 顺序交叉(OX) offspring {}; for i 1:2:pop_size parent1 selected{i}; parent2 selected{i1}; [child1, child2] ox_crossover(parent1, parent2, num_facilities); offspring [offspring; {child1}; {child2}]; end % 交换变异 for i 1:pop_size if rand() mutation_rate offspring{i} swap_mutation(offspring{i}, num_facilities); end end population offspring; end处理LRP特有的路径分割问题时我开发了一个实用函数function routes split_routes(chromosome, facilities, customers, vehicle_capacity) facility_part chromosome(1:length(facilities)); route_part chromosome(length(facilities)1:end); selected_facilities find(facility_part); routes cell(length(selected_facilities), 1); for f 1:length(selected_facilities) fac selected_facilities(f); associated_customers route_part(...); % 根据分配规则获取该设施服务的客户 % 使用节约算法进行路径划分 routes{f} clarke_wright(associated_customers, vehicle_capacity); end end4. 实战技巧与性能优化在多次项目实践中我总结了几个提升算法效率的秘诀并行计算加速利用MATLAB的parfor并行评估种群适应度在32核服务器上实测速度提升可达8-12倍fitness zeros(pop_size, 1); parfor i 1:pop_size fitness(i) evaluate_fitness(population{i}); end自适应参数调整动态调整交叉率和变异率能显著改善收敛性。这是我常用的调整策略if std(fitness) 0.1*mean(fitness) % 种群多样性下降 mutation_rate min(0.2, mutation_rate * 1.5); crossover_rate max(0.6, crossover_rate * 0.9); end混合局部搜索在每代精英个体上应用2-opt局部优化能快速提升解质量function improved two_opt_swap(route, distance_matrix) improved route; for i 1:length(route)-2 for j i2:length(route)-1 % 计算交换后的距离变化 delta distance_matrix(route(i),route(j)) ... distance_matrix(route(i1),route(j1)) - ... distance_matrix(route(i),route(i1)) - ... distance_matrix(route(j),route(j1)); if delta 0 improved(i1:j) flip(improved(i1:j)); end end end end可视化对理解算法行为至关重要。这个绘图函数能清晰展示解决方案function plot_solution(facilities, customers, routes) figure; hold on; % 绘制设施点 scatter(facilities(:,1), facilities(:,2), 100, r, filled); % 绘制客户点 scatter(customers(:,1), customers(:,2), 50, b, filled); % 绘制路径 colors lines(length(routes)); for f 1:length(routes) for r 1:length(routes{f}) path [facilities(f,:); customers(routes{f}{r},:); facilities(f,:)]; plot(path(:,1), path(:,2), Color, colors(f,:), LineWidth, 2); end end legend(Facilities, Customers); title(LRP Solution Visualization); end5. 典型问题排查指南过早收敛如果算法在20代内就停滞不前可以尝试1) 增大变异率到0.1-0.15 2) 采用小生境技术 3) 引入外来个体。我曾遇到一个案例通过添加下面这个多样性维持机制成功解决了问题if max(fitness) - min(fitness) 0.01 * max(fitness) % 随机替换50%的最差个体 [~, idx] sort(fitness); for i 1:floor(pop_size/2) population{idx(i)} initialize_individual(num_facilities, num_customers); end end违反约束的解对于频繁出现的超载路径需要在解码阶段严格检查function [total_load, is_valid] check_vehicle_load(route, demands, capacity) total_load sum(demands(route)); is_valid total_load capacity; if ~is_valid % 实施修复策略移除需求最大的客户 [~, idx] max(demands(route)); route(idx) []; [total_load, is_valid] check_vehicle_load(route, demands, capacity); end end计算耗时过长对于超过100个客户点的大规模问题可以采用以下优化手段使用KD-tree加速距离计算实现快速非支配排序采用精英保留策略减少无效评估这是我优化后的距离矩阵计算代码function dist_mat fast_distance_matrix(points) [n, ~] size(points); dist_mat zeros(n); for i 1:n diff points(i1:end,:) - points(i,:); dist_mat(i,i1:end) sqrt(sum(diff.^2, 2)); end dist_mat dist_mat dist_mat; % 利用对称性 end6. 进阶应用与扩展思路当掌握基础LRP求解后可以尝试以下扩展方向多目标优化同时考虑成本和服务水平使用NSGA-II算法function [cost, service_level] multi_objective_eval(chromosome) cost calculate_total_cost(chromosome); latest_delivery max(calculate_delivery_times(chromosome)); service_level -latest_delivery; % 最小化最晚送达时间 end动态需求场景客户需求随时间变化时需要在线调整方案。我开发过一个基于滚动时域的解法function solution dynamic_lrp_solver(time_horizon, demand_forecast) solution {}; for t 1:time_horizon current_demands demand_forecast(t,:); if t 1 || isempty(solution{t-1}) % 冷启动 solution{t} ga_lrp_solver(current_demands); else % 热启动基于上一周期解微调 solution{t} adaptive_ga_solver(solution{t-1}, current_demands); end end end鲁棒优化考虑需求不确定性时可以采用鲁棒优化方法。这个示例使用场景法function robust_solution robust_lrp(demand_scenarios) num_scenarios length(demand_scenarios); population initialize_population(pop_size, num_facilities, num_customers); for gen 1:max_generations % 评估每个解在所有场景下的表现 fitness zeros(pop_size, num_scenarios); for s 1:num_scenarios fitness(:,s) evaluate_scenario_fitness(population, demand_scenarios{s}); end % 采用最差场景表现作为适应度 overall_fitness min(fitness, [], 2); % 标准遗传算法操作... end end在实际物流系统中我经常将遗传算法与模拟退火结合使用。这种混合策略能在前期快速收敛后期精细搜索function hybrid_solution ga_sa_hybrid(initial_solution) current initial_solution; best current; T 1000; % 初始温度 while T 1 % 遗传算法生成候选解 offspring genetic_operations(current); % 模拟退火接受准则 deltaE offspring.fitness - current.fitness; if deltaE 0 || rand() exp(deltaE/T) current offspring; if current.fitness best.fitness best current; end end T 0.95 * T; % 降温 end end