(北京物資學院 信息學院，北京 110049)

大型物流車輛配送線路自適應調度方法

郭鍵

(北京物資學院信息學院，北京110049)

為了有效提高物流配送車輛的利用率，降低配送車輛的空載率及物流運輸成本，需要對大型物流車輛配送線路自適應調度方法進行研究；當前方法多是采用通過對物流車輛配送過程中的調度與路徑選擇進行分析，建立多類型的物流配送車輛調度模型，并構建改進后的遺傳算法，對物流調度模型的算法效率以及計算時間和復雜度進行優(yōu)化，以獲取物流車輛配送調度問題的最優(yōu)解，但該方法存在過程較為繁瑣的問題；為此，提出一種大型物流車輛配送線路自適應調度方法；該方法首先建立物流車輛配送線路調度問題的數(shù)學模型，為實現(xiàn)自適應調度方法對數(shù)學模型進行優(yōu)化求出最優(yōu)解，利用蟻群算法對物流車輛配送調度數(shù)學模型的最優(yōu)解進行優(yōu)化，獲取最優(yōu)路徑的適應度初始化蟻群算法的各客戶點之間的信息素，從而得出了優(yōu)化的最優(yōu)路徑；以優(yōu)化的最優(yōu)路徑完成對大型物流車輛配送線路自適應調度；仿真實驗表明，利用蟻群算法不僅加快了物流配送路線調度優(yōu)化問題求解的速度，降低了物流運輸?shù)某杀?，而且獲取了最優(yōu)解的概率，比其他調度算法具有更明顯的優(yōu)勢。

大型物流；車輛配送；自適應調度；蟻群算法

0 引言

隨著經(jīng)濟的飛速發(fā)展，物流水平的不斷提高，物流平臺已成為各行業(yè)中必不可少的輔助平臺[1]。物流配送加快了經(jīng)濟的發(fā)展，帶動了人們的消費。但進行物流配送時易受到很多因素的影響，例如客戶的位置、客戶配送要求、以及配送車輛等多方面，導致物流車輛配送的自適應調度問題越來越嚴峻[2]。在這種情況下，如何利用有限的車輛高效的安排配送，在配送過程中降低配送成本是該領域急需解決的主要問題。對科學物流進行有效地管理是加快物流配送的效率，提高物流配送服務質量的有效途徑[3]?？茖W的物流管理涉及到很多方面，車輛配送為主要環(huán)節(jié)，配送指按客戶要求進行物品的派發(fā)和收攬，物流車輛配送是配送過程中最主要的部分[4]。車輛配送自適應調度的主要目標是滿足客戶要求的條件下，降低物流配送的成本。引起了很多專家的關注與重視，由于物流車輛配送調度方法具有廣泛的發(fā)展意義，因此成為物流領域人士研究的重點課題。

近年來也取得了一定的成果，李明對物流車輛調度的優(yōu)化問題的現(xiàn)狀進行了總體的探究，分析了當前物流配送調度問題的現(xiàn)狀。徐銀聰對物流車輛配送調度的優(yōu)化方法進行了比較，為物流車輛配送調度過程中進行合理的選擇方法提供了依據(jù)。郭耀提出了基于物流車輛配送的優(yōu)化理論方法，主要以物流車輛配送調度的基本理論為主，對單車場和多車場車輛配送調度的優(yōu)化問題、滿載和非滿載的物流車輛配送優(yōu)化問題以及物流車輛配送調度算法的實現(xiàn)進行了詳細的介紹[5]。袁慶達提出將搜索算法應用到物流車輛配送線路調度優(yōu)化問題。李軍對非滿載物流車輛配送調度問題的遺傳算法進行了研究，將基于編碼的遺傳算法應用于物流車輛配送調度優(yōu)化問題，利用遺傳算法解決物流車輛配送調度問題提供了理論支持。陸杰將遺傳算法的思想與物流車輛配送調度的程序設計相結合，對遺傳算法進行簡單的編程[6]。李寧提出了一個調度算法來解決物流車輛配送的問題，在此基礎上利用遺傳算法給出車輛行駛的最優(yōu)路徑。高偉倫針對遺傳算法求解物流車輛配送調度問題進行了研究。文獻[8]提出了一種基于改進遺傳算法的物流配送調度方法。主要對物流車輛配送過程中的調度與最優(yōu)路徑進行分析，建立多類型的配送車輛調度模型，在此基礎上構建改進后的遺傳算法，對物流調度模型得算法效率以及減少計算時間和復雜度進行優(yōu)化，更加高效的獲取物流車輛配送調度問題的最優(yōu)解，但該方法存在過程較為繁瑣的問題。文獻[9]提出了一種基于神經(jīng)網(wǎng)絡的物流配送調度優(yōu)化算法。首先對城市物流配送建立數(shù)學模型，建立解決非滿載車輛優(yōu)化路線的神經(jīng)網(wǎng)絡模型。利用神經(jīng)網(wǎng)絡對物流車輛調度進行優(yōu)化，給出解決物流車輛配送優(yōu)化調度為一體的具體方法，但該方存在成本較高的問題。文獻[10]提出一種基于改進粒子群算法的物流配送調度模型。建立物流配送調度模型，將物流車輛與車輛路徑進行編碼編成粒子，利用粒子間的協(xié)作找出最優(yōu)物流車輛配送調度方案，對粒子算法存在的不足進行了改進，但該方法存在調度結果不理想的問題。

