趙鴻飛 齊玉東 司維超

(1.91395部隊(duì)裝備處 北京 102443)(2.海軍航空工程學(xué)院兵器科學(xué)與技術(shù)系 煙臺(tái) 264001)

?

空運(yùn)裝載問(wèn)題求解方法研究*

趙鴻飛1齊玉東2司維超2

(1.91395部隊(duì)裝備處 北京 102443)(2.海軍航空工程學(xué)院兵器科學(xué)與技術(shù)系 煙臺(tái) 264001)

針對(duì)空運(yùn)裝載問(wèn)題,重點(diǎn)研究多目標(biāo)多載具裝載問(wèn)題的數(shù)學(xué)模型,并提出基于重量差優(yōu)先的禁忌鄰域搜索優(yōu)化算法來(lái)求解模型。實(shí)驗(yàn)結(jié)果表明該算法不僅保證目標(biāo)函數(shù)值不惡化,還使得解空間搜索時(shí)間大大減少,極大地提高了模型求解速度。

空運(yùn)裝載; 多目標(biāo); 重量差優(yōu)先; 禁忌鄰域搜索; 優(yōu)化

Class Number TP202

1 引言

物資空運(yùn)裝載問(wèn)題可以描述為：給定一組需要運(yùn)輸?shù)呢浳镆约耙唤M可實(shí)施運(yùn)輸?shù)娘w機(jī),通過(guò)合理安排貨物在各個(gè)飛機(jī)上的位置,在滿足空間條件、重量條件和飛行平衡限制條件等基礎(chǔ)上,以最小代價(jià)(常具體化為最少飛機(jī)數(shù)目)實(shí)現(xiàn)物資的全部運(yùn)輸。

國(guó)內(nèi)對(duì)物資裝載問(wèn)題的研究多集中在單個(gè)載具的貨物裝載方面,對(duì)多飛機(jī)多約束條件下的貨物裝載方案的研究還不是很成熟。文獻(xiàn)[1]通過(guò)構(gòu)建空間布局轉(zhuǎn)化模式,將空間布局約束轉(zhuǎn)換成0-1整數(shù)線性約束,實(shí)現(xiàn)了對(duì)0-1數(shù)線性空運(yùn)裝載問(wèn)題的求解,但如果問(wèn)題規(guī)模較大,受限于整數(shù)規(guī)劃算法,容易出現(xiàn)解空間巨大,不容易找到最優(yōu)解。在軍事裝載問(wèn)題研究方面,文獻(xiàn)[2]在分析航空兵空運(yùn)轉(zhuǎn)場(chǎng)和轉(zhuǎn)場(chǎng)物資特點(diǎn)的基礎(chǔ)上確定了轉(zhuǎn)場(chǎng)物資集約化裝載方案制定方法提出集約化裝載方案制定流程。文獻(xiàn)[3]運(yùn)用遺傳算法,采用降維、物資集約等策略,研究了軍事空運(yùn)二維裝載問(wèn)題。文獻(xiàn)[4]考慮了飛機(jī)重心、裝貨順序和物資承壓等約束條件,使用禁忌搜索算法對(duì)空運(yùn)裝載問(wèn)題進(jìn)行了求解,但仍有其它一些約束如飛機(jī)費(fèi)用、貨盤(pán)位置和飛機(jī)加油后對(duì)重心的影響等沒(méi)有加以考慮。文獻(xiàn)[5]針對(duì)陸路和水路形式的集裝箱裝載問(wèn)題,分別建立了裝載模型并給出了求解算法。文獻(xiàn)[6]研究了民航貨運(yùn)裝載問(wèn)題,在維度方面采用了二維裝載方案,但沒(méi)有考慮裝載物資對(duì)貨機(jī)重心的影響。文獻(xiàn)[7]針對(duì)當(dāng)前軍事物資裝載與運(yùn)輸問(wèn)題,映射建立數(shù)學(xué)模型,運(yùn)用兩次禁忌搜索算法自動(dòng)輸出較優(yōu)的可行運(yùn)輸方案。第一次禁忌搜索用于確定較優(yōu)的初始解,然后針對(duì)初始解,運(yùn)用第二次禁忌搜索,保證在一定時(shí)間限制條件下,對(duì)運(yùn)輸問(wèn)題進(jìn)行優(yōu)化求解。在軍事裝載問(wèn)題研究方面,文獻(xiàn)[8]以軍用物資飛機(jī)裝載為研究對(duì)象,構(gòu)造軍用物資的裝載優(yōu)化模型,并考慮裝載容積、裝載質(zhì)量及裝載密度等約束條件,提出了一種基于啟發(fā)策略的遺傳算法。

