改進(jìn)差分進(jìn)化算法在物流配送中的多目標(biāo)優(yōu)化研究

張　新

(紹興職業(yè)技術(shù)學(xué)院信息工程學(xué)院,浙江 紹興 312000)

0　引言

物流配送是物流中的重要環(huán)節(jié)，它解決了物資到消費(fèi)者的最后一公里問(wèn)題，關(guān)系到消費(fèi)者對(duì)企業(yè)的滿意度和降低物流管理成本兩方面。物流配送能力將直接影響物流企業(yè)的市場(chǎng)竟?fàn)幜?。為了滿足用戶的需要、降低物流配送成本，如何科學(xué)地規(guī)劃和部署配送，已成為物流企業(yè)管理者必須考慮的問(wèn)題[1]。

車輛路徑問(wèn)題(vehicle routing problem,VRP)最早在1959年由Dantzig提出。它是指配送中心在了解客戶個(gè)性化要求的前提下(如客戶物品對(duì)應(yīng)單一車輛)，安排配送物品的車輛從配送中心出發(fā)，并使車輛完成所有配送服務(wù)后返回配送中心。為了解決車輛路徑規(guī)劃問(wèn)題，1992年，J.Lawrence等人首先研究了進(jìn)化算法，使帶有時(shí)間窗口車輛路徑問(wèn)題(vehicle routing problems with time windows,VRPTW)問(wèn)題得到了較好的解決。2006年，為了解決多目標(biāo)VRP問(wèn)題，Tan等人采用了混合多目標(biāo)進(jìn)化算法，較好地解決了帶有時(shí)間窗口要求的VRP問(wèn)題。

本文采用改進(jìn)的差分進(jìn)化算法，對(duì)物流配送中的車輛運(yùn)輸路徑規(guī)劃優(yōu)化，提高了物流配送的經(jīng)濟(jì)效益，實(shí)現(xiàn)了物流管理的精準(zhǔn)化和科學(xué)化[2-3]。

1　多目標(biāo)物流配送及其模型

1.1　多目標(biāo)物流配送問(wèn)題

物流配送是物流管理中的重要環(huán)節(jié)，優(yōu)化配送要素十分關(guān)鍵。物流配送的最大目標(biāo)是讓用戶滿意，同時(shí)要合理規(guī)劃配送計(jì)劃，使車輛運(yùn)輸成本最小化。配送過(guò)程指物資由車輛運(yùn)輸，從配送中心出發(fā)按時(shí)間節(jié)點(diǎn)要求及時(shí)送到消費(fèi)者手中；然后車輛返回配送中心。這個(gè)過(guò)程涉及兩個(gè)優(yōu)化目標(biāo)：車輛與路徑。物流配送的車輛路徑規(guī)劃在配送過(guò)程中要滿足用戶物資送到時(shí)間等個(gè)性化的約束，是帶有時(shí)間窗要求的多目標(biāo)VRP問(wèn)題。假設(shè)車輛出發(fā)點(diǎn)與結(jié)束點(diǎn)同是配送中心、所有配送車輛的最大載重質(zhì)量和速度是定值、顧客的貨物只能由一輛車配送并且車輛不可重復(fù)到達(dá)顧客點(diǎn)、顧客對(duì)配送時(shí)間有明確的要求，則路徑和車輛優(yōu)化目標(biāo)是達(dá)到配送成本最小化[4-5]。

1.2　問(wèn)題模型研究

物流配送路徑優(yōu)化可以采用無(wú)向連通圖進(jìn)行描述。假設(shè)圖G=(V，E)表示無(wú)向連通圖。其中，V為無(wú)向連通圖中的點(diǎn)，代表一個(gè)顧客點(diǎn)或配送中心，V={vi|i=0,1,...,n}；E為兩點(diǎn)之間的邊，它代表顧客(包括配送中心)之間的距離,E={ei,j|i,j=0,1,...，n且i≠j},i、j為顧客號(hào),n為顧客數(shù)量。本研究是帶有時(shí)間窗口的VRP問(wèn)題。它涉及幾個(gè)約束條件：車輛載重約束、配送時(shí)間節(jié)點(diǎn)約束、顧客被訪問(wèn)次數(shù)約束等[6]。

