基于兩次禁忌搜索的軍事物資裝運方案研究

齊玉東，齊玉華，謝曉方

（1.海軍航空工程學(xué)院 計算機教研室，山東 煙臺264001；2.國防科學(xué)技術(shù)大學(xué) 計算機學(xué)院，湖南 長沙410073）

0 引 言

現(xiàn)代戰(zhàn)爭中，由于戰(zhàn)爭的突然性以及戰(zhàn)場地點的不確定性，要求我方必須具有強大的軍事力量投送能力，從而能及時有效的將戰(zhàn)爭急需的人員和武器裝備物資投入戰(zhàn)場，積極搶占戰(zhàn)爭主導(dǎo)權(quán)。在有限的運輸資源，如何分配各種資源運輸，并在劃定的時間段中安全有效的完成特定大量的物資裝載與運輸問題，顯然是局部尋優(yōu)最小化問題，并已證明是 NP－h(huán)ard［1－3］。文獻 ［4］對具有廣泛應(yīng)用背景、多約束條件和求解困難的集裝箱裝載問題，引入具有人工智能記憶機制、基于鄰域搜索而避免局部最優(yōu)的禁忌搜索算法，探討了在求解集裝箱裝載問題中禁忌搜索的編碼、解碼和鄰域解生成等關(guān)鍵技術(shù)。文獻 ［5］根據(jù)軍事空運裝載的特點，建立了空運裝載的數(shù)學(xué)模型，討論了求解空運裝載問題的緊急搜索算法編碼、解碼、評價函數(shù)、鄰域操作和禁忌表等關(guān)鍵問題，實現(xiàn)了對空運裝載問題的求解。文獻 ［6］針對物資裝載問題提出了一種可變鄰域搜索 （VNS）算法，其基于最大空或類禁忌搜索方法對物資裝載和運輸問題進行研究，但是搜索時間過長，不利于實際應(yīng)用，本文針對此問題，提出兩次禁忌搜索，第一次禁忌搜索生成初始解，然后進行第二次禁忌搜索對初始解進行鄰域優(yōu)化移動。這樣通過第一次搜索的較優(yōu)初始解，限制了第二次禁忌搜索的隨機性，使總體搜索過程更快速有效。

1 Tabu簡介

1.1 算法概述

禁忌搜索算法思想由Glover等人于1985年最早提出，其是對局部鄰域搜索的一種擴展，本質(zhì)是一種全局逐步尋優(yōu)算法，是對人類思考問題過程的一種模擬。禁忌搜索為了避免迂回搜索，引入了一個靈活的存儲結(jié)構(gòu)和相應(yīng)的禁忌準(zhǔn)則，并通過藐視準(zhǔn)則赦免一些被禁忌的優(yōu)良狀態(tài)，進而保證多樣化的有效搜索以最終實現(xiàn)全局尋優(yōu)。為了避免重復(fù)搜索某些局部最優(yōu)解，禁忌搜索維持一個禁忌表，根據(jù)特定算法標(biāo)記一些局部最優(yōu)解，并在后續(xù)搜索過程中跳過已標(biāo)記過得最優(yōu)解，從而保證對不同的有效搜索途徑進行搜索，因此具有較強的爬山能力［7］。禁忌搜索涉及到鄰域、禁忌表、禁忌長度、候選解、藐視準(zhǔn)則等參數(shù)概念。

對上述基本算法的修改則衍生了各種版本的改進禁忌搜索算法，如根據(jù)調(diào)整禁忌長度的算法不同，可分為自適應(yīng)禁忌搜索 （ATS）和反應(yīng)禁忌搜索 （RTS）算法［8］。

1.2 算法基本思想

基礎(chǔ)禁忌搜索算法的基本流程如下［9－10］：

（1）設(shè)定參數(shù)值，隨機生成初始解x，bestsofar＝x，并將禁忌表設(shè)置為空。

（2）若終止條件成立，終止算法并輸出結(jié)果，否則，繼續(xù)搜索。

（3）利用當(dāng)前解的鄰域函數(shù)抽樣生成若干鄰域解，并從中根據(jù)目標(biāo)函數(shù)確定若干候選解。

（4）判斷是否滿足藐視準(zhǔn)則，若滿足，則用滿足藐視準(zhǔn)則的最優(yōu)解替換當(dāng)前解，同時將此最優(yōu)解對應(yīng)的對象列入禁忌表，并替換bestsofar值，轉(zhuǎn)入步驟 （6），否則繼續(xù)。

（5）根據(jù)候選解對應(yīng)對象的禁忌屬性，搜索禁忌表，將非禁忌對象中的最佳狀態(tài)確認為當(dāng)前解，并根據(jù) “先入先出”原則，替換禁忌表中的禁忌對象。

