科学网旅行商问题车辆路径问题
旅行商和车辆路径问题是组合优化问题,是很多工程优化问题的基本原型。
旅行商问题: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);
魏明 中国民航大学空中交通管理学院
魏明的学术名片
同类文章排行
- 2019年广东公务员考试面试热点练习(62)
- 2019年广东公务员考试面试热点练习(57)
- 津巴布韦总理称上周车祸是意外
- 持居留条回国 旅游千万不要打擦边球
- 英国计划斥资4000万镑帮白领找工作
- 王健林又悄悄卖了几家万达广场!保险、信托接
- 2019年深圳公务员考试公告
- 俄罗斯醉酒外交官在飞机上与人打架迫使飞机返
- 2019年广东公务员考试面试热点练习(56)
- 2020年广东公务员面试模拟题:大学生贷款享受优惠政策
最新资讯文章
- 梅德韦杰夫承认俄罗斯经济被危机重创
- 伊朗又试射了一枚远程导弹
- 朝鲜最高司令部要求做好一切战斗准备
- 持居留条回国 旅游千万不要打擦边球
- “外交为民”新举措 罗马地区侨团联络会正式成
- 以色列称伊朗已跨越核武技术门坎
- 美军文件公开宣称以色列为有核国家
- 俄罗斯专家称中国应向北约开放瓦罕走廊
- 伊拉克发生自杀式袭击28人死亡57人受伤
- 关塔那摩囚犯称英军情五处串通CIA对其酷刑
- 奥地利兽父案下周开审 乱伦父刑期或少于10年
- 苏丹总统:决不向殖民主义和国际刑事法院屈服
- 朝鲜切断朝韩陆路通行线 620名韩国人被困当地
- 日本首相麻生再次表示美国对钓鱼岛立场没变
- 委内瑞拉将建立人民公社大食堂
- 马达加斯加军营哗变 士兵拒绝向民众开枪(组图
- 美韩展开12天联合军演 7艘宙斯盾舰参加
- 日本发明新型遥控器 脸部肌肉可遥控家电(图)
- 英国计划斥资4000万镑帮白领找工作
- 世行报告称全球经济将现二战后首“负”