基于遺傳禁忌混合算法的戰(zhàn)時(shí)后方倉庫彈藥配送多任務(wù)車輛調(diào)度

雷 敉，陳 金，楊志遠(yuǎn)，高 軍

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

基于遺傳禁忌混合算法的戰(zhàn)時(shí)后方倉庫彈藥配送多任務(wù)車輛調(diào)度

雷 敉，陳 金，楊志遠(yuǎn)，高 軍

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

后方倉庫承擔(dān)著戰(zhàn)略戰(zhàn)役級(jí)彈藥物資的周轉(zhuǎn)、儲(chǔ)存、供應(yīng)的重要任務(wù)，在整個(gè)彈藥保障體系中具有不可替代的作用，對(duì)后方倉庫彈藥配送的車輛調(diào)度進(jìn)行合理安排是提高彈藥保障效率的關(guān)鍵因素，是實(shí)現(xiàn)精確保障的前提條件。本文針對(duì)能夠以汽車配裝運(yùn)輸?shù)耐ㄓ脧椝幈Ｕ?，建立了帶時(shí)間窗約束的多任務(wù)車輛調(diào)度數(shù)學(xué)模型，對(duì)基本遺傳算法進(jìn)行了改進(jìn)，構(gòu)造了一個(gè)兩層搜索結(jié)構(gòu)的遺傳禁忌混合算法，其算法的優(yōu)化能力、運(yùn)行效率、可靠性相對(duì)于基本的遺傳算法均得到了提高，通過仿真進(jìn)行驗(yàn)證取得了良好的效果。

彈藥配送；多任務(wù)車輛調(diào)度；遺傳混合算法

1 問題分析

后方倉庫作為戰(zhàn)時(shí)彈藥保障的樞紐環(huán)節(jié)，其儲(chǔ)備的彈藥物資能否及時(shí)、準(zhǔn)確、高效地輸送到作戰(zhàn)前沿，關(guān)系著整個(gè)戰(zhàn)役的進(jìn)程，甚至決定戰(zhàn)爭(zhēng)成敗。在戰(zhàn)時(shí)的彈藥配送中，作為執(zhí)行主體的后勤系統(tǒng)運(yùn)輸分隊(duì)能否科學(xué)、合理地進(jìn)行車輛調(diào)度是提高整個(gè)保障效率的關(guān)鍵，也是實(shí)現(xiàn)彈藥精確保障的重要條件［1］。本文針對(duì)能夠以汽車配裝運(yùn)輸?shù)耐ㄓ脧椝幈Ｕ?，建立了?zhàn)時(shí)后方倉庫彈藥配送多任務(wù)車輛調(diào)度問題的數(shù)學(xué)模型，并應(yīng)用遺傳禁忌混合算法對(duì)問題進(jìn)行求解。

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

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

2 模型建立

現(xiàn)做出如下假設(shè)：

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

（2）每個(gè)保障單位所需物資只能由單獨(dú)運(yùn)輸單元完成，且其需求量是已知的，同時(shí)所有保障單位的需求都必須得到滿足；

（3）每個(gè)運(yùn)輸單元行駛線路的開始和結(jié)束位置都在后方倉庫；

（4）每個(gè)保障單位都有一個(gè)指定的保障時(shí)間窗口，物資的運(yùn)輸必須在此時(shí)間范圍內(nèi)進(jìn)行。

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

式（1）為總運(yùn)輸里程最短的目標(biāo)函數(shù)；

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

式（3）保證了每條路線上的任務(wù)數(shù)不超過總?cè)蝿?wù)數(shù)；

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

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

式（6）規(guī)定每個(gè)保障點(diǎn)只能由一個(gè)運(yùn)輸單元進(jìn)行保障；

式（7）表示當(dāng)?shù)趉個(gè)運(yùn)輸單元保障的單位數(shù)≥1時(shí)，則該單元參加了運(yùn)輸，取sign（nk）＝1；當(dāng)?shù)趉個(gè)單元保障的單位數(shù)＜1時(shí)。表示未使用該運(yùn)輸單元，sign（nk）＝0；

