基于遺傳禁忌混合算法的戰時后方倉庫彈藥配送多任務車輛調度

雷 敉，陳 金，楊志遠，高 軍

（軍械工程學院裝備指揮與管理系，河北石家莊 050003）

基于遺傳禁忌混合算法的戰時后方倉庫彈藥配送多任務車輛調度

雷 敉，陳 金，楊志遠，高 軍

（軍械工程學院裝備指揮與管理系，河北石家莊 050003）

后方倉庫承擔著戰略戰役級彈藥物資的周轉、儲存、供應的重要任務，在整個彈藥保障體系中具有不可替代的作用，對后方倉庫彈藥配送的車輛調度進行合理安排是提高彈藥保障效率的關鍵因素，是實現精確保障的前提條件。本文針對能夠以汽車配裝運輸的通用彈藥保障，建立了帶時間窗約束的多任務車輛調度數學模型，對基本遺傳算法進行了改進，構造了一個兩層搜索結構的遺傳禁忌混合算法，其算法的優化能力、運行效率、可靠性相對于基本的遺傳算法均得到了提高，通過仿真進行驗證取得了良好的效果。

彈藥配送；多任務車輛調度；遺傳混合算法

1 問題分析

后方倉庫作為戰時彈藥保障的樞紐環節，其儲備的彈藥物資能否及時、準確、高效地輸送到作戰前沿，關系著整個戰役的進程，甚至決定戰爭成敗。在戰時的彈藥配送中，作為執行主體的后勤系統運輸分隊能否科學、合理地進行車輛調度是提高整個保障效率的關鍵，也是實現彈藥精確保障的重要條件［1］。本文針對能夠以汽車配裝運輸的通用彈藥保障，建立了戰時后方倉庫彈藥配送多任務車輛調度問題的數學模型，并應用遺傳禁忌混合算法對問題進行求解。

戰時車輛調度問題一般可分為兩種。若保障點的需求量是單個運輸單元（若干輛車）裝載容量的整數倍，則為單任務車輛調度問題，即每個運輸單元只給一個保障點送貨；如果每個保障點的需求量都小于運輸單元裝載容量，則單一運輸單元可以同時為多個保障點送貨，這就是多任務車輛調度問題。

戰時后方倉庫彈藥配送多任務車輛調度問題可以描述為：在給定的條件下，要求合理安排若干個運輸單元去往若干個需求單位的行車路線，把需求的彈藥從后方倉庫送到部隊，使得目標函數取得最優。目標函數可以取為運輸總里程數最短、運輸總時間最少、需要的運輸單元數最少等。文［2］實現了帶時間窗的多目標派車問題優化；文［3］在運力不足條件下解決了戰時物資調運的問題；文［4］改進了傳統的遺傳算法，提出了戰時備件配送車輛調度的優化方案。

2 模型建立

現做出如下假設：

（1）設后勤運輸分隊有K個運輸單元，每個運輸單元都有一定的裝載能力限制，且滿足單個運輸單元的容量大于每個保障單位的需求量；

（2）每個保障單位所需物資只能由單獨運輸單元完成，且其需求量是已知的，同時所有保障單位的需求都必須得到滿足；

（3）每個運輸單元行駛線路的開始和結束位置都在后方倉庫；

（4）每個保障單位都有一個指定的保障時間窗口，物資的運輸必須在此時間范圍內進行。

設后方倉庫有K個運輸單元，每個單元k的載重量為Qk（k＝1，2，…，K），總共有L個單位需要保障，每個單位i的需求量為qi（i＝1，2，…，L），且要求物資運到處在時間范圍［ai，bi］內，保障點i到j的運輸距離為dij，后方倉庫到各單位的距離為d0j（i，j＝1，2，…，L）。設si表示車輛到達保障點i的時刻，ti表示車輛在保障點i的卸貨時間，tij表示車輛從保障點i行駛到保障點j的運輸時間。再設nk為第k個運輸單元保障的單位數（nk＝0時則表示未使用第k輛車），用集合Rk表示第k條路徑，其中的元素rki表示保障單位rk在路徑k中的順序為i，rk0＝0表示后方倉庫，s0＝0表示運輸單元從后方倉庫出發的時刻為0。將車輛運輸總里程作為戰時多任務彈藥配送車輛調度問題的目標函數，將運輸時間及其他要求作為約束條件，建立數學模型：

式（1）為總運輸里程最短的目標函數；

式（2）表示每條路線上各保障點的貨物需求量之和不超過運輸單元的載重量；

式（3）保證了每條路線上的任務數不超過總任務數；

式（4）表明每個單位都得到保障；

