改進差分進化算法在物流配送中的多目標優化研究

張　新

(紹興職業技術學院信息工程學院,浙江 紹興 312000)

0　引言

物流配送是物流中的重要環節，它解決了物資到消費者的最后一公里問題，關系到消費者對企業的滿意度和降低物流管理成本兩方面。物流配送能力將直接影響物流企業的市場竟爭力。為了滿足用戶的需要、降低物流配送成本，如何科學地規劃和部署配送，已成為物流企業管理者必須考慮的問題[1]。

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

本文采用改進的差分進化算法，對物流配送中的車輛運輸路徑規劃優化，提高了物流配送的經濟效益，實現了物流管理的精準化和科學化[2-3]。

1　多目標物流配送及其模型

1.1　多目標物流配送問題

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

1.2　問題模型研究

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

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

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

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

(1)

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

(2)

式中：K為配送車輛數；x0jk為車輛從配送中心到顧客的直達性。

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

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

(3)

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

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

(4)

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

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

(5)

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

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

(6)

(7)

(8)

式(9)、式(10)對時間窗口進行約束控制。

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

(9)

ai≤sik≤bi

(10)

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

2　差分進化算法

差分進化(differentialevolution,DE)算法是一種啟發式優化算法。它最早在1995年，由Storn和Price首次共同提出，主要用于求解實數優化問題。該算法具有結構簡單、容易實現、收斂快速和魯棒性強的特點，目前在電磁學、模式識別、數據挖掘、人工神經網絡等方面取得了較好的應用成效。

2.1　基本算法概述

DE算法的主要算法過程與其他進化算法大致相同，主要操作有變異、交叉和選擇。算法起始于初始種群。初始種群隨機產生。首先進行變異操作：從種群中隨機選取兩個不同個體進行差向量操作；隨機選取不同的個體作為第三個個體，把差向量加權后按照一定的規則與第三個個體求和，其結果就是變異個體。然后進行交叉操作：按規則選定目標個體，把變異得到的變異個體與目標個體進行參數混合，產生試驗個體。最后，進行選擇操作，把試驗個體與目標個體進行比較。如果試驗個體的適應度值更優，則試驗個體將取代目標個體；否則，保留目標個體。

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

2.2　改進的差分進化算法

為了解決帶有時間窗口的多目標物流配送優化問題，本文對基本差分算法進行了適當的改進，以下通過具體案例加以分析說明。假設配送顧客數量為8個，配送車輛的最大載重質量和行車速度統一為2 000 kg和60 km/h，顧客對配送時間有要求。

①編碼與初始化種群。

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

②變異操作的改進。

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

設定：

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)，得中間結果： 3 8 5 7。

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

③交叉操作。

(11)

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

④選擇操作。

(12)

通過執行步驟②～步驟④的循環操作，可得最大進化代數。

⑤選擇Pareto最優解。

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

3　實例仿真與分析

3．1　實例條件

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

表1　顧客配送時間要求及所需物品質量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　仿真過程分析

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

表3為NP=6時隨機產生的初始化種群，車輛數最多為6輛、最少為5輛，總運輸路程最長為1 301 km，最短為932 km，平均為1 180 km左右。這些初始化種群的可行解離最優化較遠。

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

表4為NP=6時，經過十次迭代運算后的可行解集。從表4中可明顯發現車輛運輸總路程和配送車輛數都有了減少，最短總路程數為862 km，車輛數最小為3輛。

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

表5為當NP=10時，經過十次迭代運算后的最優可行解。表5數據表明，最優配車數為3輛，最短總運輸路程為862 km，產生的3條規劃路徑為：5-4-6，2-3，1-8-7。

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

表6為當NP=20時，經過百次迭代運算后的最優可行解。表6數據表明，最優配車數為3輛，最短總運輸路程為799 km，產生的3條規劃路徑為：5-4-6，2-3，1-7-8。

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

4　結束語

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

參考文獻:

[1] 鄒霞玲.基于物聯網的航空物流管理系統研究[J].自動化儀表，2016,37(6)：66-70.

[2] 楊振宇.差分進化算法參數控制與適應策略綜述[J].智能系統學報，2011(10)：415-423.

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

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

[5] 裴振奎.差分進化算法在多目標路徑規劃中的應用[J].遼寧工程技術大學學報，2010(5)：899-902.

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

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

[8] 李昌兵.物聯網環境下生鮮農產品物流配送路徑優化研究[J].商業研究，2017(4)：1-9.

[9] 李榮雨.改進的差分進化算法在電力經濟調度中的應用[J].自動化儀表，2016,37(11)：43-47.

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