摘要：煤炭物流中生產(chǎn)物資的運輸問題屬于典型的車輛路徑問題（CVRP， Capacitated Vehicle Routing Problem）。文章采用改進的人工蜂群算法對該問題進行求解。首先按照相對中心位置（物資供應中心）的角度大小，對各個位置的礦區(qū)進行排序，然后產(chǎn)生合法初始解；通過算子操作產(chǎn)生鄰域解，采用蟻群信息素更新方式，在鄰域內(nèi)進行更為細致的迭代搜索。通過國際測試算例仿真，改進的人工蜂群算法可以找到近似最優(yōu)解，證明算法的有效性，對于解決實際運輸問題具有應用價值。
關(guān)鍵詞：煤炭物流；車輛路徑問題；混合人工蜂群算法
一、 引言
煤炭是我國生產(chǎn)和消費的主要能源，而煤炭物流是保證煤礦家具企業(yè)安全生產(chǎn)的前提條件，合理的煤炭物流不僅能夠保證煤礦家具企業(yè)的正常生產(chǎn)，而且可以為煤礦家具企業(yè)節(jié)約可觀的物流成本，因此煤炭物流中CVRP（Capacitated Vehicle Routing Problem）問題的優(yōu)化顯得十分重要。所謂煤炭物流中的CVRP問題，即是在煤礦家具企業(yè)生產(chǎn)物資供應中心（可能是一個或多個物資供應中心）向附近多個煤礦礦區(qū)運輸維持其生產(chǎn)所需要的各種物資，并且達到最低運輸成本的目標。
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ā)式智能算法的興起，不同學者針對此問題，分別采用遺傳算法、模擬退火算法、蟻群優(yōu)化算法、粒子群優(yōu)化算法等。
人工蜂群算法（Artificial Bee Colony algorithm，ABC）是近年興起的模擬蜜蜂覓食行為的優(yōu)化算法，Dervis Karaboga在其文章中對人工蜂群算法的正反饋、負反饋、波動性以及相互作用的特性進行了細致的闡述。在組合優(yōu)化、函數(shù)尋優(yōu)、以及神經(jīng)網(wǎng)絡權(quán)值優(yōu)化等問題中，人工蜂群算法均得到了很好應用。M.Dorigo等人于1992年提出蟻群算法（Ant Colony Optimization，ACO），蟻群算法群體搜索能力較強，易于與其他優(yōu)化算法結(jié)合；但存在搜索時間長容易陷入局部極值的缺點，而人工蜂群算法在種群內(nèi)個體分工協(xié)作上優(yōu)勢明顯，因此本文在此基礎上提出算法，首先采用人工蜂群算法進行初步搜索以期望獲得較好的鄰域解，然后采用蟻群優(yōu)化算法進行更細致搜索，最終得到近似最優(yōu)解的策略。
文章結(jié)構(gòu)安排如下：第一部分對煤炭物流中CVRP問題數(shù)學模型進行描述分析；第二部分對混合人工蜂群算法設計進行詳細闡述，包括編碼形式、初始解產(chǎn)生、鄰域計算方式以及局部更新策略；第三部分是仿真實驗與結(jié)果分析，最后是結(jié)論部分。
二、 CVRP問題數(shù)學模型
假設某煤礦家具企業(yè)有一個物資供應中心，該物資供應中心擁有m輛同質(zhì)的運輸車，每輛車的最大運輸能力為Q，共有n個需要服務的礦區(qū)，每個礦區(qū)Ai（i=1，2，…，n）對物資的需求為qi，dij代表第Ai個礦區(qū)與第Aj個礦區(qū)之間的距離或者運輸費用，對CVRP建立如下的數(shù)學模型，如公式（1）-（7）所示。
公式（1）為目標函數(shù)，公式（2）-（7）為約束條件。公式（2）表示礦區(qū)Ai和礦區(qū)Aj之間是否有連接，即為1表示二者由某一輛車共同服務，否則為0；公式（3）表示礦區(qū)Ai是否由車輛k服務，為1即表示由車輛k為其運輸物資，否則為0；公式（4）表示車輛k所服務礦區(qū)的物資需求量之和不超過車輛最大載重量；公式（5）表示路徑約束；公式（6）-（7）表示一個礦區(qū)僅由一輛運輸車服務，且從物資供應中心出發(fā)后仍回到物資供應中心。
三、 混合人工蜂群算法
1. 人工蜂群算法。Dervis Karaboga和Bahriye Basturk根據(jù)蜜蜂群體覓食行為，提出人工蜂群算法（Artificial bee colony algorithm，ABC）。人工蜂群算法以食物源、采蜜蜂（Employed Foragers）和待工蜂（Unemployed Foragers）作為基本要素；以向食物源招募（Recruit）蜜蜂和放棄（Abandon）某個食物源作為兩種基本的行為模式。
食物源與巢穴的距離、豐富度、集中度以及容易程度有關(guān)，代表問題解的優(yōu)劣好壞程度。采蜜峰（Employed Foragers）是當前正在進行“開采”工作的蜜蜂，它們可能與某一特定食物源有關(guān)，掌握某一食物源的信息，并且在一定程度上共享食物源信息。待工蜂（Unemployed Foragers）分為偵查蜂和圍觀蜂，偵查蜂負責搜索巢穴附近新的食物源，圍觀蜂在巢穴內(nèi)等待新的食物源信息，當采蜜峰共享的食物源信息后，圍觀蜂開始工作。
待工蜂在可能作為圍觀蜂在巢穴中等待信息共享，也可能作為偵查蜂到巢穴附近去尋找食物源；當作為偵查蜂找到新的食物源后，其角色變?yōu)椴擅鄯澹擅刍氐匠惭ú⑿遁d食物后，它可能因為食物源即將枯竭而放棄該食物源，也可能共享信息招募其它蜜蜂，或者沒有招募行為繼續(xù)獨自去“開采”該食物源。
2. 混合人工蜂群算法設計
（1）解的編碼形式。假設n個礦區(qū)分別采用阿拉伯數(shù)字表示，“1”作為標記，表示物資供應中心。解的表示形式如表1所示。解的涵義即表示用3輛車為7個礦區(qū)服務，第一輛車的行駛路線依次為1-3-7-2-1；第二輛車行駛路線依次為1-5-6-1；第三輛車行駛路線依次為1-4-8-1，且各個車輛運輸?shù)奈镔Y滿足其服務礦區(qū)的物資需求又不超過車的承載能力。
（2）初始解的產(chǎn)生。一般采用群智能優(yōu)化算法解決問題時，問題的初始解往往采用隨機生成的方式，但是由于CVRP問題約束條件的限制，采用隨機產(chǎn)生初始解的方式會產(chǎn)生大量非法解存在，導致無效迭代，造成時間浪費；因此采用構(gòu)造符合條件的初始解方式。假設礦區(qū)及物資供應中心的坐標分別記作（xi，yi）和（x0，y0）。按照公式（9）計算各個礦區(qū)相對于原點的坐標，然后根據(jù)公式（10）計算各個礦區(qū)的角度，然后根據(jù)角度大小排序。將排序后的各個礦區(qū)，按照承載能力Q，進行裝載直至不能再裝載物資為止。
關(guān)鍵詞：煤炭物流；車輛路徑問題；混合人工蜂群算法
一、 引言
煤炭是我國生產(chǎn)和消費的主要能源，而煤炭物流是保證煤礦家具企業(yè)安全生產(chǎn)的前提條件，合理的煤炭物流不僅能夠保證煤礦家具企業(yè)的正常生產(chǎn)，而且可以為煤礦家具企業(yè)節(jié)約可觀的物流成本，因此煤炭物流中CVRP（Capacitated Vehicle Routing Problem）問題的優(yōu)化顯得十分重要。所謂煤炭物流中的CVRP問題，即是在煤礦家具企業(yè)生產(chǎn)物資供應中心（可能是一個或多個物資供應中心）向附近多個煤礦礦區(qū)運輸維持其生產(chǎn)所需要的各種物資，并且達到最低運輸成本的目標。
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ā)式智能算法的興起，不同學者針對此問題，分別采用遺傳算法、模擬退火算法、蟻群優(yōu)化算法、粒子群優(yōu)化算法等。
人工蜂群算法（Artificial Bee Colony algorithm，ABC）是近年興起的模擬蜜蜂覓食行為的優(yōu)化算法，Dervis Karaboga在其文章中對人工蜂群算法的正反饋、負反饋、波動性以及相互作用的特性進行了細致的闡述。在組合優(yōu)化、函數(shù)尋優(yōu)、以及神經(jīng)網(wǎng)絡權(quán)值優(yōu)化等問題中，人工蜂群算法均得到了很好應用。M.Dorigo等人于1992年提出蟻群算法（Ant Colony Optimization，ACO），蟻群算法群體搜索能力較強，易于與其他優(yōu)化算法結(jié)合；但存在搜索時間長容易陷入局部極值的缺點，而人工蜂群算法在種群內(nèi)個體分工協(xié)作上優(yōu)勢明顯，因此本文在此基礎上提出算法，首先采用人工蜂群算法進行初步搜索以期望獲得較好的鄰域解，然后采用蟻群優(yōu)化算法進行更細致搜索，最終得到近似最優(yōu)解的策略。
文章結(jié)構(gòu)安排如下：第一部分對煤炭物流中CVRP問題數(shù)學模型進行描述分析；第二部分對混合人工蜂群算法設計進行詳細闡述，包括編碼形式、初始解產(chǎn)生、鄰域計算方式以及局部更新策略；第三部分是仿真實驗與結(jié)果分析，最后是結(jié)論部分。
二、 CVRP問題數(shù)學模型
假設某煤礦家具企業(yè)有一個物資供應中心，該物資供應中心擁有m輛同質(zhì)的運輸車，每輛車的最大運輸能力為Q，共有n個需要服務的礦區(qū)，每個礦區(qū)Ai（i=1，2，…，n）對物資的需求為qi，dij代表第Ai個礦區(qū)與第Aj個礦區(qū)之間的距離或者運輸費用，對CVRP建立如下的數(shù)學模型，如公式（1）-（7）所示。
公式（1）為目標函數(shù)，公式（2）-（7）為約束條件。公式（2）表示礦區(qū)Ai和礦區(qū)Aj之間是否有連接，即為1表示二者由某一輛車共同服務，否則為0；公式（3）表示礦區(qū)Ai是否由車輛k服務，為1即表示由車輛k為其運輸物資，否則為0；公式（4）表示車輛k所服務礦區(qū)的物資需求量之和不超過車輛最大載重量；公式（5）表示路徑約束；公式（6）-（7）表示一個礦區(qū)僅由一輛運輸車服務，且從物資供應中心出發(fā)后仍回到物資供應中心。
三、 混合人工蜂群算法
1. 人工蜂群算法。Dervis Karaboga和Bahriye Basturk根據(jù)蜜蜂群體覓食行為，提出人工蜂群算法（Artificial bee colony algorithm，ABC）。人工蜂群算法以食物源、采蜜蜂（Employed Foragers）和待工蜂（Unemployed Foragers）作為基本要素；以向食物源招募（Recruit）蜜蜂和放棄（Abandon）某個食物源作為兩種基本的行為模式。
食物源與巢穴的距離、豐富度、集中度以及容易程度有關(guān)，代表問題解的優(yōu)劣好壞程度。采蜜峰（Employed Foragers）是當前正在進行“開采”工作的蜜蜂，它們可能與某一特定食物源有關(guān)，掌握某一食物源的信息，并且在一定程度上共享食物源信息。待工蜂（Unemployed Foragers）分為偵查蜂和圍觀蜂，偵查蜂負責搜索巢穴附近新的食物源，圍觀蜂在巢穴內(nèi)等待新的食物源信息，當采蜜峰共享的食物源信息后，圍觀蜂開始工作。
待工蜂在可能作為圍觀蜂在巢穴中等待信息共享，也可能作為偵查蜂到巢穴附近去尋找食物源；當作為偵查蜂找到新的食物源后，其角色變?yōu)椴擅鄯澹擅刍氐匠惭ú⑿遁d食物后，它可能因為食物源即將枯竭而放棄該食物源，也可能共享信息招募其它蜜蜂，或者沒有招募行為繼續(xù)獨自去“開采”該食物源。
2. 混合人工蜂群算法設計
（1）解的編碼形式。假設n個礦區(qū)分別采用阿拉伯數(shù)字表示，“1”作為標記，表示物資供應中心。解的表示形式如表1所示。解的涵義即表示用3輛車為7個礦區(qū)服務，第一輛車的行駛路線依次為1-3-7-2-1；第二輛車行駛路線依次為1-5-6-1；第三輛車行駛路線依次為1-4-8-1，且各個車輛運輸?shù)奈镔Y滿足其服務礦區(qū)的物資需求又不超過車的承載能力。
（2）初始解的產(chǎn)生。一般采用群智能優(yōu)化算法解決問題時，問題的初始解往往采用隨機生成的方式，但是由于CVRP問題約束條件的限制，采用隨機產(chǎn)生初始解的方式會產(chǎn)生大量非法解存在，導致無效迭代，造成時間浪費；因此采用構(gòu)造符合條件的初始解方式。假設礦區(qū)及物資供應中心的坐標分別記作（xi，yi）和（x0，y0）。按照公式（9）計算各個礦區(qū)相對于原點的坐標，然后根據(jù)公式（10）計算各個礦區(qū)的角度，然后根據(jù)角度大小排序。將排序后的各個礦區(qū)，按照承載能力Q，進行裝載直至不能再裝載物資為止。