大規模作戰物流配送VRP模型及求解

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

(鎮江船艇學院動力指揮系，江蘇鎮江212003)

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

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

1 問題描述及約束條件

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

2 模型的設計思路

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

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

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

圖1 單配送中心VRP虛設配送中心示意

(3)與傳統模型的優劣分析。傳統VRP模型一般將決策變量設置為三維下標的形式，如用0－1變量xijk表示第k輛車依次對vi和vj進行補給，對于節點規模為20，動用5輛車進行配送的案例，決策變量數為20×20×5。而采用本文的建模思想，只需采用二維下標的決策變量xij即可對問題進行描述，決策變量數為24×24。顯然，本文的建模思路將大幅減少決策變量和約束條件數量，大大降低模型復雜度，有效提高求解效率。

3 單配送中心單車型帶時間窗裝卸一體VRP優化模型

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

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

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

4 多配送中心多車型帶時間窗裝卸一體VRP優化模型

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

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

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

圖2 多配送中心VRP虛設配送中心示意

5 模型求解分析

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

6 想定案例分析

前方配送中心接到戰略物流中心補給的物資后，最多可以派出5輛載質量為8 t的車，向8個部隊用戶進行物資配送，要求5 h內必須全部送達。其中，一對一配送方案優化相對簡單(適用于需求量大于車輛載質量的情況)，因此本想定案例中考慮的是一對多的情況。考慮到前方配送中心的給養物資大多情況是由上級調撥來的，可以不考慮其來源和量的限制，因此在這里只考慮物資不受限情況下的一對多配送，這種配送方式在當前配送中心為部隊用戶配送給養物資的活動中具有代表性［7］。

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

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

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

表2 車輛路徑問題仿真結果

7 結語

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

［1］ 潘小霞.應急作戰軍事物流配送方案優化研究［D］.鎮江:江蘇大學，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］ 張錦，宋業新，李芳，等.基于TSP的軍交VRP優化模型及其求解［J］.數學的實踐與認識，2011，41(22):162-166.

［6］ 袁新生，卲大宏，郁時煉.LINGO和EXCEL在數學建模中的應用［M］.北京:科學出版社，2006:75-77.

［7］ 周峰.部隊給養物資配送方案優化模型及其應用研究［D］.長沙:國防科學技術大學，2008.