段熙鵬，蔡延光，湯雅連

（廣東工業(yè)大學(xué) 自動(dòng)化學(xué)院，廣東 廣州510006）

類電磁機(jī)制 EM（Electromagnetism-like Mechanism）算法是一種新型的基于種群的隨機(jī)全局優(yōu)化算法，在現(xiàn)實(shí)生活中具有很強(qiáng)的應(yīng)用背景，可以應(yīng)用到分子生物、調(diào)度安排、工程設(shè)計(jì)等領(lǐng)域。近幾年來(lái)已有不少學(xué)者做了相關(guān)研究[1-4]，并取得了很好的成果。但是對(duì)于關(guān)聯(lián)運(yùn)輸調(diào)度問(wèn)題 RVRP（Related Vehicle Routing Problem）的探討在國(guó)內(nèi)還不多見(jiàn)。但是前人研究的各種車輛路徑問(wèn)題VRP（Vehicle Routing Problem）對(duì)本文的研究有很重要的借鑒意義。本文主要研究在載重約束下，對(duì)各車場(chǎng)中的多種不同類型車輛及配送路線進(jìn)行合理安排，在滿足所有客戶要求的前提下，使配送成本最低。

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

1.1 問(wèn)題描述

多車場(chǎng)多車型關(guān)聯(lián)運(yùn)輸調(diào)度問(wèn)題可以簡(jiǎn)單描述為：假設(shè)給定車場(chǎng)信息以及客戶信息(位置和貨物需求量等)、貨物之間的關(guān)聯(lián)系數(shù)、不同類型車輛信息（載重約束、里程約束和關(guān)聯(lián)約束等），要求合理安排車輛和運(yùn)輸路線，在滿足所有客戶需求的前提下，使配送成本最低。

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

假設(shè)客戶編號(hào)為 1，2，…，l，車場(chǎng)編號(hào)為 l+1，l+2，…，l+N。定義變量如下：

2 改進(jìn)的EMA

2.1 傳統(tǒng)EMA基本原理

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

根據(jù)電磁理論中的吸引——排斥機(jī)制，EMA把每個(gè)搜索粒子想象成空間中的一個(gè)帶電粒子，每個(gè)粒子的電荷由待優(yōu)化的目標(biāo)函數(shù)的函數(shù)值決定。該電荷也決定了該粒子對(duì)其他粒子的吸引或排斥的強(qiáng)弱。目標(biāo)函數(shù)值越優(yōu)，尋優(yōu)越強(qiáng)。通過(guò)計(jì)算其他粒子與當(dāng)前粒子的合力來(lái)確定每個(gè)粒子下一步的走向。

2.2 算法流程

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

算法流程如下所述：

(1)初始化

初始化就是從已知可行域中隨機(jī)取一定數(shù)量的點(diǎn)，然后對(duì)這些點(diǎn)進(jìn)行進(jìn)一步搜索，計(jì)算每個(gè)粒子的目標(biāo)函數(shù)值，并將目標(biāo)函數(shù)值最優(yōu)的粒子記為xbest。

(2)局部搜索

局部搜索針對(duì)單個(gè)粒子，用來(lái)改進(jìn)種群中已搜索到的解。它為種群的全局搜索提供了有效的局部信息，使得算法既有全局搜索能力，又有局部區(qū)域精細(xì)搜索能力。當(dāng)只對(duì)當(dāng)前最優(yōu)粒子進(jìn)行局部搜索時(shí)，能較好地維持速度和精度的平衡。

(3)計(jì)算合力

模擬電磁理論的疊加原理，EMA通過(guò)計(jì)算合力來(lái)決定粒子的下一步走向。粒子i的電荷量qi決定了此粒子所受吸引力或排斥力的大小，電荷量qi的計(jì)算如式（13）所示，由此可知，目標(biāo)函數(shù)值較優(yōu)的粒子擁有較大的電荷數(shù)，具有更強(qiáng)的吸引力。作用在粒子i上的合力Fi的計(jì)算如式（14）所示。每?jī)蓚€(gè)粒子之間，目標(biāo)函數(shù)值較優(yōu)的粒子將吸引另一個(gè)粒子，目標(biāo)函數(shù)值較劣的粒子會(huì)排斥另外一個(gè)粒子。由于當(dāng)前最優(yōu)粒子xbest的目標(biāo)函數(shù)值最優(yōu)，所以它是絕對(duì)吸引子，吸引所有其他粒子。