（6）轉(zhuǎn)步驟 （2）。

上述算法過程為禁忌搜索的基礎(chǔ)，可以對具體環(huán)節(jié)進行精化和改進，構(gòu)造出多種新的禁忌搜索算法。其中，算法中所述禁忌對象，可以是具體的搜索操作，也可以是搜索狀態(tài)和搜索目標(biāo)值等等。

2 基于禁忌搜索算法的物資裝載與運輸問題

一般的，將運輸方式分為空運、陸運和水運3種方式。由于空運具有較大的時間優(yōu)勢，能夠?qū)⒅匾奈镔Y以最快的速度運達目的地，因此3種運輸方式首先考慮空運。但是相對陸運和水運，空運又具有負荷載重低，有效利用空間小，可用數(shù)量有限等不利因素，因此必須根據(jù)物資的屬性 （重量和體積）及重要性，使用禁忌搜索算法得出在滿足時間限制條件下的成本最小的運輸飛機數(shù)，若運輸飛機數(shù)不能滿足需求，則將剩余的物資進行陸運和水運。

2.1 物資空運

由于禁忌搜索是一種基于鄰域的智能搜索算法，具有一定的隨機性，為了使搜索過程更為快速有效，論文使用兩次禁忌搜索。不同于一般禁忌搜索隨即生成初始解，本文初始解由第一次禁忌搜索輸出生成，然后進行第二次禁忌搜索對初始解進行鄰域優(yōu)化移動。

2.1.1 一次禁忌搜索生成初始解

禁忌搜索算法本質(zhì)是一種基于鄰域的方案移動，即在現(xiàn)有方案的領(lǐng)域中選擇一個最優(yōu)，并替換現(xiàn)有方案，因此其初始解并不要求為可行解，但是較優(yōu)的方案則可以極大減少禁忌算法的搜索時間。具體到空運問題，較優(yōu)的初始解方案意味著，對于每架飛機，要保證其空間利用和負荷載重貨物同時達到最大化。其中空間利用最大化是指貨盤數(shù)目全部占用，負荷載重貨物最大化則是指不可增加貨物，否則負荷載重超過飛機額定載重量。本文使用第一次禁忌搜索算法，尋找較優(yōu)的初始解。

詳細步驟如下：

（1）飛機索引變量置0。

（2）若全部飛機已被索引，則結(jié)束搜索，否則轉(zhuǎn) （3）。

（3）找出一架飛機，該飛機的額定載重量與其貨盤數(shù)量的比值最大。

（4）若①全部物資沒有被裝入飛機，且②該飛機空間沒有被全部利用或載重量沒有完全被利用，轉(zhuǎn) （5），否則轉(zhuǎn) （2）。

（5）禁忌表操作計數(shù)器加1。

（6）若①該架飛機空間沒有被全部利用，且②載重量沒有完全被利用，轉(zhuǎn) （7），否則轉(zhuǎn) （8）。

（7）對于每一組物資，如果將其裝入當(dāng)前選定的飛機時，并不會造成飛機容積和載重量越界，則將該組物資裝入飛機。轉(zhuǎn) （12）。

（8）若該架飛機空間沒有被全部利用但載重量已完全被利用，轉(zhuǎn) （9），否則轉(zhuǎn) （10）。

（9）依次進行以下操作：①從飛機上取下最重的物資，并將其放回原始物資組；②更新禁忌表；③按照從輕到重的順序，依次從物資組中，選取重量最輕的物資，直到找到一個物資能被放入飛機或已遍歷所有物資組。轉(zhuǎn) （12）。

（10）若①該架飛機空間已被全部利用，且②載重量沒有完全被利用，轉(zhuǎn) （11），否則轉(zhuǎn) （12）。

（11）依次進行以下操作：①從飛機上取下最輕的物資，并將其放回原始物資組；②更新禁忌表；③按照從重到輕的順序，依次從物資組中，選取重量最重的物資，直到找到一個物資能被放入飛機或已遍歷所有物資組。轉(zhuǎn)（12）。

（12）若飛機上的物資發(fā)生變化，轉(zhuǎn) （13），否則轉(zhuǎn)（14）。

（13）循環(huán)變量置0，轉(zhuǎn) （15）。

（14）循環(huán)變量加1。

（15）若已經(jīng)循環(huán)了10次，飛機上的物資一直沒有發(fā)生變化，轉(zhuǎn) （2），否則轉(zhuǎn) （4）。

