摘要:煤炭物流中生產(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,進行裝載直至不能再裝載物資為止。