式（5）表示每條路線上的保障單位；

式（6）規定每個保障點只能由一個運輸單元進行保障；

式（7）表示當第k個運輸單元保障的單位數≥1時，則該單元參加了運輸，取sign（nk）＝1；當第k個單元保障的單位數＜1時。表示未使用該運輸單元，sign（nk）＝0；

式（8）反應了每條運輸路線上車輛到達下一個保障點的時刻＝車輛到達當前保障點的時刻＋當前保障點的等待時間＋從當前保障點到下一個保障點車輛的行駛時間＋從當前保障點到下一個保障點車輛的行駛時間；

式（9）表示車輛在某個保障點的等待時間取決于車輛到達該點的時刻與該點保障時間窗開始時刻的關系。當車輛到達該保障點的時刻小于該保障點時間窗開始時刻時，車輛需要在該單位等待，一直到時間窗開始時刻，才能進行卸貨；即等待時間為該保障點的時間窗開始時刻與車輛到達該點的時刻的差；當車輛到達該單位的時刻大于或等于該單位的時間窗開始時刻時，則車輛在該保障點不等待，即等待時間為0；可見，該式保證了車輛卸貨的時刻大于或等于該單位的保障時間窗開始時刻；

式（10）表示車輛到達某單位的時刻必須小于或等于其時間窗結束時刻。

上述模型具有較好的擴充性，便于設計求解算法和使用計算機編程求解；同時考慮的目標函數和約束條件都比較全面，與現實較為接近。

3 算法設計

本文首先利用遺傳算法進行全局搜索，使群體中的個體比較穩定地分布在解空間的大部分區域，再以群體中每個個體為出發點，用禁忌算法進行局部搜索，以改善群體的質量。該混合算法有效地結合了GA的全局搜索能力和TS的局部搜索能力，是一種高效的優化方法。

針對戰時彈藥配送多任務車輛調度問題，本文設計的遺傳禁忌混合啟發式算法的主要步驟如下：

Step1：輸入原始數據及所需參數，包括群體規模、最優保持個數、交叉概率、變異概率、禁忌表長度、最大迭代數等，同時令GA和TS的迭代計數器為0；

Step2：形成初始化種群；

Step3：適應度計算；

Step4：判斷是否滿足GA終止條件；若滿足，則跳出遺傳算法主優化過程并輸出優化結果；否則，轉入Step5；

Step5：選擇與交叉操作；

Step6：禁忌算法移動操作，通過改變當前解的狀態達到移動的目的，從而產生一個試驗鄰域解；

Step7：適應度計算，計算出Step6所得到的所有鄰域解的適應度；

Step8：禁忌表處理和蔑視操作，

Step9：判斷是否滿足禁忌算法終止條件。若滿足，則跳出禁忌算法優化過程，并轉入Step3進行遺傳算法優化操作；若不滿足，則繼續返回Step6進行禁忌操作。操作步驟如圖1所示。

圖1 遺傳禁忌混合算法流程圖Fig.1 Steps of hybrid algorithm

4 實例分析

戰時后方倉庫接到彈藥保障任務，需對12個作戰單位進行彈藥保障，各單位之間距離如表1所示，各作戰單位的需求量、卸貨時間和時間窗約束如表2所示。

倉庫領導對后勤運輸分隊提出以下要求：一、在規定時間內送達。作戰條件下情況緊急，彈藥必須在每個部隊用戶時間窗區間內送達，彈藥送到時間早于時間窗的上界時，車輛必須等待；晚于時間窗的下界時，帶來時間延遲，貽誤戰機。二、總運輸里程最短。運輸分隊從后方倉庫出發，直到完成任務回到倉庫，為該運輸單元的運輸里程，所有運輸單元的運輸里程之和構成總運輸里程。三、由于各單位需要的作戰物資較少，且運力緊張，要求使用盡可能少調用運輸單元。

表1 節點間距離矩陣Tab.1 Matrix of inter node distance

表2 需求量、卸貨時間和時間窗Tab.2 Dem and、discharge time and time w indow

其中，每個運輸單元的最大裝載容量是500箱，在保證彈藥運輸安全的情況下平均車速為60 km／h。到中午12：00時應安排駕駛員30分鐘的吃飯休息時間，車輛卸貨完畢后返回后方倉庫。

采用本文設計的模型求解該問題步驟如下：

（1）通過運輸距離除以車速60 km／h，得到相應運輸時間矩陣。

（2）將各個數據輸入到遺傳禁忌混合算法程序中，并設置各參數：群體規模n＝20，交叉概率Pc＝0.85，變異概率Pm＝0.01。