由上述流程可知，本次搜索的基本思想是使每個飛機的空間利用和負荷載重貨物同時達到最大化，但是因為本次搜索沒有考慮飛機重心越界問題，因此得出的方案通常為次優(yōu)，甚至是不可行方案。為了找到滿足各個約束的較優(yōu)可行解方案，需要進行第二次禁忌搜索。

2.1.2 二次禁忌搜索優(yōu)化初始解

本次禁忌搜索是在第一次搜索得到的初始解的基礎(chǔ)上，考慮重心越界問題，其目標(biāo)是，在滿足各種限制的前提下，移向目標(biāo)函數(shù)最小的可行方案。

設(shè)物資 （已打包）總數(shù)為N，運輸飛機總數(shù)為M。

（1）目標(biāo)函數(shù)為

限制條件為

λ1，物資未被完全裝載時的懲罰系數(shù)。

Cj，飛機j的使用成本。

WFj，飛機j的利用率。

λ2，飛機未被充分利用時的懲罰系數(shù)。

W＿CBj，飛機裝入所有物資后的橫向重心位置

式中：Wk——物資k的重量，DWk——物資k的重點到飛機重心縱向參考線的距離，Kj——已裝入飛機j的物資集合。xj，min、xj，max——飛機j的橫向重心邊界值。

λ3，飛機橫向重心偏離時的懲罰系數(shù)。

H＿CBj，飛機裝入所有物資后的縱向重心位置

式中：Wk——物資k的重量，DHk——物資k的重點到飛機重心橫向參考線的距離，Kj——已裝入飛機j的物資集合。yj，min、yj，max——飛機j的縱向重心邊界值。

λ4，飛機縱向重心偏離時的懲罰系數(shù)。

（2）下限解與上限解

下限解為

式中：N——物資總數(shù)目，NP—— 一架飛機貨艙中的貨盤總數(shù)，WN——物資的總重量，ACLP—— 一架飛機的額定載重。

上限解為執(zhí)行空運的部隊所能提供的最大運輸機數(shù)量。

（3）領(lǐng)域操作算法

1）迭代變量初始化。

2）若①持續(xù)沒有改善的迭代次數(shù)不大于規(guī)定的次數(shù)，且②輕微改善迭代次數(shù)不大于規(guī)定的次數(shù)，且③禁忌迭代次數(shù)不大于規(guī)定的次數(shù)，則轉(zhuǎn)2），否則結(jié)束搜索。

3）若全部物資已被裝入飛機，則轉(zhuǎn)6），否則轉(zhuǎn)4）。

4）若某個飛機上仍有空的位置，則獲得剩余載重能力最大且空位置最多的飛機，否則，找出一架可用的飛機，該飛機的額定載重量與其貨盤數(shù)量的比值最大。

5）找到未被裝入飛機的最重的物資。將其放入飛機。更新禁忌表。

6）若某架飛機的重心偏離越界，轉(zhuǎn)7），否則轉(zhuǎn)8）。

7）重心調(diào)整次數(shù)加1，調(diào)整已裝入該架飛機的物資的位置，若調(diào)整后沒有效果，則撤消調(diào)整操作，重心調(diào)整次數(shù)置0，否則，更新禁忌表，轉(zhuǎn)11）。

8）若①有某架飛機空間沒有被全部利用，或②非空飛機的數(shù)量大于下限解且對候選解已進行了一定程度的改進，或③非空飛機的數(shù)量大于下限解且候選解沒有得到一定的改進，轉(zhuǎn)9），否則轉(zhuǎn)10）。

9）從載重量最輕的飛機上取下所有物資，并將取下的最重的物資裝入載重量最輕的飛機，更新禁忌表，轉(zhuǎn)11）。

10）在非空飛機之間調(diào)換物資，更新禁忌表，轉(zhuǎn)11）。

11）針對候選解計算目標(biāo)函數(shù)值，轉(zhuǎn)2）。

2.2 陸運、水運方式的裝載與運輸

若空運裝載時，運輸飛機數(shù)量不能滿足需求，則將剩余物資按公路、水路方式運輸。求解過程如下：

（1）參考運輸網(wǎng)絡(luò)，對每一個物資指定初始解，即每一種物資的起始點、起始時間、到達點、到達時間、運輸方式。

（2）根據(jù)物資體積和重量計算所需的載具數(shù)量。

（3）將晚到的物資按照晚到懲罰度從大到小排序后，生成一個晚到物資清單。

（4）對晚到物資清單中的所有物資在相同的起始點－到達點領(lǐng)域內(nèi)進行禁忌搜索，得到可減少晚到懲罰度后的物資清單。

（5）重復(fù) （3）、（4）。

（6）重復(fù) （2）。

3 實例求解

