matlab-基于ACO蚁群优化算法解决CDVRP问题,CVRP问题,DVRP问题,TSP问题以及VRPTW问题-源码

clc; clear; close all; warning off; addpath(genpath(pwd)); tic % 保存当前时间 %% 蚁群算法求解VRPTW %输入： %City 需求点经纬度 %Distance 距离矩阵 %TravelTime 行驶时间矩阵 %Demand 各需求点需求量 %Travelcon 行程约束 %Capacity 车容量约束 %TimeWindow 各需求点时间窗 %AntNum 种群个数 %Alpha 信息素重要程度因子 %Beta 启发函数重要程度因子 %Rho 信息素挥发因子 %Q 常系数 %Eta 启发函数 %Tau 信息素矩阵 %MaxIter 最大迭代次数 %输出： %bestroute 最短路径 %mindisever 路径长度 %% 加载数据 load('../test_data/City.mat') %需求点经纬度，用于画实际路径的XY坐标 load('../test_data/Distance.mat') %距离矩阵 load('../test_data/TravelTime.mat') %行驶时间矩阵 load('../test_data/Demand.mat') %需求量 load('../test_data/TimeWindow.mat') %时间窗 load('../test_data/Travelcon.mat') %行程约束 load('../test_data/Capacity.mat') %车容量约束 %% 初始化问题参数 CityNum = size(City,1)-1; %需求点个数 %% 初始化参数 AntNum = 8; % 蚂蚁数量 Alpha = 1; % 信息素重要程度因子 Beta = 5; % 启发函数重要程度因子 Rho = 0.1; % 信息素挥发因子 Q = 1; % 常系数 Eta = 1./Distance; % 启发函数 Tau = ones(CityNum+1); % (CityNum+1)*(CityNum+1)信息素矩阵 初始化全为1 Population = zeros(AntNum,CityNum*2+1); % AntNum行,(CityNum*2+1)列 的路径记录表 MaxIter = 100; % 最大迭代次数 bestind = ones(MaxIter,CityNum*2+1); % 各代最佳路径 MinDis = zeros(MaxIter,1); % 各代最佳路径的长度 %% 迭代寻找最佳路径 Iter = 1; % 迭代次数初值 while Iter <= MaxIter %当未到达最大迭代次数 %% 逐个蚂蚁路径选择 for i = 1:AntNum TSProute=2:CityNum+1; %生成一条顺序不包括首尾位的升序TSP路线 VRProute=[]; %初始化VRP路径 while ~isempty(TSProute) %开辟新的子路径 subpath=1; %先将配送中心放入子路径起点 DisTraveled=0; %此子路径的距离初始化为零 CurrentTime=0; %车辆已行驶时间置零 delivery=0; %此子路径的车辆可配送量初始化为零 delete=subpath; %delete(end)=1给第一次进入内while的P(k)首项用 while ~isempty(TSProute) %为子路径subpath第二个及以后的位置安排需求点 %% 计在内while中计算城市间转移概率 P = TSProute; % 为轮盘赌选择建立等于剩余需经过城市数量的长度的向量 for k = 1:length(TSProute) %delete(end)为刚刚经过的城市，TSProute(k)为剩余可能经过的城市 P(k) = Tau(delete(end),TSProute(k))^Alpha * Eta(delete(end),TSProute(k))^Beta; %省略相同分母 end P = P/sum(P); % 轮盘赌法选择下一个访问城市 Pc = cumsum(P); %累加概率 TargetIndex = find(Pc >= rand); %寻找左数第一个大于伪随机数的累加概率的索引 target = TSProute(TargetIndex(1)); %此索引对应的城市 %不要强行改变蚂蚁通过轮盘法选到的下一个城市 %它选到就确定了，然后如果超约束，结束此subpath %判断行程约束 if delivery+Demand(target) > Capacity || DisTraveled+Distance(delete(end),target)+Distance(target,1) > Travelcon break else DisTraveled=DisTraveled+Distance(delete(end),target); %若符合，则经过的距离累加此距离 CurrentTime=max(CurrentTime+TravelTime(delete(end),target),TimeWindow(target,2)); %当前时间累加，并与该需求点早时间窗比较得出开始服务时间 delivery = delivery+Demand(target); %车辆已配送量累加 %此点加入子路径 subpath=[subpath,target]; %此点加入要删除的点序列 delete=[delete,target]; %TSP路径中排除已安排的城市 TSProute=setdiff(TSProute,delete); end end %内while结束，此subpath结束 %直接在VRProute后面填充这条子路径 VRProute=[VRProute,subpath]; end %外while结束，此VRProute完整 %在VRProute后未到CityNum*2+1的空位填入1 fillwithones = linspace(1,1,CityNum*2+1-length(VRProute)); VRProute=[VRProute,fillwithones]; %把成型的VRP路径赋给种群矩阵 Population(i,:)=VRProute; end %% 计算各个蚂蚁的路径距离 ttlDistance = zeros(AntNum,1); %预分配内存 for i = 1:AntNum DisTraveled=0; % 蚂蚁子路径已经过的距离 CurrentTime=0; %所有车辆行驶时间置零 delivery=0; % 汽车已经送货量，即已经到达点的需求量之和 Dis=0; %此蚂蚁所有子路径的总距离 route = Population(i,:); %单独取出一只蚂蚁的路线 for j=2:length(route) DisTraveled = DisTraveled+Distance(route(j-1),route(j)); %每两点间距离累加 if route(j)==1 %若此点是配送中心 if DisTraveled > Travelcon %若超行程约束 Dis = Inf; %对非可行解进行惩罚 break else Dis=Dis+DisTraveled; %累加已行驶距离 DisTraveled=0; %已行驶距离置零 CurrentTime=0; %时间置零TimeWindow(1,2) delivery=0; %可配送量置零 end else %若此点非配送中心 if DisTraveled > Travelcon %若超行程约束 Dis = Inf; %对非可行解进行惩罚 break else delivery = delivery+Demand(route(j)); %累加可配送量 if delivery > Capacity %若超容量约束 Dis = Inf; %对非可行解进行惩罚 break else CurrentTime=CurrentTime+TravelTime(route(j-1),route(j)); %计算车辆到达需求点的时刻 if CurrentTime > TimeWindow(route(j),2) %将晚时间窗是否超约束放到route(j)是否=1外判断，防止route(j)=1时TW=0始终超约束的错误判断，这一步也是为什么要将route(j)是否为1分开判断的原因 Dis = Inf; %对非可行解进行惩罚 break else CurrentTime=max(CurrentTime,TimeWindow(route(j),2));%若到达时间早于早时间窗，等待至早时间窗 end end end end end ttlDistance(i)=Dis; %存储此方案总距离 end %% 存储历史最优信息 if Iter == 1 %若是第一次迭代 不需要与上次迭代结果对比 [min_Length,min_index] = min(ttlDistance); %取得此次迭代最短距离 MinDis(Iter) = min_Length; %存储此次迭代最优路线的距离 bestind(Iter,:) = Population(min_index,:); %存储此次迭代最优路径 else [min_Length,min_index] = min(ttlDistance); %取得此次迭代最短距离