趙鴻飛 齊玉東 司維超

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

?

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

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

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

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

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

Class Number TP202

1 引言

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

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

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

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

1) 如何將貨物分組；

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

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

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

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

2.1 變量定義

表1 物資裝載模型中的變量說明

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

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

(1)

2.3 約束條件

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

1) 重量約束

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

(2)

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

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

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

(3)

其中Pj表示第j架飛機(jī)的貨位數(shù)目。Pk∈[0,1],0表示當(dāng)前貨位沒有貨物,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) 縱向重心偏移約束

與橫向重心偏移約束類似：

H_CBj,min≤H_CBj≤H_CBj,max

(5)

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

3 Roesener算法分析

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

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

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

3.2 第二次搜索

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

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

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

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

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

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

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

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

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

4.2 改進(jìn)方法

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

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

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

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

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

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

3) 提取重量差較大的鄰域,并計算其代價

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

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

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è)定不同的鄰域計算百分比p,進(jìn)行二次禁忌搜索,并根據(jù)結(jié)果方案,計算其相關(guān)評估參數(shù)如表2所示。

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

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

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

6 結(jié)語

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

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

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

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

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

[5] 張劫.航空貨運(yùn)裝載問題算法設(shè)計與研究[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ī)工程與設(shè)計,2012,33(7):2766-2770.

[8] 周柯雯,姚愛祥基.基于遺傳算法和啟發(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日

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

TP202

10.3969/j.issn1672-9730.2015.01.012