假設(shè)配送中心需要為n個(gè)不同地點(diǎn)的顧客配送物資,用S表示顧客；配送中心有足夠的車輛數(shù)m來(lái)滿足配送需求，用K表示配送車輛,那么V={S0，S1，…，Sn},K={1,2,…，m}。差分進(jìn)化算法一般采用實(shí)數(shù)方式編碼，顧客點(diǎn)編號(hào)為1，2,…,n,并且規(guī)定配送中心為編號(hào)0[7]。T為配送所需總成本，由配送距離dij和單位車輛路程配送成本Pk計(jì)算所得。dij表示顧客之間的距離；每位顧客的貨物量為gi，配送車輛的最大載重質(zhì)量為Q，配送車輛是否到達(dá)顧客i處用yik表示。

帶有時(shí)間窗口的物流配送多目標(biāo)函數(shù)主要由兩部分組成：配送成本最低和配送所用車輛最少。

式(1)和式(2)分別表示配送總費(fèi)用最低和配送用車最少。

(1)

式中：T為配送總成本；dij為配送距離；Pk為車輛單位配送成本；xijk為顧客之間的車輛直達(dá)性。

(2)

式中：K為配送車輛數(shù)；x0jk為車輛從配送中心到顧客的直達(dá)性。

模型的主要約束條件如下。

式(3)表示顧客i和顧客j之間的車輛k可達(dá)性，即車輛k是否配送到顧客i處。

(3)

式中：xijk為顧客之間的車輛直達(dá)性；yjk為車輛可達(dá)性。

式(4)表示車輛可到達(dá)顧客點(diǎn)，且只到達(dá)一次。

(4)

式中：xijk為顧客之間的車輛直達(dá)性。

式(5)表示配送車輛載重受限，不能超重運(yùn)輸。

(5)

式中：gi為顧客的貨物量;yik為車輛是否到達(dá)顧客點(diǎn)；Q為配送車輛的最大載重。

式(6)～式(8)表示車輛在不重復(fù)到達(dá)顧客點(diǎn)的情況下返回配送中心。

(6)

(7)

(8)

式(9)、式(10)對(duì)時(shí)間窗口進(jìn)行約束控制。

sik+tij-K(1-xijk) ≤sjk

(9)

ai≤sik≤bi

(10)

式中：sik為車載k到達(dá)某一顧客處的時(shí)間要求；i=1,2,…,n;k=1,2,…,m。

2　差分進(jìn)化算法

差分進(jìn)化(differentialevolution,DE)算法是一種啟發(fā)式優(yōu)化算法。它最早在1995年，由Storn和Price首次共同提出，主要用于求解實(shí)數(shù)優(yōu)化問(wèn)題。該算法具有結(jié)構(gòu)簡(jiǎn)單、容易實(shí)現(xiàn)、收斂快速和魯棒性強(qiáng)的特點(diǎn)，目前在電磁學(xué)、模式識(shí)別、數(shù)據(jù)挖掘、人工神經(jīng)網(wǎng)絡(luò)等方面取得了較好的應(yīng)用成效。

2.1　基本算法概述

DE算法的主要算法過(guò)程與其他進(jìn)化算法大致相同，主要操作有變異、交叉和選擇。算法起始于初始種群。初始種群隨機(jī)產(chǎn)生。首先進(jìn)行變異操作：從種群中隨機(jī)選取兩個(gè)不同個(gè)體進(jìn)行差向量操作；隨機(jī)選取不同的個(gè)體作為第三個(gè)個(gè)體，把差向量加權(quán)后按照一定的規(guī)則與第三個(gè)個(gè)體求和，其結(jié)果就是變異個(gè)體。然后進(jìn)行交叉操作：按規(guī)則選定目標(biāo)個(gè)體，把變異得到的變異個(gè)體與目標(biāo)個(gè)體進(jìn)行參數(shù)混合，產(chǎn)生試驗(yàn)個(gè)體。最后，進(jìn)行選擇操作，把試驗(yàn)個(gè)體與目標(biāo)個(gè)體進(jìn)行比較。如果試驗(yàn)個(gè)體的適應(yīng)度值更優(yōu)，則試驗(yàn)個(gè)體將取代目標(biāo)個(gè)體；否則，保留目標(biāo)個(gè)體。

DE算法的主要步驟為：①基本參數(shù)包括NP、F、CR；②隨機(jī)產(chǎn)生初始化種群；③計(jì)算種群適應(yīng)度值；④終止條件不滿足時(shí)，進(jìn)行循環(huán)，依次執(zhí)行變異、交叉、選擇運(yùn)算，直到滿足終止條件。

2.2　改進(jìn)的差分進(jìn)化算法