針對上述問題，提出一種物流配送自適應調度的方法。仿真實驗表明，結合蟻群算法加快物流配送自適應調度問題求解的速度，降低了物流運輸?shù)某杀?，具有廣泛的實用價值。

1 物流車輛配送自適應調度方法

首先對物流車輛配送建立自適應調度模型，采用調度方法對自適應模型進行求最優(yōu)解，結合蟻群算法對物流車輛自適應調度的數(shù)學模型最優(yōu)解進行優(yōu)化，獲取最優(yōu)路徑對蟻群算法客戶間的信息素進行初始化，從而得出了優(yōu)化的最優(yōu)路徑；以優(yōu)化的最優(yōu)路徑完成對物流配送自適應調度問題。具體步驟如下：

1.1 建立物流車輛調度問題的數(shù)學模型

首先建立物流車輛配送自適應調度的數(shù)學模型，自適應調度的問題主要是對有限的車輛在規(guī)定時間內完成任務作出相應的安排。本文主要對物流車輛配送自適應調度問題的可用資源與活動以及調度目標進行研究。

活動主要指有物流配送中心為客戶進行配送貨物，假設有一個物流配送中心，M表示客戶的數(shù)目，配送貨物的客戶位置固定，qi(i=1,2,…,M)表示配送貨物的重量。

可用資源指配送貨物的車輛，K表示配送車的車輛數(shù)，Qk(k=1,2,…,K)表示配送車輛的載重量，Dk(k=1,2,…,K)表示物流車輛單次配送的里程數(shù)，Ck(k=1,2,…,K)表示配送車輛單次配送的客戶數(shù)。

物流調度目標是對調度序列盡心優(yōu)化求解。滿足在配送任務約束的條件下，實現(xiàn)配送車輛里程為最短。

綜合上述，建立物流配送自適應調度的數(shù)學模型為：

(1)

公式(1)表示物流配送的目標函數(shù)，要求車輛配送的總里程最短。

(2)

公式(2)表示車輛配送要求，要求每個客戶的車輛配送要求都需要滿足。

(3)

公式(3)表示為物流車輛配送里程的約束條件，物流車輛進行調度安排配送時，要求物流車輛配送的任務不可超過單次配送車輛里程的上限。

(4)

公式(4)表示物流車輛配送載重量的約束條件，物流自適應調度安排車輛配送時，要求配送車輛不可超載。

0≤nk≤Ck,Ck≤M

(5)

公式(5)表示是物流車輛配送客戶數(shù)的約束條件，要求車輛配送路線上客戶數(shù)不可超過物流車輛單次配送客戶數(shù)上限，客戶數(shù)目M為限制的上限。

Rk={rki|rki∈{1,2,…,M},i=1,2,…,nk}

(6)

公式(6)表示物流車輛配送路線的安排。

Rk1∩Rk2=φ,?k1≠k2

(7)

公式(7)表示是車輛配送隱含的約束，要求每個客戶僅貨物由一臺車進行配送。

其中，doj(j=1,2,…,M)表示物流配送中心到每個客戶的距離，dij(i,j=1,2,…,M)表示客戶i到j的距離，nk表示第k輛車進行配送服務的用戶數(shù)(nk=0表示不使用第k輛車)。Rk表示第k條配送車輛行駛的路線，其中，rko=0表示配送中心，rki表示路線k中第i個訪問的客戶。

1.2 基于蟻群算法的物流配送自適應調度方法

蟻群算法是以螞蟻尋找食物生成的路徑模擬的一種算法，當環(huán)境發(fā)生變化時，螞蟻依然可以找出新的路徑。

將物流配送車輛的數(shù)目比喻為螞蟻的數(shù)目，螞蟻從物流配送中心尋找最優(yōu)路徑，路徑上的物流信息素為路徑上的適應值，由公式(8)表示：

τij=F(rij)

(8)

