2019 MCM B 思路总结

假设

  1. 考虑到无人机成本高，为降低成本，无人机的投放数量满足工作的最低需求，尽可能运送多的医疗物资；
  2. 无人机可通过更换电池或其他方式多次使用；
  3. 无人机起飞、降落、装货与卸货花费时间为均为1min，装货与卸货不计入无人机飞行时间内；
  4. 夜晚无人机不工作；
  5. ISO集装箱与无人机货舱装载要求不同：在ISO集装箱中，无人机与医药包的装载方式正面朝上，可由水平方向旋转；在无人机运送中，医药箱装载方式不做要求；
  6. 无人机载货情况下速度减小为原来的80%；
  7. 无人机运送医疗包的数量是每天医院消耗医疗包数量的整数倍

问题一（分配）

飓风将波多黎各岛上通信破坏，视频监控路网需通过网络传输。因此，每个枢纽因至少配备一台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

问题二（地点）

由于波多黎各岛灾后情况等多种因素综合考虑，我们假设物资将由航运方式将货物运送上岛，且将选取港口作为集装箱枢纽，下图显示了波多黎各岛所有港口。

在这里插入图片描述

考虑到飓风从东南海岸登陆，并综合问题一分析，选取的三个港口以及集装箱摆放方案如下所示。

港口图片

问题三（路线）

无人机队需要完成的任务可以拆解为两部分：

  1. 从 ISO 集装箱，即枢纽处将药瓶运送到医院
  2. 从医院出发，遍历、监控路网

alt

对于任务1，我们的目标是尽可能快地将药品运送到医院，考虑转化为最短路问题，采用Dijkstra算法求解。
对于任务2，我们的目标是尽可能快地遍历路网，考虑转化为旅行商问题，采用蚁群算法求解。

考虑到无人机的飞行高度有限制，故设定海拔为h以上的区域为禁飞区，且航线要尽可能贴合路网，以保证对路网的监控效果，生成简化的网格地图如下。

alt 三个货运枢纽位置示意图

alt 五所医院位置示意图

最终得到飞行路线方案如下： alt alt alt

为第一问第二问制作的图片

alt

alt

alt

alt