航运策略优化设计遗传算法数学综合训练.docx
- 文档编号:13256386
- 上传时间:2023-06-12
- 格式:DOCX
- 页数:36
- 大小:135.90KB
航运策略优化设计遗传算法数学综合训练.docx
《航运策略优化设计遗传算法数学综合训练.docx》由会员分享,可在线阅读,更多相关《航运策略优化设计遗传算法数学综合训练.docx(36页珍藏版)》请在冰点文库上搜索。
航运策略优化设计遗传算法数学综合训练
航运策略优化设计
摘要
航班的规划是指对航空公司的资源(如飞机、航线、资金、人员等)进行调度,并且规定正班飞行的航线、机型、飞行频率及班期时刻。
根据市场分析和预测结果对航班的频率进行确定,并对机型进行指派。
建立数学模型确立航班调度方案,并做出相关分析。
本文通过运用遗传算法,模拟达尔文生物进化论的自然选择和遗传学机理的生物进化过程,建立了以广州为中心的航班网络模型,通过初始化50组基因型,杂交迭代500代,以此得到适应度最好的个体,寻求航班收益的最大化。
最后在附录中列出了运算数据和主要程序的代码。
关键词:
遗传算法;适应度;遗传算子;
一、问题重述
在飞机调度问题的流程中,航班规划属于市场规划的范畴。
通常由市场部根据机务部调度员提供的次日可用每种机型和飞机架数以及其它的具体的实际情况制定次日的航班计划。
航班计划的制定在很多情况下依赖于工作人员的经验,但是随着科技的发展,航空公司的航线不断增加,飞机数也在不断增加,使用人工来进行排班便成了一件消耗时间和精力而且极难完成的事。
所以,使用算法对飞机的航班进行规划是必然的时代进步,科学、高效的排班计划是算法可以满足的。
实验要求根据已给的航班信息,对各个航线每天的航班进行分配,以取得最大的日盈利。
图一:
广州——香港——上海——北京航线网络图
根据附件所提供的数据,建立模型分析解决下面的问题:
问题一:
通过题目给出的机型数据、每条航线的票价、客座率、运行成本,计算出航班飞往目的地单程的获利。
给出盈利的计算公式。
问题二:
航班飞往香港、北京、上海的耗时、盈利均有所差异,评估航班安排对于获利的影响。
问题三:
广州——香港线与广州——上海线均有机型限制,737-800机型不能飞往上海,757-200机型不能飞往香港。
同时有航班次数上限与下限的要求。
在满足约束条件的情况下,制定出有利于获利最大化的航班安排策略。
二、问题假设
1.是否存在着某条航线,使得飞该条航线的航班越多,获利越大。
2.是否存在着唯一的解,使得获利最大化。
三、符号说明
POPSIZE——初始化种群的数量
MAXGENS——杂交的代数
NVARS——染色体的个数
PXOVER——杂交的概率
PMUTATION——变异的概率
TP1——飞广州——北京线的737-800航班
TP2——飞广州——北京线的757-200航班
TS——飞广州——上海线的757-200航班
TH——飞广州——香港线的737-800航班
四、问题分析
1、对航班线路获利的分析
欲获得最大盈利,首先应当分析每架航班单程的获利。
经分析得:
单程收入为:
客座率*座位数*票价
单程支出为:
飞行时长*小时运营成本
单程盈利为单程收入减去单程支出,即:
客座率*座位数*票价-飞行时长*小时运营成本
根据已知信息,可以制表如下:
表一:
飞往北京的航班
737-800(TP1)
757-200(TP2)
座位容量
168
200
票价
1500
1500
客座率
0.9
0.9
航程所需时间
3.0
3.1
小时运营成本
30000
40000
收入
226800
270000
支出
90000
124000
盈利
136800
146000
表二:
飞往上海的航班
757-200(TS)
座位容量
200
票价
1200
客座率
0.7
航程所需时间
2.0
小时运营成本
40000
收入
168000
支出
80000
盈利
88000
表三:
飞往香港的航班
737-800(TH)
座位容量
168
票价
600
客座率
0.2
航程所需时间
0.56
小时运营成本
30000
收入
20160
支出
16800
盈利
3360
2、对于航班模型约束条件的分析
在航班规划模型中,存在着许多客观约束条件,只有满足这些约束条件,系统才可以正常运行。
(1)日利用率问题。
737-800的日利用率为10h,因此每架737-800的日飞行时间最多为10小时。
故对于每架737-800,皆需满足:
3.0(广——北线单程所需时间)*TP1(广——北线日飞行次数)+0.56(广——港线单程所需时间)*TH(广——港线日飞行次数)<=10.0。
757-200的日利用率为11h,因此每架757-200的日飞行时间最多为11小时。
故对于每架757-200,皆需满足:
3.1(广——北线单程所需时间)*TP1(广——北线日飞行次数)+2.0(广——上线单程所需时间)*TS(广——上线日飞行次数)<=11.0。
(2)航班班次问题
飞往北京的下限班次为5,上限班次为20。
即每日飞往北京的737-800次数+每日飞往北京的757-200次数需大于等于5,小于等于20。
飞往上海的下限班次为4,上限班次为20。
即每日飞往上海的757-200次数需大于等于4,小于等于20。
飞往香港的下限班次为3,上限班次为20。
即每日飞往香港的737-800次数需大于等于3,小于等于20。
(3)航班出发问题
对于每架737-800航班,应满足以下情况之一。
A.航班从广州出发,飞广州——北京线的次数为偶数,飞香港——广州线的次数为偶数,当天最终降落在广州。
B.航班从广州出发,飞广州——北京线的次数为偶数,飞香港——广州线的次数为奇数,每日分别最终降落在香港、广州、香港、广州。
C.航班从广州出发,飞广州——北京线的次数为奇数,飞香港——广州线的次数为偶数,每日分别最终降落在北京、广州、北京、广州。
航班从广州出发,飞广州——北京线的次数为奇数,飞香港——广州线的次数为奇数的情况不满足约束条件。
对于每架757-200航班,应满足以下情况之一。
D.航班从广州出发,飞广州——北京线的次数为偶数,飞上海——广州线的次数为偶数,当天最终降落在广州。
E.航班从广州出发,飞广州——北京线的次数为偶数,飞上海——广州线的次数为奇数,每日分别最终降落在上海、广州、上海、广州。
F.航班从广州出发,飞广州——北京线的次数为奇数,飞上海——广州线的次数为偶数,每日分别最终降落在北京、广州、北京、广州。
航班从广州出发,飞广州——北京线的次数为奇数,飞上海——广州线的次数为奇数的情况不满足约束条件。
五、模型的建立
航班规划模型:
1、算法简述
遗传算法也是计算机科学人工智能领域中用于解决最优化的一种搜索启发式算法,是进化算法的一种。
这种启发式通常用来生成有用的解决方案来优化和搜索问题。
进化算法最初是借鉴了进化生物学中的一些现象而发展起来的,这些现象包括遗传、突变、自然选择以及杂交等。
遗传算法在适应度函数选择不当的情况下有可能收敛于局部最优[1] ,而不能达到全局最优。
遗传算法的基本运算过程如下:
a)初始化:
设置进化代数计数器t=0,设置最大进化代数T,随机生成M个个体作为初始群体P(0)。
b)个体评价:
计算群体P(t)中各个个体的适应度。
c)选择运算:
将选择算子作用于群体。
选择的目的是把优化的个体直接遗传到下一代或通过配对交叉产生新的个体再遗传到下一代。
选择操作是建立在群体中个体的适应度评估基础上的。
d)交叉运算:
将交叉算子作用于群体。
遗传算法中起核心作用的就是交叉算子。
e)变异运算:
将变异算子作用于群体。
即是对群体中的个体串的某些基因座上的基因值作变动。
群体P(t)经过选择、交叉、变异运算之后得到下一代群体P(t+1)。
f)终止条件判断:
若t=T,则以进化过程中所得到的具有最大适应度个体作为最优解输出,终止计算。
2、建立模型
由于737-800日使用率为10h,飞往北京需3.0h,故每日飞往北京的最大次数为3次,可用两位二进制码将其表示出来。
(00、01、10、11分别表示该航班飞往北京0、1、2、3次)。
飞往香港最大次数为17次,可用五位二进制码表示。
即对于每架737-800,均可用形为AABBBBB的七位二进制串表示其飞行状态。
总共三架737-800,共需21位表示其状态。
由于757-200日使用率为11h,飞往北京需3.1h,故每日飞往北京的最大次数为3次,可用两位二进制码将其表示出来。
飞往上海需要2.0h,每日飞往上海最多6次,可用三位二进制码表示,即对于每架757-200,均可用形为CCDDD的五位二进制码表示其飞行状态。
总共有五架757-200,共需25位表示其状态。
(1)定义总长度为46位的染色体,表示全部航班的飞行状态。
其中:
第1-2位表示737-800
(1)飞北京——广州线的次数。
第3-7位表示737-800
(1)飞香港——广州线的次数。
第8-9位表示737-800
(2)飞北京——广州线的次数。
第10-14位表示737-800
(2)飞香港——广州线的次数。
第15-16位表示737-800(3)飞北京——广州线的次数。
第17-21位表示737-800(3)飞香港——广州线的次数。
第22-23位表示757-200
(1)飞北京——广州线的次数。
第24--26位表示757-200
(1)飞往广州——上海线的次数。
第27-28位表示757-200
(2)飞北京——广州线的次数。
第29-31位表示757-200
(2)飞往广州——上海线的次数。
第32-33位表示757-200(3)飞北京——广州线的次数。
第34-36位表示757-200(3)飞往广州——上海线的次数。
第37-38位表示757-200(4)飞北京——广州线的次数。
第39-41位表示757-200(4)飞往广州——上海线的次数。
第42-43位表示757-200(5)飞北京——广州线的次数。
第44-46位表示757-200(5)飞往广州——上海线的次数。
(2)检验染色体是否满足约束条件。
1.航班飞行时间问题。
对于每架737-800,皆需满足日飞行时间<=10.0,即第1-2位*3.0+第3-7位*0.56<=10.0,第8-9位*3.0+第10-14位*0.56<=10.0,第15-16位*3.0+第17-21位*0.56<=10.0。
对于每架757-200,皆需满足日飞行时间<=11.0,即第22-23位*3.0+第24--26位*2.0<=11.0,第27-28位*3.0+第29-31位*2.0<=11.0,第32-33位*3.0+第34-36位*2.0<=11.0,第37-38位*3.0+第39-41位*2.0<=11.0,第42-43位*3.0+第44-46位*2.0<=11.0。
2.航班班次问题。
飞往北京的下限班次为5,上限班次为20。
即第1-2位+第8-9位+第15-16位+第22-23位+第27-28位+第32-33位+第37-38位+第42-43位需大于等于5,小于等于20。
飞往上海的下限班次为4,上限班次为20。
即第24--26位+第29-31位+第34-36位+第39-41位+第44-46位大于等于4,小于等于20。
飞往香港的下限班次为3,上限班次为20。
即第3-7位+第10-14位+第17-21位大于等于3,小于等于20。
3.航班出发问题。
由之前的分析可知,对于三架737-800,需满足:
第1-2位与第3-7位不可同为奇数,第8-9位与第10-14位不可同为奇数,第15--16位与第17-21位不可同为奇数。
对于五架757-200航班,需满足:
第22-23位与第24-26位不可同为奇数,第27-28位与第29-31位不可同为奇数,第32-33位与第34-36位不可同为奇数,第37-38位与第39-41位不可同为奇数,第42-43位与第44-46位不可同为奇数。
(3)计算盈利
对于一条满足约束条件的染色体,可通过计算表一、表二、表三中的数据计算其适应度。
染色体适应度evaluate=(第3-7位+第10-14位+第17-21位)*3360+(第24--26位+第29-31位+第34-36位+第39-41位+第44-46位)*88000+(第1-2位+第8-9位+第15-16位)*136800+(第22-23位+第27-28位+第32-33位+第37-38位+第42-43位)*146000。
六、模型求解
1、模型的求解
算法设计和选择:
基因算法(GA)
算法思想依据:
借鉴生物界自然选择和自然遗传机制的随机化搜索算法
步骤及实现:
a)初始化:
首先初始化种群。
随机产生46位二进制数。
b)个体评价:
分别对其进行判定是否满足约束条件,直到产生50个满足约束条件的二进制数为止。
c)选择运算:
根据适者生存原则选择下一代的个体。
在选择时,对于随机产生的个体评估适应度。
适应度准则体现了适者生存,不适应者淘汰的自然法则。
显然:
(1)适应度较高的个体,繁殖下一代的数目较多。
(2)适应度较小的个体,繁殖下一代的数目较少;甚至被淘汰。
这样,就产生了对环境适应能力较强的后代。
对于问题求解角度来讲,就是选择出和最优解较接近的中间解。
d)交叉运算:
选取其中适应度较高的个体进行杂交,培育下一代基因型。
对于选中用于繁殖下一代的个体,随机地选择两个个体的相同位置,按交叉概率0.3在选中的位置实行交换。
这个过程反映了随机信息交换,目的在于产生新的基因组合,也即产生新的个体。
交叉时,实行多点交叉。
e)变异运算:
将变异算子作用于群体。
即是对群体中的个体串的某些基因座上的基因值作变动。
根据生物遗传中基因变异的原理,以变异概率Pm对某些个体的某些位执行变异。
在变异时,对执行变异的串的对应位求反,即把1变为0,把0变为1。
变异概率Pm与生物变异极小的情况一致,所以,Pm的取值较小,此处取0.07。
群体P(t)经过选择、交叉、变异运算之后得到下一代群体P(t+1)。
f)终止条件判断:
当最优个体的适应度和群体适应度不再上升时,则算法的迭代过程收敛、算法结束。
否则,用经过选择、交叉、变异所得到的新一代群体取代上一代群体,并返回到第2步即选择操作处继续循环执行。
算法流程图如图二:
图二:
算法流程图
2、计算结果
使用visualstudio编程(代码见附录),运行得到结果如图三。
图三:
运行结果
3、问题解答
问题一:
通过题目给出的机型数据、每条航线的票价、客座率、运行成本,计算出航班飞往目的地单程的获利。
给出盈利的计算公式。
解答:
单程盈利为单程收入减去单程支出,即:
客座率*座位数*票价-飞行时长*小时运营成本
问题二:
航班飞往香港、北京、上海的耗时、盈利均有所差异,评估航班安排对于获利的影响。
解答:
航班安排盈利表如表四:
航线机型
737-800(TP1)
757-200(TP2)
北京——广州线
136800
146000
广州——上海线
88000
香港——广州线
3360
表四:
航班安排盈利表
运行得到结果如图三,可知,
737-800
(1)飞北京——广州线的次数:
3
737-800
(1)飞香港——广州线的次数:
0
737-800
(2)飞北京——广州线的次数:
2
737-800
(2)飞香港——广州线的次数:
7
737-800(3)飞北京——广州线的次数:
3
737-800(3)飞香港——广州线的次数:
0
757-200
(1)飞北京——广州线的次数:
1
757-200
(1)飞广州——上海线的次数:
4
757-200
(2)飞北京——广州线的次数:
1
757-200
(2)飞广州——上海线的次数:
4
757-200(3)飞北京——广州线的次数:
1
757-200(3)飞广州——上海线的次数:
4
757-200(4)飞北京——广州线的次数:
1
757-200(4)飞广州——上海线的次数:
4
757-200(5)飞北京——广州线的次数:
1
757-200(5)飞广州——上海线的次数:
4
问题三:
广州——香港线与广州——上海线均有机型限制,737-800机型不能飞往上海,757-200机型不能飞往香港。
同时有航班次数上限与下限的要求。
在满足约束条件的情况下,制定出有利于获利最大化的航班安排策略。
解答:
由问题二可知,有利于获利最大化的航班安排策略如表五:
机型航线
737
(1)
737
(2)
737(3)
757
(1)
757
(2)
757(3)
757(4)
757(5)
北京—广州线
3
2
3
1
1
1
1
1
广州—上海线
4
4
4
4
4
香港—广州线
0
7
0
表五:
有利于获利最大化的航班安排策略表
最大利益为:
3607920
七、模型检验
1、模型的稳定性:
在测试时发现,使交叉率在0.1-0.9之间变化、变异率在0.01-0.09之间变化时,最大利益保持不变(如图三),说明模型较稳定。
图三:
交叉率在0.1-0.9之间变化、变异率在0.01-0.09之间变化时的最大利益
2、模型的正确性:
经过检验可知,模型满足题目要求,且改变交叉率和变异率对最终结果没有影响,故模型正确性基本可以保证。
八、模型评价
每一个模型都是通过与近似方法的对比而择优选取的。
对其优缺点简要评述如下:
1.优点
(1)对比粒子群PSO算法的简单便捷但不一定能收敛到全局最优点,遗传算法尽管运算繁复,但基本保证全局最优。
(2)经假设检验,交叉率和变异率改变时对最大利益没有影响,证明了我们构建的模型和设计的代码的可行性和精确性。
2. 缺点
在进行计算前,由于构建模型考虑的因素有限,题目信息不足以及为了对情况进行简化,只简单考虑飞机不停站、只有两种飞机、固定客座率和机票价格以及飞机运行成本,所以得到的结果不完全有代表性实际。
生活中航空公司面临的情况远比这复杂,这也使得此模型稍显粗糙,还有颇多需要改进的地方,来使其更好地适应真实生活。
3.改进方案
由于题中信息有限,所以本文模型在实际应用时仍存在改进空间,若信息充足,则为使模型更具实用性
(1)机型选择的影响因素众多,包括飞机的技术性能评估、飞机使用的经济性分析、政府政策、所承运旅客以及竞争对手等对机型选择的影响。
而影响航线运行机型选择的经济性因素很多。
本文中模型考虑的因素非常有限。
(2)根据淡旺季的飞机客座率变化规律,用函数表示以达到更接近现实生活的目的
(3)在模型中还可以考虑机组的人员安排,因为在航空公司机组人员,特别是飞行员是一个较缺的资源。
九、模型推广
通过对题目的解读我们不难发现这是一类规划问题。
仔细分析我们建立的模型不难发现:
这个模型不仅仅适用于飞机航线的规划问题,它对规划类问题的求解都可以起到指导作用。
其不仅可以推广到其他飞行航线中,还可以推广到铁路运输以及公路运输中。
规划问题是运筹学的一个重要分支。
它在解决工业生产组织、经济计划、组织管理人机系统中,都发挥着重要的作用。
通过资源配置最优化为杠杆平衡它们之间的分配关系。
决策者通过概念抽象、关系分析可将各类影响因子放入规划模型中,可以通过修改代码得到需要的最优解。
十、参考文献
[1] 邓举功.航空公司机队规划数学模型建立和分析[J].民航经济与技术,2000年7月,第223卷:
51~53。
[2]数学建模经典算法及试题分析:
5-8,
[3] 范玉妹等. 数学规划及其应用(第3版).北京:
冶金工业出版社, 2009. 9.
[4] 王庚, 王敏生. 现代数学建模方法.北京:
科学出版社, 2008[5] 徐玖平、胡知能、李军,运筹学(II类),北京:
科学出版社,2004。
附录:
#include
#include
#include
#include
#include
#include
usingnamespacestd;
/*Changeanyoftheseparameterstomatchyourneeds*/
#definePOPSIZE100/*populationsize*/
#defineMAXGENS500/*max.numberofgenerations*/
#defineNVARS46/*no.ofproblemvariables*/
#definePXOVER0.3/*probabilityofcrossover*/
#definePMUTATION0.07/*probabilityofmutation*/
#defineTRUE1
#defineFALSE0
intgeneration;/*currentgenerationno.*/
intcur_best;/*bestindividual*/
structgenotype/*genotype(GT),amemberofthepopulation*/
{
intgene[NVARS];/*astringofvariables*/
doublefitness;/*GT'sfitness*/
doublerfitness;/*relativefitness*/
doublecfitness;/*cumulativefitness*/
};
structgenotypepopulation[POPSIZE+1];/*population*/
structgenotypenewpopulation[POPSIZE+1];/*newpopulation;*/
/*replacesthe*/
/*oldgeneration*/
/*Declarationofproceduresusedbythisgeneticalgorithm*/
voidinitialize(void);
int*randval();
voidevaluate(void);
voidkeep_the_best(void);
voidelitist(void);
voidselect(void);
voidcrossover(void);
voidXover(int,int);
voidswap(int*,int*);
voidmutate(void);
voidreport(void);
boolcheck(int*);
intBinToDec(int*,int,int);
voidgetReasult(int*);
/*************************************************************
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 航运 策略 优化 设计 遗传 算法 数学 综合 训练