毕业答辩-大型集装箱码头ALV实时分配方式设计及A搜索算法研究.pptx

大型集装箱码头ALV实时分配方式设计及A*搜索算法研究,工物102指导老师：,上海海事大学本科毕业设计,目录,研究背景,问题分析,ALV实时分配方式设计,模型建立,算法设计和算例分析,结论,研究背景,ALV简介,研究背景,同时作业车辆多容易发生交通拥堵,任务到达频率高,运输距离长,集装箱船舶大型化,码头向大型高效方向发展,问题分析,FCFS分配方式,目前常用水平运输车辆任务分配FCFS（先到先服务）分配方式，根据FCFS分配方式，每当一个集装箱运输任务产生时就为这个任务分配一辆空闲的车辆，这辆车是在分配时最适合去执行这个运输任务的车，一旦为任务分配车辆后，即使任务有更合适的车辆可以选择，分配给任务的车辆也不再发生变化。这种分配方式虽然操作简单，但在大型高效的集装箱码头采用FCFS分配方式分配ALV的作业任务则会遇到更多的问题，下面进行举例说明。,问题分析,FCFS分配方式,交通堵塞,集装箱,ALV,问题分析,FCFS分配方式,ALV实时分配方式,从上面的例子可以看出，在大型集装箱码头经常会出现某一时刻的最优分配方案过一段时间后不是最优分配方案，应用FCFS分配方式不能实时的进行分配方案更新，不能保证ALV作业任务实时保持最优，难以提高ALV的作业效率，所以应该设计新的分配方式ALV实时分配方式。,ALV实时分配方式设计,一组触发事件,一个ALV实时分配模型,新任务的产生,ALV完成上一个作业任务,ALV在前往作业地点途中速度发生较大的变化,ALV实时分配方式,ALV实时分配方式设计,交通堵塞速度减慢,ALV实时分配方式,ALV实时分配模型,参数,决策变量,=1=1+=+1+=1,需要运输的集装箱数量；正在进行装卸作业的岸桥数量；实时分配时考虑的作业任务数量,=+；闲置ALV数量；每辆闲置ALV某时的行驶速度；ALV到任务作业地点的距离；ALV到任务作业地点估计时间；、时间价值正常数，=2；一个很大的数，作为预计行驶时间的上限；一个较小的距离常数；,模型决策变量：=1,ALV分配给任务0,其他,约束,=11=11=1=1,=,0,00,算法设计,A*搜索算法简介：A*搜索算法是启发式算法的一种，常用在路网中寻找最短路径，A*搜索算法用启发式估价值对搜索到的点进行评价，由估计值的大小决定搜索的顺序，可以省略大量的无意义搜索，提高搜索效率。计算估计值的启发式估价函数为：=+()是在路网中从初始节点到节点的实际代价；()是从到目标节点最佳路径的估计代价；,算法设计,A*搜索算法搜索流程图,算法设计,A*搜索算法求解ALV实时分配问题,S,1,2,3,4,6,8,5,7,9,14,任务1分给ALV1,任务1分给ALV1任务2分给ALV2,任务1分给ALV1任务2分给ALV2任务3分给ALV3,是从起始点S到达n点所走的总路程；()是搜索到n时未分配的ALV对于的到达每一个作业地点的估计时间里最小的m个的总和（m是未分配ALV的数量）,2,3,S,1,g(s)=0h(s)=60f(s)=60,g(1)=80h(1)=50f(1)=130,g(2)=70h(2)=50f(2)=120,g(3)=10h(3)=50f(3)=60,g(14)=80h(14)=0f(14)=80,g(9)=100h(9)=20f(9)=120,g(8)=50h(8)=20f(8)=70,8,9,算例分析,本文分别用A*搜索算法和贪婪算法对ALV实时分配问题进行求解，本文用贪婪算法对ALV实时算法进行求解的过程和用A*搜索算法的求解过程相似，只是在搜索的过程中，贪婪算法不考虑从n到目标节点最佳路径的估计代价h(n)，可以看做h(n)=0，f(n)=g(n)。本文设计12组实验，每组实验进行5次，每次实验两种算法使用的实验数据相同，实验结果如图所示,算例分析,A*搜索算法求解性能测试实验,结论,本文设计ALV实时分配方式能有效的解决FCFS分配的弊端，能上使ALV的分配方案实时保持最优，提高ALV的作业效率。使ALV能更好的服务于其他作业设备，提高整个码头的作业效率。本文选择A*搜索算法对ALV实时分配