湯雅連 蔡延光 郭棟 郭帥

(廣東工業(yè)大學(xué) 自動化學(xué)院，廣州 510006)

在實際中常有這樣的情況，客戶需要多種零件商品，這些零件商品是成品的組成部分，具有關(guān)聯(lián)性?？蛻舫３榱吮ＷC其需求不受影響而將所有的零件商品供貨交付給一個物流運輸公司來為其配貨。客戶的這種需求稱之為關(guān)聯(lián)需求;零件商品在被客戶使用，即在加工組成成品的過程中，零件的使用有一個先后順序，稱零件商品具有時間關(guān)聯(lián)性。這時，物流公司應(yīng)該考慮怎樣進(jìn)行車輛分配和尋求最優(yōu)配送路線以達(dá)到最低的物流成本來為多個這種性質(zhì)的客戶配送貨物，這樣的問題稱之為關(guān)聯(lián)物流運輸調(diào)度問題［1］(Incident Vehicle Routing Problem)。由于車輛的行駛速度在一天中不同時間段是變化的，而且行駛速度的變化直接導(dǎo)致客戶間的往返時間不同，所以提出了時變關(guān)聯(lián)運輸調(diào)度問題(Time Varying Incident Vehicle Routing Problem，TVIVRP)。

針對單車場單車型的車輛路徑問題(Vehicle Routing Problem，VRP)，Barrie M. Baker 等［2］對單車場有容量限制且?guī)r間窗的VRP 做了研究，引進(jìn)領(lǐng)域搜索后的GA 能更好地尋優(yōu);Geonwook Jeon［3］等也利用基于OPL-STUDIO 的混合遺傳算法及對多車場多種車型的VRP 求解，尋優(yōu)結(jié)果優(yōu)于GA 得到的結(jié)果。Birbil 和Fang 受電磁場中帶點粒子見“吸引—排斥”機制的啟發(fā)，于2003年提出了一種新的全局優(yōu)化啟發(fā)式算法——類電磁機制算法(Electromagnetism-like Mechanism Algorithm，EMA)。韓麗霞等［4］提出了無約束優(yōu)化問題的類電磁機制算法。王曉娟等［5］對此算法進(jìn)行了研究，綜述了該算法在函數(shù)優(yōu)化、神經(jīng)網(wǎng)絡(luò)訓(xùn)練和調(diào)度等方面的應(yīng)用;Peitsang Wu 等［6］運用傳統(tǒng)EMA 及改進(jìn)的EMA(引入二分法)對不同規(guī)?？蛻舻腣RP 進(jìn)行求解，得出改進(jìn)的算法可找到更優(yōu)解;Alkin Yurtkuran 等［7］利用領(lǐng)域搜索和傳統(tǒng)EMA 的混合算法對有容量約束的benchmark 問題求解，證明該混合算法解決此類問題是極有優(yōu)勢的。但是對于時變關(guān)聯(lián)物流運輸調(diào)度問題的探討甚少，本文就單車場單車型的TVIVRP 問題進(jìn)行探討，將車輛行駛速度表述為與行駛時間相關(guān)的分段函數(shù)，并提出了改進(jìn)的類電磁機制算法來對其求解。

1 問題描述及數(shù)學(xué)模型的建立

1.1 問題描述

問題可以簡單描述為，假設(shè)給定車場及客戶信息(位置和貨物需求量等)，貨物之間的關(guān)聯(lián)系數(shù)，車輛信息(載重約束、里程約束和容量約束等)，要求合理安排車輛、車輛出發(fā)時間和運輸路線，在滿足所有客戶需求的前提下，使配送成本最低。

1)物流配送渠道由1 個車場，l 個客戶(1，2，…，l)，1 個車場，1 個配送中心;

2)車輛從車場出發(fā)，完成配送后返回原車場;

3)配送車輛有最大配送距離約束，非滿載;

4)硬時間窗約束;

5)速度時變約束。車輛的行駛速度隨著所處時間段變化，非高峰期的行駛速度明顯高于高峰期。車輛行駛速度分段函數(shù)圖示如圖1 所示。

6)優(yōu)化目標(biāo)為車輛完成所有配送任務(wù)的配送成本最低。

第i 個客戶的貨運量為gi(i=1，2，…，l)，需要從車場將貨物運給客戶，車輛載重量為q，已知gi＜q。預(yù)先對需要車輛數(shù)進(jìn)行估計?？梢园凑帐?1)確定車輛數(shù)。

式中，［］表示不大于括號內(nèi)數(shù)字的最大整數(shù);0 ＜α ＜1，是對裝車(或卸車)的復(fù)雜程度及約束多少的估計。

以cij表示為從點i 到點j 的運輸成本，cij=cji。目標(biāo)為使車輛的總配送成本最小。車場編號為0。關(guān)聯(lián)系數(shù)為r，rij表示點i 處的貨物與點j 處貨物的關(guān)聯(lián)系數(shù)。

