物流車輛調度一般模型及啟發式算法求解現狀及研究方向

趙建峰，梁伯棟

（深圳職業技術學院，廣東 深圳 518055）

1 前言

物流服務提供者通過運輸、存儲、裝卸、包裝、流通加工、配送和信息管理等方式滿足客戶的物流需求，其過程中將企業的采購、生產、制造、銷售緊密地聯系在一起，是現代社會企業發展的“加速器”和“第三利潤源泉”。隨著我國經濟的不斷發展，物流業已經成為社會經濟的基礎組成部分，根據《2016年全國物流運行情況通報》，我國2016年全國社會物流總額為229.7萬億元，比上年增長6.1%。在物流行業高速發展的同時，物流行業費用依然較高，2016年社會物流總費用11.1萬億元，與GDP的比率為14.9%，與歐美等發達國家10%的比率相比依然有很大提升空間。因此，如何降低物流費用，對于提升我國經濟具有重要意義。

在物流領域，車輛貨物的裝配及車輛路徑的規劃對于提升物流調度效率、降低物流成本具有重要意義。但是，由于車輛貨物的裝配及運輸路徑規劃均是NP難題，如何求解該問題一直是物流領域的難題，受到諸多學者關注，如：文獻[1]對物流車輛的調度問題進行了綜述，描述了物流調度的一般模型，指出了車輛調度主要的優化目標，并對調度模型進行了分類，同時指出模型求解方面，包含精確算法、傳統啟發式算法和現代智能算法。文獻[2]較好地對物流配送車輛優化調度問題進行了綜述，對物流車輛調度文件進行了較好地分類，描述了調度模型及主要求解算法。文獻[3]對配送車輛調度路徑優化問題進行了深入分析，并進行了概況和分析。首先給出了物流配送調度包含的要素：道路、貨物、車輛、物流中心、客戶、運輸網絡、約束條件等，然后對VRP問題進行了分類，并對VRP的理論基礎進行了介紹。文獻[4]對包含產品生產在內的車輛調度問題進行了綜述。文獻[5]對多約束的車輛調度問題（multi-constrained Vehicle Routing Problems,VRPs），也稱 Rich Vehicle Routing Problems(RVRPs)進行了綜述，包含：對RVRPs進行了分類并給出了一個定義。

上述文獻較好地對物流車輛調度問題進行綜述，然而，缺乏對車輛調度模型的具體描述，在求解方面，只描述了啟發式算法的求解方法，未對算法的求解過程進行描述，特別是基因編碼方法及算法迭代進行描述。本文首先對物流調度問題進行簡單介紹，然后，在綜合各個文獻研究的基礎上，抽象出一個典型的物流調度模型并進行了詳細的描述，并對當前主流的求解算法從基因編碼及算法迭代兩個方面，進行了綜述。通過本文獻，研究者能夠快速了解當前物流車輛調度的最新進展并結合自身的經驗，提出更加有效的模型或求解方法。

2 物流車輛調度典型模型

在費用最小、時間最少等約束下，如何將物流中的各種貨物合理的裝載在對應的車輛并運輸到相應的目的地，對于提升物流行業的效率具有重要意義。

大家目前認為最早提出物流調度模型的是Dantzig等[6]，該文獻以汽油車的向加油站配送汽油為研究案例，提出了物流車輛的調度問題并采用線性規劃進行求解。典型的物流車輛調度，如：物流貨物配送、便利店貨物配送、企業生產倉儲配送等，其總的目標是將貨物從一個地方（倉庫）運輸到多個客戶并達到運輸成本最小、運輸時間最短、運輸路徑最短等目標中的一個或多個，同時假定貨物的最大重量或最大體積不超過車輛的最大載重或最大體積。

通過閱讀目前的文獻，其物流調度模型可以抽象為一個具有代表性的物流調度模型，用形式化的語言可以描述為，存在一個路網G={V,W}，如圖1所示，其中，V為路網節點，W為路網間相互連通的帶權路徑，通常為路徑的長度及行駛時間，用（wlij，wtij）表示。其中，V0為中心倉儲節點，存有待運輸的貨物集F，V1，V2，…Vi，…，Vn，為待服務的客戶，Wij為Vi和Vj之間的連通權重。運輸車輛Ci={ID，Wei，Vol，Pri}，i=1，2，…,c，其中，ID表示車輛的標識，Wei為車輛載重，Vol為車輛容積，Pri表示該車輛運輸一公里的價格；倉儲貨物 Fi={ID，Wei，Vol，Des}，i=1，2，…，f，其中，Des表示貨物的目的節點。