海軍航空兵某一飛行團實施機動轉(zhuǎn)場到A地 （到達點），所需要的彈藥裝備型號及時間要求見表1，各個彈藥起始點所裝運的彈藥裝備數(shù)量、可以采用的運輸方式、及各種載具的性能參數(shù)分別見表2～表4。

表1 彈藥裝備型號

表2 起始點需裝運的彈藥裝備數(shù)量

表3 起始點可以使用的載具數(shù)量

表4 載具性能參數(shù)

按照前述進行第一次禁忌搜索，得到最大利用飛機貨倉空間和負荷載重貨物的初始解方案見表5。

表5 飛機裝運方案

將表5所示初始方案作為初始解輸入，并取λ1＝λ2＝λ3＝λ4＝1，考慮飛機的重心限制問題和陸運、水運綜合方式，進行第二次禁忌搜索，得到可行的較優(yōu)裝載方案見表6。

表6 最終裝運方案

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

4 結(jié)束語

在有限的運輸資源，如何分配各種資源運輸，并在劃定的時間段中安全有效的完成特定大量的物資裝載與運輸問題，是當(dāng)前軍事力量投射的關(guān)鍵問題之一。本文在總結(jié)其它文獻的基礎(chǔ)上，提出了兩次禁忌搜索算法：第一次禁忌搜索生成初始解方案，然后進行第二次禁忌搜索對初始解進行鄰域優(yōu)化移動，得到較優(yōu)的可行運輸方案。通過第一次搜索的較優(yōu)初始解，限制了第二次禁忌搜索的隨機性，使總體搜索過程更快速有效。

［1］Stephen C H Leung，Zhou Xi－yue，Zhang Defu，et al.Extended guided tabu search and a new packing algorithm for the two－dimensional loading vehicle routing problem ［J］.Computers ＆ Operations Research，2011，38 （1）：205－215.

［2］Fuellerer G，Doerner K F，Hartl R F，et al.Metaheuristics for vehicle routing problems with three－dimensional loading constraints ［J］.European Journal of Operational Research，2010，201 （3）：751－759.

［3］ZHANG Tao，ZHANG Yue－jie，TIAN Wen－xin，et al.A residual－loading－capacity－based ant colony system for the vehicle routing problem with simultaneous delivery and pickup ［J］.Control Theory ＆ Applications，2009，26 （5）：546－549 （in Chinese）.［張濤，張玥杰，田文馨，等.基于剩余裝載能力的蟻群算法求解同時送取貨車輛路徑問題 ［J］.控制理論與應(yīng)用，2009，26 （5）：546－549.］

［4］LIU Jia－min，DONG Zong－ran，MA Guang－ni.Solving container loading based on tabu search algorithm ［J］.Journal of Shenyang University of Technology，2009，31 （2）：212－216 （in Chinese）.［劉嘉敏，董宗然，馬廣妮.基于禁忌搜索算法求解集裝箱裝載問題 ［J］.沈陽工業(yè)大學(xué)，2009，31 （2）：212－216.］

［5］ZHANG Jun，CHEN Bo－song，WANG Xin－h(huán)u，et al.Application of the tabu search algorithm to solving the loading problems in military airlift ［J］.TrafficEngineering and Technology for National Defence，2010，8 （6）：10－13 （in Chinese）. ［張軍，陳柏松，王新虎，等.軍事空運裝載問題的禁忌搜索算法實現(xiàn) ［J］.國防交通工程與技術(shù)，2010，8 （6）：10－13.］

［6］Parreno F，Alvarez－Valdes R，Oliveira J F，et al.Neighborhood structures for the container loading problem：A VNS imple－mentation ［D］.University of Valencia，2005：1－21.

［7］Hadi Mashinchi M，Mehmet A Orgun，Witold Pedrycz.Hybrid optimization with improved tabu search ［J］.Applied Soft Computing，2011，11 （2）：1993－2006.

［8］Kaye McKinzie.A tabu search approach to strategic mobility mode selection ［D］.Austin：University of Texas at Austin，2005：38－39.

［9］SUN Yan－feng.A hybrid strategy based on genetic algorithm and tabu search ［J］.Journal of Beijing University of Technology，2006，32 （3）：258－262 （in Chinese）. ［孫艷豐.基于遺傳算法和禁忌搜索算法的混合策略及其應(yīng)用 ［J］.北京工業(yè)大學(xué)學(xué)報，2006，32 （3）：258－262.］

［10］ZHANG Shu－rong，SU Bing.Something about tabu search approach ［J］.Kaoshi Zhoukan，2006 （48）：228－228 （in Chinese）.［張淑榮，蘇兵.談?wù)劷伤阉魉惴?［J］.考試周刊，2006 （48）：228－228.］