上述研究表明載具裝載物資需滿足一定的限制條件,如何綜合考慮載具數(shù)量、載具平衡條件和運(yùn)輸成本,以形成物資裝運(yùn)方案是一個(gè)有著重要應(yīng)用意義的研究方向。

本文重點(diǎn)研究在貨物已經(jīng)被打包,并可以合適的放置在飛機(jī)貨盤(pán)上的前提下的空運(yùn)裝載優(yōu)化問(wèn)題,包括：

1) 如何將貨物分組；

2) 如何選取合適的一組飛機(jī),包括飛機(jī)類(lèi)型以及飛機(jī)數(shù)量；

3) 如何將貨物放置在合理的位置上,并滿足飛機(jī)的配重要求。

2 Roesener數(shù)學(xué)模型

Roesener等[9～10]對(duì)空運(yùn)裝載問(wèn)題進(jìn)行了深入的研究,給出了數(shù)學(xué)模型和求解算法,不妨將該數(shù)學(xué)模型稱(chēng)為Roesener模型。Roesener模型主要包含目標(biāo)函數(shù)、約束條件以及一些相關(guān)子過(guò)程的計(jì)算方法,其中,目標(biāo)函數(shù)綜合考慮了飛機(jī)數(shù)量、飛機(jī)重量、空間以及平衡性的限制等條件下的物資裝運(yùn)代價(jià)。

2.1 變量定義

表1 物資裝載模型中的變量說(shuō)明

在給出模型之前,首先給出模型中用到的變量及其說(shuō)明,如表1所示。

2.2 目標(biāo)函數(shù)

(1)

2.3 約束條件

除了以上目標(biāo)函數(shù)最小化帶來(lái)的動(dòng)態(tài)限制,在算法求解中,還需要下面的運(yùn)算基本約束。

1) 重量約束

對(duì)于每一架飛機(jī),所載貨物的總重均不能超過(guò)飛機(jī)的載重量?？梢员硎緸?/p>

(2)

其中Wj表示第j架飛機(jī)的載重量上限。

2) 貨位數(shù)量約束

對(duì)于每一架飛機(jī),所載貨物打包數(shù)量不能超過(guò)每一架飛機(jī)上的貨位數(shù)目。

(3)

其中Pj表示第j架飛機(jī)的貨位數(shù)目。Pk∈[0,1],0表示當(dāng)前貨位沒(méi)有貨物,1表示有貨物。

3) 橫向重心偏移約束

橫向重心偏移盡管在一定范圍上是允許的,但在算法運(yùn)算中,為了增加運(yùn)算速度,仍需要進(jìn)一步限制這一偏移的大小。有以下約束：

W_CBj,min≤W_CBj≤W_CBj,max

(4)

其中W_CBj,min和W_CBj,max分別為飛機(jī)j的橫向重心邊界值。

4) 縱向重心偏移約束

與橫向重心偏移約束類(lèi)似：

H_CBj,min≤H_CBj≤H_CBj,max

(5)

其中H_CBj,min和H_CBj,max分別為飛機(jī)j的縱向重心邊界值。

3 Roesener算法分析

為了求解多目標(biāo)下多載具物資裝載問(wèn)題,Roesener等運(yùn)用兩次禁忌搜索算法得到可行運(yùn)輸方案,不妨將此算法稱(chēng)為Roesener算法。訪算法將第一次禁忌搜索用于確定較優(yōu)的初始解,然后針對(duì)初始解,運(yùn)用第二次禁忌搜索,保證在一定時(shí)間限制條件下,對(duì)運(yùn)輸問(wèn)題進(jìn)行優(yōu)化求解。

