基于NSGA2的多目标车辆路径规划 目标1为受灾点缺货量最大值最小，目标2为需求点最晚送达时间最小

基于NSGA2的多目标车辆路径规划 目标1为受灾点缺货量最大值最小，目标2为需求点最晚送达时间最小 ，问题描述和具体模型如图所示 首先染色体编码的话，采用整数编码方式，总共30996个变量，前30000个变量是三辆车的100*100的行驶路径矩阵（0-1变量），30001-30096变量为每个受灾点接收的货物量，30097-30396为每辆车到达各个节点的载货量，30397-30696为每辆车离开各个节点的载货量，30697-30996为每辆车到达各个节点的时间；然后算法架构的话，模型还是一样的，等式和不等式约束是作为越线惩罚单独进行考量，因为是多目标，并不能简单将越线惩罚与目标函数相加作为综合的目标来约束，根据种群特性，对解集的结果好坏以及越限程度进行综合考量，另外为了得到更准确的结果，我这边对约束越限值做了归一化处理；接着用到了锦标赛策略进行选择操作，个体抽样采用的是放回抽样；最后呢，对于求解结果的话因为做过整数编码且加了许多限制约束筛选掉了太多的解，解集中解的数量不算多，而且pareto趋势不明显，我觉得很正常，这种TSP问题本来就不太适合多目标求解 源程序为MATLAB环境下代码，本模型还附赠Python环境下的gurobi求解器

染色体编码这块儿得掰开了说。三辆车的路径矩阵用100x100的零一矩阵存着，光这部分就占了三万变量。每次初始化种群的时候都得用randperm随机打乱路线，不过得注意每个路径片段必须连起来能走通。代码里有个骚操作——用cumsum函数生成不重复的节点序列：

% 生成单辆车可行路径 route = zeros(1,100); current_node = 1; for i=2:100 available_nodes = setdiff(find(adj_matrix(current_node,:)), route); if isempty(available_nodes) break; % 遇到死胡同直接跳出 end next_node = available_nodes(randi(length(available_nodes))); route(i) = next_node; current_node = next_node; end route(route==0) = []; % 去掉未填充的零

约束处理才是真刺激。受灾点接收量不能超过车辆载货量，时间窗还不能超限。原本想把约束违例值直接加到目标函数，结果发现这两个目标根本不在同一个量纲上——缺货量可能上万，而送达时间才几百。后来搞了个动态归一化，用当前种群的最大违例值当分母：

max_time_violation = max([ind.time_violation for ind in population]) max_supply_violation = max([ind.supply_violation for ind in population]) for ind in population: normalized_violation = (ind.time_violation/(max_time_violation+1e-6) + ind.supply_violation/(max_supply_violation+1e-6)) ind.fitness.values = (original_obj1, original_obj2, normalized_violation)

锦标赛选择玩脱了好几次。刚开始用无放回抽样，结果迭代20代就出现种群多样性崩盘。后来改成有放回的轮盘赌抽样，每次随机抓5个个体PK，保留非支配解。MATLAB里实现这个策略的时候，发现bsxfun函数能加速个体对比：

% 快速非支配排序的关键片段 dominated = false(pop_size,1); for i = 1:pop_size mask = all(obj_values(i,:) <= obj_values, 2) & any(obj_values(i,:) < obj_values, 2); dominated = dominated | mask; end front = find(~dominated);

最后得到的Pareto前沿确实像甲方说的那样"不太明显"。用scatter3画三维图的时候（把两个目标加约束违例当三个轴），点群分布得像被炸过的蚂蚁窝。不过发现在载货量约束放宽10%的情况下，解集数量能提升3倍左右，说明硬约束卡太死可能是瓶颈。

Gurobi的精确解反而给了启发——把混合整数规划模型的松弛解作为NSGA-II的初始种群，收敛速度提升了40%。不过要注意Python和MATLAB之间的变量转换，特别是稀疏矩阵的存储格式差异，用scipy.io的savemat时得强制类型转换才不会报错。

这种级别的组合优化问题，可能更适合用分解式多目标框架。下次打算试试把车辆路径和货物分配拆成两个子问题，用协同进化策略来做，说不定能让Pareto前沿稍微像样点。不过内存占用估计要爆炸，得先升级服务器配置了...