大規(guī)模作戰(zhàn)物流配送VRP模型及求解

張 錦，聶 偉，沈 軍，謝小平

(鎮(zhèn)江船艇學(xué)院動(dòng)力指揮系，江蘇鎮(zhèn)江212003)

隨著以信息化為核心的新軍事變革的深入推進(jìn)，基于信息系統(tǒng)體系作戰(zhàn)的戰(zhàn)斗力生成模式正在加速轉(zhuǎn)型。作為軍隊(duì)作戰(zhàn)“生命線”和后勤保障中心環(huán)節(jié)的軍交運(yùn)輸，在戰(zhàn)爭中的地位和作用將更顯突出，甚至直接制約著戰(zhàn)爭的進(jìn)程和結(jié)局。配送是軍事物流的重要環(huán)節(jié)，是將后勤保障物資轉(zhuǎn)化為作戰(zhàn)能力的紐帶，肩負(fù)著將作戰(zhàn)物資交付到作戰(zhàn)部隊(duì)的重要任務(wù)，其路徑的優(yōu)化選擇對(duì)軍交運(yùn)輸效率有著重要影響。交戰(zhàn)雙方的較量，不僅是武器裝備的較量，也是軍事物流配送力量的較量，哪一方能得到高質(zhì)量的軍事物流支持和保障，哪一方便獲得了軍事行動(dòng)的主動(dòng)權(quán)［1］。

按照運(yùn)輸任務(wù)樣式的不同，大規(guī)模作戰(zhàn)物流配送問題可分為多式聯(lián)運(yùn)問題和車輛路徑問題:由后方物流中心或戰(zhàn)略倉庫向前方配送中心或部隊(duì)用戶的配送一般屬于長距離運(yùn)輸，需要綜合運(yùn)用多種運(yùn)輸方式，屬于多式聯(lián)運(yùn);由前方配送中心向各部隊(duì)用戶的配送一般屬于車輛路徑問題。這里的車輛是廣義概念，可以是汽車、船艇、飛機(jī)等。大規(guī)模作戰(zhàn)需要保障的部隊(duì)用戶眾多，配送方案決策復(fù)雜，需要通過建立數(shù)學(xué)模型，運(yùn)用計(jì)算機(jī)求解的方法來制訂快速、精確、安全、高效的配送方案。車輛路徑問題(vehicle routing problem，VRP)最先由Dantzig和Ramser于1959年提出，經(jīng)過半個(gè)多世紀(jì)的深化和擴(kuò)展，國內(nèi)外學(xué)者針對(duì)不同領(lǐng)域應(yīng)用衍生出不同類型的VRP:按照信息(包括客戶需求、車輛信息和路況信息等)是否確定可大致分為不確定性VRP和確定性VRP［2－4］。根據(jù)軍事物流配送中VRP的特點(diǎn)，本文將重點(diǎn)針對(duì)確定VRP中的單/多配送中心、單/多車型、裝卸一體、帶時(shí)間窗的VRP開展研究。

1 問題描述及約束條件

車輛路徑問題是車輛裝載物資由前方配送中心出發(fā)，對(duì)配送網(wǎng)中的部隊(duì)用戶進(jìn)行保障，然后返回配送中心的過程。配送網(wǎng) G(V，E，S，T，C，P)中:V為點(diǎn)集，總數(shù)為n，vi∈V為配送網(wǎng)中的點(diǎn)，包括配送中心和部隊(duì)用戶;E為邊集，eij∈E為能找到連通vi和vj的路徑(不要求直接連通);S為E的距離屬性矩陣，sij∈S為eij的里程;T為E的時(shí)間屬性矩陣，tij∈T為在eij上行駛的時(shí)間;C為E的費(fèi)用屬性矩陣，cij∈C為在eij上行駛的經(jīng)濟(jì)成本;P為E的安全屬性矩陣，pij∈P為eij的安全概率。配送中心向部隊(duì)用戶配送物資時(shí)，每個(gè)部隊(duì)用戶的位置和物資需求量已知，要求合理安排車輛和配送路線，以制訂配送時(shí)間短、配送費(fèi)用低、配送安全性高的配送方案，并滿足以下約束條件:①任何時(shí)刻車輛的裝載量不超過其最大裝載限制;②車輛配送距離不超過其最大行駛距離限制;③部隊(duì)用戶的需求必須滿足，且只能由一輛配送車送貨，對(duì)需求量大于車輛最大載量的部隊(duì)用戶考慮另外單獨(dú)配送;④車輛必須在規(guī)定時(shí)間窗內(nèi)到達(dá)部隊(duì)用戶。