3.1 初始解產(chǎn)生方法

較優(yōu)的初始解方案意味著,對(duì)于每架飛機(jī),要保證其空間利用和負(fù)荷載重貨物同時(shí)達(dá)到最大化?；谏鲜隹紤],在第一次禁忌搜索中,Roesener算法試圖通過(guò)讓每一個(gè)飛機(jī)同時(shí)獲得最大載重量和最大體積,以較低的計(jì)算代價(jià)來(lái)產(chǎn)生一個(gè)高質(zhì)量的初始解。其評(píng)定標(biāo)準(zhǔn)為：當(dāng)添加任意一個(gè)貨物,飛機(jī)就會(huì)超重則認(rèn)為是飛機(jī)獲得了最大載重量；當(dāng)所有貨位被占用就認(rèn)為是獲得了最大體積。

3.2 第二次搜索

第二次禁忌搜索是在第一次搜索得到的初始解的基礎(chǔ)上,考慮重心越界問(wèn)題,其目標(biāo)是,在滿足各種限制的前提下,選擇目標(biāo)函數(shù)最小的最優(yōu)方案。Roesener算法使用了一種動(dòng)態(tài)鄰域選擇機(jī)制,在不同的運(yùn)行上下文中根據(jù)飛機(jī)裝載貨物情況來(lái)選擇合適的鄰域操作。

經(jīng)過(guò)第二次禁忌搜索的鄰域移動(dòng),根據(jù)飛機(jī)的重心調(diào)整了飛機(jī)貨物載量,并以最小化目標(biāo)函數(shù)為指標(biāo),得到最終的裝運(yùn)方案。

4 兩次禁忌搜索算法的改進(jìn)

Roesener算法雖然求解了多目標(biāo)下多載具物資裝載問(wèn)題。但當(dāng)存在大量物資需要裝載于多架飛機(jī)時(shí),算法的執(zhí)行效率隨著問(wèn)題規(guī)模變大而出現(xiàn)明顯下降。通過(guò)追蹤算法的執(zhí)行過(guò)程,發(fā)現(xiàn)其90%以上的時(shí)間都花費(fèi)在鄰域搜索上面,這是因?yàn)猷徲蛩阉鲿r(shí)間與物資數(shù)量、飛機(jī)數(shù)量和貨盤(pán)數(shù)量均成正比關(guān)系。因此,為了提高Roesener算法的效率,鄰域搜索算法還需進(jìn)行優(yōu)化,優(yōu)化的方向就是在目標(biāo)函數(shù)值不出現(xiàn)惡化的前提下,盡量減少搜索時(shí)間。

4.1 算法改進(jìn)的依據(jù)

待裝載物資首先要進(jìn)行規(guī)格化為包裝體(pallet),然后將其固定到飛機(jī)貨位上。一般的,同種型號(hào)的飛機(jī),其貨位數(shù)是固定的。在二次禁忌搜索優(yōu)化的過(guò)程中,當(dāng)前裝載方案的鄰域可以定義為：如果兩個(gè)貨位(并不局限于同機(jī))不同時(shí)為空,那么交換這兩個(gè)貨位后的新裝載方案,即為當(dāng)前裝載方案的一個(gè)鄰域。

定義一個(gè)二元組pallet(aircraft_id,position),其中元組中的第一個(gè)元素為飛機(jī)編號(hào),第二個(gè)元素為貨位放置的pallet編號(hào)。那么貨物可以用一個(gè)二元組pallet(aircraft_id,position)來(lái)表示,如第3架飛機(jī)的第5個(gè)貨位,可以標(biāo)示為pallet(3,5)。任意交換兩個(gè)貨位上的貨物后的方案,即為當(dāng)前方案的一個(gè)鄰域。

為了提高禁忌算法的搜索速度,必須降低運(yùn)算的集群規(guī)模,具體來(lái)說(shuō)就是減少需要計(jì)算花費(fèi)的鄰域個(gè)數(shù)。單步跟蹤Roesener算法的搜索結(jié)果,發(fā)現(xiàn)每次鄰域搜索得到的具有最低花費(fèi)的最優(yōu)鄰域,其所屬的交換位置的pallet都具有較大的重量差,而且絕大部分是當(dāng)前所有鄰域中重量差最大的。

