劉越 王志堅(jiān)

摘 要：本文研究了救援響應(yīng)系統(tǒng)開(kāi)發(fā)，在裝箱問(wèn)題上面對(duì)客觀約束采用非線性規(guī)劃模型，在空間利用率達(dá)到最大化的目標(biāo)函數(shù)下，對(duì)貨物的數(shù)量、旋轉(zhuǎn)方向、體積和承載重量做出約束，再使用動(dòng)態(tài)規(guī)劃模型確定裝箱方案。在配送集裝箱時(shí)分3種情況構(gòu)造模型，分為停靠1個(gè)、2個(gè)和3個(gè)港口，遍歷港口與5個(gè)醫(yī)療包交貨地點(diǎn)間的距離并篩選得到最小距離求得對(duì)應(yīng)的?？扛劭?。

關(guān)鍵詞：非線性規(guī)劃；動(dòng)態(tài)規(guī)劃；遍歷

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

1 研究背景

2017年美國(guó)波多黎各遭受當(dāng)?shù)厥飞献顕?yán)重颶風(fēng)，造成了嚴(yán)重破壞和重大人員傷亡。非政府組織HELP，Inc通過(guò)設(shè)計(jì)“DroneGo”可移動(dòng)災(zāi)難響應(yīng)系統(tǒng)來(lái)提高其救援響應(yīng)能力。HELP，Inc已經(jīng)確定使用各種旋翼無(wú)人機(jī)來(lái)組成DroneGo車隊(duì)。為了增加受災(zāi)現(xiàn)場(chǎng)的援助用品，DroneGo準(zhǔn)備了三種醫(yī)療包MED1、MED2和MED3。無(wú)人機(jī)承擔(dān)運(yùn)輸醫(yī)療包的任務(wù)，可以通過(guò)外部貨艙運(yùn)輸多個(gè)醫(yī)療包。本文根據(jù)各營(yíng)救點(diǎn)的需求及救援路線和偵查路線為HELP，Inc解決營(yíng)救計(jì)劃的包裝配置和物資運(yùn)輸問(wèn)題。結(jié)合波多黎各的颶風(fēng)災(zāi)難情景，為最多三個(gè)標(biāo)準(zhǔn)ISO集裝箱設(shè)計(jì)相關(guān)的包裝配置，形成HELP，Inc設(shè)計(jì)無(wú)人機(jī)隊(duì)和醫(yī)療包裝配方案。找到波多黎各的最佳位置，確定DroneGo災(zāi)難響應(yīng)系統(tǒng)一個(gè)或多個(gè)集裝箱位置，有利于提供醫(yī)療服務(wù)和道路視頻偵察。

2 裝箱問(wèn)題與包裝配置

無(wú)論是醫(yī)療包放進(jìn)無(wú)人機(jī)外部貨艙和運(yùn)輸集裝箱，還是運(yùn)輸集裝箱放進(jìn)ISO集裝箱，都要與集裝箱邊線平行，即正交布局。

要求最多使用三個(gè)標(biāo)準(zhǔn)ISO集裝箱，本文運(yùn)用非線性規(guī)劃模型，把醫(yī)療包放入無(wú)人機(jī)的外部貨艙，將無(wú)人機(jī)和剩余醫(yī)療包放入運(yùn)輸集裝箱內(nèi)，再把運(yùn)輸集裝箱按數(shù)量最大限度地裝載進(jìn)標(biāo)準(zhǔn)ISO集裝箱，即研究三維裝箱問(wèn)題，假設(shè)各種集裝箱和醫(yī)療包的形狀都是規(guī)則的長(zhǎng)方形，它們的重心即其幾何中心，對(duì)此建立空間直角坐標(biāo)系?？紤]目標(biāo)函數(shù)和現(xiàn)實(shí)約束，其中需要注意的是無(wú)人機(jī)的運(yùn)輸集裝箱只能正交旋轉(zhuǎn)90°，不能對(duì)任何運(yùn)輸物品進(jìn)行倒置或側(cè)放。

3 集裝箱?？课恢眠x取

裝載包裝配置后需要將標(biāo)準(zhǔn)ISO集裝箱進(jìn)行分配派送，需獲取1個(gè)、2個(gè)或3個(gè)最佳?？课恢?。由于最多使用3個(gè)港口，故分3種情況構(gòu)造模型。

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

結(jié)合醫(yī)療包交貨地點(diǎn)的經(jīng)緯度，繪制地圖如下圖1：

先建立平面直角坐標(biāo)系，再將波多黎各地圖上任意一點(diǎn)A與任意一點(diǎn)B的經(jīng)緯度換算為平面直角坐標(biāo)系上兩個(gè)坐標(biāo)點(diǎn)，并求這兩點(diǎn)之間的直線距離：

