2019 MCM B 思路总结
2019 MCM B 思路总结
假设
- 考虑到无人机成本高，为降低成本，无人机的投放数量满足工作的最低需求，尽可能运送多的医疗物资；
- 无人机可通过更换电池或其他方式多次使用；
- 无人机起飞、降落、装货与卸货花费时间为均为1min，装货与卸货不计入无人机飞行时间内；
- 夜晚无人机不工作；
- ISO集装箱与无人机货舱装载要求不同：在ISO集装箱中，无人机与医药包的装载方式正面朝上，可由水平方向旋转；在无人机运送中，医药箱装载方式不做要求；
- 无人机载货情况下速度减小为原来的80%；
- 无人机运送医疗包的数量是每天医院消耗医疗包数量的整数倍
问题一（分配）
飓风将波多黎各岛上通信破坏，视频监控路网需通过网络传输。因此，每个枢纽因至少配备一台H型号无人机。
五家医院分别标号为：
Ⅰ. Caribbean Medical Center
Ⅱ. Hospital HIMA
Ⅲ. Hospital Pavia Santurce
Ⅳ. Puerto Rico Children's Hospital
Ⅴ. Hospital Pavia Arecibo
五家医院分布如图所示
可以发现Ⅴ医院离其他各医院的距离超过无人机最大飞行距离，因此不可能找到一个位置满足条件。必须单独在Ⅴ医院附近布置一个枢纽负责为Ⅴ医院服务，且为了最大化监控路网范围，将设置三个枢纽。
考虑医院与医院之间距离以及无人机载重负荷量，我们制定如下无人机舰队规划
- 无人机队1负责服务Ⅴ医院，编号为①
- 无人机队2负责服务Ⅱ、Ⅲ、Ⅳ医院，编号为②
- 无人机队3负责服务Ⅰ医院，编号为③
- 三台H型号无人机负责在枢纽提供数据网络
B型无人机飞行速度最快，飞行时间最长，最大飞行距离为52.7km，但荷载量小，且Ⅴ医院每日仅需一个MED1，故适合单独服务Ⅰ和Ⅴ医院；
C型无人机荷载量最大，适合服务ⅡⅢⅣ医院。
至此，三个枢纽集装箱中无人机配置和医疗包配置情况已知，通过3d bin paking算法求解即可。
The container in area A: Drones: One H-type drone, one F-type drone, two B-type drone Medical:90 MED1 The container 1 in area B: Drones: One Drone H,two Drone F,six Drone B Medical:450 MED1,180 MED2,270 MED3 The container 2 in area B: Drone: One Drone H,one Drone F,one Drone B Medical:90 MED1,90 MED3
问题二（地点）
由于波多黎各岛灾后情况等多种因素综合考虑，我们假设物资将由航运方式将货物运送上岛，且将选取港口作为集装箱枢纽，下图显示了波多黎各岛所有港口。
考虑到飓风从东南海岸登陆，并综合问题一分析，选取的三个港口以及集装箱摆放方案如下所示。
问题三（路线）
无人机队需要完成的任务可以拆解为两部分：
- 从 ISO 集装箱，即枢纽处将药瓶运送到医院
- 从医院出发，遍历、监控路网
对于任务1，我们的目标是尽可能快地将药品运送到医院，考虑转化为最短路问题，采用Dijkstra算法求解。
对于任务2，我们的目标是尽可能快地遍历路网，考虑转化为旅行商问题，采用蚁群算法求解。
考虑到无人机的飞行高度有限制，故设定海拔为h以上的区域为禁飞区，且航线要尽可能贴合路网，以保证对路网的监控效果，生成简化的网格地图如下。
最终得到飞行路线方案如下：
查看12道真题和解析