基于非線性動態規劃的波多黎各颶風災難救援模型研究

劉越 王志堅

摘 要：本文研究了救援響應系統開發，在裝箱問題上面對客觀約束采用非線性規劃模型，在空間利用率達到最大化的目標函數下，對貨物的數量、旋轉方向、體積和承載重量做出約束，再使用動態規劃模型確定裝箱方案。在配送集裝箱時分3種情況構造模型，分為停靠1個、2個和3個港口，遍歷港口與5個醫療包交貨地點間的距離并篩選得到最小距離求得對應的停靠港口。

關鍵詞：非線性規劃；動態規劃；遍歷

很多學者研究過三維裝箱問題及最佳分配問題。本文研究的是相同尺寸物品裝箱問題，通過構造模型尋找最佳包裝配置，且綜合考慮救援效率及成本和其他客觀要求，結合實際情況為最佳包裝配置選取合適港口以便進行組織的下一步營救。

1 研究背景

2017年美國波多黎各遭受當地史上最嚴重颶風，造成了嚴重破壞和重大人員傷亡。非政府組織HELP，Inc通過設計“DroneGo”可移動災難響應系統來提高其救援響應能力。HELP，Inc已經確定使用各種旋翼無人機來組成DroneGo車隊。為了增加受災現場的援助用品，DroneGo準備了三種醫療包MED1、MED2和MED3。無人機承擔運輸醫療包的任務，可以通過外部貨艙運輸多個醫療包。本文根據各營救點的需求及救援路線和偵查路線為HELP，Inc解決營救計劃的包裝配置和物資運輸問題。結合波多黎各的颶風災難情景，為最多三個標準ISO集裝箱設計相關的包裝配置，形成HELP，Inc設計無人機隊和醫療包裝配方案。找到波多黎各的最佳位置，確定DroneGo災難響應系統一個或多個集裝箱位置，有利于提供醫療服務和道路視頻偵察。

2 裝箱問題與包裝配置

無論是醫療包放進無人機外部貨艙和運輸集裝箱，還是運輸集裝箱放進ISO集裝箱，都要與集裝箱邊線平行，即正交布局。

要求最多使用三個標準ISO集裝箱，本文運用非線性規劃模型，把醫療包放入無人機的外部貨艙，將無人機和剩余醫療包放入運輸集裝箱內，再把運輸集裝箱按數量最大限度地裝載進標準ISO集裝箱，即研究三維裝箱問題，假設各種集裝箱和醫療包的形狀都是規則的長方形，它們的重心即其幾何中心，對此建立空間直角坐標系。考慮目標函數和現實約束，其中需要注意的是無人機的運輸集裝箱只能正交旋轉90°，不能對任何運輸物品進行倒置或側放。

3 集裝箱停靠位置選取

裝載包裝配置后需要將標準ISO集裝箱進行分配派送，需獲取1個、2個或3個最佳停靠位置。由于最多使用3個港口，故分3種情況構造模型。

本文在GoogleMap上獲取波多黎各的11個主要港口的經緯度。如下表所示：

結合醫療包交貨地點的經緯度，繪制地圖如下圖1：

先建立平面直角坐標系，再將波多黎各地圖上任意一點A與任意一點B的經緯度換算為平面直角坐標系上兩個坐標點，并求這兩點之間的直線距離：

當集裝箱僅停靠在一個港口時，計算每個醫療包交貨地點與此港口間的距離，把最短距離對應的港口作為最佳位置。

當為兩個港口時，從11個港口中隨機抽取2個，共有C211種可能。記為港口A和港口B，將五個醫療包交貨地點隨機分配給這兩個港口。

其中港口A分得m個醫療包交貨地點，則港口B分得5-m個交貨地點（m=1，2，3，4）。計算港口與所分配交貨地點間的距離，求和得到分配方案總距離。通過遍歷方法篩選出多種分配方案總距離最小值，把該種方案對應的兩個停靠港口視為最佳停靠位置。

當標準ISO集裝箱停靠三個港口時，從11個港口中任意抽取三個港口，將5個醫療包交貨地點隨機分配給這三個港口。同理可得多種分配方案的總距離最小值，把該種方案確定的三個停靠港口視為最佳位置。

4 研究結論

對本文非線性規劃的約束條件和目標函數使用python求解，得到結果如下：

本文為災難響應系統設置2臺E型無人機，1個H Tethered平臺，363個E型運輸集裝箱，1個H型運輸集裝箱和3個標準ISO集裝箱。其中會出現兩種裝載情況，第一種情況是用無人機外部攜帶的貨艙裝載醫療包，運輸集裝箱裝載無人機；第二種情況是僅用運輸集裝箱裝載醫療包。再把所有運輸集裝箱放進ISO集裝箱。

使用C++對包裝配置的動態規劃二維裝箱模型進行裝載計算，其中兩個標準ISO集裝箱，一個內部裝載126個E型運輸集裝箱，空間利用率為85.1%。另一個裝載111個E型運輸集裝箱和1個H型運輸集裝箱，其中有兩個E型運輸集裝箱裝載E型無人機，H型運輸集裝箱裝載H Tethered平臺，空間利用率為85%。兩種裝箱方案的空間利用率較高，是可行的結果。其中醫療包放進運輸集裝箱的方法有兩種：第一種方法是3個MED1和3個MED3。第二種方法是4個MED1，2個MED2和3個MED3；且每一天所需醫療包的包裝量剛好滿足兩個E型運輸集裝箱的最大承重能力，裝載后的剩余運輸集裝箱底面面積相對較少。

在尋找最佳位置的模型中，通過python多次遍歷計算得到在3種情況中港口與醫療包交貨地點之間的距離，并自動篩選出之中的最短距離，其對應的港口即為標準ISO集裝箱的最佳放置地點。求解得到結果如下：

參考文獻：

[1]許佳瑜.三維裝箱約束下的車輛路徑優化研究[D].長安大學，2018.2.

[2]農健恒.同尺寸物品裝箱的動態規劃算法[D].廣西大學，2014.

[3]鄭洪清.CS算法在應急救援中最佳路徑的應用研究[J].山東工業技術，2018（15）：241-242.

作者簡介：劉越（1997-），廣東潮陽人，2016級本科生，研究方向：應用統計學；王志堅（1982-），江西余干人，博士，講師，研究方向：管理統計方法。