摘  要： 針對(duì)多車場(chǎng)多車型的關(guān)聯(lián)運(yùn)輸調(diào)度問(wèn)題（Multi-depot and Multi-vehicle-type Related Vehicle Routing Problem），對(duì)傳統(tǒng)的類電磁機(jī)制算法進(jìn)行改進(jìn)，局部搜索可以提高算法在局部區(qū)域精細(xì)搜索的能力，并引入了移動(dòng)系數(shù)來(lái)提高算法的收斂速度。實(shí)驗(yàn)結(jié)果證明，改進(jìn)的算法有效地解決了此類問(wèn)題且優(yōu)于傳統(tǒng)類電磁機(jī)制算法。
關(guān)鍵詞： 多車場(chǎng)多車型；關(guān)聯(lián)運(yùn)輸調(diào)度問(wèn)題；類電磁機(jī)制算法；移動(dòng)系數(shù)

    類電磁機(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)輸路線，在滿足所有客戶需求的前提下，使配送成本最低。


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為決策向量。

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

    本文中的實(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所示。

    本文考慮關(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等模型中。
參考文獻(xiàn)
[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.