带时间窗的电动汽车路径规划（智能算法求解）
⼀、问题概述
随着电动汽车环保和购买使⽤的经济性，越来越普及到社会⽣产和⽣活中，也逐渐成为了科研研究的⼀⼤热点。主要包括电动汽车的充换电问题，充电桩换电站选址定容问题，路径规划问题等等。今天，我们主要谈⼀下电动汽车的路径规划问题。
燃油车的路径规划问题从最简单的TSP问题被提出和解决，演变到VRP问题，以及VRP问题的各种复杂情况，带时间窗的，静态的，动态的等等，不⼀⽽论。⽽电动汽车的路径规划问题因单次⾏驶⾥程不长以及充换电消耗路程和时间，成为其路径规划不得不考虑的重要约束条件，其复杂性也体现在此。下⾯我将重点讨论带时间窗的充电电动汽车的路径规划的求解思路和算法流程。
⼆、⽬标函数
⾸先，带时间窗的充电式电动汽车的路径问题的⽬标函数主要为⼀系列成本之和最⼩，⼀般包括固定成本，运营成本，充电成本，时间窗惩罚成本等等。其他成本也可以考虑，多⽬标时也可计算。
三、约束条件
⼀般包括以下5条。
1. 单次⾏驶⾥程约束
2. ⽇最⼤⾏驶⾥程约束（⽇最⼤⼯作时长约束）
3. 时间窗约束
4. 载重约束
(1) 单次⾏驶⾥程约束
电动汽车满电状态下最多⾏驶的⾥程数，⼀般会参考设计最⼤⾏驶⾥程乘以⼀个系数求出，⼀般电动车辆电量降到20%时，容易怠机。因此系数可取80%。
(2) ⽇最⼤⾏驶⾥程约束（⽇最⼤⼯作时长约束）
为了可持续的使⽤以及降低车辆的保养维修费，往往每天设定车辆最⼤的⾏驶公⾥数，或者按照司机每天的最⼤⼯作时长进⾏约束。
(3) 时间窗约束
顾名思义，车辆到达配送的客户的时间要满⾜⼀定的时间窗约束，否则将会产⽣等待成本和惩罚成本。
(4) 载重约束
车辆配送的载货量不得超过最⼤载货量。
四、算法设计
此处，可选择的算法有蚁算法、粒⼦和遗传算法，⽐较容易实现的算法应该是遗传算法和蚁算法。下⾯以遗传算法为例，讲⼀点⼲货。
1. 染⾊体编码
遗传算法求解电动汽车的路径规划问题，⼀般采⽤⾃然数编码，通常有随机⽣成和其他⽅法⽣成初始解两种。
随机⽣成：通过⽣成的从1到N（客户数量）的随机⾃然数排列，表⽰客户的配送次序，通过载重约束和⽇最⼤⾏驶⾥程约束，将其划分为若⼲辆车。⽣成配送车辆的初始路径。
初始解：通过最⼩近邻法或者最短路算法⽣成路程较少的客户配送次序，通过载重约束和⽇最⼤⾏驶⾥程约束，将其划分为若⼲辆车。⽣成配送车辆的初始路径。
2. 适应度函数
适应度函数为总成本的倒数。
总成本的计算要计算各⼦成本。
⽣成的初始配送路径仍然需要考虑除了载重约束、⽇最⼤⾏驶⾥程约束以外的其他两个约束。
需要在满⾜两个约束的条件下，选择合适的充电桩进⾏充电，充电时长⼀般分为固定时长和⾮固定时长，其难度⼜⼤不⼀样。若为固定时长，则⽐较容易计算，若为⾮固定时长，则需要根据配送的成本倒推选择合适的充电时长。
3. 选择
选择算⼦有竞标赛，赌和精英策略三种，可适当选择⼀种。
4. 交叉
交叉算⼦有单点交叉，⽚段交叉和对称交叉等，适当选择即可，同时，要注意交叉后不可⾏解的复杂处理。
5. 变异
变异算⼦有交换变异和随机变异等，适当选择即可，同时，要注意变异后不可⾏解的复杂处理。
6. 重组
将⼦代和⽗代重新组合成新的种。
7. 最优解和可视化输出
输出最优解，并可视化输出配送路径和迭代曲线图。
五、举例
（1）总成本计算代码举例：
function [Cost,costarray]=totalcost(tabu_list,n)
%%固定成本+变动成本+充电成本+惩罚成本+环境成本
PowerConsumption=27;%百公⾥耗电量
太平洋汽车网ChargePrice=1.2;%充电平均电价
F=100;%单车固定成本
per_km=5;%单位公⾥⾏驶成本
Chj=0.315;%元/kg 碳排放环境成本
Hrate=0.72;%⽕⼒发电占⽐；
Erate=0.94;%电能转换系数；
Eprice=0.82;%单位电价
悍马 h1SatiCost=zeros(n,1);
for i=1:n
saticost=0;
Satif=cell2mat(tabu_list(i,7));
Satif(Satif>1)=0;
for j =1:size(Satif,1)
saticost=saticost+max(0.7-Satif(j,1),0)*300;
end
SatiCost(i,1)=saticost;%满意度
end
fixCost=cell2mat(tabu_list(:,5))*F;%固定成本
runCost=per_km*cell2mat(tabu_list(:,4));
chargeCost=Eprice*PowerConsumption*cell2mat(tabu_list(:,4))/100;%变动成本punishCost=cell2mat(tabu_list(:,6));%充电成本
envCost=PowerConsumption*cell2mat(tabu_list(:,4))/100*Erate*Hrate*Chj;%环境成本%Cost=fixCost + runCost + chargeCost + punishCost + envCost + SatiCost;
Cost=fixCost + runCost + chargeCost + punishCost + envCost ;
costarray=[fixCost,runCost,chargeCost,punishCost,envCost,Cost];
end
（2）约束处理代码举例
function [Weight_remainder2,Max_remainder_dis2,Charge_remainder_dis2]=ThreeRestrain(current,remainder,Max_remainder_dis,Charge_remainder_di s,Weight_remainder,S)
%到满⾜三约束的点：满⾜车载容量（<=40），剩余电量续驶⾥程（已⾏驶距离要⼩于7），最剩余单车⽇⾏驶⾥程(<=15)
长城哈弗h8%[n,B,XY,dis,tw1,tw2,Q,QQ,per_km,max_hour,v,F,P_max,P0,W,...
%    PowerConsumption,ChargePrice,s,Charge_station,D]=data();
%%
%global n B XY dis tw1 tw2 Q QQ per_km max_hour v F P_max P0 W PowerConsumption ChargePrice s Charge_station
%计算选择剩余未选点后的三个状态变量
%%
n=S.n;%客户数量
B=S.B;%充电桩数量
NV=S.NV;%所有点的个数：客户+充电桩+1
XY=S.XY;%所有点坐标
tw1=S.tw1 ;%时间窗
tw2=S.tw2;
W=S.W;%需求量
Set=S.Set;%服务时长
disXY=S.dpXY;%配送中⼼坐标
csXY=S.csXY;%充电桩坐标
Charge_station=S.Charge_station;%充电桩对应编号22：25
dis=S.dis;
Q=S.Q;%最⼤载重量
QQ=S.QQ;
per_km=S.per_km;%单位公⾥⾏驶成本
max_hour=S.max_hour;%⼀天最⼤⾏驶时长（⼩时）
v=S.v;%平均车速
F=S.F;%单车固定成本
P_max=S.P_max;%单车⽇⾏驶⾥程
P0=S.P0;%单次充电续驶⾥程上海收购二手车
%
PowerConsumption=S.PowerConsumption;%百公⾥耗电量
ChargePrice=S.ChargePrice;%充电平均电价
电瓶车电池保养%%
Weight_remainder2=(Weight_remainder-W(remainder));
Max_remainder_dis2=Max_remainder_dis-dis(current,remainder)-dis(1,remainder);
if sum(Max_remainder_dis2>=0)<length(remainder)%表⽰不都是第⼀种三约束，即存在⼩于0的点
[rol_1,col_1]=find(Max_remainder_dis2<0);%到第⼆种三约束的点汽车违章查询系统
[rol_2,col_2]=min(dis(remainder(col_1),Charge_station)');%到距离最近的充电桩编号
Max_remainder_dis2(col_1)=Max_remainder_dis2(col_1)+dis(1,remainder(col_1))-min(dis(remainder(col_1),Charge_station)')-dis(1,Charge_station(col _2));
end
Charge_remainder_dis2=Charge_remainder_dis-dis(current,remainder)-min(dis(remainder,Charge_station)');
（3）输出结果举例
六、总结展望
有任何问题请留⾔或者私信咨询，⼀起学习进步加油！