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

    類電磁機制EM（Electromagnetism-like Mechanism）算法是一種新型的基于種群的隨機全局優(yōu)化算法，在現(xiàn)實生活中具有很強的應用背景，可以應用到分子生物、調度安排、工程設計等領域。近幾年來已有不少學者做了相關研究[1-4]，并取得了很好的成果。但是對于關聯(lián)運輸調度問題RVRP（Related Vehicle Routing Problem）的探討在國內還不多見。但是前人研究的各種車輛路徑問題VRP（Vehicle Routing Problem）對本文的研究有很重要的借鑒意義。本文主要研究在載重約束下，對各車場中的多種不同類型車輛及配送路線進行合理安排，在滿足所有客戶要求的前提下，使配送成本最低。
1 問題描述及數學模型的建立
1.1 問題描述
    多車場多車型關聯(lián)運輸調度問題可以簡單描述為：假設給定車場信息以及客戶信息(位置和貨物需求量等)、貨物之間的關聯(lián)系數、不同類型車輛信息（載重約束、里程約束和關聯(lián)約束等），要求合理安排車輛和運輸路線，在滿足所有客戶需求的前提下，使配送成本最低。


2 改進的EMA
2.1 傳統(tǒng)EMA基本原理
    EMA是一種隨機全局優(yōu)化算法。它模擬電磁場中的吸引和排斥機制，將每個解比作一個帶電粒子，然后按一定的準則使得搜索粒子朝最優(yōu)解移動。由于此思想與電磁理論中吸引與排斥機制有相似性，但也存在差異性，所以稱之為類電磁機制。該算法的收斂性已經得到證明，當迭代次數趨于極限時，種群中至少有一個粒子以概率1移動到全局最優(yōu)附近。
    根據電磁理論中的吸引——排斥機制，EMA把每個搜索粒子想象成空間中的一個帶電粒子，每個粒子的電荷由待優(yōu)化的目標函數的函數值決定。該電荷也決定了該粒子對其他粒子的吸引或排斥的強弱。目標函數值越優(yōu)，尋優(yōu)越強。通過計算其他粒子與當前粒子的合力來確定每個粒子下一步的走向。
2.2 算法流程
    為不失一般性，考慮極小值的優(yōu)化問題，如式(12)所示。f(x)為目標函數，x為決策向量。

3 數值實驗分析
    某貨物供應商有3個車場，且每個車場有不同類型的車輛，客戶信息如表1所示，車場信息如表2所示。每輛車的最大配送里程為120 km。

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

    本文考慮關聯(lián)運輸調度問題的一種擴展特征——多車場多車型模型，并引入了移動系數，對傳統(tǒng)的移動粒子步長進行改進，相當于對粒子添加擾動，使移動步長更為明顯，從而增加了解空間的多樣性。實驗證明，改進的類電磁機制算法求解此類問題是有效可行的，而且具有更快的收斂速度，并得到了更優(yōu)解。接下來可以將EMA運用到MDVRP、VRPTW、AVRP等模型中。
參考文獻
[1] 韓麗霞，王宇平.求解無約束優(yōu)化問題的類電磁機制算法[J].電子學報，2009，37（3）：29-31.
[2] 王曉娟，高亮，陳亞洲.類電磁機制算法及其應用[J].計算機應用研究，2006，23（6）：67-70.
[3] 韓麗霞，王宇平，蘭紹江.基于模式搜索的類電磁算法求解約束優(yōu)化問題[J].系統(tǒng)工程與電子技術，2009，31（9）：2219-2222.
[4] 尚云，何雪妮，雷虹.求全局最優(yōu)的類電磁機制算法[J]. 計算機應用，2010，30（11）：2914-2916.
[5] 高亮，王曉娟，魏巍，等.一種改進的類電磁機制算法[J]. 華中科技大學學報（自然科學版），2006，34（11）：4-6.