混合人工蜂群算法求解煤炭物流中的CVRP問題

龐柒 阮平南 關(guān)志強

摘要：煤炭物流中生產(chǎn)物資的運輸問題屬于典型的車輛路徑問題（CVRP， Capacitated Vehicle Routing Problem）。文章采用改進的人工蜂群算法對該問題進行求解。首先按照相對中心位置（物資供應(yīng)中心）的角度大小，對各個位置的礦區(qū)進行排序，然后產(chǎn)生合法初始解；通過算子操作產(chǎn)生鄰域解，采用蟻群信息素更新方式，在鄰域內(nèi)進行更為細(xì)致的迭代搜索。通過國際測試算例仿真，改進的人工蜂群算法可以找到近似最優(yōu)解，證明算法的有效性，對于解決實際運輸問題具有應(yīng)用價值。

關(guān)鍵詞：煤炭物流；車輛路徑問題；混合人工蜂群算法

一、 引言

煤炭是我國生產(chǎn)和消費的主要能源，而煤炭物流是保證煤礦企業(yè)安全生產(chǎn)的前提條件，合理的煤炭物流不僅能夠保證煤礦企業(yè)的正常生產(chǎn)，而且可以為煤礦企業(yè)節(jié)約可觀的物流成本，因此煤炭物流中CVRP（Capacitated Vehicle Routing Problem）問題的優(yōu)化顯得十分重要。所謂煤炭物流中的CVRP問題，即是在煤礦企業(yè)生產(chǎn)物資供應(yīng)中心（可能是一個或多個物資供應(yīng)中心）向附近多個煤礦礦區(qū)運輸維持其生產(chǎn)所需要的各種物資，并且達到最低運輸成本的目標(biāo)。

VRP問題是典型的NP問題，作為組合問題，VRP問題可以看作是背包（Bin Packing Problem，BPP）和TSP二者的綜合問題。對于大型TSP問題求解已經(jīng)不容易，再融合BPP問題后，CVRP的求解就更加困難。在求解方法上，傳統(tǒng)的求解方法有G.Clarke和J.W.Wright提出的節(jié)約算法，B.E.Gillet和L.R.Miller提出的掃描算法。隨著研究進展以及各類啟發(fā)式智能算法的興起，不同學(xué)者針對此問題，分別采用遺傳算法、模擬退火算法、蟻群優(yōu)化算法、粒子群優(yōu)化算法等。

人工蜂群算法（Artificial Bee Colony algorithm，ABC）是近年興起的模擬蜜蜂覓食行為的優(yōu)化算法，Dervis Karaboga在其文章中對人工蜂群算法的正反饋、負(fù)反饋、波動性以及相互作用的特性進行了細(xì)致的闡述。在組合優(yōu)化、函數(shù)尋優(yōu)、以及神經(jīng)網(wǎng)絡(luò)權(quán)值優(yōu)化等問題中，人工蜂群算法均得到了很好應(yīng)用。M.Dorigo等人于1992年提出蟻群算法（Ant Colony Optimization，ACO），蟻群算法群體搜索能力較強，易于與其他優(yōu)化算法結(jié)合；但存在搜索時間長容易陷入局部極值的缺點，而人工蜂群算法在種群內(nèi)個體分工協(xié)作上優(yōu)勢明顯，因此本文在此基礎(chǔ)上提出算法，首先采用人工蜂群算法進行初步搜索以期望獲得較好的鄰域解，然后采用蟻群優(yōu)化算法進行更細(xì)致搜索，最終得到近似最優(yōu)解的策略。

文章結(jié)構(gòu)安排如下：第一部分對煤炭物流中CVRP問題數(shù)學(xué)模型進行描述分析；第二部分對混合人工蜂群算法設(shè)計進行詳細(xì)闡述，包括編碼形式、初始解產(chǎn)生、鄰域計算方式以及局部更新策略；第三部分是仿真實驗與結(jié)果分析，最后是結(jié)論部分。

二、 CVRP問題數(shù)學(xué)模型

假設(shè)某煤礦企業(yè)有一個物資供應(yīng)中心，該物資供應(yīng)中心擁有m輛同質(zhì)的運輸車，每輛車的最大運輸能力為Q，共有n個需要服務(wù)的礦區(qū)，每個礦區(qū)Ai（i=1，2，…，n）對物資的需求為qi，dij代表第Ai個礦區(qū)與第Aj個礦區(qū)之間的距離或者運輸費用，對CVRP建立如下的數(shù)學(xué)模型，如公式（1）-（7）所示。

