呓语 | 杨英明的个人博客

专注于c++、Python,欢迎交流

By

2018年“华为杯”研究生数学建模比赛总结

前言

参加数学建模比赛是一次难忘的经历,不管是比赛的过程还是其中的收获,我想不管最终结果如何,这样的一个经历已经十分难得,真正应了比赛的那句口号——“建模一次,终身受益”,所以让我在这里记录下参赛的过程和感受。

赛前

最初其实是学弟(虎三)拉我参赛,当然是一拍即合,然后我们俩计算机的在建模群里发布了找队友的信息,然后曾有数学建模经验的数学系小伙伴wyr便加入进来,最终我们的队伍配置是这样的:两名计算机系队员,一名数学系队员。三人成行,目标NPMCM!

研究生数模比赛时间为 2018.9.15 早上8:00 ~ 9.19 中午12:00,一共四天,期间要完成读题、讨论、读论文、建模、编程、写作等过程,最后提交代表成果的论文。

第一天 周六

参加数学建模比赛,参赛场地很重要。因为小组要一起讨论,还需要编程,所以一个可以说话,有插座,有网络的环境是十分重要的,它直接影响到比赛的效率。

比赛前我想好了几个可以讨论的地方,本来是想约学校图书馆的研讨室,但是下手太晚已经被占用了,于是想着早点去理科楼二楼大厅的沙发那儿占位置。

早上8:00我到达理科楼二楼的大厅,发现已经有两个位置被占了,都是数学建模的,没想到参赛的人还挺多……

在大厅占的位置

8:00比赛正式开始,需要到官网上查看赛题解压密码,但是由于人太多,刷了半个小时才进入官网后台看到解压密码。把赛题解压之后,发现有6道题,每道题有一个文件夹,里面放着这道题的赛题描述和数据。这时候队友还没到齐,我只是快速浏览了一遍,没有细看。

8点多的时候虎三过来,9点多的时候wyr也到达,她是从闵行校区过来,还带着行李,为了比赛也蛮不容易的!

简单自我介绍坐下之后,我把赛题发给他们,同时发现大厅的座位桌子太矮,灯光也不好,于是我临时想起来楼上会议室周末可能是不用的,跑上去确认过之后,我们带着装备转战会议室。

会议室的环境就比较好了,长桌子,有插座,有网络,关键是可以讨论。这里同时也有几个队伍在,大家也发现了会议室空闲的情况。

上午的时间已经过去一半,剩下的时间,我们开始读题,然后一起讨论选题。

这六道题中:

  • A题是一道跳水的题,貌似需要物理的知识,商量之后,pass;
  • B题是一道通信方面的题目,公式比较明确,专业性偏强,商量后不太想做,pass;
  • C题是我看着最顺眼的题,典型的数据分析题目,可以用机器学习和可视化方法做,数据竞赛的一般套路,但是考虑到可能会有很多人选,pass;
  • D题是一道海洋方面的题,专业性十分强,pass;
  • E题是一道无人机轨迹优化的题目,商量之后,pass;
  • F题是一道航班-登机口分配问题,商量之后有一些思路,虽然也在纠结其他题目,但一拍板决定不浪费时间,就是它了。

选题花费了我们半天时间,其实一开始想从ACF中选择一道题来做,但到中午去吃饭前也没选好题目,回来之后仍然在纠结。


收拾东西准备去吃午饭

到一点多钟的时候,我们决定不浪费时间,正好在思考F题,于是就决定是它了。

下午的时候我们走了一些弯路,在决定好赛题之后,又花费了半天时间来讨论赛题的思路,实际上这个时候直接去找参考文献和读参考文献比较好。

比如我们选的F题,在赛题给出的一篇参考文献中,摘要的第一句话就说明了这是一个“Airport Gate Assignment Problem”(机场停机位分配问题),再去知网上根据关键字找论文就明确多了。


机场登机口分布

