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

大型物流車輛配送線路自適應(yīng)調(diào)度方法

郭鍵

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

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

大型物流；車輛配送；自適應(yīng)調(diào)度；蟻群算法

0 引言

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

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

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

1 物流車輛配送自適應(yīng)調(diào)度方法

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

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

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

活動主要指有物流配送中心為客戶進(jìn)行配送貨物，假設(shè)有一個物流配送中心，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ù)。

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

綜合上述，建立物流配送自適應(yīng)調(diào)度的數(shù)學(xué)模型為：

(1)

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

(2)

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

(3)

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

(4)

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

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)表示是車輛配送隱含的約束，要求每個客戶僅貨物由一臺車進(jìn)行配送。

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

1.2 基于蟻群算法的物流配送自適應(yīng)調(diào)度方法

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

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

τij=F(rij)

(8)

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

(9)

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

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

(10)

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

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

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

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

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

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

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

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

步驟5：計(jì)算螞蟻當(dāng)前行走的路徑，認(rèn)定為當(dāng)前的最優(yōu)解；

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

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

2 實(shí)驗(yàn)結(jié)果分析

2.1 實(shí)驗(yàn)數(shù)據(jù)來源

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

表1 各收貨點(diǎn)所需配送量

表2 各收貨點(diǎn)的配送費(fèi)用

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

圖1 迭代100次的最少費(fèi)用

圖2 迭代500次的最少費(fèi)用

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

2.2 與其他算法性能對比

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

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

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

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

仿真實(shí)驗(yàn)證明，利用蟻群算法加快了物流配送路線自適應(yīng)調(diào)度求解的速度，降低了物流運(yùn)輸?shù)某杀荆哂袕V泛的實(shí)用價值。

3 結(jié)論

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

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

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

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

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

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

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

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

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

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

[10]柯俊山,胡 凱,朱文奇.基于啟發(fā)式算法的乘用車物流運(yùn)輸計(jì)劃問題研究[J].數(shù)學(xué)的實(shí)踐與認(rèn)識,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。

北京市屬高等學(xué)校青年拔尖人才培育計(jì)劃項(xiàng)目(CIT&TCD201504052)。

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

1671-4598(2017)11-0166-04

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

F224

A