隨著迭代次數(shù)的逐漸增加，第t+1迭代后物流車輛配送路徑的信息素在迭代的基礎上由公式(9)表示：

(9)

式中，τij(t)max表示物流車輛配送路徑信息素的最大值，τij(t)min表示物流車輛配送路徑信息素的最小值，當物流路徑信息素逐漸加大時，易過早得出局部的最優(yōu)解，獲取不出全局最優(yōu)解。當物流信路徑息素較小時，易導致迭代的次數(shù)過多，收斂的速度逐漸變慢。

第k只螞蟻在物流車連配送的路徑(i,j)間進行轉移的概率為：

(10)

式中，τij(t)表示物流車輛配送路徑(i,j)物流信息素的濃度，wij表示路徑(i,j)間的距離，a表示物流路徑信息素的主要程序，b表示物流車輛配送路徑耗費的時間。r∈R表示螞蟻在配送路徑中連續(xù)經(jīng)過的客戶點。

1.3 蟻群優(yōu)化車輛配送路徑算法的描述

算法輸入：螞蟻的總數(shù)量(客戶的數(shù)目)，任意的兩個客戶點(i,j)間車輛配送的距離wij，任意客戶(i,j)的物流路徑信息素的濃度τij(t)，a表示物流路徑信息素濃度的主要性，b編號物流車輛配送路徑的重要性，allowk表示螞蟻k訪問的客戶點，ρ表示物流路徑信息素的持久性；

蟻群算法的輸出：物流車輛自適應調度的最優(yōu)路徑；

步驟1：迭代次數(shù)表示為i=0；

步驟2：第k只螞蟻從物流配送中心開始出發(fā)，依據(jù)公式(10)從allowk中選擇第j個配送客戶點，在進行迭代時，所有的螞蟻共享一個allowk；

步驟3：當螞蟻選擇配送客戶點j作為訪問的配送客戶點，并且ck+qk≤bk時，可滿足配送車輛容量的要求，將j從allowk中刪除，依據(jù)公式(9)對物流路徑信息素進行更新；

步驟4：對于螞蟻的k=1,2,…,M，假設allowk不為空時，轉到步驟2繼續(xù)進行此步驟，假設allowk為空時，轉到步驟5繼續(xù)進行此步驟；

步驟5：計算螞蟻當前行走的路徑，認定為當前的最優(yōu)解；

步驟6：迭代次數(shù)由i=i+1表示，達到最大迭代次數(shù)imax；

步驟7：迭代輸出的結果表示為當前的最優(yōu)解；

2 實驗結果分析

2.1 實驗數(shù)據(jù)來源

為確定蟻群算法對物流車輛配送線路自適應調度問題求解的有效性，在P42核3.6GHz，內存為4GB，Windows7的仿真的環(huán)境下，利用VC++8.0編程進行一次仿真實驗。仿真實驗對象為：1個配送中心，10個收貨點，5臺配送車輛，每臺配送車的最大載重量為20，每個收貨點配送量由表1所示，物流收貨點費用如表2所示，物流車輛配送線路的最優(yōu)調度方案的最少的費用是950元。

表1 各收貨點所需配送量

表2 各收貨點的配送費用

為了測試迭代數(shù)對蟻群算法求大型解物流車輛配送線路自適應調度問題的影響，分別采用進行迭代100與500次仿真實驗，分析迭代次數(shù)變化對最少費用的影響，最優(yōu)方案的最少費用的變化曲線由圖1與圖2表示。

圖1 迭代100次的最少費用

圖2 迭代500次的最少費用

由圖1和圖2可知，隨著配送迭代次數(shù)的增加，蟻群算法不斷向最優(yōu)解靠近，即貼近最少費用950元，圖1、圖2對比能看出，配送迭代的次數(shù)逐漸增多，尋找最優(yōu)物流車輛配送自適應調度方案的成功率也在逐漸增加，同時蟻群算法的運行時間也在逐漸增加，降低了自適應調度問題求解的效率，由此本文物流配送自適應調度迭代的次數(shù)選擇為200次。

2.2 與其他算法性能對比

選擇標準粒子算法、改進粒子群算法以及動態(tài)規(guī)劃算法與本文算法進行對比實驗。對各種算法進行20次實驗，找出自適應調度問題最優(yōu)解的概率與求解的時間，結果由表3所示。將表3的分析結果進行對比，能得出以下結論：

1)相對于動態(tài)規(guī)劃算法，其他算法的最優(yōu)求解時間逐漸減少，提高了物流車輛配送自適應調度求解的效率，動態(tài)規(guī)劃算法是利用窮舉方式對自適應調度最優(yōu)解進行搜索，自適應調度問題尋優(yōu)的次數(shù)與調度問題的規(guī)模表示為指數(shù)變化的關系，實際物流自適應調度應用性較差。