客戶要求送貨的時間窗為［eti，lti］，每小時等待費用和延遲費用分別為s1和s2，車輛早到或者晚到，都會受到懲罰。tij表示車輛從客戶i 出發(fā)到j(luò) 的行駛時間;ati表示車輛抵達(dá)用戶i 的時間，wi為車輛在客戶i 的等待時間，si為車輛在客戶i 的服務(wù)時間。

圖1 車輛行駛速度

1.2 數(shù)學(xué)模型

定義變量如下:

建立數(shù)學(xué)模型

目標(biāo)函數(shù)式(2)表示總運輸成本最小，rij越大，表明貨物的兼容性越好，因不兼容產(chǎn)生的成本越低，反之亦然。式(3)為車輛行駛距離約束，其中表示車輛k 行駛了客戶i 到j(luò) 的路程，n 是車輛k服務(wù)的客戶數(shù)目，最大為N。式(4)和式(5)表示兩個變量之間的關(guān)系。式(6)表示車輛服務(wù)客戶i 后直接行駛到j(luò) 為其服務(wù)。式(7)表示每個客戶只能由1 輛車來服務(wù)且每個客戶都能得到服務(wù)。式(8)表示每輛車所運送的貨物重量不能超過車輛載重量的限制。式(9)表示保證每輛車的客戶總數(shù)小于等于總客戶數(shù)目。式(10)、式(11)和式(12)表示時間窗約束，T 為一足夠大的整數(shù)。

2 改進(jìn)的EMA

2.1 基本原理

EMA 是一種隨機全局優(yōu)化算法。它是模擬電磁場中的吸引和排斥機制，將每個解比作一個帶電粒子，然后按一定準(zhǔn)則使得搜索粒子朝最優(yōu)解移動。由于此思想與電磁理論中吸引與排斥機制有相似性，但也存在差異性，所以稱之為類電磁機制。該算法的收斂性已經(jīng)得到證明，當(dāng)?shù)螖?shù)趨于極限時，種群中至少有一個粒子以概率1 移動到全局最優(yōu)附近。

根據(jù)電磁理論中的吸引—排斥機制，EM 算法把每個搜索粒子想象成空間中的一個帶電粒子，每個粒子的電荷由待優(yōu)化的目標(biāo)函數(shù)的函數(shù)值決定。該電荷也決定了該粒子對其他粒子的吸引或排斥的強弱。目標(biāo)函數(shù)值越有，尋優(yōu)越強。通過計算其他粒子與當(dāng)前粒子的合力來確定每個粒子下一步的走向。其流程圖如圖2 所示。

2.2 算法流程

不失一般性，考慮極小值的優(yōu)化問題，如式(13)所示。f(x)為目標(biāo)函數(shù)，x 為決策向量。

Step1 初始化

初始化就是從已知可行域中隨機取一定數(shù)量的點，即從可行解空間中等概率地選取樣本點{y1，y2，…，ypop_size}作為初始解。然后對這些點進(jìn)行進(jìn)一步搜索，計算每個粒子的目標(biāo)函數(shù)值，并將目標(biāo)函數(shù)值最優(yōu)的粒子記為xbest。

初始解的選取方法為:1)采用旋轉(zhuǎn)賭輪機制從集合{0，1，…，ri}中選擇任意一個整數(shù)令=，i=1，2，…，l;2)采用旋轉(zhuǎn)賭輪機制從集合 {，+1，…，ri}中選擇任意一個整數(shù)，令=i=1，2，…，l。

Step2 局部搜索

局部搜索是針對單個粒子，用來改進(jìn)種群中已搜索到的解。它為種群的全局搜索提供了有效的局部信息，使得算法既有全局搜索能力，又有局部區(qū)域精細(xì)搜索能力。

Step3 計算合力

模擬電磁理論的疊加原理，EM 算法通過計算合力來決定粒子的下一步走向。粒子i 的電荷量qi決定了此粒子所受吸引力或排斥力的大小，電荷量qi的計算如式(14)所示。

圖2 改進(jìn)EMA 算法流程圖

由此可知，目標(biāo)函數(shù)值較優(yōu)的粒子擁有較大的電荷數(shù)，具有更強的吸引力，在比較兩粒子的目標(biāo)函數(shù)值后決定兩粒子間作用力的方向。作用在粒子i 上的合力Fi，如式(15)所示。每兩個粒子之間，目標(biāo)函數(shù)值較優(yōu)的粒子將吸引另一個粒子，目標(biāo)函數(shù)值較劣的粒子會排斥另外一個粒子。由于當(dāng)前最優(yōu)粒子xbest的目標(biāo)函數(shù)值最優(yōu)，所以它是絕對吸引子，吸引所有其他粒子。

Step4 移動粒子

由于傳統(tǒng)的EMA 中，粒子移動步長的確定沒有考慮粒子的優(yōu)劣及進(jìn)化代數(shù)的影響［8］，所以為了使粒子能更精確地靠近最優(yōu)解，設(shè)計了一個自適應(yīng)移動算子，如式(16)所示。t 表示粒子i 當(dāng)前的進(jìn)化代數(shù)。并將作用在粒子上的力做“歸一化”處理，λ∈(0，1)范圍內(nèi)的隨機數(shù)，則更新后的位置如式(17)所示，由該式可知，粒子在每次移動時，目標(biāo)函數(shù)值較差的粒子所帶電荷量較小，因而其移動步長要比目標(biāo)函數(shù)值較優(yōu)的粒子也就是所帶電荷量較大的粒子移動的步長要大，這樣能夠使得較差粒子能快速收斂到當(dāng)前最優(yōu)值附近。隨著迭代次數(shù)的增加，移動步長開始變小，在進(jìn)化后期，粒子只在當(dāng)前最優(yōu)粒子附近隨機擾動。RNG 為可行步長，uk為上邊界，lk為下邊界，如式(18)所示。