公式（1）為目標(biāo)函數(shù)，公式（2）-（7）為約束條件。公式（2）表示礦區(qū)Ai和礦區(qū)Aj之間是否有連接，即為1表示二者由某一輛車共同服務(wù)，否則為0；公式（3）表示礦區(qū)Ai是否由車輛k服務(wù)，為1即表示由車輛k為其運輸物資，否則為0；公式（4）表示車輛k所服務(wù)礦區(qū)的物資需求量之和不超過車輛最大載重量；公式（5）表示路徑約束；公式（6）-（7）表示一個礦區(qū)僅由一輛運輸車服務(wù)，且從物資供應(yīng)中心出發(fā)后仍回到物資供應(yīng)中心。

三、 混合人工蜂群算法

1. 人工蜂群算法。Dervis Karaboga和Bahriye Basturk根據(jù)蜜蜂群體覓食行為，提出人工蜂群算法（Artificial bee colony algorithm，ABC）。人工蜂群算法以食物源、采蜜蜂（Employed Foragers）和待工蜂（Unemployed Foragers）作為基本要素；以向食物源招募（Recruit）蜜蜂和放棄（Abandon）某個食物源作為兩種基本的行為模式。

食物源與巢穴的距離、豐富度、集中度以及容易程度有關(guān)，代表問題解的優(yōu)劣好壞程度。采蜜峰（Employed Foragers）是當(dāng)前正在進行“開采”工作的蜜蜂，它們可能與某一特定食物源有關(guān)，掌握某一食物源的信息，并且在一定程度上共享食物源信息。待工蜂（Unemployed Foragers）分為偵查蜂和圍觀蜂，偵查蜂負(fù)責(zé)搜索巢穴附近新的食物源，圍觀蜂在巢穴內(nèi)等待新的食物源信息，當(dāng)采蜜峰共享的食物源信息后，圍觀蜂開始工作。

待工蜂在可能作為圍觀蜂在巢穴中等待信息共享，也可能作為偵查蜂到巢穴附近去尋找食物源；當(dāng)作為偵查蜂找到新的食物源后，其角色變?yōu)椴擅鄯澹擅刍氐匠惭ú⑿遁d食物后，它可能因為食物源即將枯竭而放棄該食物源，也可能共享信息招募其它蜜蜂，或者沒有招募行為繼續(xù)獨自去“開采”該食物源。

2. 混合人工蜂群算法設(shè)計

（1）解的編碼形式。假設(shè)n個礦區(qū)分別采用阿拉伯?dāng)?shù)字表示，“1”作為標(biāo)記，表示物資供應(yīng)中心。解的表示形式如表1所示。解的涵義即表示用3輛車為7個礦區(qū)服務(wù)，第一輛車的行駛路線依次為1-3-7-2-1；第二輛車行駛路線依次為1-5-6-1；第三輛車行駛路線依次為1-4-8-1，且各個車輛運輸?shù)奈镔Y滿足其服務(wù)礦區(qū)的物資需求又不超過車的承載能力。

（2）初始解的產(chǎn)生。一般采用群智能優(yōu)化算法解決問題時，問題的初始解往往采用隨機生成的方式，但是由于CVRP問題約束條件的限制，采用隨機產(chǎn)生初始解的方式會產(chǎn)生大量非法解存在，導(dǎo)致無效迭代，造成時間浪費；因此采用構(gòu)造符合條件的初始解方式。假設(shè)礦區(qū)及物資供應(yīng)中心的坐標(biāo)分別記作（xi，yi）和（x0，y0）。按照公式（9）計算各個礦區(qū)相對于原點的坐標(biāo)，然后根據(jù)公式（10）計算各個礦區(qū)的角度，然后根據(jù)角度大小排序。將排序后的各個礦區(qū)，按照承載能力Q，進行裝載直至不能再裝載物資為止。

（3）鄰域解的計算。在得到初始解之后，為保持解的多樣性，采用兩種方法產(chǎn)生鄰域解，（1）使用插入、交換和反向操作算子，由于是按照約束條件產(chǎn)生合法解，因此不同路線之間不再使用交換算子；（2）使用交互向量。交互向量可以使得初始解在不同路線間發(fā)生變化，即服務(wù)礦區(qū)會產(chǎn)生由不同車輛服務(wù)的變化效果。假設(shè)三個初始解a，b，c，交互向量v=[1，1，1]，交互向量的作用之后可能產(chǎn)生的解為a*，b*，c*。交互向量根據(jù)礦區(qū)需求量和位置角度設(shè)計產(chǎn)生。

四、 實驗仿真與分析

本文選取國際標(biāo)準(zhǔn)測試數(shù)據(jù)進行實驗，數(shù)據(jù)來源于網(wǎng)站。算法首先根據(jù)問題規(guī)模設(shè)置種群規(guī)模及參數(shù)，然后根據(jù)生產(chǎn)滿足約束條件的初始解，根據(jù)交叉向量信息進行采蜜峰的搜索，然后根據(jù)共享信息進入了圍觀蜂搜索階段，偵查蜂對搜索到的解進行評價后以一定概率放棄并生成新的解，直至滿足條件為止。混合人工蜂群算法迭代的流程圖如圖（1）所示。

