改進類電磁機制算法的時變關聯(lián)運輸調度問題

湯雅連 蔡延光 郭棟 郭帥

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

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

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

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

1.1 問題描述

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

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

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

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

4)硬時間窗約束;

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

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

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

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

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

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

圖1 車輛行駛速度

1.2 數(shù)學模型

定義變量如下:

建立數(shù)學模型

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

2 改進的EMA

2.1 基本原理

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

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

2.2 算法流程

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

Step1 初始化

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

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

Step2 局部搜索

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

Step3 計算合力

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

圖2 改進EMA 算法流程圖

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

Step4 移動粒子

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

Step5 終止準則

當達到最大迭代次數(shù)時，算法結束;否則，轉Step2。

3 算例分析及結果

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

本文中的實驗是在Intel(R)CoreTMi3 CPU2.53 GHz、內存2.0G 的win7 平臺上采用Microsoft Visual C++ 6.0 編程實現(xiàn)的。關聯(lián)系數(shù)由Visual C++隨機產(chǎn)生。遺傳算法中參數(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 兩種算法運行結果對比

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

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

4 結語

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

［1］湯雅連，蔡延光，趙學才.關聯(lián)物流運輸調度問題的改進遺傳算法［J］. 微型機與應用，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］王曉娟，高亮，陳亞洲.類電磁機制算法及其應用［J］.計算機應用研究，2006(6):67－70.

［5］韓麗霞，王宇平. 求解無約束優(yōu)化問題的類電磁機制算法［J］.電子學報，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］.西安電子科技大學學報:自然科學版，2011，38(6):167－172.