式（8）反應(yīng)了每條運(yùn)輸路線上車輛到達(dá)下一個(gè)保障點(diǎn)的時(shí)刻＝車輛到達(dá)當(dāng)前保障點(diǎn)的時(shí)刻＋當(dāng)前保障點(diǎn)的等待時(shí)間＋從當(dāng)前保障點(diǎn)到下一個(gè)保障點(diǎn)車輛的行駛時(shí)間＋從當(dāng)前保障點(diǎn)到下一個(gè)保障點(diǎn)車輛的行駛時(shí)間；

式（9）表示車輛在某個(gè)保障點(diǎn)的等待時(shí)間取決于車輛到達(dá)該點(diǎn)的時(shí)刻與該點(diǎn)保障時(shí)間窗開始時(shí)刻的關(guān)系。當(dāng)車輛到達(dá)該保障點(diǎn)的時(shí)刻小于該保障點(diǎn)時(shí)間窗開始時(shí)刻時(shí)，車輛需要在該單位等待，一直到時(shí)間窗開始時(shí)刻，才能進(jìn)行卸貨；即等待時(shí)間為該保障點(diǎn)的時(shí)間窗開始時(shí)刻與車輛到達(dá)該點(diǎn)的時(shí)刻的差；當(dāng)車輛到達(dá)該單位的時(shí)刻大于或等于該單位的時(shí)間窗開始時(shí)刻時(shí)，則車輛在該保障點(diǎn)不等待，即等待時(shí)間為0；可見，該式保證了車輛卸貨的時(shí)刻大于或等于該單位的保障時(shí)間窗開始時(shí)刻；

式（10）表示車輛到達(dá)某單位的時(shí)刻必須小于或等于其時(shí)間窗結(jié)束時(shí)刻。

上述模型具有較好的擴(kuò)充性，便于設(shè)計(jì)求解算法和使用計(jì)算機(jī)編程求解；同時(shí)考慮的目標(biāo)函數(shù)和約束條件都比較全面，與現(xiàn)實(shí)較為接近。

3 算法設(shè)計(jì)

本文首先利用遺傳算法進(jìn)行全局搜索，使群體中的個(gè)體比較穩(wěn)定地分布在解空間的大部分區(qū)域，再以群體中每個(gè)個(gè)體為出發(fā)點(diǎn)，用禁忌算法進(jìn)行局部搜索，以改善群體的質(zhì)量。該混合算法有效地結(jié)合了GA的全局搜索能力和TS的局部搜索能力，是一種高效的優(yōu)化方法。

針對(duì)戰(zhàn)時(shí)彈藥配送多任務(wù)車輛調(diào)度問題，本文設(shè)計(jì)的遺傳禁忌混合啟發(fā)式算法的主要步驟如下：

Step1：輸入原始數(shù)據(jù)及所需參數(shù)，包括群體規(guī)模、最優(yōu)保持個(gè)數(shù)、交叉概率、變異概率、禁忌表長(zhǎng)度、最大迭代數(shù)等，同時(shí)令GA和TS的迭代計(jì)數(shù)器為0；

Step2：形成初始化種群；

Step3：適應(yīng)度計(jì)算；

Step4：判斷是否滿足GA終止條件；若滿足，則跳出遺傳算法主優(yōu)化過程并輸出優(yōu)化結(jié)果；否則，轉(zhuǎn)入Step5；

Step5：選擇與交叉操作；

Step6：禁忌算法移動(dòng)操作，通過改變當(dāng)前解的狀態(tài)達(dá)到移動(dòng)的目的，從而產(chǎn)生一個(gè)試驗(yàn)鄰域解；

Step7：適應(yīng)度計(jì)算，計(jì)算出Step6所得到的所有鄰域解的適應(yīng)度；

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

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

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

4 實(shí)例分析

戰(zhàn)時(shí)后方倉庫接到彈藥保障任務(wù)，需對(duì)12個(gè)作戰(zhàn)單位進(jìn)行彈藥保障，各單位之間距離如表1所示，各作戰(zhàn)單位的需求量、卸貨時(shí)間和時(shí)間窗約束如表2所示。