F题要求安排尽量多的航班到登机口,在此基础上有多个优化要求:

  1. 尽量少的使用登机口;
  2. 要求尽量少的旅客总体流程时间,以及尽量少的使用登机口;
  3. 要求尽量少的旅客总体换乘紧张度,以及尽量少的使用登机口;

乘客流程时间是指乘客办理乘机手续的时间,每个航班类型对应的手续处理时间不同。

乘客换乘紧张度 = 乘客换乘时间 / 航班连接时间;
乘客换乘时间 = 乘客流程时间 + 乘客行走时间 + 捷运时间;
航班连接时间 = 后一航班出发时间 − 前一航班到达时间;

除此之外,航班安排到登机口还有诸多属性限制,某个航班的飞机到达/出发类型必须和登机口的到达/出发类型相同,比如到达/出发航班是国际航班,那它必须停靠在国际航班专用登机口;飞机机型也必须和登机口类型相同,比如窄体机必须停靠在窄体机的专用登机口;

在满足以上属性限制之后,我从753班航班转场记录中筛选出303班20号出发或20号到达的航班(题目要求只靠20号的航班)。

经过查阅资料,晚上我们大概了解了这个问题的主要解决思路,大致有三种:

  1. 基于专家系统,通过将配置原则建立于知识库系统,但容易忽视关键因素而导致配置结果不理想;
  2. 运用数学规划的方法,选定优化目标函数利用0-1整数规划探讨配置的可行性及如何 配置,这种方法主要问题是目标函数的选择,影响机场停机位的因素较多,如何结合考虑各种因素提出符合实际需求的优化目标函数以及设计快速、有效的求解算法是该方法要解决的问题;
  3. 采用蚁群算法、遗传算法、禁忌搜索算法等最优化算法优化停机位的分配,但求解的结果是往往是得到局部最优解,且当航班起降架次数量达到上千后,复杂度将呈阶数递增,难以满足机位分配实时性的要求。

由于我和虎三都有最优化算法的经验,所以我们打算尝试采用第三种思路解决该问题。

同时我们发现F题的停机位分配问题可以转化为图着色问题,着色问题是指给图上的所有节点着色,要求相邻节点不能着相同颜色。在这道题 中,可以将每架航班看做图上的一个节点,如果两家航班在时间上不冲突,那么就在它们之间建立一条无向边,根据这样的规则建立一张图。在这张图上应用着色问题,相邻节点不能着相同颜色,即对应了时间上冲突的两架航班不能放在同一登机口,最后统计着色之后图上一共有多少不同颜色,即使用了多少登机口。

就这样,一道数学问题被转换为一个计算机图论的问题,我们可以采用计算机的方法尝试解决它。

第一天的成果就是这样,总结一下主要是 读题-讨论-看论文-找方向,和虎三回去的路上还是兴冲冲的,感觉找到了方向。

第二天 周日

第二天开始尝试昨天的思路写代码,首先是建立图,我将输入文件中各航班和登机口的属性统一处理后,根据属性是否匹配以及时间是否冲突建立了无向图。

将图文件给虎三之后,虎三找了个图着色算法运行了一下,发现要将所有航班全部分配,至少需要78个登机口,而题目只给了69个登机口,也就是说这303班航班无法全部分配到登机口。换句话说,图上的点无法被全部着色,这就变成了一个不完全的图着色问题。

好吧,知识开始进入盲区,查论文也无用了。

这个时候我们的思路开始出现混乱,冒出各种奇思妙想,这种没有明确方向的感觉很痛苦,因为不确定到底哪个方向能做出来。

这段时间我找到一个现成的轮子,在github上一个开源的蚁群算法解决图着色问题的代码,还兴奋了一下(后来发现这代码没什么用),毕竟这是当时匹配度最高的代码了。如果可用,我们将省却不少时间。

我和虎三一起研究了一下这个代码,发现虽然写的比较规范,但是貌似有些问题。当时还没意识到这些问题可能会一叶障目,反正是障了我的目,我看了这段代码很长时间,而且越看越感觉这个代码写的不对!这里要反思一下自己,这个时候不应该纠结于一个看不懂的代码,思路大概懂了还不如自己写一个。

