网站域名选择的原则,低价网站制作企业,怎么制作网站接口,个体户能做网站备案吗【数梦工场】【智慧航空AI大赛】比赛分享_天池技术圈-阿里云天池
先介绍一下团队#xff0c;我们这几个人也是在天池众智赛【广东大赛】机场停机位资源分配优化】中互掐认识的#xff0c;也算不打不相识#xff0c;大家都有一些IP问题的建模经验
我们是前三里面唯一的一支…【数梦工场】【智慧航空AI大赛】比赛分享_天池技术圈-阿里云天池
先介绍一下团队我们这几个人也是在天池众智赛【广东大赛】机场停机位资源分配优化】中互掐认识的也算不打不相识大家都有一些IP问题的建模经验
我们是前三里面唯一的一支没有专业背景的队伍人员也是比较杂具体如下 数梦达文西 数梦工场 码农 终结卡尔斯 西安电子科技大学 在读研究生 绿洲520 飞友科技 码农 Robo 飞友科技 码农 麦芽的香气 阿里妈妈 码农
数梦达文西 和 终结卡尔斯 是Carry位绿洲520、Robo、麦芽的香气是辅助位。嗯没有打野
由于没一个好看的照片就不贴了以免辣眼睛~
---------------------------------------------------------------
---------------------------------------------------------------
言归正传说一下比赛历程。
第一赛季拿到问题我们就判断这是一个比较难的问题其复杂度会比广东机场停机位资源分配优化大赛的问题高很多。大家都没有经验大家都没底。
总体方案的选取上马上就出现分歧终结卡尔斯相对激进主张用比较先进的列生成数梦达文西主张用传统的大领域搜索框架绿洲520、Robo、麦芽的香气选择用相对传统的分析和小规模建模方式。最终没谈拢结果就是前面两人做列生成后面三人按照自己的想法做。事后来看终结卡尔斯的方向无疑是正确的但继续坚持也可能是万劫不复具体情况后面会说
题目比较复杂第一赛季时间过得很快看看题目读读文档不知不觉已经到了第一赛季的尾声。最终结果是 终结卡尔斯 和 数梦达文西 一起做的列生成失败做失败了虽然大致的原理了解了代码框架也搭出来了但有个地方没有搞定那就是主问题的求解。随着列的增多原来天真的以为主问题求解也就是建个model给求解器跑一下结果发现完全跑不动。。。。关于列生成的介绍相信同济梁哲教授会分享在此就不展开了最终是绿洲520、Robo、麦芽的香气给了一个结果62万多点虽然离57.x有很大的gap但好歹也保证我们进入复赛了。对于这个62万的解由于结果不算很优秀在此也就不分享具体实现了大致思路就是把两头时间的航班定死只调整中间的航班多个航班打包。 第一赛季结束总体效果不满意数梦达文西 和 终结卡尔斯 交流后决定只能放弃列生成算法转用大领域搜索框架整数规划建模。第一赛季结束后中间大约空了一周的时间由于之前已经对问题比较了解了用这一周的时间数梦达文西 和 终结卡尔斯写了一下大领域搜索整数规划的代码跑了一下得到一个578626.58的结果这个结果算然比不上排行榜上同济梁哲教授的成绩但也还算不错了要是之前提交了也能在排行榜上排第二了。大家在心底默默想要把终结卡尔斯吊打一顿的同事又觉得找到了一点希望。 于是第二赛季我们就坚定地贯彻大领域搜索的框架怀着“只要功夫深铁棒磨成针”的美好愿景积极开展数据分析努力优化各种细节几乎每天晚上 达文西 和 卡尔斯 都QQ语音teamviewer暧昧到深夜就这么苦逼地把成绩逐步提升上去说多了都是泪 总结一下比赛感悟
大方案的选择很重要事实证明列生成方法是优秀的但比赛中尝试使用新方法同样存在风险风险与机会并存
只要足够用心相对土鳖的方法也能出不错的解不过速度可能会慢很多 ---------------------------------------------------------------
---------------------------------------------------------------
鸡毛蒜皮说了一堆下面说说大家最关心的算法实现吧。列生成方面我们没有做成功没有太多经验相信同济梁教授应该会给大家一个教科书般的完美说明 我们就直接介绍一下我们的大致方案经验也好教训也好供大家参考 我们的方案是大领域搜索整数规划建模。其核心是整数规划建模。这个模型是我们的核心相对而言大领域搜索框架没有太大技术含量之前也用过几次实现起来也没啥风险
以下是之前文档里面ctrlc过来了请原谅我的懒惰
算法原理
3.1算法框架
我们的解决方案是大领域搜索Large Neighborhood SearchLNS与混合整数线性规划Mixed Integer Linear ProgrammingMILP。通过MILP模型可以精确的表达本次竞赛的问题但是由于问题规模较大并且有时效性要求直接求解是不切实际的。用LNS框架每次只取一部分飞机和航班进行计算得到初始解然后基于当前的解每次取一部分飞机和航班进行调整改进当前解。由于每次只取一部分飞机和航班模型较小可以实现快速迭代在合理时间内获得让人满意的结果。 大领域搜索Large Neighborhood SearchLNS是一种用于解决组合优化问题的启发式算法其核心思想是通过迭代地破坏和修复当前解来探索解空间从而在保证计算效率的同时实现全局优化。LNS通过两个关键阶段实现优化破坏阶段Destruction和修复阶段Repair。在破坏阶段算法从当前解中移除一部分变量或解组件形成一个部分解在修复阶段利用约束规划、整数线性规划或其他优化方法对破坏后的部分解进行重新优化生成新的完整解。这一过程反复执行直到满足终止条件如时间限制、迭代次数或解质量阈值。
LNS的邻域定义由破坏和修复方法隐式决定这与传统的邻域搜索算法不同。破坏方法通常包含随机性元素以便在每次调用时破坏解的不同部分而修复方法则通过不同的策略重新构造解。例如在旅行商问题TSP中破坏操作可能随机移除部分城市修复操作则通过贪心算法或最短路径插入法将移除的城市重新插入路径中。这种方法的优势在于能够通过较大的邻域范围跳出局部最优解同时避免传统搜索方法因邻域过大而导致的计算负担。
LNS的灵活性使其能够与其他启发式方法结合如局部搜索、模拟退火或遗传算法从而进一步提升解的质量。例如在车辆路径问题VRP中LNS可以与禁忌搜索结合通过动态调整破坏和修复策略来优化路径规划。然而LNS的性能高度依赖于参数设置如破坏和修复策略的选择、移除元素的数目以及局部搜索的方法。若参数设置不当算法可能陷入局部最优或效率低下。
自适应大邻域搜索Adaptive Large Neighborhood SearchALNS是LNS的扩展它通过引入多种破坏和修复方法并根据其历史表现动态调整权重进一步提升了算法的鲁棒性和效率。ALNS会根据每次迭代中解的质量评估各方法的性能并优先选择表现较好的方法生成邻域。例如在带时间窗的取送问题PDPTW中ALNS通过竞争性子启发式方法如随机移除、最差移除和贪心插入动态调整搜索策略显著提升了求解效率。LNS及其变体已广泛应用于各类组合优化问题如旅行商问题、车辆路径问题、车间调度问题等。其强大的局部搜索能力和高效性使其成为解决大规模复杂问题的有效工具。然而算法的性能仍受初始解质量和参数设置的影响未来研究可结合机器学习技术如强化学习进一步优化破坏和修复策略的自适应性。 3.2整数规划模型
模型主要包含航班模型和乘客模型两个部分
航班模型给每个飞机安排航班序列满足台风窗口约束、机场关闭约束等。
乘客模型给每个乘客安排航班尽量将乘客安排在原始航班上无法安排到原始航班上时考虑签转或取消。
在程序中设置选择考虑安排乘客或不考虑安排乘客在LNS初期通过不考虑乘客模型可以快速获得一个较好的结果。 3.2.1 航班模型
我们采用离散时空网络和多商品网络流模型来表达航班模型。在离散时空网络中每一个节点对应一个机场的一个时间点每一条弧Arc对应一个航班或飞机停留在机场。飞机可以网络中的流量飞机在网络中从起始边界流向结束边界流经的航班弧即为该飞机需要执行的航班任务。 网络中包含多种弧具体定义如下
1普通航班弧
对应一个没有延误或提前的航班从该航班的起始机场预计起飞时间的时空点指向目标机场预计降落时间加准备时间的时空点。通过在弧的指向方向加上默认的间隔时间来描述飞机过站约束。普通航班弧包含单一的航班、联程拉直航班和单独执行的联程航班的某一段联程航班单独执行的时候只能执行其中一个航班。
2停机弧
飞机已经做好的了下一次飞行的准备但是在当前时间点没有需要执行的航班在机场的一个时间点停留到下一个时间点。
3复合航班弧
复合弧为描述了多个航班一起执行的情况。通过多个航班复合在一个弧上可以表达多个联系航班的间隔小于50两个联程航班同时执行的情况。
4平行弧
除了停机弧以上弧通过同时修改起始时空点和结束时空点可以描述航班时间改变的情况。
5调机弧
和普通航班弧类似只是弧的权重计算不同可以多次执行。但是在计算中发现对于本次赛题的数据可以做到不调机。在计算中不添加调机弧。
每一个弧都满足飞机航班禁飞关系约束、机场关闭限制、台风窗口限制、最大提前和延误时间限制。
决策变量为每个弧对应的一个01变量表示飞机是否执行该弧对应的航班或停机。每个弧的权重包含了负的取消损失、延误或提前损失、换飞机损失、换机型损失、拉直损失目标函数即为每个弧的权重乘以每个弧的决策变量。 约束分为以下几种约束
1流量守恒约束
在时空网络中对于每一个时空点进入该节点的飞机数量等于从该节点出去的飞机数量。
2每个航班号只能执行一次
一个航班号在网络中对应多个弧包括普通弧和延误弧某些航班还存在复合弧在一个航班对应的多个弧中只能有一个弧对应的变量为1。两次联程航班视为一个航班单独执行时只能执行一班想要一起执行只能通过对应的复合弧来执行。
3源点、汇点平衡
对应题目中的边界调整约束飞机需要从指定机场出发指定机场结束。
4停机限制
在停机限制的时间范围内所有停机弧都取1则表示停机一次累加所有飞机的停机数量小于等于限制停机数。
5单位容量限制
单位时间内取的弧的数量小于等于单位容量限制的数量。 弧的生成
完整的模型需要描述航班所有的延误情况这样会导致弧决策变量的数量爆炸难以求解。我们采用动态生成弧的方法同时在生成过程采用一些贪心的策略减少弧的数量。
首先将飞机起始的时空点加入一个待更新的时空点集合。从集合中取出一个时空点选择所有可以从该时空点出发的航班生成对应的最早起飞航班弧。在生成了一个新弧之后会产生一个结束的时空点若该时空点没有生成过出去的弧则加入带更新的时空点中。迭代直到不产生任何的新的时空点。
在生成弧时的一些细节如下
1对于离台风窗口较远的航班禁止时间调整即没有平行弧。对于离台风窗口较近的航班给定义个限制的调整范围该范围小于题目所给出的国内24小时、国际36小时。
2考虑到台风窗口附近有飞机起飞降落容量限制需要在生成arc时判断如果在限制窗口内则随机在该时间点之后多生成几条平行弧。
3赛题给出的数据的时间粒度是5分钟。在生成平行弧时将航班的延误的时间按一定的粒度和和偏移量对齐这个时间粒度通常大于5分钟LNS中的每次迭代随机选取时间粒度和随机偏移量进行计算。每轮迭代中每个航班的随机偏是不同的例如按30分钟的时间粒度某航班得到的偏移量可能是25,50,95,130...下一轮可能是35,55, 80,110...。这样能减少很多的情况又能在多次迭代中消除其副作用。 3.2.2 乘客模型
乘客模型的本质是指派即把乘客指派到航班的座位上。只不过乘客的情况存在不确定性座位的情况也存在不确定性。通过分析梳理最终实现了航班模型和乘客模型的统一。 1乘客说明
乘客分为几种情况普通乘客、联程乘客第一班和第二班、第一班的中转乘客、第二班的中转乘客。
其中按照题目的要求联程乘客和中转第一班的乘客和航班是绑定的即只要航班存在就必然坐这个航班人数确定。在航班取消时这部分旅客也不能签转。所以这部分旅客的损失可以在生成弧的时候算入弧的权重上。
普通乘客总是存在。
第二班的中转乘客想要乘坐第二班航班的中转乘客能否搭上飞机还要取决于他第一班的降落时间因此不同准备时间的第二班中转乘客视为不同的乘客。当执行了带第一班的中转乘客的航班弧后产生对应准备时间的第二班中转乘客。当所有第一班的航班弧都没有执行时即中转失败不产生对应的第二班的中转乘客。
2航班座位说明。
航班座位不需要考虑飞机ID、机型等信息关注的是飞机的座位数、航班号、起飞时间、是否有联程乘客。飞机有上百个但是座位数的种类只有8种按座位数区分航班座位可以减少变量个数。
当执行了一个航班弧后对应“座位数、航班号、起飞时间、是否有联程乘客”的航班座位提供的座位数为当前飞机的座位数减去联程乘客的数量对应的航班弧没有执行时航班座位提供的座位数为0。
3指派说明
将安排多少旅客能否安排到某一种航班座位上定义为决策变量记为乘客安排变量可能可以签转的情况才会产生乘客安排变量。将签转、延误损失计算在乘客安排变量在目标函数中的系数上。
乘客安排变量需满足以下约束
1基本约束
所有乘客都需要被安排乘坐航班或取消。安排的乘客不大于原有的乘客同一种航班座位上的乘客数小于等于航班座位当前的座位数。
2签转约束
只有乘客对应的原始航班对应的所有航班座位都满座的时候才可以签转或取消。其中当前一种航班座位对应的弧没有执行时该航班座位的座位数为0乘客数也是0可以理解为座位数满。 具体的数学公式就不贴了因为我自己看着都头疼~ 有具体那个约束不明白怎么搞的可以跟帖讨论。整个模型还是比较复杂的建出来也不容易这也是我们团队这次比赛的一个亮点。但是这个规模直接丢进去完全解不动差远了。我们只要退而求其次把模型作为一个局部求解的工具外面套上领域搜索的启发式框架进行迭代 敲了这么多乱七八糟的手也累了脑子也不够用说都不会话了后面有时间的话再整理一下直接说一下结论吧
1、直接建模还是比较复杂的需要开动脑筋多思考
2、直接建模还是比较low的因为虽然有模型但是解不动大规模总体来说并没有什么luan用用专业的话来降解列生成问题的过程相当于解原始问题的拉格朗日松弛问题而拉格朗日松弛是要比LP松弛优的所以列生成方法更好
3、大领域搜索框架整数规划建模由于是启发式在前期的优化速度也是很快的甚至可以1分钟出一个可行解第二赛季的数据上68万左右cost并且能够快速迭代到61万左右如果一些场景下对时间要求特别高对cost要求相对低比如两分钟希望能有个可行解那也是值得考虑的方案。但是到了一定的程度之后由于启发式框架不能准确评价局部的优劣优化效率会降低甚至到最后会比较接近纯随机的效果。反观列生成每轮迭代都可以更新每种资源的影子价格所以总能慢慢进化确实是更胜一筹不得不感叹数学真的是神奇 所以总体来说我们组的方案土鳖实现也苦逼要你命3000还是不敌高科技武器不建议各位同学模仿。。。各位看官还是期待一下同济梁教授的分享吧~
先放这里等进一步理解业务在做展开研究