為了解決帶有時(shí)間窗口的多目標(biāo)物流配送優(yōu)化問(wèn)題，本文對(duì)基本差分算法進(jìn)行了適當(dāng)?shù)母倪M(jìn)，以下通過(guò)具體案例加以分析說(shuō)明。假設(shè)配送顧客數(shù)量為8個(gè)，配送車輛的最大載重質(zhì)量和行車速度統(tǒng)一為2 000 kg和60 km/h，顧客對(duì)配送時(shí)間有要求。

①編碼與初始化種群。

首先，進(jìn)行編碼處理。采用自然數(shù)1～8分別表示8位顧客，并把8位顧客數(shù)字通過(guò)隨機(jī)排位組合，以形成的8位數(shù)向量作為初始種群個(gè)體。這個(gè)8位向量代表車輛到達(dá)顧客處的順序，其中的分段代表配送車輛數(shù)。如果隨機(jī)產(chǎn)生的個(gè)體向量Xi(t)為425|681|73，則表明配送車輛為3，3輛車的配送順序分別為：4-2-5，6-8-1，7-3。

②變異操作的改進(jìn)。

變異操作的改進(jìn)基本思想為：首先，選定一個(gè)隨機(jī)向量Xr1(t)作為變異目標(biāo)；然后，對(duì)Xr1(t)的各分矢量作乘2處理，得到新的向量Xr2(t)；最后，隨機(jī)另外選取一個(gè)向量Xr3(t),將Xr2(t)-Xr3(t)，得到Vi(t+1)。分析向量Vi(t+1)各分量值：如大于限定的最大值則用其減最大值；如小于限定的最小值則用其加最大值，從中刪除分向量值為0 的分向量；如出現(xiàn)重復(fù)分向量就留下排在前面的分向量。按序補(bǔ)上向量Xr1(t)中沒(méi)有出現(xiàn)的分向量值，即可得到新的變異向量Vi(t+1)。案例說(shuō)明如下。

設(shè)定：

Xr1(t)=4 2 5 6 8 1 7 3；

Xr3(t)=5 4 2 7 8 3 1 6；

Xr2(t)=2×Xr1(t)=8 4 10 12 16 2 14 6；

Vi(t+1)=Xr2(t)-Xr3(t)=3 0 8 5 8 -1 13 0。

分析Vi(t+1)，得中間結(jié)果： 3 8 5 7。

修正后變異向量Vi(t+1)=3 8 5 7 4 2 6 1。

③交叉操作。

(11)

式(1)中：rand(0,1)取0～1之間的隨機(jī)數(shù)；CR為確定交叉概率，取0～1之間的實(shí)數(shù)；jrand的取值為1～n(n=8)之間的自然數(shù)。這就保證了Ui(t+1)向量至少有一個(gè)分量來(lái)自目標(biāo)向量。

④選擇操作。

(12)

通過(guò)執(zhí)行步驟②～步驟④的循環(huán)操作，可得最大進(jìn)化代數(shù)。

⑤選擇Pareto最優(yōu)解。

建立初始為空的非支配集Y，將產(chǎn)生的非支配解存放在Y中，并將產(chǎn)生的可行解Xi(t+1)與Y中的向量作比較。如存在支配關(guān)系，就刪除該支配解，將非支配解存入Y中，直到滿足結(jié)束條件。最終，最優(yōu)解都在Y中[8-9]。

3　實(shí)例仿真與分析

3．1　實(shí)例條件

從一個(gè)配送中心出發(fā)，為了滿足8位顧客的配送要求，用1～8分別對(duì)顧客進(jìn)行編號(hào)。用0表示配送中心，采用同一型號(hào)車輛來(lái)配送物品。車輛最大載重質(zhì)量為2 000 kg，平均行駛速度60 km/h。顧客配送時(shí)間要求及所需物品質(zhì)量如表1所示。車輛從配送中心的出發(fā)時(shí)間為上午7∶00；顧客(含配送中心)之間的距離如表2所示。

表1　顧客配送時(shí)間要求及所需物品質(zhì)量Tab.1　Delivery time requested by customers and the weight of the goods

表2　顧客(含配送中心)之間的距離Tab.2　Distance between customers (including the distribution center)　km

3.2　仿真過(guò)程分析

整個(gè)仿真過(guò)程采用了3組起始種群數(shù)NP和迭代次數(shù)N∶NP=6,N=10；NP=10,N=10；NP=20，N=100。