倉庫領(lǐng)導(dǎo)對(duì)后勤運(yùn)輸分隊(duì)提出以下要求：一、在規(guī)定時(shí)間內(nèi)送達(dá)。作戰(zhàn)條件下情況緊急，彈藥必須在每個(gè)部隊(duì)用戶時(shí)間窗區(qū)間內(nèi)送達(dá)，彈藥送到時(shí)間早于時(shí)間窗的上界時(shí)，車輛必須等待；晚于時(shí)間窗的下界時(shí)，帶來時(shí)間延遲，貽誤戰(zhàn)機(jī)。二、總運(yùn)輸里程最短。運(yùn)輸分隊(duì)從后方倉庫出發(fā)，直到完成任務(wù)回到倉庫，為該運(yùn)輸單元的運(yùn)輸里程，所有運(yùn)輸單元的運(yùn)輸里程之和構(gòu)成總運(yùn)輸里程。三、由于各單位需要的作戰(zhàn)物資較少，且運(yùn)力緊張，要求使用盡可能少調(diào)用運(yùn)輸單元。

表1 節(jié)點(diǎn)間距離矩陣Tab.1 Matrix of inter node distance

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

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

采用本文設(shè)計(jì)的模型求解該問題步驟如下：

（1）通過運(yùn)輸距離除以車速60 km／h，得到相應(yīng)運(yùn)輸時(shí)間矩陣。

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

（3）通過MATLAB進(jìn)行運(yùn)算求解，得到最優(yōu)調(diào)度方案。

為了體現(xiàn)本文設(shè)計(jì)的遺傳禁忌混合算法的優(yōu)勢(shì)，以該案例為基礎(chǔ)數(shù)據(jù)進(jìn)行實(shí)驗(yàn)，分別采用基本遺傳算法和遺傳禁忌混合算法進(jìn)行計(jì)算。兩種算法的參數(shù)相同。算法終止條件為迭代次數(shù)達(dá)到500代或最佳染色體保持20代這兩者中達(dá)成其中之一即終止。兩者算法計(jì)算結(jié)果對(duì)比如表3所示。

表3 兩種算法計(jì)算結(jié)果對(duì)比Tab.3 Results of vehicle dispatching and route selecting

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

5 結(jié) 論

彈藥物資收發(fā)和運(yùn)輸車輛調(diào)度是實(shí)現(xiàn)物資配送的兩個(gè)具體工作。其中，收發(fā)環(huán)節(jié)是后方倉庫彈藥保障業(yè)務(wù)流程的核心環(huán)節(jié)，而由后勤運(yùn)輸系統(tǒng)負(fù)責(zé)的車輛調(diào)度作為彈藥收發(fā)的外延，是整個(gè)彈藥保障物資輸送到部隊(duì)的最后一步，其安排是否科學(xué)、合理，是否能滿足精確保障的需要，決定了整個(gè)后方倉庫彈藥保障成功與否。針對(duì)戰(zhàn)時(shí)后方倉庫彈藥配送多任務(wù)車輛調(diào)度問題，設(shè)計(jì)的遺傳禁忌混合搜索算法，相比較與單一算法其搜索效率有了很大程度的提高，優(yōu)化能力提升顯著，可以認(rèn)定遺傳禁忌混合算法適用于解決戰(zhàn)時(shí)車輛調(diào)度問題上。

［1］ 曲倩倩，曲仕茹，溫凱歌.混合遺傳算法求解配送車輛調(diào)度問題［J］.計(jì)算機(jī)工程與應(yīng)用，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］ 李芳，鄭晴，邱俊茹，等.帶時(shí)間窗的某物流配送車輛調(diào)度問題的方案優(yōu)化分析［J］.數(shù)學(xué)的實(shí)踐與認(rèn)識(shí)，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］ 李仁傳，嚴(yán)永林，劉楠.運(yùn)力不足條件下的戰(zhàn)時(shí)物資調(diào)運(yùn)模型及算法［J］.軍事運(yùn)籌與系統(tǒng)工程，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］ 張立峰，趙方庚，孫江生，等.基于遺傳算法的戰(zhàn)時(shí)備件配送車輛調(diào)度［J］.測(cè)控自動(dòng)化，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－），湖南邵陽人，碩士生，主要研究方向?yàn)槲锪鞴芾砝碚撆c應(yīng)用。

陳 金 男（1992－），山東泰安人，碩士生，主要研究方向?yàn)檐娦滴锪鞴?yīng)鏈。

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