2 模型的設(shè)計(jì)思路

考慮到VRP與推銷員回路問題(traveling salesman problem，TSP)的內(nèi)在聯(lián)系，本文提出虛設(shè)配送中心的思想實(shí)現(xiàn)VRP向約束性TSP的轉(zhuǎn)化。

(1)VRP與TSP的相關(guān)性概述。TSP是指有一名推銷員，從城市1出發(fā)，要遍訪城市2，3，…，n各一次，最后返回城市1，他應(yīng)按怎樣的次序訪問這些城市，才能使總費(fèi)用最少。而軍交運(yùn)輸VRP作為TSP的拓展和延伸，是一個(gè)約束性多回路的TSP問題。VRP的多回路特性比TSP具有更復(fù)雜的特性，因此，本文提出虛設(shè)配送中心的構(gòu)想，以消除VRP的多回路特性［5］。

(2)虛設(shè)配送中心構(gòu)想的提出。VRP和TSP最本質(zhì)的差異是前者具有多回路特性，后者只是單環(huán)路問題。本文提出的虛設(shè)配送中心的構(gòu)想能夠很好地消除這一差異(如圖1所示)。具體描述為:在滿足給定約束條件的前提下，配送中心出動(dòng)m輛車向n個(gè)部隊(duì)用戶輸送物資的VRP是一個(gè)節(jié)點(diǎn)數(shù)為n+1，具有m條回路的約束性TSP。虛設(shè)與原配送中心位置重合的m－1個(gè)配送中心(原配送中心編號(hào)為1;虛擬配送中心編號(hào)分別為2，3，…，m;部隊(duì)用戶編號(hào)為 m+1，m+2，…，m+n)。規(guī)定第1輛車裝載一定的物資從1#配送中心出發(fā)，完成對(duì)若干部隊(duì)的補(bǔ)給任務(wù)后以空車狀態(tài)回到2#配送中心，第2輛車裝載一定物資從2#配送中心出發(fā)，對(duì)未被補(bǔ)給的若干部隊(duì)用戶進(jìn)行補(bǔ)給后以空車狀態(tài)回到3#配送中心，依次類推，第m輛車裝載一定物資從m#配送中心出發(fā)，對(duì)剩下的部隊(duì)用戶進(jìn)行補(bǔ)給后再回到1#配送中心，這m輛車的m條路徑貫穿起來實(shí)際上就是一條推銷員回路。這樣，原本n+1個(gè)節(jié)點(diǎn)的約束性m條回路的TSP轉(zhuǎn)化成了n+m個(gè)城市的約束性單回路TSP問題。規(guī)定所有(虛擬)配送中心之間的距離sij為0，安全概率pij為1，其他節(jié)點(diǎn)之間的距離sij可以通過Floyd算法求得，進(jìn)而易求得時(shí)間tij和費(fèi)用cij。

圖1 單配送中心VRP虛設(shè)配送中心示意

(3)與傳統(tǒng)模型的優(yōu)劣分析。傳統(tǒng)VRP模型一般將決策變量設(shè)置為三維下標(biāo)的形式，如用0－1變量xijk表示第k輛車依次對(duì)vi和vj進(jìn)行補(bǔ)給，對(duì)于節(jié)點(diǎn)規(guī)模為20，動(dòng)用5輛車進(jìn)行配送的案例，決策變量數(shù)為20×20×5。而采用本文的建模思想，只需采用二維下標(biāo)的決策變量xij即可對(duì)問題進(jìn)行描述，決策變量數(shù)為24×24。顯然，本文的建模思路將大幅減少?zèng)Q策變量和約束條件數(shù)量，大大降低模型復(fù)雜度，有效提高求解效率。

3 單配送中心單車型帶時(shí)間窗裝卸一體VRP優(yōu)化模型

(虛擬)配送中心 vi(i=1，2，…，m)計(jì)劃派出m輛車(最大載質(zhì)量為G，最大行駛距離為L)對(duì)需求量為gi的n個(gè)部隊(duì)用戶 vi(i=m+1，m+2，…，m+n)進(jìn)行物資配送，同時(shí)將需要后送的物品及裝備hi帶回配送中心，要求制訂快速、精確、安全、低成本的配送方案。不同戰(zhàn)場環(huán)境下，配送任務(wù)的優(yōu)化目標(biāo)不同，分別以部隊(duì)用戶的平均等待時(shí)間TIME、總費(fèi)用 COST和總安全概率的對(duì)數(shù)值 ln(SAFETY)為目標(biāo)函數(shù)，建立多目標(biāo) VRP優(yōu)化模型:

式中:qj為車輛到達(dá)vj的時(shí)刻;Oj為離開vj時(shí)的載質(zhì)量與出發(fā)時(shí)相比減少的量;sij為車輛由vi至vj的里程;gj、hj分別為 vj的需求量、后送量;fj為車輛到達(dá)vj時(shí)行駛的距離;α、β分別為裝、卸載速度;τ1j為到達(dá)vj的最早時(shí)刻;τ2j為到達(dá) vj的最晚時(shí)刻;xij為決策變量。

該模型屬于0－1非線性規(guī)劃模型，考慮到對(duì)數(shù)函數(shù)的單調(diào)性，取安全概率(SAFETY=∏pijxij)的對(duì)數(shù)值為優(yōu)化目標(biāo)，不影響決策結(jié)果。式(1)構(gòu)成了可行解必須是一條遍歷所有節(jié)點(diǎn)的回路，且除此不包括其他任意路段的充分必要條件［6］;式(2)、式(3)描述了車輛在運(yùn)行過程中的裝卸貨情況及最大載質(zhì)量約束;式(4)—(6)描述了車輛的運(yùn)行距離及受到的最大行駛距離約束;式(7)、式(8)描述了車輛到達(dá)每個(gè)部隊(duì)用戶的時(shí)刻及受到的時(shí)間窗約束。

4 多配送中心多車型帶時(shí)間窗裝卸一體VRP優(yōu)化模型

該模型以兩個(gè)配送中心，兩種車型為例說明。假設(shè)兩個(gè)配送中心分別計(jì)劃派出m輛車和M輛車，對(duì)n個(gè)部隊(duì)用戶進(jìn)行物資補(bǔ)給。虛設(shè)配送中心后，在1#配送中心的位置共有m+1個(gè)(虛擬)配送中心 vi(i=1，2，…，m+1)，在 2#配送中心的位置共有M+1個(gè)配送中心vi(i=m+2，m+3，…，m+M+2)，如圖2所示。規(guī)定任意兩個(gè)(虛擬)配送中心之間的距離和運(yùn)輸耗時(shí)均為0，安全概率為1，其他距離按實(shí)際距離計(jì)算。

已知1#配送中心和2#配送中心所配備車輛的最大載質(zhì)量分別為G1和G2，最大行駛距離分別為L1和L2，待補(bǔ)給的n個(gè)部隊(duì)用戶vi(i=m+M+3，m+M+4，…，m+M+n+2)的需求量為 gi，后送量為hi，要求制訂快速、精確、安全、低成本的配送方案。不同戰(zhàn)場環(huán)境下，配送任務(wù)的優(yōu)化目標(biāo)不同，分別以部隊(duì)用戶的平均等待時(shí)間TIME、總費(fèi)用COST和總安全概率的對(duì)數(shù)值ln(SAFETY)為目標(biāo)函數(shù)，建立多目標(biāo)VRP優(yōu)化模型:

該模型屬于0－1非線性規(guī)劃模型。式(9)構(gòu)成了可行解必須是一條遍歷所有節(jié)點(diǎn)的回路，且除此不包括其他任意路段的充分必要條件［6］;式(10)、式(11)對(duì)1#配送中心和2#配送中心的車輛的最大載重進(jìn)行限制;式(12)、式(13)對(duì)1#配送中心和2#配送中心車輛的最大行駛距離進(jìn)行限制;其他變量和約束條件的含義同單配送中心模型。

圖2 多配送中心VRP虛設(shè)配送中心示意

5 模型求解分析

大規(guī)模作戰(zhàn)軍交運(yùn)輸路徑優(yōu)化問題可以歸結(jié)為規(guī)劃問題，其中VRP屬于0－1非線性規(guī)劃問題，多路徑多式聯(lián)運(yùn)和車輛路徑問題屬于非線性規(guī)劃。這些規(guī)劃問題涉及變量多，約束條件表達(dá)式比較復(fù)雜，用手工計(jì)算求解幾乎是不可能的，運(yùn)用各種元啟發(fā)式算法編程計(jì)算雖然可行，但工作量大、程序長而繁瑣，選擇參數(shù)和終止條件對(duì)求解有一定影響，且往往難以求得全局最優(yōu)解。所以，本文選擇專用的求解非線性規(guī)劃軟件——LINGO進(jìn)行編程求解。