表3為NP=6時(shí)隨機(jī)產(chǎn)生的初始化種群，車輛數(shù)最多為6輛、最少為5輛，總運(yùn)輸路程最長(zhǎng)為1 301 km，最短為932 km，平均為1 180 km左右。這些初始化種群的可行解離最優(yōu)化較遠(yuǎn)。

表3　初始化種群(NP=6Tab.3　Initialization population (NP=6)

表4為NP=6時(shí)，經(jīng)過(guò)十次迭代運(yùn)算后的可行解集。從表4中可明顯發(fā)現(xiàn)車輛運(yùn)輸總路程和配送車輛數(shù)都有了減少，最短總路程數(shù)為862 km，車輛數(shù)最小為3輛。

表4　十次迭代運(yùn)算后的種群(NP=6)Tab.4　The population after ten generation operation (NP=6)

表5為當(dāng)NP=10時(shí)，經(jīng)過(guò)十次迭代運(yùn)算后的最優(yōu)可行解。表5數(shù)據(jù)表明，最優(yōu)配車數(shù)為3輛，最短總運(yùn)輸路程為862 km，產(chǎn)生的3條規(guī)劃路徑為：5-4-6，2-3，1-8-7。

表5　十次迭代運(yùn)算后的最優(yōu)化解(NP=10)Tab.5　The optimal solution after ten generation operation (NP=10)

表6為當(dāng)NP=20時(shí)，經(jīng)過(guò)百次迭代運(yùn)算后的最優(yōu)可行解。表6數(shù)據(jù)表明，最優(yōu)配車數(shù)為3輛，最短總運(yùn)輸路程為799 km，產(chǎn)生的3條規(guī)劃路徑為：5-4-6，2-3，1-7-8。

表6　百次迭代運(yùn)算后的最優(yōu)化解(NP=20)Tab.6　The optimal solution after one hundred generation operation (NP=20)

4　結(jié)束語(yǔ)

VRP問(wèn)題一直是大家關(guān)心的重要課題。研究者從不同的角度對(duì)其展開(kāi)了研究與應(yīng)用，取得了不少成功的案例。帶有時(shí)間窗口的VRP問(wèn)題相對(duì)較復(fù)雜，受到更多的約束條件限制[10]。本文采用了適當(dāng)改進(jìn)的差分進(jìn)化算法，對(duì)物流配送中的多目標(biāo)優(yōu)化進(jìn)行了應(yīng)用研究，MATLAB仿真結(jié)果表明，算法可行、有效，收斂快且穩(wěn)定，為物流配送規(guī)劃提供了一種優(yōu)化方案。(

參考文獻(xiàn):

[1] 鄒霞玲.基于物聯(lián)網(wǎng)的航空物流管理系統(tǒng)研究[J].自動(dòng)化儀表，2016,37(6)：66-70.

[2] 楊振宇.差分進(jìn)化算法參數(shù)控制與適應(yīng)策略綜述[J].智能系統(tǒng)學(xué)報(bào)，2011(10)：415-423.

[3] 蔡浩原.基于人工蜂群算法的鮮活農(nóng)產(chǎn)品冷鏈物流配送路徑優(yōu)化[J].江蘇農(nóng)業(yè)科學(xué)，2017(15)：318-321.

[4] 楊啟文.差分進(jìn)化算法綜述[J].模式識(shí)別與人工智能，2008(4)：506-513.

[5] 裴振奎.差分進(jìn)化算法在多目標(biāo)路徑規(guī)劃中的應(yīng)用[J].遼寧工程技術(shù)大學(xué)學(xué)報(bào)，2010(5)：899-902.

[6] 李偉.基于時(shí)間最短路徑的停車場(chǎng)車位引導(dǎo)算法[J].自動(dòng)化儀表，2015,36(8)：23-25.

[7] 徐杰.基于混合粒子群算法的多目標(biāo)車輛路徑研究[J].計(jì)算機(jī)集成制造系統(tǒng)，2007(3)：573-580.

[8] 李昌兵.物聯(lián)網(wǎng)環(huán)境下生鮮農(nóng)產(chǎn)品物流配送路徑優(yōu)化研究[J].商業(yè)研究，2017(4)：1-9.

[9] 李榮雨.改進(jìn)的差分進(jìn)化算法在電力經(jīng)濟(jì)調(diào)度中的應(yīng)用[J].自動(dòng)化儀表，2016,37(11)：43-47.

[10]虎濤濤.一種混沌變參數(shù)粒子群優(yōu)化算法[J].自動(dòng)化儀表，2017,38(3)：37-40.