根據(jù)這一線索,仔細(xì)分析目標(biāo)函數(shù),可以發(fā)現(xiàn)pallets的重量影響五個(gè)費(fèi)用因素中的三個(gè),也就意味著重量是目標(biāo)函數(shù)中的關(guān)鍵敏感性因素,較大的重量差將顯著影響目標(biāo)函數(shù)的取值。因此,重量因子相對(duì)于目標(biāo)函數(shù)的其他變量因子,具有較大的影響力,也即,目標(biāo)函數(shù)對(duì)重量相對(duì)更加敏感。顯然,在鄰域禁忌搜索中,具有較高敏感性的重量差越大的兩個(gè)pallets交換,將優(yōu)先成為當(dāng)前鄰域的最優(yōu)計(jì)算方案。

4.2 改進(jìn)方法

基于上述思想,本文提出基于重量差優(yōu)先的禁忌鄰域搜索算法,即在鄰域搜索過(guò)程中,通過(guò)排除重量差較小的pallets位置交換,減少鄰域計(jì)算搜索的次數(shù),從而加快禁忌搜索的時(shí)間,具體方法如下所述。

1) 保證交換的貨位不全為空

實(shí)際鄰域搜索過(guò)程,兩個(gè)空位置的交換是沒(méi)有意義的。為了保證要交換的貨位不同時(shí)為空,定義這樣一個(gè)二元組：(pallet_num,position)。其中pallet_num代表pallet編號(hào),position代表貨位編號(hào)(相對(duì)于全部飛機(jī)而言)。

對(duì)于(pallet_num,position)二元組,其對(duì)應(yīng)的鄰域?yàn)椋壕幪?hào)為pallet_num的pallet所在的貨位編號(hào)position和其它position交換后的方案。這樣就可以保證要交換的兩個(gè)位置不同時(shí)為空。

2) 計(jì)算當(dāng)前方案鄰域的重量差值表

遍歷所有鄰域,并根據(jù)各個(gè)鄰域的交換屬性,計(jì)算其重量差,最終形成重量差值表。實(shí)際搜索過(guò)程中,相對(duì)于計(jì)算對(duì)應(yīng)的鄰域方案花費(fèi)的計(jì)算量,關(guān)于pallet重量差的計(jì)算量,可以忽略不計(jì),因此該方法是可行的。

3) 提取重量差較大的鄰域,并計(jì)算其代價(jià)

由于重量并不是目標(biāo)函數(shù)的唯一敏感變量,而只是其中較為敏感的一個(gè),為了平衡其他敏感變量的影響,需要提取多個(gè)而不是唯一的一個(gè)鄰域。根據(jù)設(shè)定的提取比例,提取重量差最大的鄰域方案,并計(jì)算提取的鄰域花費(fèi)。

4) 根據(jù)當(dāng)前的鄰域花費(fèi)代價(jià),進(jìn)行鄰域禁忌搜索計(jì)算。

5 實(shí)驗(yàn)驗(yàn)證

為了比較基于重量差優(yōu)先的鄰域搜索算法和Roesener算法,本節(jié)應(yīng)用文獻(xiàn)[10]中使用的部分原始實(shí)驗(yàn)數(shù)據(jù),分別應(yīng)用兩種搜索算法,以驗(yàn)證前者的優(yōu)越性。

根據(jù)上述鄰域優(yōu)化方法,設(shè)定不同的鄰域計(jì)算百分比p,進(jìn)行二次禁忌搜索,并根據(jù)結(jié)果方案,計(jì)算其相關(guān)評(píng)估參數(shù)如表2所示。

表2 不同參數(shù)的搜索方案評(píng)估

由表2可知,第一次禁忌搜索得到的方案,最大利用了飛機(jī)的貨艙空間和負(fù)荷載重貨物,但由于沒(méi)有考慮飛機(jī)的重心偏移問(wèn)題,方案并不一定是可行解,經(jīng)過(guò)第二次禁忌搜索的鄰域移動(dòng),根據(jù)飛機(jī)的重心調(diào)整了飛機(jī)貨物載量,并以最小化目標(biāo)函數(shù)為指標(biāo),得到表2所示的二次較優(yōu)的可行裝運(yùn)方案。

