空運裝載問題求解方法研究*

趙鴻飛 齊玉東 司維超

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

?

空運裝載問題求解方法研究*

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

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

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

空運裝載; 多目標; 重量差優先; 禁忌鄰域搜索; 優化

Class Number TP202

1 引言

物資空運裝載問題可以描述為：給定一組需要運輸的貨物以及一組可實施運輸的飛機,通過合理安排貨物在各個飛機上的位置,在滿足空間條件、重量條件和飛行平衡限制條件等基礎上,以最小代價(常具體化為最少飛機數目)實現物資的全部運輸。

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

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

本文重點研究在貨物已經被打包,并可以合適的放置在飛機貨盤上的前提下的空運裝載優化問題,包括：

1) 如何將貨物分組；

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

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

2 Roesener數學模型

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

2.1 變量定義

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

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

2.2 目標函數

(1)

2.3 約束條件

除了以上目標函數最小化帶來的動態限制,在算法求解中,還需要下面的運算基本約束。

1) 重量約束

對于每一架飛機,所載貨物的總重均不能超過飛機的載重量。可以表示為

(2)

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

2) 貨位數量約束

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

(3)

其中Pj表示第j架飛機的貨位數目。Pk∈[0,1],0表示當前貨位沒有貨物,1表示有貨物。

3) 橫向重心偏移約束

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

W_CBj,min≤W_CBj≤W_CBj,max

(4)

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

4) 縱向重心偏移約束

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

H_CBj,min≤H_CBj≤H_CBj,max

(5)

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

3 Roesener算法分析

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

3.1 初始解產生方法

較優的初始解方案意味著,對于每架飛機,要保證其空間利用和負荷載重貨物同時達到最大化。基于上述考慮,在第一次禁忌搜索中,Roesener算法試圖通過讓每一個飛機同時獲得最大載重量和最大體積,以較低的計算代價來產生一個高質量的初始解。其評定標準為：當添加任意一個貨物,飛機就會超重則認為是飛機獲得了最大載重量；當所有貨位被占用就認為是獲得了最大體積。

3.2 第二次搜索

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

經過第二次禁忌搜索的鄰域移動,根據飛機的重心調整了飛機貨物載量,并以最小化目標函數為指標,得到最終的裝運方案。

4 兩次禁忌搜索算法的改進

Roesener算法雖然求解了多目標下多載具物資裝載問題。但當存在大量物資需要裝載于多架飛機時,算法的執行效率隨著問題規模變大而出現明顯下降。通過追蹤算法的執行過程,發現其90%以上的時間都花費在鄰域搜索上面,這是因為鄰域搜索時間與物資數量、飛機數量和貨盤數量均成正比關系。因此,為了提高Roesener算法的效率,鄰域搜索算法還需進行優化,優化的方向就是在目標函數值不出現惡化的前提下,盡量減少搜索時間。

4.1 算法改進的依據

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

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

為了提高禁忌算法的搜索速度,必須降低運算的集群規模,具體來說就是減少需要計算花費的鄰域個數。單步跟蹤Roesener算法的搜索結果,發現每次鄰域搜索得到的具有最低花費的最優鄰域,其所屬的交換位置的pallet都具有較大的重量差,而且絕大部分是當前所有鄰域中重量差最大的。

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

4.2 改進方法

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

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

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

對于(pallet_num,position)二元組,其對應的鄰域為：編號為pallet_num的pallet所在的貨位編號position和其它position交換后的方案。這樣就可以保證要交換的兩個位置不同時為空。

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

遍歷所有鄰域,并根據各個鄰域的交換屬性,計算其重量差,最終形成重量差值表。實際搜索過程中,相對于計算對應的鄰域方案花費的計算量,關于pallet重量差的計算量,可以忽略不計,因此該方法是可行的。

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

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

4) 根據當前的鄰域花費代價,進行鄰域禁忌搜索計算。

5 實驗驗證

為了比較基于重量差優先的鄰域搜索算法和Roesener算法,本節應用文獻[10]中使用的部分原始實驗數據,分別應用兩種搜索算法,以驗證前者的優越性。

根據上述鄰域優化方法,設定不同的鄰域計算百分比p,進行二次禁忌搜索,并根據結果方案,計算其相關評估參數如表2所示。

表2 不同參數的搜索方案評估

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

可見,通過設置適當的提取比例,將會極大地減少計算量,同時又不影響最終的計算結果。另外二次搜索可以顯著的降低初始方案的目標函數值(20.3%),減少運輸成本。

6 結語

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

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

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

[3] 孟沖.航空兵應急轉場空運裝載方案優化研究[D].西安:空軍工程大學,2009.

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

[5] 張劫.航空貨運裝載問題算法設計與研究[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] 齊玉東,謝曉方.基于兩次禁忌搜索的軍事物資裝運方案研究[J].計算機工程與設計,2012,33(7):2766-2770.

[8] 周柯雯,姚愛祥基.基于遺傳算法和啟發策略的軍用物資飛機裝載優化[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