因此，在上述形式化描述下，車輛的調度目標為：

圖1 帶權的路網

尋找最佳的車輛行駛路徑 P(p1，p2，…，pc)，s.t min F={price,time,path}

其中，pi={Vi1,Vi2,…,Vil}表示車輛經過的節點，

同場PK：將葛蘭許和Bin 707放在一起PK是極其不公平的，這里不過是想比較一下兩款酒的風格而已，因為Bin707近年價位越來越逼近葛蘭許，是Penfolds眾多紅葡萄酒中最為強壯、飽滿的代表。707充滿力量，卻不會讓你覺得太霸道，濃郁的黑漿果香，入口復雜的香料香和更多層次的香氣。葛蘭許要深沉和沉穩很多，它是一款你得要品嘗到第三口才能喝明白的年份，剛開始有很多你無法形容的感受。

并且滿足：

在典型模型中，對調度邊界條件、調度方式等做了相應的假定，即：每個客戶通過一次服務可以完成服務，待運輸貨物的總重量不超過車輛的總載重和總體積，每次運輸都可以達到車輛的滿載運輸等，同時也未對貨物或客戶服務動態變化的情況予以考慮。目前，主要的文獻研究都是基于本文抽象出的調度模型，在此基礎上，將模型的邊界條件及限定條件進行修訂，以達到不同的研究目的，如：車輛運輸并非滿載運輸[7]，其假定車輛的裝載并不滿載，只需要滿足客戶的需求即可；更多約束條件下的物流車輛調度問題，如文獻[8]就研究了帶彈性時間約束的車輛調度問題；發貨點更多更加復雜[9-11]；車輛類型更多樣[12]；時間約束更嚴格[13-14]、多裝貨地點多卸貨地點；車輛、貨物、客戶動態變化下的物流調度求解問題[16-17]等。

3 常見啟發式求解算法

啟發式算法是一類通過模仿自然界的生物特性進而獲得問題的近似解的求解算法。在現實世界中，存在一類問題，其無法通過精確求解的方法獲得最佳解，而只能通過不斷迭代試錯的方式獲得近似解。通常此類問題具有較大的求解空間，在有限的時間內遍歷算法所有的解。因而，通過模擬自然界生物的求解過程，如：遺傳進化、螞蟻尋求食物、鳥群覓食、退火過程等，以在較短的時間內獲得問題的近似解（可接受解）。物流車輛調度中，從主體角度分析，涉及到調度中心、配送點、貨物及車輛，從問題求解過程分析，涉及到車輛的裝配、車輛路徑的規劃等，其求解過程是典型的NP問題，因此，使用進化算法進行求解是一種典型的求解方法，典型的文獻有：遺傳算法[18-19]、蝙蝠算法[20]、多智能體[21]、粒子群算法[22]、蟻群算法[23]、模擬退火算法[24]、免疫算法[25]、混合算法，即包含了多種啟發算法的求解方法，如文獻[26]使用了遺傳算法和模糊規則。

在進化算法求解中，其求解過程分為兩個核心部分：編碼和迭代。編碼是用計算機表示問題的解的方式，迭代是對編碼進行不斷更新以獲得更優解的方法。在編碼中，對于物流調度問題，常見的有整數編碼方法、實數編碼方法；而迭代問題，以遺傳算法的基因迭代和粒子群的迭代算法最具代表性。本文以前文描述的調度模型為基礎，對這兩種典型的編碼方法和迭代方法進行詳細介紹，以使研究者清晰了解當前物流調度問題的啟發式求解過程。

3.1 編碼方法

（1）整數編碼方法[14,27-28]。用一組長度為n+c+1的實數進行編碼，表示一組調度方案，如：一個調度中包含8個客戶節點3輛車，則一個編碼為047201308560，其對應的含義為：車輛1負責客戶4、7、2的運輸，車輛2負責客戶1、3的運輸，車輛3負責8、5、6的運輸，客戶順序亦為車輛行駛路徑。

