旅行商和车辆路径问题是组合优化问题，是很多工程优化问题的基本原型。

旅行商问题：N个城市，找到一条路径遍历这些程序，追求距离最小。例如：五个城市1,2,3,4,5，一条路径为3-2-1-4-5.

车辆路径问题：N个客户，一个调度中心，构建几条车辆路径，从调度中心出发，访问几个客户，返回调度中心。例如：五个客户1,2,3,4,5，调度中心0,两条路径为0-1-2-0,0-4-3-5-0.

两个问题是接驳公交、车间作业调度、手术排班、飞行计划排班、跑道进离场排序等问题的问题原型，研究内容和形式相似，可以解决该问题的数学模型和算法求解思路、框架。

以遗传算法求解旅行商和车辆路径问题的思路为了，核心在于染色体编码，主要思路有二：

第一、自然数编码，以10个客户为例，如果旅行商问题可以编码为3-2-1-4-5-6-7-8-9-10，如果车辆路径问题（两辆车），采用n+2模式，编码为12-3-2-1-11-4-5-6-7-8-9-10，以11和12为辆车，解码为车辆2:3-2-1 车辆1:4-5-6-7-8-9-10

第二、实数或整数编码，对车辆路径问题，先确定每个客户的被分配车辆，然后利用最短路算法确定路径。例如：五个客户、辆车2的编码为1 2 1 1 2，车辆1访问1、3、4、车辆2访问3和5，它们的顺序由最短路确定

在此基础上，如果需要确定车辆的出发时刻表，增加染色体的维度，即：1 2 1 1 2 6:30 6:40

嵌入Dijkstra的遗传算法部分代码如下：

______________________________初始化过程_____________________________________________

MaxCapicity=12;

StartTime=360; %1小时内的车辆调度

Costomers=[2   1   2    2   2   2   1   2    2  2    2   1   2   2   2    2   1   2   2   2    2   1  2    2   2   2   1   2     2   2   1    1   2;

510 500 480  400 600 480 400 400  370 460 390 450 380  380 380 400 480 390  420 410 390 480 490  480 430 460 400 600  470 470 400  480 480 ;

520 510 490  410 610 500 430 430  390 480 420 480 400  410 400 420 510 420  430 430 420 500 510  510 450 470 430 610  480 490 410  500 490 ;

30 30 30 30  30 30 30 30 30  30 30 30 30 30  30 30 30 30 30  30 30 30 30 30  30 30 30 30 30  30 30 30 30;];%人数，客户点起讫时间窗,最大在车时间等

NumberOfCostomers=size(Costomers,2);

NumberOfRoutes=6;

lb = repmat(1,1,NumberOfCostomers );

ub =  repmat(NumberOfRoutes , 1,NumberOfCostomers );

lb =[lb , repmat(1,1,NumberOfRoutes )];

ub = [ub, repmat(NumberOfDepots , 1,NumberOfRoutes )];

lb =[lb , repmat(0,1,NumberOfRoutes )];

ub = [ub, repmat(60 , 1,NumberOfRoutes )];

options = gaoptimset('stallGenLimit',200,'TolFun',1e-10,'ParetoFraction',0.3,'EliteCount',0.05*PopulationSize,'CrossoverFraction',0.8, 'PopulationSize', PopulationSize,'Generations', 5000,'PlotFcn',@gaplotpareto);

[x,Fval,exitFlag,Output] = gamultiobj(@GA_fun, NumberOfCostomers+2*NumberOfRoutes, [], [], [], [], ...

lb, ub, [], options);

____________________________解码过程____________________________________________________

function Fitness = GA_fun(chrom)

busTask=zeros(NumberOfRoutes,51);

for eachtrip=1:NumberOfCostomers

%提取不同飞机跑道的起飞降落航班分配

eachbus=round(chrom(eachtrip));

busTask(eachbus,51)= busTask(eachbus,51)+1;

busTask(eachbus,busTask(eachbus,51))=eachtrip;

routeCapicity(eachbus)=routeCapicity(eachbus)+Costomers(1,eachtrip);

end

%各个班次在跑道的排序

for eachbus=1:NumberOfRoutes

if busTask(eachbus,51)>0&& busTask(eachbus,51)< NumberOfCostomers/(NumberOfRoutes-2)

if routeCapicity(eachbus)>MaxCapicity

Fitness(2)=publishment;

break;

end

Fitness(2)= Fitness(2)+120;

%起始节点包含其中，结束节点不包括在内，故应该另外增加进去

startPoint=NumberOfCostomers+round(chrom(NumberOfCostomers+eachbus));

endPoint=NumberOfCostomers+NumberOfDepots+1;

%        busTask(eachbus,1:busTask(eachbus,51))

routeSet=Dijkstra(NumberOfCostomers+NumberOfDepots+1,Distance,busTask(eachbus,1:busTask(eachbus,51)),startPoint,endPoint);

route=GetRoute(busTask(eachbus,1:busTask(eachbus,51)),routeSet,startPoint);

eachRoutePassenger=eachRoutePassenger+Distance(route(i-1),route(i));

end

else

Fitness(2)=publishment;

end

end

Fitness2=Fitness(1);

魏明 中国民航大学空中交通管理学院

魏明的学术名片