（3）通過MATLAB進行運算求解，得到最優調度方案。

為了體現本文設計的遺傳禁忌混合算法的優勢，以該案例為基礎數據進行實驗，分別采用基本遺傳算法和遺傳禁忌混合算法進行計算。兩種算法的參數相同。算法終止條件為迭代次數達到500代或最佳染色體保持20代這兩者中達成其中之一即終止。兩者算法計算結果對比如表3所示。

表3 兩種算法計算結果對比Tab.3 Results of vehicle dispatching and route selecting

從中對比可發現：在配送總距離方面，采用基本遺傳算法的配送總距離的平均值為854.8 km，而采用遺傳禁忌混合算法的配送總距離的平均值為746 km，比基本遺傳算法低16.6%；在使用車輛數方面，采用基本遺傳算法的平均使用車輛數為4.6，而采用遺傳禁忌混合算法的平均使用車輛數為4輛，較基本遺傳算法性能提升15%；在計算時間方面，采用基本遺傳算法的平均計算時間為12 s，而采用遺傳禁忌混合算法的平均計算時間僅為2s，較基本遺傳算法性能提升400%。

5 結 論

彈藥物資收發和運輸車輛調度是實現物資配送的兩個具體工作。其中，收發環節是后方倉庫彈藥保障業務流程的核心環節，而由后勤運輸系統負責的車輛調度作為彈藥收發的外延，是整個彈藥保障物資輸送到部隊的最后一步，其安排是否科學、合理，是否能滿足精確保障的需要，決定了整個后方倉庫彈藥保障成功與否。針對戰時后方倉庫彈藥配送多任務車輛調度問題，設計的遺傳禁忌混合搜索算法，相比較與單一算法其搜索效率有了很大程度的提高，優化能力提升顯著，可以認定遺傳禁忌混合算法適用于解決戰時車輛調度問題上。

［1］ 曲倩倩，曲仕茹，溫凱歌.混合遺傳算法求解配送車輛調度問題［J］.計算機工程與應用，2008，44（15）：205－208.

QU Qianqian，QU Shiru，WEN Kaige.Hybrid genetic algorithm for distribution vehicle routing problem［J］.Computer Engineering and Applications，2008，44（15）：205－207.

［2］ 李芳，鄭晴，邱俊茹，等.帶時間窗的某物流配送車輛調度問題的方案優化分析［J］.數學的實踐與認識，2010，9（17）：176－181.

LIFang，ZHENG Qing，QIU Junru，et al.An optimization analysis on a vehicle scheduling problem of logistics and distribution with time windows［J］.Mathematics in Practice and Theory，2010，9（17）：176－181.

［3］ 李仁傳，嚴永林，劉楠.運力不足條件下的戰時物資調運模型及算法［J］.軍事運籌與系統工程，2007，6（2）：37－40.

LI Renchuan，YAN Yonglin，LIU Nan.The material distribution model and algorithm under the condition of lack of capacity［J］.Military Operations Research and Systems Engineering，2007，6（2）：37－40.

［4］ 張立峰，趙方庚，孫江生，等.基于遺傳算法的戰時備件配送車輛調度［J］.測控自動化，2009（25）：222－224.

ZHANG Lifeng，ZHAO Fanggeng，SUN Jiangsheng.et al.Genetic algorithm for the vehicle scheduling problem of the wartime spare parts［J］.Automation of Measurement and Control，2009（25）：222－224.

雷 敉 男（1991－），湖南邵陽人，碩士生，主要研究方向為物流管理理論與應用。

陳 金 男（1992－），山東泰安人，碩士生，主要研究方向為軍械物流供應鏈。

Multitasking Vehicle Routing for Delivering the Explosive During Wartime Based on a Mixed Algorithm of Genetic Taboos

LEIMi，CHEN Jin，YANG Zhiyuan，GAO Jun

（Equipment Command and Management Department，Ordnance Engineering College，Shijiazhuang 050003，China）

The rear warehouse is responsible for the storage and supply of ammunition.In the entire ammunition support system has irreplaceable role.The reasonable arrangement of the vehicle scheduling is the key factor to improve the efficiency of ammunition support，and it is the precondition to realize the accurate guarantee.For transportation to car equipped w ith general ammunition，I w ill build up a mathematical model of multitasking vehicle w ith Time W indow constraint and construct a mixed algorithm of genetic taboos w ith two－layer searching structure.The algorithm has ability of optimization，operating efficiency and reliability compared w ith basic genetic algorithm.Good results are obtained by simulation.

delivering the explosive；multitasking vehicle routing

TP 301.6

A