（2）粒子編碼方法，實數編碼方法[11-22]。用一組長度為n的實數向量表示，實數整數部分表示該節點客戶由那個車輛進行服務，小數部分的大小決定了車輛的行駛路徑。如：一個調度中包含8個客戶節點，2輛車，則n=8，對應的編碼為[1.232,2.356,1.587,2.654,2.965,1.852,1.478,1.357],則表示節點1,3,6,7,8由車輛1進行服務，節點2,4,5由車輛2進行服務，車輛的行駛路徑為，車輛1：0-＞1-＞8-＞7-＞3-＞6-＞0;車輛2：0-＞2-＞4-＞5-＞0。

3.2 迭代方法

在進化算法中，必須通過迭代的方法獲取更優的下一代個體，如遺傳算法是通過選擇、交叉、變異來進行。一個典型的遺傳算法（整數編碼）迭代過程如下：

其中，n為種群大小，fi為染色體i的適應值，則個體pi的累積概率為：

生成一個隨機數r，若 pi-1＜r≤pi，則選擇個體i作為下一代個體種群。

（2）交叉。對于兩個個體，隨機選擇一個任務點，并交換相應的任務點，為保證編碼中個體不重復，需要替換個體中相同點，示例如下：

（3）變異。對一個個體，隨機選擇兩個任務點，并交換位置，示例如下：

Pi=[012034506780]互換一個位置Pi1=[012037506380]

對于粒子群算法，則通過個體的最佳位置和群體的最佳位置來計算個體的下一個運動位置，一個典型的粒子群算法（實數編碼）的主要計算過程如下：

設粒子i在t時刻的狀態為Xit，則粒子i在t+1時刻的狀態：

其中，λ是慣性權重，表示粒子的當前位置對粒子移動到下一個位置的影響；α、β為加速系數，pBest表示粒子運動中出現的最佳位置，gBest表示粒子群的最佳位置，r1、r2為隨機數。

4 未來的研究方向

（1）新能源物流車調度。新能源車是未來發展的趨勢，相比傳統燃油車，新能源車在單位運輸成本方面有較大的優勢，同時物流企業也更容易提供固定的充電樁，因此，未來城市物流一定使用新能源車作為運輸工具。新能源車相比傳統燃油車，其運輸里程和充電時間、位置都需要在運輸中進行考慮，其物流車輛的調度更加復雜，這是未來物流調度研究方向之一，具體內容可以參考文獻[29]。

（2）基于物聯網及車聯網的物流運輸。目前，調度模型的假設都是以零售配送為原型設計，現代物流的復雜已經遠遠超過了經典的物流調度模型。如：動態的物流調度模型，在運輸過程中，可以動態地根據客戶的需求調整物流過程；基于預測及大數據分析的物流調度方法，可以依據數據的分析，精準的調整物流配送的過程，確保整個物流環節盡可能達到零庫存。

隨著物聯網的發展，物流貨物的信息，包含體積，重量、目的地、時間約束等信息可以更加充分的獲取，同時車輛的狀態也可以通過車聯網實時獲取，因此，如果更好地匹配貨物和車輛是一個重要的研究方向。同時，由于上述技術發展所帶來的實時動態物流調度也是一個研究方向。

（3）更加高效的編碼方法。首先，目前以節點為序的編碼方式，限制了基因表達的多樣性，只能局限于對特定問題的求解，限定條件較多。如：經典的整數編碼方法，限定了每個服務點允許且只允許訪問一次，一個服務節點可以通過一次服務滿足其需求。這種限定條件在特定的物流環境，如：零售配送是適用的，但是對于倉儲物流，如，不同倉儲節點間的調度，很多倉儲節點是不可以通過一次服務得以滿足，必須通過多輛車進行服務以滿足其調度需求。

其次，目前對于物流車輛的調度，無論是整數編碼還是實數編碼，其編碼效率較低。如：實數編碼要求以節點為編碼，要求每個節點出現且只出現一次，這就極大地降低了解空間的遍歷效率，容易陷入局部最優。同時，以0為車輛遍歷路徑的分割點，這種分割在初始化時便確定，存在部分解無法遍歷的問題。

因此，尋找更加有效的基因編碼方法是物流車輛調度的一個研究難點。一種較為可行的研究思路是，不在采用以節點為編碼的方式，可以考慮以車輛為編碼或者以貨物為編碼，進而建立更加符合實際需求的調度模型。

[1]肖柯偉,陳志,趙博.物流配送車輛調度問題智能算法研究進展[J].物流科技,2015,(12):21-24.