6 想定案例分析

前方配送中心接到戰(zhàn)略物流中心補(bǔ)給的物資后，最多可以派出5輛載質(zhì)量為8 t的車，向8個(gè)部隊(duì)用戶進(jìn)行物資配送，要求5 h內(nèi)必須全部送達(dá)。其中，一對(duì)一配送方案優(yōu)化相對(duì)簡單(適用于需求量大于車輛載質(zhì)量的情況)，因此本想定案例中考慮的是一對(duì)多的情況?？紤]到前方配送中心的給養(yǎng)物資大多情況是由上級(jí)調(diào)撥來的，可以不考慮其來源和量的限制，因此在這里只考慮物資不受限情況下的一對(duì)多配送，這種配送方式在當(dāng)前配送中心為部隊(duì)用戶配送給養(yǎng)物資的活動(dòng)中具有代表性［7］。

由于上級(jí)調(diào)撥的時(shí)間限制，以及卸貨、裝車等原因，汽車只能在早上7:00從前方配送中心出發(fā)，受路況影響途中平均速度為50 km/h，車輛最大行駛距離為400 km，平均卸貨速度為0.1 t/min，已知配送中心和各部隊(duì)用戶的距離，以及各部隊(duì) 用戶需求量見表1。

表1 部隊(duì)用戶與配送中心距離及物資需求量

運(yùn)用單配送中心單車型帶時(shí)間窗的VRP優(yōu)化模型，選定優(yōu)化目標(biāo)(以平均等待時(shí)間最短為例)，通過LINGO軟件進(jìn)行求解仿真，求得全局最優(yōu)解，制訂出兩套預(yù)案(見表2)。結(jié)果表明:出動(dòng)3輛車能以最短的里程完成任務(wù)，車輛最晚到達(dá)部隊(duì)用戶(v6)的時(shí)刻為11:51，平均等待時(shí)間為2.6 h;出動(dòng)4輛車時(shí)總里程增加170 km，最晚到達(dá)的部隊(duì)用戶(v7)的時(shí)刻為10:48，平均等待時(shí)間為2.21 h。對(duì)于緊急物資的配送，可選擇出動(dòng)4輛車的方案，一般物資的配送可選擇派出3輛車即可。

表2 車輛路徑問題仿真結(jié)果

7 結(jié)語

隨著全面建設(shè)現(xiàn)代后勤的深入推進(jìn)，軍事物流信息化建設(shè)加速發(fā)展，可視化技術(shù)和射頻識(shí)別技術(shù)等物流技術(shù)廣泛應(yīng)用，如何更好地運(yùn)用計(jì)算機(jī)輔助決策來制訂高效的軍事物流配送方案，實(shí)現(xiàn)資源和運(yùn)力的優(yōu)化配置，是從管理學(xué)視角提高軍交運(yùn)輸保障能力和決策科學(xué)化水平的重要途徑，對(duì)于實(shí)現(xiàn)快速保障、精確保障、高效保障意義重大。

［1］ 潘小霞.應(yīng)急作戰(zhàn)軍事物流配送方案優(yōu)化研究［D］.鎮(zhèn)江:江蘇大學(xué)，2010.

［2］ Dantzig G B，Ramser J H.The truck dispatching problem［J］.Management Science，1959，6(1):80-91.

［3］ Rajmohan M，Shahabudeen P.Genetic algorithm based approach for vehicle routing problem with time windows［J］.International Journal of Logistics Systems and Management，2008，4(3):338-365.

［4］ Bazgan C，Hassin R，Monnot M.Approximation algorithms for some vehicle routing problems［J］.Discrete Applied Mathematics，2005，164(1):27-42.

［5］ 張錦，宋業(yè)新，李芳，等.基于TSP的軍交VRP優(yōu)化模型及其求解［J］.數(shù)學(xué)的實(shí)踐與認(rèn)識(shí)，2011，41(22):162-166.

［6］ 袁新生，卲大宏，郁時(shí)煉.LINGO和EXCEL在數(shù)學(xué)建模中的應(yīng)用［M］.北京:科學(xué)出版社，2006:75-77.

［7］ 周峰.部隊(duì)給養(yǎng)物資配送方案優(yōu)化模型及其應(yīng)用研究［D］.長沙:國防科學(xué)技術(shù)大學(xué)，2008.