论文部分内容阅读
摘 要：波多黎各的飓风对人的生命和财产造成威胁，飓风发生后的应急救援因灾难信息获取困难，导致破坏性增大。
首先，综合考虑运送路况和道路视频侦查指标，运用拉格朗日乘子法构造条件极值函数，建立拉格朗日乘子法选址模型，求得两个最佳地点P与Arecibo的经纬度坐标分别为（18.33°N，65.97°W）、（18.47°N，66.73°W）;基于混合式模拟退火算法构建三维装箱模型，根据所给数据确定出无人机舰队由3架B型无人机，1架F型无人机，1架C型无人机组成，并确定出异构无人机间的具体协作方式。
关键词：物资配送;Lagrange乘子法;三维装箱;混合式模拟退火算法
引言
美国波多黎各遭遇严重飓风，这场灾难造成了数千人死亡，并且对波多黎各的建筑与植被造成了巨大的破坏。波多黎各财产损失严重，灾难使得波多黎各几乎全部断电、断网，这严重阻碍了救援行动的展开和波多黎各居民的自救。
对此情况，非政府组织HELP， Inc.需要设计一种名为“Drone Go”的无人机救援系统，包括无人机对医疗包的运送与无人机对灾后道路情况的侦查。系统具体功能：
首先，对于所给医院的位置确定一个放置“Drone Go”系统的最佳地点，确定地点时既要考虑到医疗用品的运送也要考虑到道路视频侦查;其次，确定无人机选取方案，求出最终需要各种无人机与医疗包的数量。对于确定好的无人机与医疗包的数量，为最多三个ISO集装箱提供相关的装载方案。针对所提供的“Drone Go”方案中的所有无人机，为其提供有效载荷包装配置、送货路线和时间表，使其足够满足確定的医疗包要求，并提供一份无人机飞行计划，使无人机能使用机载摄像头录制路况信息回馈给救援队，对其开展救援提供帮助。
1 建立拉格朗日乘子法选址模型
1.1坐标转换
大多情况下使用的为平面坐标点，首先利用Global Mapper软件将五个地点的经纬度坐标转换为平面坐标，以方便进行间距离的计算
1.2 运用拉格朗日乘子法确定最优坐标点
拉格朗日乘子法又称为拉格朗日乘数法，是用来求解函数f（x1，x2，…，xn）=0在g（x1，x2，…，xn）=0的约束条件下的极值。
1.3模型建立与求解
已知四座城市的坐标，确定一坐标点P（x，y），使P到Q1、Q2、Q3、Q4距离之和最小，通过两点之间的距离公式 ，分别计算出各城市之间的距离[2]。
2. 无人机舰队构造
无人机货舱只有两种，容积分别为1120、6900，结合医院对医疗包的需求可以得出医院所需医疗包总体积，显然部分飞机无法实现一次将医疗包送向某需求量较大的医院，筛选后可得到可以到飞往各城市的无人机种类[3]。
将运送物资的无人机与侦察路线的无人机分开讨论。F型飞机虽然没有视察功能，但是有效载荷能力相对于其他型的无人机占有巨大优势。再结合它空载可飞行的距离来看，确定出F型飞机从F点出发相继向Q3、Q4 两地送往物资，B型无人机向Q1地运送物资，C型无人机向Q2地运送，B型无人机空载时飞行的距离最大，所以选派B作为侦察机，同时送货的B、C运送完药品后还可以侦察路况。
尽管Q5 医院本身就是物资点不需要配送医疗包，但是由于还需要Q5 医院与其他医院之间的路况信息。考虑到其他所有医院与Q5 医院的距离都远大于无人机最大飞行航程，本文提出两架无人机相向行驶的方案。但是本方案中无人机飞行后会相遇在非救助点，此时能量耗尽而不能确保有人能够及时给无人机更换电池，因而本方案中需要的无人机在很大的概率上是无法回收的[4]。
时，说明货物 没有被装进集装箱;Ri-Ri=0 时，表示货物可以任意旋转;Ri=1时，表示货物可以水平旋转;Ri=2时，表示货物不可以旋转;a1，a2，b1，b2，c表示货物装载后在三维方向上的重心坐标边界[8]。
设定灾难救援持续8个月，所以一套医疗包包括1680个MED1，480个MED2，960个MED3。集装箱放置点为两个，每个点一个集装箱[10]。其中P点处集装箱装箱情况为2架B型无人机，1架C型无人机，1架F型无人机;1440个MED1，480个MED2，960个MED3;Q5点处集装箱装箱情况：1架B型无人机，240个MED1，具体的装箱顺序和装箱排列见图 4。
3. 结论
最终确定选用5架无人机，分别为3架B型无人机，1架F型无人机，1架C型无人机。异构无人机间的协作方式：派两架B型无人机作为侦察机，另一架B型无人机、C型无人机和F型无人机一起运送物资，同时B型无人机、C型无人机运送完药品还可继续侦察。其次，该侦查方式还考虑到没有探测到路线信息、侦察型无人机在探测到危险时的状况，保证了其可行性与自适应性。
参考文献：
[1] Everett， Hugh. "Generalized Lagrange Multiplier Method for Solving Problems of Optimum Allocation of Resources." Operations Research 11.3（1963）：399-417.
[2]肖东. 异构多无人机自主任务规划方法研究[D].南京航空航天大学，2018.
[3] Kunoth， Angela . "Multilevel preconditioning - appending boundary conditions by Lagrange multipliers. " Advances in Computational Mathematics 4.1（1995）：145-170.
[4] Liao， Chung Shou ， and C. H. Hsu . "New lower bounds for the three-dimensional orthogonal bin packing problem. " European Journal of Operational Research 225.2（2013）：244-252.
[5]庞海龙. 一种异构多无人机多目标任务分配方法[A]. 中国指挥与控制学会.第四届中国指挥控制大会论文集[C].中国指挥与控制学会：中国指挥与控制学会，2016：4.
[6]丁臻极，王从庆，丛楚滢，李志宇.城市环境下的异构多无人机层次化任务分配[J].华中科技大学学报（自然科学版），2015，43（S1）：302-306.
首先，综合考虑运送路况和道路视频侦查指标，运用拉格朗日乘子法构造条件极值函数，建立拉格朗日乘子法选址模型，求得两个最佳地点P与Arecibo的经纬度坐标分别为（18.33°N，65.97°W）、（18.47°N，66.73°W）;基于混合式模拟退火算法构建三维装箱模型，根据所给数据确定出无人机舰队由3架B型无人机，1架F型无人机，1架C型无人机组成，并确定出异构无人机间的具体协作方式。
关键词：物资配送;Lagrange乘子法;三维装箱;混合式模拟退火算法
引言
美国波多黎各遭遇严重飓风，这场灾难造成了数千人死亡，并且对波多黎各的建筑与植被造成了巨大的破坏。波多黎各财产损失严重，灾难使得波多黎各几乎全部断电、断网，这严重阻碍了救援行动的展开和波多黎各居民的自救。
对此情况，非政府组织HELP， Inc.需要设计一种名为“Drone Go”的无人机救援系统，包括无人机对医疗包的运送与无人机对灾后道路情况的侦查。系统具体功能：
首先，对于所给医院的位置确定一个放置“Drone Go”系统的最佳地点，确定地点时既要考虑到医疗用品的运送也要考虑到道路视频侦查;其次，确定无人机选取方案，求出最终需要各种无人机与医疗包的数量。对于确定好的无人机与医疗包的数量，为最多三个ISO集装箱提供相关的装载方案。针对所提供的“Drone Go”方案中的所有无人机，为其提供有效载荷包装配置、送货路线和时间表，使其足够满足確定的医疗包要求，并提供一份无人机飞行计划，使无人机能使用机载摄像头录制路况信息回馈给救援队，对其开展救援提供帮助。
1 建立拉格朗日乘子法选址模型
1.1坐标转换
大多情况下使用的为平面坐标点，首先利用Global Mapper软件将五个地点的经纬度坐标转换为平面坐标，以方便进行间距离的计算
1.2 运用拉格朗日乘子法确定最优坐标点
拉格朗日乘子法又称为拉格朗日乘数法，是用来求解函数f（x1，x2，…，xn）=0在g（x1，x2，…，xn）=0的约束条件下的极值。
1.3模型建立与求解
已知四座城市的坐标，确定一坐标点P（x，y），使P到Q1、Q2、Q3、Q4距离之和最小，通过两点之间的距离公式 ，分别计算出各城市之间的距离[2]。
2. 无人机舰队构造
无人机货舱只有两种，容积分别为1120、6900，结合医院对医疗包的需求可以得出医院所需医疗包总体积，显然部分飞机无法实现一次将医疗包送向某需求量较大的医院，筛选后可得到可以到飞往各城市的无人机种类[3]。
将运送物资的无人机与侦察路线的无人机分开讨论。F型飞机虽然没有视察功能，但是有效载荷能力相对于其他型的无人机占有巨大优势。再结合它空载可飞行的距离来看，确定出F型飞机从F点出发相继向Q3、Q4 两地送往物资，B型无人机向Q1地运送物资，C型无人机向Q2地运送，B型无人机空载时飞行的距离最大，所以选派B作为侦察机，同时送货的B、C运送完药品后还可以侦察路况。
尽管Q5 医院本身就是物资点不需要配送医疗包，但是由于还需要Q5 医院与其他医院之间的路况信息。考虑到其他所有医院与Q5 医院的距离都远大于无人机最大飞行航程，本文提出两架无人机相向行驶的方案。但是本方案中无人机飞行后会相遇在非救助点，此时能量耗尽而不能确保有人能够及时给无人机更换电池，因而本方案中需要的无人机在很大的概率上是无法回收的[4]。
时，说明货物 没有被装进集装箱;Ri-Ri=0 时，表示货物可以任意旋转;Ri=1时，表示货物可以水平旋转;Ri=2时，表示货物不可以旋转;a1，a2，b1，b2，c表示货物装载后在三维方向上的重心坐标边界[8]。
设定灾难救援持续8个月，所以一套医疗包包括1680个MED1，480个MED2，960个MED3。集装箱放置点为两个，每个点一个集装箱[10]。其中P点处集装箱装箱情况为2架B型无人机，1架C型无人机，1架F型无人机;1440个MED1，480个MED2，960个MED3;Q5点处集装箱装箱情况：1架B型无人机，240个MED1，具体的装箱顺序和装箱排列见图 4。
3. 结论
最终确定选用5架无人机，分别为3架B型无人机，1架F型无人机，1架C型无人机。异构无人机间的协作方式：派两架B型无人机作为侦察机，另一架B型无人机、C型无人机和F型无人机一起运送物资，同时B型无人机、C型无人机运送完药品还可继续侦察。其次，该侦查方式还考虑到没有探测到路线信息、侦察型无人机在探测到危险时的状况，保证了其可行性与自适应性。
参考文献：
[1] Everett， Hugh. "Generalized Lagrange Multiplier Method for Solving Problems of Optimum Allocation of Resources." Operations Research 11.3（1963）：399-417.
[2]肖东. 异构多无人机自主任务规划方法研究[D].南京航空航天大学，2018.
[3] Kunoth， Angela . "Multilevel preconditioning - appending boundary conditions by Lagrange multipliers. " Advances in Computational Mathematics 4.1（1995）：145-170.
[4] Liao， Chung Shou ， and C. H. Hsu . "New lower bounds for the three-dimensional orthogonal bin packing problem. " European Journal of Operational Research 225.2（2013）：244-252.
[5]庞海龙. 一种异构多无人机多目标任务分配方法[A]. 中国指挥与控制学会.第四届中国指挥控制大会论文集[C].中国指挥与控制学会：中国指挥与控制学会，2016：4.
[6]丁臻极，王从庆，丛楚滢，李志宇.城市环境下的异构多无人机层次化任务分配[J].华中科技大学学报（自然科学版），2015，43（S1）：302-306.