[2]楊弋,顧幸生.物流配送車輛優化調度的綜述[J].東南大學學報(自然科學版),2003,(S1):105-111.

[3]浮萍萍,葉春明,李佳桐.物流配送車輛調度路徑優化問題算法研究[J].物流科技,2015,(3):5-8.

[4]Adulyasak Y,Cordeau J-F,Jans R.The production routing problem:A review of formulations and solution algorithms[J].Computers&Operations Research,2015,55(Supplement C):141-152.

[5]Lahyani R,Khemakhem M,Semet F.Rich vehicle routing problems:From a taxonomy to a definition[J].European Journal of Operational Research,2015,241(1):1-14.

[6]Dantzig G B,Ramser J H.The Truck Dispatching Problem[M].INFORMS,1959.

[7]楊貴紅.非滿載物流車輛調度優化方法研究[J].計算機仿真,2017,(3):147-150.

[8]Manisri T,Mungwattana A,Janssens GK,et al.A Hybrid Algorithm for the Vehicle Routing Problem with Soft Time Windows and Hierarchical Objectives[J].Journal of Information and Optimization Sciences,2015,36(3):283-300.

[9]王楨,黃磊.考慮訂單發貨區域的物流配送調度問題研究[J].計算機應用研究,2016,(1):82-86.

[10]金濤.多配送中心物流車輛調度的改進差分進化算法[J].計算機工程與應用,2014,(3):232-235.

[11]鄧先瑞,于曉慧,李春艷,等.基于種群分類粒子群算法的物流車輛調度優化[J].計算機工程與應用,2016,(10):237-240.

[12]王陽明,趙利.基于多車型多約束的動態車輛調度算法研究[J].計算機工程,2016,(9):305-309.

[13]任雪甜,朱曉敏,何中祥,等.基于改進C-K節約算法的第三方冷鏈物流企業車輛調度[J].北京交通大學學報,2015,(4):125-132.

[14]黃遵娟.基于遺傳算法的城市冷鏈物流配送路徑優化研究[J].經營與管理,2017,(8):97-101.

[15]李秀娟,楊玥,蔣金葉,等.蟻群優化算法在物流車輛調度系統中的應用[J].計算機應用,2013,(10):2 822-2 826.

[16]張婷,賴平仲,何琴飛,等.基于實時信息的城市配送車輛動態路徑優化[J].系統工程,2015,(7):58-64.

[17]馮亮,梁工謙.聯網中物流配送車輛調度目標定位設計與仿真[J].計算機仿真,2017,(4):377-381.

[18]鄭丹陽,毛劍琳,郭寧,等.求解動態需求車輛調度問題的自適應量子遺傳算法[J].傳感器與微系統,2017,(8):130-133.

[19]張玉,賈遂民.多資源約束的車輛調度問題的改進遺傳算法[J].計算機工程與應用,2016,(7):253-258.

[20]張曉磊,馬從安,申晨.物流云服務下基于改進蝙蝠算法的任務調度[J].計算機應用研究,2015,(6):1 676-1 679.

[21]席釕姿,張峰.基于多智能體技術的物流運輸調度系統分析[J].物流工程與管理,2017,(5):67-70.

[22]吳聰,楊建輝.基于改進粒子群算法的物流配送車輛調度優化[J].計算機工程與應用,2015,(13):259-262.

[23]王曉東,張永強,薛紅.基于改進蟻群算法對VRP線路優化[J].吉林大學學報(信息科學版),2017,(2):198-203.

[24]唐沖.基于模擬退火算法的應急物流車輛調度[J].物流技術,2017,(1):114-116.

[25]潘世舉.應急物流車輛調度優化中免疫算法的應用[J].物流技術,2016,(7):80-82.

[26]張潛,李鐘慎,胡祥培.基于模糊優化的物流配送路徑(MLRP)問題研究[J].控制與決策,2006,(6):689-692.

[27]甘寶,薛玉璽,魏文萍.基于改進遺傳算法的車輛路徑問題[J].交通運輸研究,2015,(4):88-94.

[28]馮輝宗,陳勇,劉飛.基于遺傳算法的配送車輛優化調度[J].計算機集成制造系統,2004,(S1):81-84.

[29]Juan A,Méndez C,Faulin J,et al.Electric Vehicles in Logistics and Transportation:A Survey on Emerging Environmental,Strategic,and Operational Challenges[J].Energies,2016,9(7):86-107.