2)相對于其他的智能算法，蟻群算法尋找最優(yōu)解的成功率逐漸在增加，自適應調度問題求解的時間也逐漸減少，蟻群算法減少了尋找最優(yōu)解的物流配送迭代次數(shù)，復雜度逐漸在下降，增強蟻群算法搜尋的能力，獲取更優(yōu)的物流車輛配送自適應的調度方案。

表3不同算法的綜合性能對比

仿真實驗證明，利用蟻群算法加快了物流配送路線自適應調度求解的速度，降低了物流運輸?shù)某杀?，具有廣泛的實用價值。

3 結論

采用通過對物流車輛配送過程中的調度與路徑選擇進行分析，建立多類型的物流配送車輛調度模型，在此基礎上構建改進后的遺傳算法，對物流調度模型得算法效率以及減少計算時間和復雜度進行優(yōu)化，更加高效的獲取物流車輛配送調度問題的最優(yōu)解，但該方法存在過程較為繁瑣的問題。為此，提出一種大型物流車輛配送線路自適應調度方法。仿真實驗證明，利用蟻群算法利用蟻群算法加快了物流配送路線自適應調度求解的速度，降低了物流運輸?shù)某杀?，具有廣泛的實用價值。

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

[2]程八一,李 明.面向生產(chǎn)-庫存-配送的聯(lián)合調度問題及蟻群優(yōu)化算法[J].機械工程學報,2015,51(12):202-212.

[3]田 冉,孫林夫,唐慧佳,等.多車場物流協(xié)同運輸調度問題研究[J].計算機工程與應用,2015,51(21):230-236.

[4]李 靜.一種基于蟻群改進算法的單向物流配送路徑優(yōu)化[J].電子設計工程,2016,24(10):68-70.

[5]李 雪,聶蘭順,齊文艷,等.基于近似動態(tài)規(guī)劃的動態(tài)車輛調度算法[J].中國機械工程,2015,26(5):682-688.

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

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

[8]崔 濤.基于云服務優(yōu)選的最節(jié)能物流運輸調度系統(tǒng)的設計[J].現(xiàn)代電子技術,2016,39(20):138-141.

[9]王 旭,謝沐男,鄧 蕾.基于粗糙集的物流資源分類方法研究[J].計算機工程與應用,2016,52(14):67-71.

[10]柯俊山,胡 凱,朱文奇.基于啟發(fā)式算法的乘用車物流運輸計劃問題研究[J].數(shù)學的實踐與認識,2015,45(15):89-100.

AdaptiveSchedulingMethodforLarge-scaleLogisticsDistributionVehicleLines

Guo Jian

(School of Information, Beijing WUZI University, Beijing 101149, China)

In order to effectively improve the utilization rate of logistics distribution vehicle and reduce the empty loading rate of distribution vehicles and logistics transportation cost, need adaptive scheduling method for large-scale logistics distribution vehicle lines were studied. But the current method is used to in the process of logistics distribution vehicle scheduling and the choice of path analysis, many model in the process of logistics distribution vehicle scheduling model is established, on the basis of constructing the improved genetic algorithm, the efficiency of logistics scheduling model and algorithm to optimize and reduce the computing time and complexity and more efficient to obtain the optimal solution of logistics distribution vehicle scheduling problem, but the process of this method were more complicated problems. For this, put forward a kind of large-scale logistics distribution vehicle line adaptive scheduling method. This method first to establish a logistics distribution line adaptive scheduling, the mathematical model for the realization of the adaptive scheduling method to further optimization of the mathematical model to find the optimal solution, using the mathematical model of ant colony algorithm for logistics distribution vehicle scheduling optimization, the optimal solution to obtain the optimal path of ant colony algorithm to initialize the fitness of each customer information between the point element, thus obtained the further optimization of the optimal path; In order to optimize the optimal path to complete the adaptive scheduling for large logistics vehicle distribution lines. Simulation experiments show that using ant colony algorithm not only speeds up the logistics distribution vehicle route scheduling optimization problem solving speed, reduce the cost of logistics, and obtain the optimal solution of probability, scheduling algorithm has more obvious advantages than others.

large logistics; vehicle distribution; adaptive scheduling; ant colony algorithm

2017-04-22；

2017-05-15。

北京市屬高等學校青年拔尖人才培育計劃項目(CIT&TCD201504052)。

郭 鍵(1975-)，女，遼寧錦州人，博士研究生，教授，主要從事智能監(jiān)控方向的研究。

1671-4598(2017)11-0166-04

10.16526/j.cnki.11-4762/tp.2017.11.042

F224

A