Step5 終止準(zhǔn)則

當(dāng)達(dá)到最大迭代次數(shù)時，算法結(jié)束;否則，轉(zhuǎn)Step2。

3 算例分析及結(jié)果

某供應(yīng)中心有1 個車場，車場坐標(biāo)為(30，30)，客戶信息如表2。每輛車載重8 噸，最大配送里程為150 km，關(guān)聯(lián)系數(shù)由Visual C++6.0 隨機生成。單位配送費用為1 元/t* km，已知車輛最早發(fā)車時間為7:00。

本文中的實驗是在Intel(R)CoreTMi3 CPU2.53 GHz、內(nèi)存2.0G 的win7 平臺上采用Microsoft Visual C++ 6.0 編程實現(xiàn)的。關(guān)聯(lián)系數(shù)由Visual C++隨機產(chǎn)生。遺傳算法中參數(shù)設(shè)置:初始化種群，種群規(guī)模N=20，最大迭代次數(shù)gen=500，交叉概率pc=0.8，變異概率pm=0.005。本文中用到的遺傳算法，其交叉算子指多點雜交，按Poisson 分布確定交叉點數(shù)，如式(19)所示。其中，x 為雜交點數(shù)，均值E(x)和方差D(x)為位串長度的函數(shù)。變異算子特指單點變異。

表1 客戶信息一覽表

表2 兩種算法運行結(jié)果對比

分別用GA、ANA 和改進(jìn)的EMA 運行20 次，得到該算法求解本算例的結(jié)果，如表2 所示，配送示意圖如圖3(a)、(b)和(c)所示。由表2 知，改進(jìn)的EMA 比其他兩種算法的尋優(yōu)能力更強，得到的效果更好，求得最優(yōu)配送網(wǎng)絡(luò)的總路程為321.5 米，成本為2 254.5 元。

圖3 不同算法的最優(yōu)配送路徑示意圖

4 結(jié)語

本文分別用遺傳算法、蟻群算法和改進(jìn)的類電磁機制算法對單車場單車型一個配送中心硬時間窗約束的時變關(guān)聯(lián)物流運輸調(diào)度模型求解，實驗結(jié)果證明，改進(jìn)的類電磁機制算法對解決此模型是有效可行的，而且在尋優(yōu)方面優(yōu)于另外兩種算法。粒子在每次移動過程中，目標(biāo)函數(shù)值較差的粒子移動的步長比目標(biāo)函數(shù)值較優(yōu)的粒子移動的步長要大，而且隨著進(jìn)化代數(shù)的增加，粒子的移動步長也隨著變小，而在后期，粒子只在最優(yōu)粒子附近隨機擾動，這樣可以更精細(xì)地尋優(yōu)。下一步工作可以擴展到用改進(jìn)EMA解決多擴展特征(如帶時間窗、道路容量約束、路障情形、多車場、多車型等)的TVIVRP，并可將該算法應(yīng)用到流水線生產(chǎn)物流運輸調(diào)度及時變的關(guān)聯(lián)物流運輸調(diào)度等問題中。

［1］湯雅連，蔡延光，趙學(xué)才.關(guān)聯(lián)物流運輸調(diào)度問題的改進(jìn)遺傳算法［J］. 微型機與應(yīng)用，2012，31(17):69－71.

［2］Baker Barrie M，Ayechew M A. A genetic algorithm for the vehicle routing problem［J］.Computers ＆ Operations Research，2003(30):787－800.

［3］Geonwook Jeon，Herman R Leep，Jae Young Shim.A vehicle routing problem solved by using a hybrid genetic algorithm［J］.Comerter＆Industrial Engineering，2007(37):680－692.

［4］王曉娟，高亮，陳亞洲.類電磁機制算法及其應(yīng)用［J］.計算機應(yīng)用研究，2006(6):67－70.

［5］韓麗霞，王宇平. 求解無約束優(yōu)化問題的類電磁機制算法［J］.電子學(xué)報，2009，37(3):664－668.

［6］Birbil S I，F(xiàn)ang S C. Electromagnetism-like Mechanism for Global Optimization［J］. Journal of Global Optimization，2003，25:263－282.

［7］Alkin Yurtkuran，Erdal Emel. A new Hybrid Electromagnetism-like Algorithm for capacitated vehicle routing problems［J］. Expert Systems with Applications，2010(37):3427－3433.

［8］姜建國，龍秀萍，田旻，等.一種基于佳點集的類電磁機制算法［J］.西安電子科技大學(xué)學(xué)報:自然科學(xué)版，2011，38(6):167－172.