可見(jiàn),通過(guò)設(shè)置適當(dāng)?shù)奶崛”壤?將會(huì)極大地減少計(jì)算量,同時(shí)又不影響最終的計(jì)算結(jié)果。另外二次搜索可以顯著的降低初始方案的目標(biāo)函數(shù)值(20.3%),減少運(yùn)輸成本。

6 結(jié)語(yǔ)

為了高效求解物資空運(yùn)裝載問(wèn)題,本文針對(duì)所建立的數(shù)學(xué)模型,提出了基于重量差優(yōu)先的禁忌鄰域搜索優(yōu)化算法,實(shí)驗(yàn)結(jié)果表明在二次搜索過(guò)程中,采用鄰域優(yōu)化算法處理的搜索方案,可以使得搜索時(shí)間大大減少,實(shí)驗(yàn)結(jié)果驗(yàn)證了該算法的可行性和優(yōu)越性。

[1] 孟沖,宋華文,陳柏松.規(guī)劃的軍事空運(yùn)裝載優(yōu)化算法[J].西南交通大學(xué)學(xué)報(bào),2011(3):500-505.

[2] 張克舉,孫波,劉天寶.航空兵成建制空運(yùn)轉(zhuǎn)場(chǎng)集約化裝載方案研究[J].科技信息,2012,33:636-637.

[3] 孟沖.航空兵應(yīng)急轉(zhuǎn)場(chǎng)空運(yùn)裝載方案優(yōu)化研究[D].西安:空軍工程大學(xué),2009.

[4] 張軍.軍事空運(yùn)裝載問(wèn)題的禁忌搜索算法實(shí)現(xiàn)[J].國(guó)防交通工程與技術(shù),2010,8(6):32-35.

[5] 張劫.航空貨運(yùn)裝載問(wèn)題算法設(shè)計(jì)與研究[J].計(jì)算機(jī)工程,2007,39(5):28-30.

[6] Mongeau Marcel, Bes Christian. Optimization of aircraft container loading[J]. IEEE Tractions on Aerospace and Electronic Systems,2003,39(1):140-150.

[7] 齊玉東,謝曉方.基于兩次禁忌搜索的軍事物資裝運(yùn)方案研究[J].計(jì)算機(jī)工程與設(shè)計(jì),2012,33(7):2766-2770.

[8] 周柯雯,姚愛(ài)祥基.基于遺傳算法和啟發(fā)策略的軍用物資飛機(jī)裝載優(yōu)化[J].物流科技,2010(9):122-124.

[9] Nance R. L., Roesener A. G., Moore J T. An Advanced Tabu Search Approach to the mixed payload Airlift Loading Problem[J]. Journal of the Operational Research Society,2011,62(2):337-347.

[10] Roesener A. G., Hall S N. A Nonlinear Integer Programming Formulation for the Airlift Loading Problem with Insufficient Aircraft[J]. Journal of Nonlinear Analysis and Optimization: Theory & Application,2014:87-92.

Solving Method on Airlift Loading Problem

ZHAO Hongfei1QI Yudong2SI Weichao2

(1. Equipment Department, No. 91395 Troops of PLA, Beijing 102443) (2. Department of Ordnance Science and Technology, Naval Aeronautical and Astronautical University, Yantai 264001)

The paper researched on the problem of airlift loading. It researched the problem mathematical model with multi-object and multi-carrier. And it established an algorithm of tabu neighborhood search with weight difference first, which can be used for solving the airlift loading optimization problem. The result showed that the algorithm can not only assure the target function not worse, but also reduce the search time and enhance the solving speed on the model.

airlift loading, multi-object, weight difference first, tabu search, optimization

2014年7月16日,

2014年8月26日

趙鴻飛,男,高級(jí)工程師,研究方向:裝備保障。齊玉東,男,博士,教授,研究方向:指揮控制。司維超,男,博士,講師,研究方向:指揮控制。

TP202

10.3969/j.issn1672-9730.2015.01.012