解决岸桥调度问题新的数学模型的高效算法精选PPT.ppt
-
资源ID:49773164
资源大小:997.50KB
全文页数:14页
- 资源格式: PPT
下载积分:18金币
快捷下载
会员登录下载
微信登录下载
三方登录下载:
微信扫一扫登录
友情提示
2、PDF文件下载后,可能会被浏览器默认打开,此种情况可以点击浏览器菜单,保存网页到桌面,就可以正常下载了。
3、本站不支持迅雷下载,请使用电脑自带的IE浏览器,或者360浏览器、谷歌浏览器下载即可。
4、本站资源下载后的文档和图纸-无水印,预览文档经过压缩,下载后原文更清晰。
5、试题试卷类文档,如果标题没有明确说明有答案则都视为没有答案,请知晓。
|
解决岸桥调度问题新的数学模型的高效算法精选PPT.ppt
解决岸桥调度问题新的数学模型的高效算法第1页,此课件共14页哦目录摘要12问题描述3数学模型4遗传算法5总结第2页,此课件共14页哦 本文提出了一种新的集装箱岸桥调度和分配问题的混合整数规划(MIP)模型,即QCSAP模型。利用传统的方法和优化工具在合理的时间内获得最佳的解决方案是非常困难的。因此,本文提出了一种遗传算法(GA)来解决现实世界的QCSAP问题。此外,针对小规模问题所提出的算法比LINGO软件更有效率。计算结果表明,该算法对大规模的QCSAP尤其有效。一.摘要第3页,此课件共14页哦二.问题描述 过去的十年中集装箱在海上运输中的应用增长的十分迅速。集装箱码头作为货物装卸的区域在港口起着至关重要的作用。集装箱码头的生产能力主要有两个因素影响(1)Ship operations where containers are discharged from and onto a ship;(2)receiving anddelivery operations where containers are transfered to and from outside trucks;船舶作业的规划过程主要包括泊位规划、岸桥调度规划、卸船和装船规划。在泊位规划过程中,靠泊时间和位置必须被确定。岸桥调度规划必须为船上每个倍指定岸桥服务顺序和服务时间,本论文提出的QCSAP模型是在制定船舶作业规划的第二步。第4页,此课件共14页哦假设条件1.对于QCSAP模型,船靠码头的位置和船的装卸工作量是给定的输入量;2.岸桥起重机在装卸效率和从一个倍移动速度是相同的;3.每对岸桥的之间的安全距离取决于一个倍的宽度,每个倍在同一时间只能有一台岸桥工作;4.每只船分为纵向的倍,每个倍容纳一排集装箱,船上所有倍的长度是相同的,船长就是所有倍的长度。三.数学模型第5页,此课件共14页哦三数学模型第6页,此课件共14页哦三数学模型第7页,此课件共14页哦 遗传算法已被广泛用于在组合优化问题,如排序和调度问题。它是模拟达尔文生物进化论的自然选择和遗传学机理的生物进化过程的计算模型,是一种通过模拟自然进化过程搜索最优解的方法初代种群产生之后,按照适者生存和优胜劣汰的原理,逐代演化产生出越来越好的近似解,在每一代,根据问题域中个体的适应度大小选择(selection)个体,并借助于自然遗传学的遗传算子(genetic operators)进行组合交叉(crossover)和变异(mutation),产生出代表新的解集的种群。这个过程将导致种群像自然进化一样的后生代种群比前代更加适应于环境,末代种群中的最优个体经过解码(decoding),可以作为问题近似最优解。四.遗传算法第8页,此课件共14页哦 遗传算法实现的初始和最重要的一步是问题的表示和染色体的设计,本文把每个调度计划中的工作作为一个染色体上的基因。在每一条船中,第一个基因表示了给船分配的岸桥数量,每条船上所有的工作都有一串编码。1.染色体表示及初步解程序第9页,此课件共14页哦 在本文中我们用双交叉算子来表示染色体分开的两部分,第一行基因表示为船的分配的岸桥序列,另一条基因每条船上每个工作的序列。对于第一部分和第二部分我们选择用算术交叉和扩展修补交叉。2.遗传算子设计第10页,此课件共14页哦 繁殖过程中亲本的选择十分重要,亲本的选择策略意味着如何选择当前种群中的染色体,它将会决定下一代的基因。最常用的方法是轮盘选择法,每个染色体分配的圆盘的大小与染色体的尺寸成正比。在每一次旋转中,圆盘标记部分对应的染色体作为亲本池。3.亲本选择策略第11页,此课件共14页哦 我们使用一个半贪婪的策略,接受遗传算子所产生的后代。在这一策略中,如果其适应度低于该策略其亲本平均适应度,新一代的后代将为被接受。这种策略减少了算法的计算时间,并单调收敛于最佳的解决方案附近。4.子代接受则略第12页,此课件共14页哦我们选择了两个标准作为停止规则:(1)最大迭代代数(2)当前代对染色体适应度的标准偏差。5.停止规则第13页,此课件共14页哦 在本文中,我们提出了一种高效的遗传算法来解决岸桥的调度问题,对于扩展的岸桥调度问题提出了一种混合整数规划模型,这是本文的主要研究。通过一种高效的遗传算法解决了岸桥调度问题。测试结果显示提出的遗传算法与lingo8的计算结果有1.9%到3.5%的允许误差,并且遗传算法在合理的时间内可以达接近最优解五结论第14页,此课件共14页哦