关于VRPTW的问题，我在之前的⽂章⾥都有介绍，再次不过多叙述。
那么带充电桩的电动汽车路径规划问题该怎么求解呢？
⾸先，我们要知道，带充电桩的电动汽车路径规划多了⼀个什么样的约束：即电动汽车在配送的过程中是消耗电量的，电量不⾜时，则需要对电动车进⾏充电。
那么我们分析这⼀句话。⾸先第⼀部分，电动车消耗电量。简单的处理⽅式就是电动车的电量和续航⾥程成正⽐，这个时候我们只需要关注电动车的续航⾥程就⾏，电动车⾏驶了多少距离，那么续航⾥程就减少多少。另⼀种处理⽅式，就是电动车的电量消耗和⾏驶距离及其他参数有⼀个函数，这个时候就⽐较⿇烦，但是最终还是要把电量转换成续航⾥程，看电动车能跑多远。
第⼆句：电量不⾜时，则需要对电动车进⾏充电。电量不⾜的意思不仅仅是说电动车不能到下⼀个客户点，还要保证电动车能够到达充电桩，这个问题就是这类问题的难点。所以，电动车在配送的过程中，要始终保证电动车可以到达下⼀个客户点及与下⼀个客户点最近的充电桩，如果不能满⾜这个关系，则电动车需要在当前客户点直接寻充电桩进⾏充电。(如果你理解不了这句话，那就多读⼏遍，并画图演⽰)。
根据上⾯的分析加上遗传算法求解VRPTW的基础，就可以编程解决这个问题了。
在此我要多说⼀句，我看了很多关于遗传算法求解带充电桩的电动汽车路径规划问题的相关论⽂，有⼀些是985⾼校的硕⼠论⽂。但是有⼀个问题就是，他们把充电桩作为客户点的⼀部分进⾏编码，然后参加交叉变异等操作，这些⽅法有个很致命的问题就是：对于客户点，他们必须都要经过且只能经过⼀次，这适⽤于⾃然数编码以及与其相应的交叉、变异⽅法，但是充电桩不是这样的，对于每⼀个充电桩是可以去多次的，也可以⼀次都不去。因此把充电桩当作客户点进⾏编码及交叉变异，是极其不合理的。
下⾯是我写的程序的运⾏结果。
数据1：
数据2：
数据3：
所有程序⽂件：
附录：matlab主函数
%%%% 遗传算法求解带充电桩的VRP问题
%%%% by 圆 ⼀个有⼼的⼈在⽤⼼做事
%%%% 2019-05-05
315汽车%%%% 如有问题请联系
QQ530807088(已满)/3171304690 新浪微博:MATLAB圆创⼯作室
% ======================= ⾼ 端 定 制 · 华 丽 分 割
======================
clc
clear
tic
data = xlsread('数据1.xlsx',1,'A:F');
position = data(:,2:3);
demand = data(:,4);
ET = data(:,5); % 早到时间
LT = data(:,6); % 晚到时间
CarLoad = 2; % 汽车最⼤载重量
CarDist = 100; % 汽车续航⾥程
CarDistance = 3000; % 汽车最⼤⾏驶距离CityNum = 40; % 需求点数量
CarNum = 3;% (⽆⽤)
ChargeNum = 20; % 充电桩数量
NP = 200; % 种⼤⼩
maxgen = 1500; %
最⼤进化代数
Pc = 0.8; % 交叉概率
Pm = 0.2; % 变异概率
Gap = 0.9; % 代沟(Generation gap)
speed = 50;
fitmax = 10000000;
c0 = 200;
c1 = 12;
c2 = 50; % 充电⼀次的费⽤
ST = [0; ones(CityNum + ChargeNum,1) * 0.5]; % 服务时间
CE = 24; %
早到惩罚系数
CL = 24; %
晚到惩罚系数
%% 计算各城市之间的距离
distance = zeros(CityNum+1 + ChargeNum); for i = 1 : CityNum +
ChargeNum + 1
i + 1 : CityNum + ChargeNum + 1
distance(i,j) =
((position(i,1)-position(j,1))^2+(position(i,2)-position(j,2))^2)^0.5
/ 180 * pi * 6371;
distance(j,i) =
distance(i,j);
end
end
figure(1)
plot(position(1,1),position(1,2),'b^','MarkerFaceColor','r','MarkerSize',13)
hold on
plot(position(2:CityNum +
1,1),position(2:CityNum +
1,2),'ro','MarkerFaceColor','b','MarkerSize',6,'LineWidth',0.5)
plot(position(end-ChargeNum+1:end,1),position(end-
ChargeNum+1:end,2),'bs','MarkerFaceColor','g','MarkerSize',8,'LineWidth',0.5) for i = 1 : CityNum + 1 + ChargeNum
text(position(i,1) + 0.005,position(i,2),num2str(i-1))
end
title('路径优化前各类型节点分布图')
xlabel('坐标X')
ylabel('坐标Y')
runtime = 1;
for run = 1 : runtime
%%
路径初始化
X=
initpop(NP, CityNum, demand, CarLoad);
Xa =
X(1,:);
%%
迭代
gen=1;
gen<=maxgen
gen
% 计算适应值矩阵
[allcost,fit]=fitness(distance,demand,X,CarDist,CarLoad,ET,LT,ST,CE,CL,speed,fitmax,CityNum,ChargeNum,CarNum,c0,c1,c2);
%出最优个体适应值
[leastcost,bestindex]=min(allcost);
bestindex=bestindex(1);
fpbest(gen)=leastcost; %
最⼩适应值fit的集
pbest(gen,:)=X(bestindex,:);%
最优个体集
% 选择
XSel=Select(X,fit,Gap);
% 交叉操作
XSel=Cross(XSel,Pc);
% 变异
XSel = Mutate(XSel,Pm);
% 逆转操作
if gen > 2 *maxgen / 4
XSel =
Reverse(distance,demand,XSel,CarDist,CarLoad,ET,LT,ST,CE,CL,speed,fitmax,CityNum,ChargeNum,CarNum,c0,c1,c2);
end
% 重插⼊⼦代的新种
X=Reins(X,XSel,fit);
gen=gen+1;
end
%
出最优的适应值、个体
[minfpbest,minindex]=min(fpbest);% 取最优适应值的位置、最优适应值
minindex=minindex(1);
gbest=pbest(minindex,:); % 取最优个体
XR(run,:) = gbest;
PR(run,1) = minfpbest;
end
[fgbest,id] = min(PR);
gbest = XR(id(1),:);
fpbest = GR(id(1),:);
%% 输出最优解的路线和总距离
disp('最优配送路径:')
route =
OutputPath(distance,demand,gbest,CarDist,CarLoad,ET,LT,ST,CE,CL,speed,fitmax,CityNum,ChargeNum,CarNum,c0,c1,c2); %% 计算结果数据输出
disp(['最优⾏驶路径成本为：',num2str(fgbest)]);
%% 绘制实际路线
figure(2)
plot(position(1,1),position(1,2),'b^','MarkerFaceColor','r','MarkerSize',13)
hold on
plot(position(2:CityNum +
1,1),position(2:CityNum +
1,2),'ro','MarkerFaceColor','b','MarkerSize',6,'LineWidth',0.5)
plot(position(end-ChargeNum+1:end,1),position(end-
ChargeNum+1:end,2),'bs','MarkerFaceColor','g','MarkerSize',8,'LineWidth',0.5)
for i = 1 : CityNum + 1 + ChargeNum
text(position(i,1) + 0.005,position(i,2),num2str(i-1))
end
ccc = [1 0 0
0 1
0 0
1
1 0
1
0.8 0.2
1
0 0
发布评论