(4)移動(dòng)系數(shù)[5]

計(jì)算移動(dòng)步長(zhǎng)是比較關(guān)鍵的一步，當(dāng)步長(zhǎng)較小時(shí)，對(duì)粒子的擾動(dòng)較小，因而效果不明顯。針對(duì)此情況，可以引入移動(dòng)系數(shù) k1和 k2，移動(dòng)公式如式(15)所示，λ 在[0，1]上均勻分布，r表示第r維的分量，這樣每個(gè)粒子都可以得到不同程度的更新，且擾動(dòng)程度較大。k1和k2能明顯地影響算法的收斂速度和解，根據(jù)經(jīng)驗(yàn)，本文取k1=0.9，k2=1.0。

(5)終止準(zhǔn)則

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

3 數(shù)值實(shí)驗(yàn)分析

某貨物供應(yīng)商有3個(gè)車場(chǎng)，且每個(gè)車場(chǎng)有不同類型的車輛，客戶信息如表1所示，車場(chǎng)信息如表2所示。每輛車的最大配送里程為120 km。

表1 客戶信息表

表2 車場(chǎng)位置信息表

本文中的實(shí)驗(yàn)是在 Intel?CoreTMi3 CPU2.53 GHz、內(nèi)存2.0 GB的PC機(jī)上采用Microsoft Visual C++6.0編程實(shí)現(xiàn)，關(guān)聯(lián)系數(shù)由Microsoft Visual C++6.0隨機(jī)產(chǎn)生。運(yùn)行程序30次，某一代迭代例證如表3所示。得到該算法求解本算例的最優(yōu)結(jié)果如表4所示，配送示意圖如圖1所示。

表3 迭代例證

表4 最優(yōu)配送方案

本文考慮關(guān)聯(lián)運(yùn)輸調(diào)度問(wèn)題的一種擴(kuò)展特征——多車場(chǎng)多車型模型，并引入了移動(dòng)系數(shù)，對(duì)傳統(tǒng)的移動(dòng)粒子步長(zhǎng)進(jìn)行改進(jìn)，相當(dāng)于對(duì)粒子添加擾動(dòng)，使移動(dòng)步長(zhǎng)更為明顯，從而增加了解空間的多樣性。實(shí)驗(yàn)證明，改進(jìn)的類電磁機(jī)制算法求解此類問(wèn)題是有效可行的，而且具有更快的收斂速度，并得到了更優(yōu)解。接下來(lái)可以將EMA運(yùn)用到MDVRP、VRPTW、AVRP等模型中。

[1]韓麗霞，王宇平.求解無(wú)約束優(yōu)化問(wèn)題的類電磁機(jī)制算法[J].電子學(xué)報(bào)，2009，37（3）：29-31.

[2]王曉娟，高亮，陳亞洲.類電磁機(jī)制算法及其應(yīng)用[J].計(jì)算機(jī)應(yīng)用研究，2006，23（6）：67-70.

[3]韓麗霞，王宇平，蘭紹江.基于模式搜索的類電磁算法求解約束優(yōu)化問(wèn)題[J].系統(tǒng)工程與電子技術(shù)，2009，31（9）：2219-2222.

[4]尚云，何雪妮，雷虹.求全局最優(yōu)的類電磁機(jī)制算法[J].計(jì)算機(jī)應(yīng)用，2010，30（11）：2914-2916.

[5]高亮，王曉娟，魏巍，等.一種改進(jìn)的類電磁機(jī)制算法[J].華中科技大學(xué)學(xué)報(bào)（自然科學(xué)版），2006，34（11）：4-6.