表2為采用國際標(biāo)準(zhǔn)測試案例中E集合中不同規(guī)模案例的測試結(jié)果。算法中蜂群最小規(guī)模設(shè)為20，最大規(guī)模設(shè)為問題規(guī)模二倍，迭代步數(shù)設(shè)為150步，算法迭代次數(shù)為10次。采用局部搜索策略時，蟻群搜索機制的參數(shù)分別設(shè)為ρ=0.1。從表2中可以看出對于，不同規(guī)模的的問題，本文提出的算法均得到近似最優(yōu)解，且車輛平均滿載率較高，除E_n23_3外，各個案例車輛滿載率均在90%左右。表3為對應(yīng)各個算例的實際路線安排表。圖2為大規(guī)模測試用例E-n101-k8各個車輛運行路線圖，圖3為該算例下算法迭代后收斂效果圖，從圖中可以看出，運行距離從930逐漸下降到850，在80步之后逐漸穩(wěn)定。

五、 結(jié)論

通過國際測試用例仿真，驗證了混合人工蜂群算法在求解煤炭物流中CVRP的有效性，可以快速計算出近似最優(yōu)解，證明了算法的實際應(yīng)用價值。同時，通過算法設(shè)計以及仿真過程可以得出以下結(jié)論：

1. 在對煤炭物流中CVRP問題研究基礎(chǔ)上，采用改進的人工蜂群算法對該類問題進行求解，并取得近似最優(yōu)解的效果，可將算法用于實際煤炭物流路線優(yōu)化。

2. 根據(jù)問題約束特點以及算法自身特點，采用了以“1”作為標(biāo)記的編碼方式，該編碼方式簡單易懂，迭代方便。

3. 改進人工蜂群算法中，初始解產(chǎn)生按照極角方式，避免非法解參與運算；鄰域解采用交叉向量作為“指引”，避免大范圍的無效搜索；局部搜索采用蟻群搜索機制，增強局部搜索能力。

參考文獻：

1. 汪文生，曾志猛，王娟.多級煤炭物流網(wǎng)絡(luò)優(yōu)化選擇模型的構(gòu)建與應(yīng)用.煤炭學(xué)報，2011，26（6）：1060-1064.

2. WANG Wen-sheng， ZENG Zhi-meng， WANG Juan. Construction and application of multi-level coal logistics network optimization model. JOURNAL OF CHINA COAL SOCIETY，2011，26（6）：1060-1064.

3. T.K.Ralphsy， L.Kopmanz， W.R. Pulleyblankx， L.E. Trotter， Jr. On the Capacitated Vehicle Routing Problem. Mathematical Programming，2003，94（2）：343-359.

4. G.Clarke， J W Wright.Scheduling of Vehic- les from a Central Depot to a Number of Delivery Points. Operations Research，1964，12（4）：568-581.

5. 姜大立，楊西龍，杜文，周賢偉.車輛路徑問題的遺傳算法研究. 系統(tǒng)工程理論與實踐，1996，（6）：40-44.

6. 張麗萍， 柴躍廷.車輛路徑問題的改進遺傳算法.系統(tǒng)工程理論與實踐，2002，（8）：79-84.

7. 謝秉磊，安實，郭耀煌.隨機車輛路徑問題的多回路優(yōu)化策略.系統(tǒng)工程理論與實踐，2007，（2）：167-171.

8. 袁健，劉晉，盧厚清.隨機需求情形VRP 的退火網(wǎng)絡(luò)解法.系統(tǒng)工程理論與實踐，2002，（3）：109-113.

9. 張濤，田文馨，張玥杰，劉士新.帶車輛行程約束的VRPSPD問題的改進蟻群算法.系統(tǒng)工程理論與實踐，2008，（1）：132-140.

10. 劉志碩， 申金升， 關(guān)偉.車輛路徑問題的混合蟻群算法設(shè)計與實現(xiàn). 管理科學(xué)學(xué)報，2007，10（3）：15-21.

11. 李琳，劉士新，唐加福.改進的蟻群算法求解帶時間窗的車輛路徑問題.控制與決策，2010，25（9）：1379-1383.

12. 李寧，鄒彤，孫德寶.車輛路徑問題的粒子群算法研究.系統(tǒng)工程學(xué)報，2004，19（6）：596-600.

13. 王素欣，高利，崔曉光等. 多需求點車輛調(diào)度模型及其群體智能混合求解.自動化學(xué)報，2008，34（1）：102-104.

作者簡介：阮平南，北京工業(yè)大學(xué)經(jīng)管學(xué)院教授、博士生導(dǎo)師；龐柒，北京工業(yè)大學(xué)經(jīng)管學(xué)院管理科學(xué)與工程專業(yè)博士生；關(guān)志強，北京工業(yè)大學(xué)電控學(xué)院碩士生。

收稿日期：2013-11-20。