當(dāng)集裝箱僅?？吭谝粋€(gè)港口時(shí)，計(jì)算每個(gè)醫(yī)療包交貨地點(diǎn)與此港口間的距離，把最短距離對(duì)應(yīng)的港口作為最佳位置。

當(dāng)為兩個(gè)港口時(shí)，從11個(gè)港口中隨機(jī)抽取2個(gè)，共有C211種可能。記為港口A和港口B，將五個(gè)醫(yī)療包交貨地點(diǎn)隨機(jī)分配給這兩個(gè)港口。

其中港口A分得m個(gè)醫(yī)療包交貨地點(diǎn)，則港口B分得5-m個(gè)交貨地點(diǎn)（m=1，2，3，4）。計(jì)算港口與所分配交貨地點(diǎn)間的距離，求和得到分配方案總距離。通過(guò)遍歷方法篩選出多種分配方案總距離最小值，把該種方案對(duì)應(yīng)的兩個(gè)?？扛劭谝暈樽罴淹？课恢谩?/p>

當(dāng)標(biāo)準(zhǔn)ISO集裝箱?？咳齻€(gè)港口時(shí)，從11個(gè)港口中任意抽取三個(gè)港口，將5個(gè)醫(yī)療包交貨地點(diǎn)隨機(jī)分配給這三個(gè)港口。同理可得多種分配方案的總距離最小值，把該種方案確定的三個(gè)?？扛劭谝暈樽罴盐恢?。

4 研究結(jié)論

對(duì)本文非線性規(guī)劃的約束條件和目標(biāo)函數(shù)使用python求解，得到結(jié)果如下：

本文為災(zāi)難響應(yīng)系統(tǒng)設(shè)置2臺(tái)E型無(wú)人機(jī)，1個(gè)H Tethered平臺(tái)，363個(gè)E型運(yùn)輸集裝箱，1個(gè)H型運(yùn)輸集裝箱和3個(gè)標(biāo)準(zhǔn)ISO集裝箱。其中會(huì)出現(xiàn)兩種裝載情況，第一種情況是用無(wú)人機(jī)外部攜帶的貨艙裝載醫(yī)療包，運(yùn)輸集裝箱裝載無(wú)人機(jī)；第二種情況是僅用運(yùn)輸集裝箱裝載醫(yī)療包。再把所有運(yùn)輸集裝箱放進(jìn)ISO集裝箱。

使用C++對(duì)包裝配置的動(dòng)態(tài)規(guī)劃二維裝箱模型進(jìn)行裝載計(jì)算，其中兩個(gè)標(biāo)準(zhǔn)ISO集裝箱，一個(gè)內(nèi)部裝載126個(gè)E型運(yùn)輸集裝箱，空間利用率為85.1%。另一個(gè)裝載111個(gè)E型運(yùn)輸集裝箱和1個(gè)H型運(yùn)輸集裝箱，其中有兩個(gè)E型運(yùn)輸集裝箱裝載E型無(wú)人機(jī)，H型運(yùn)輸集裝箱裝載H Tethered平臺(tái)，空間利用率為85%。兩種裝箱方案的空間利用率較高，是可行的結(jié)果。其中醫(yī)療包放進(jìn)運(yùn)輸集裝箱的方法有兩種：第一種方法是3個(gè)MED1和3個(gè)MED3。第二種方法是4個(gè)MED1，2個(gè)MED2和3個(gè)MED3；且每一天所需醫(yī)療包的包裝量剛好滿足兩個(gè)E型運(yùn)輸集裝箱的最大承重能力，裝載后的剩余運(yùn)輸集裝箱底面面積相對(duì)較少。

在尋找最佳位置的模型中，通過(guò)python多次遍歷計(jì)算得到在3種情況中港口與醫(yī)療包交貨地點(diǎn)之間的距離，并自動(dòng)篩選出之中的最短距離，其對(duì)應(yīng)的港口即為標(biāo)準(zhǔn)ISO集裝箱的最佳放置地點(diǎn)。求解得到結(jié)果如下：

參考文獻(xiàn)：

[1]許佳瑜.三維裝箱約束下的車輛路徑優(yōu)化研究[D].長(zhǎng)安大學(xué)，2018.2.

[2]農(nóng)健恒.同尺寸物品裝箱的動(dòng)態(tài)規(guī)劃算法[D].廣西大學(xué)，2014.

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

作者簡(jiǎn)介：劉越（1997-），廣東潮陽(yáng)人，2016級(jí)本科生，研究方向：應(yīng)用統(tǒng)計(jì)學(xué)；王志堅(jiān)（1982-），江西余干人，博士，講師，研究方向：管理統(tǒng)計(jì)方法。