反之这段时间虎三闭关了一晚上,自己撸了一个蚁群算法,第二天套到题目上,发现可行,Nice!(这是后话)发现根本不用像那个代码里写的那么复杂,简单有效,虎三的代码推动很大。

在我和虎三研究算法期间,yr小伙伴开始写论文,我们将使用的算法和思路告诉她,她负责整理到论文里。看到她将算法转化成数学公式和文字,下笔成章,我还是很佩服的,这方面要是让我和虎三短时间内写出来这么多文字,那可真是犯了难。三个人组队参赛,在这么短的时间内需要完成一个问题的研究,还要出成果,总结成论文,建模编程写作能力真的是缺一不可,不能有任何一个短板。

总的来说,第二天的进度没有我们想象的那么顺利,在图建立起来之后,我们就陷入了迷茫混乱状态。我在纠结一个看不懂的蚁群算法,虎三转战了遗传算法一段时间,yr倒是一直在稳定输出论文。

晚上愁的在实验室熬了夜,我继续改蚁群算法,效果一直不佳,总觉得哪里不对,很晚才睡。

第三天 周一

由于会议室周一老师要用,于是今天我们就转战实验室。

8点多睡梦中惊醒,发现队友已经来了,讨论了一下昨晚的进度,这个时候虎三过来介绍他昨晚写的蚁群算法,为今天的建模注入了新活力。

虎三讲了一下代码的结构,我们发现是可行的,但是问题二和问题三的关键部分还没加上,于是上午我们就一边讨论一边改代码,将紧张度的计算和评估函数成功编写了出来。

中午的时候,算法写完,我把代码扔到学院集群上跑起来,然后我们就去吃饭,回来观察算法跑出来的结果,调整代码。

到晚上算法基本调整到可以用的地步,论文也填充起整体框架,yr妹子写了20多页…… Orz

晚上我们松了一口气的回到宿舍,今天还是蛮有成果的,起码有可以用的数据了。

一天过后的战场

第四天 周二

数学建模的最后1.5天,今天的主要任务是美化论文!

上午我们整理了一下集群里面跑出的数据,对比了一下结果,然后重新优化了一下目标函数,丢到集群里重新跑。

下午2点yr妹子要去上课,虎三代替她开始写论文。

我中午睡了一觉到3点,醒来之后开始写绘制图表的代码,一口气写到晚上10点,把题目要求的所有图表准备完毕。


工作成果

晚上8点,yr妹子回来和虎三一起写论文。

晚上11点,回宿舍睡觉。

今天的成果也比较明显,优化了下算法,论文的内容也更加丰富。

第五天 周三

今天是最后半天,中午12点就要提交论文!

我们晚上没有睡觉,过了零点之后我们三个就轮着睡觉,轮番写论文和优化图表。一直写到截止时间,最后提交还出现了惊险的插曲,还好最终顺利提交了我们的论文。

至此,持续四天的数学建模比赛结束,彼此看看,双眼中带着头脑疯狂运转四天后的疲惫和兴奋,对于我们来说,收获自然是满满当当。这四天中,绝望和希望的心情随着解题的进度此起彼伏,是队友之间的互相帮助和鼓励让我们的队伍不断前进!我想不管结果如何,这种体验本身就是十分巨大的收获!

感谢队友,感谢数学建模,希望能有一个好结果。


更新一下,研赛二等奖,对于第一次参赛的我来说,这是一个还不错的开始,也是对我们这几天努力的一个肯定。

仔细想想,和一等奖确实有些距离,我校上百只参赛队伍只有三个一等奖,全国一万支队伍也只有150多队一等奖。也许论文还需要写的突出一些,实验还需要一些新意,图表表现力需要再强一些,做到这些也许能冲击下一等奖。

保持激情,继续努力!

原创声明

转载请注明:呓语 » 2018年“华为杯”研究生数学建模比赛总结