王華 蔡延光 湯雅連 朱君

(廣東工業(yè)大學(xué) 自動(dòng)化學(xué)院，廣州510006)

隨著互聯(lián)網(wǎng)技術(shù)的快速發(fā)展，電子商務(wù)的興起，網(wǎng)購已經(jīng)成為一種潮流，各企業(yè)也把它視為一種新的銷售平臺，不論是嫁接淘寶商城，還是自建網(wǎng)上商城，從店商到電商是時(shí)下各企業(yè)發(fā)展的必然趨勢，家電行業(yè)同樣如此。未來隨著網(wǎng)購形式的逐漸成熟，整個(gè)家電行業(yè)的網(wǎng)購市場是令人期待的。消費(fèi)者選擇網(wǎng)購的最大因素是價(jià)格便宜，隨著消費(fèi)者的成熟，他們開始更多的關(guān)注產(chǎn)品的質(zhì)量、電商品牌、物流等服務(wù)體驗(yàn)。所以電商企業(yè)提高物流配送的效率也變得越發(fā)重要。隨著網(wǎng)購客戶群體的迅速發(fā)展壯大，買家的服務(wù)要求日趨細(xì)致和多樣化，快遞公司將為客戶提供靈活周到的快遞服務(wù)?？爝f公司在送貨時(shí)，不僅要考慮運(yùn)輸費(fèi)用，還要考慮商品的體積、重量等參數(shù)，這樣就形成了家電配送優(yōu)化問題，其本質(zhì)也是車輛路徑問題(Vehicle Routing Problem，VRP)。VRP［1］自1959年Dantzig 和Ramser 首先提出以來就引起了人們的高度重視。VRP 的實(shí)用性強(qiáng)，應(yīng)用廣泛。

王連峰等人［2］基于模糊可信性理論建立了多目標(biāo)模糊期望值模型，提出了一種改進(jìn)的約束多目標(biāo)粒子群優(yōu)化算法求解戰(zhàn)場物資配送中帶硬時(shí)間窗車輛路徑問題的多重模糊性，實(shí)驗(yàn)結(jié)果表明了模糊的合理性和算法的有效性;陳迎欣［3］應(yīng)用改進(jìn)蟻群算法求解車輛路徑優(yōu)化問題，驗(yàn)證了改進(jìn)蟻群算法的有效性和可行性;譚云恩等人［4］應(yīng)用蟻群算法求解軍事車輛配送的路徑優(yōu)化問題，證明了算法的有效和實(shí)用;施彥等人［5］應(yīng)用集成協(xié)同PSO 算法求解車輛路徑問題，理論分析和實(shí)驗(yàn)表明所采用的編碼方式結(jié)合改進(jìn)的集成協(xié)同PSO 算法可以有效解決車輛路徑問題;何小年等人［6］應(yīng)用禁忌搜索算法求解物流配送車輛路徑模型，實(shí)驗(yàn)結(jié)果表明該算法比遺傳算法、模擬退火算法、蟻群算法及其混合算法具有明顯的優(yōu)勢，能很好地適應(yīng)現(xiàn)代物流對配送環(huán)節(jié)快速、低成本的要求。目前，帶車輛容積約束的家電配送問題研究不多見，而該問題模型在現(xiàn)實(shí)生活中普遍存在，所以具有實(shí)際研究意義，并采用混沌人工魚群算法求解家電配送的優(yōu)化問題。

1 家電配送問題描述及數(shù)學(xué)模型的建立

1.1 問題描述

家電配送問題是指對于一系列需求點(diǎn)，給定快遞公司位置、貨車數(shù)量、客戶數(shù)量、客戶位置、客戶需求量，配送時(shí)需考慮貨車的載重和容積，組織適當(dāng)?shù)倪\(yùn)輸路線，達(dá)到總成本最少的目的。

1.2 建立數(shù)學(xué)模型

1.2.1 定義參數(shù)

客戶數(shù):i = 1，2，…，l;客戶需求產(chǎn)品重量/kg:gi;客戶需求產(chǎn)品體積/L:vi;客戶i 與j 之間的距離/km:dij;貨場額定載重/kg:qc，且gi＜qc;貨車額定容積/L:V，且vi＜V;車輛數(shù):k = 1，2，…，K;車輛k 將從點(diǎn)i 送到點(diǎn)j 的單位運(yùn)價(jià)/(km·h－1):cijk; 第k 輛車服務(wù)的客戶個(gè)數(shù):nk;啟用車輛的固定成本/元:ck;貨車速度/(km·h－1):v ;快遞員工資/(元·h－1):w。

1.2.2 定義間接參數(shù)

1)一輛貨車的行駛里程sk/km:sk=

2)所有貨車完成任務(wù)行駛的總里程S總/km:S總=

3)一輛貨車配送商品花費(fèi)的時(shí)間T/h:Tk=;

5)所有快遞員的工作時(shí)間和等于所有貨車所花費(fèi)的時(shí)間T/h:Tc= T;

6)快遞員工資和Sc/元:Sc= Tcw。

1.2.3 定義變量

1.2.4 建立數(shù)學(xué)模型

目標(biāo)函數(shù):

約束條件:

目標(biāo)函數(shù)式(3)表示總運(yùn)輸成本最低，由運(yùn)輸成本、車輛啟用成本和快遞員工資三部分構(gòu)成;式(4)和式(5)為決策變量;式(6)表示車輛完成任務(wù)后，回到原車場;式(7)表示當(dāng)某輛車配送客戶的個(gè)數(shù)大于等于1 時(shí)，則參與了配送服務(wù)，否則，沒有參與配送;式(8)表示所有客戶都被服務(wù)到;式(9)表示每次配送都不能超過車輛的載重;式(10)表示貨車每天配送商品的體積不超過貨車容積;式(11)表示保證每輛車服務(wù)的客戶總數(shù)小于等于總客戶數(shù)。

2 混沌人工魚群算法

2.1 求解思路

人工魚群算法［7］是模擬魚群的行為進(jìn)行隨機(jī)的搜索，主要利用人工魚的覓食、聚群、追尾等行為，利用局部最優(yōu)信息逐步達(dá)到全局尋優(yōu)的目的。為了提高人工魚群算法的全局搜索能力，克服基本人工魚群算法精度低、后期收斂慢、復(fù)雜度較高等特點(diǎn)，本文主要是采用基于混沌搜索和反饋策略的混沌人工魚群算法解決服飾物流運(yùn)輸調(diào)度問題。

2.2 混沌搜索

混沌搜索［1］具有隨機(jī)性、遍歷性和確定性，由混沌搜索產(chǎn)生初始種群克服了生成大量非可行解的缺陷，加速染色體向最優(yōu)解收斂。文中選用Logistic 映射［8－9］，如式(12)所示。式中，i 表示混沌變量的序號，i = 1，2，…，r;u 表示種群序號，u = 0，1，…，n =0;βi表示混沌變量，0 ≤βi≤1 ;μi表示吸引子。當(dāng)μi= 4 時(shí)，Logistic 映射完全處于混沌的狀態(tài)，此時(shí)的混沌變量βi具有很好的遍歷性。假設(shè)迭代次數(shù)為300，初值為0.6，得到Logistic 映射的概率分布圖，如圖1 所示。

圖1 Logistic 映射的概率分布圖

2.3 混沌人工魚群算法求解步驟

魚群中，每個(gè)個(gè)體的位置向量X =(x1，x2，…，xn)，X 為尋優(yōu)決策變量;人工魚個(gè)體i 與個(gè)體j 間的距離表示為di，j=;人工魚當(dāng)前所在位置的食物濃度為Y = f(X)，即為目標(biāo)函數(shù)值;Visual 表示人工魚的感知距離;step 表示人工魚的感知距離;δ 為擁擠度因子;α 為衰減因子，Pf為反饋概率;Try_ num 表示人工魚每次移動(dòng)的最大試探次數(shù)。在尋優(yōu)過程中，X 中元素的順序表示配送的訪問順序，也就是一個(gè)潛在的解，其適應(yīng)值可以衡量解X 的優(yōu)劣程度。由于混沌搜索具有隨機(jī)性、遍歷性和確定性，所以混沌搜索要比隨機(jī)搜索好。

1)反饋策略。

每條人工魚執(zhí)行完移動(dòng)操作后會檢驗(yàn)自身狀態(tài)與公告牌的狀態(tài)，若自身狀態(tài)優(yōu)于公告牌狀態(tài)，則用自身狀態(tài)代替原公告牌狀態(tài)，這樣公告牌就可以記錄下歷史最優(yōu)狀態(tài)?；谶@一思路，為人工魚定義一個(gè)新行為——反饋行為，即人工魚向公告牌記錄的最優(yōu)狀態(tài)移動(dòng)，人工魚以一定的概率執(zhí)行該行為。

對人工魚群算法進(jìn)行改進(jìn)，設(shè)置反饋概率Pf，人工魚以概率Pf執(zhí)行隨機(jī)行為，以概率1－Pf執(zhí)行反饋行為。優(yōu)化過程開始時(shí)賦予Pf一個(gè)較大的數(shù)，隨著優(yōu)化過程的進(jìn)行Pf按式(13)逐漸減小，α 為反饋概率的衰減因子。

2)覓食行為。

設(shè)人工魚i 當(dāng)前狀態(tài)為Xi，在其感知范圍內(nèi)隨機(jī)選擇一個(gè)狀態(tài)Xj，如式(14)。

其中，rand()是一個(gè)介于0 和1 之間的隨機(jī)數(shù)，若Yi＞Yj，則向該位置和全局最優(yōu)位置Xbest_af的向量和方向前進(jìn)一步;反之，再重新隨機(jī)選擇狀態(tài)Xj，判斷是否滿足前進(jìn)條件，若滿足，則按式(15)前進(jìn)一步;若不滿足則繼續(xù)試探，反復(fù)嘗試Try_ num 次后，如果仍不滿足前進(jìn)條件，則按式(16)隨機(jī)移動(dòng)一步。

3)聚群行為。

人工魚探索當(dāng)前鄰域內(nèi)(即dij＜Visual)伙伴數(shù)目nf及中心位置Xc。如果Yc·nf＜δ·Yi，表明伙伴中心有較多食物且不太擁擠，那么按式(17)朝伙伴的中心位置和全局最優(yōu)位置Xbest_af的向量和方向前進(jìn)一步，否則執(zhí)行覓食行為。

4)追尾行為。

人工魚探索當(dāng)前鄰域內(nèi)(即dij＜Visual)的伙伴中Yj為最小的伙伴Xj。如果Yj·nf＜δ·Yi，表明伙伴Xj具有較高的食物濃度并且其周圍不太擁擠，那么式(18)朝Xj的方向和全局最優(yōu)位置Xbest_af的向量和方向前進(jìn)一步，否則執(zhí)行覓食行為。

5)隨機(jī)行為。

隨機(jī)行為是為了在更大范圍內(nèi)尋覓食物或同伴，隨機(jī)選擇一個(gè)狀態(tài)，然后向該方向移動(dòng)。

混沌人工魚群算法的步驟如下:

Step1:進(jìn)行初始化設(shè)置:人工魚的感知距離Visual、人工魚的感知距離Step、擁擠度因子δ、衰減因子α、反饋概率Pf、人工魚每次移動(dòng)的最大試探次數(shù)Try_ num 和最大迭代次數(shù)MAXGEN;

Step2:計(jì)算每條人工魚的適應(yīng)度值，將最優(yōu)的人工魚狀態(tài)記入公告牌;

Step3:對每條人工魚進(jìn)行評價(jià)，對其要執(zhí)行的行為進(jìn)行選擇，包括覓食行為、群聚行為、追尾行為，若執(zhí)行后的狀態(tài)優(yōu)于當(dāng)前狀態(tài)，則向更優(yōu)狀態(tài)的方向前移一步，然后轉(zhuǎn)至Step5;

Step4:隨機(jī)產(chǎn)生一個(gè)數(shù)，若rand()＜Pf，則執(zhí)行隨機(jī)行為，否則執(zhí)行反饋行為;

Step5:最優(yōu)人工魚執(zhí)行混沌搜索;

Step6:更新公告牌和反饋概率;

Step7:若滿足循環(huán)結(jié)束的條件則輸出結(jié)果，否則轉(zhuǎn)至步驟(3)。

3 仿真實(shí)驗(yàn)

某區(qū)域內(nèi)訂單中的貨物信息如表1 所示。模型參數(shù)設(shè)定如表2 所示。

混沌人工魚群算法參數(shù)設(shè)定:人工魚群的個(gè)體數(shù)N = 20 ，每條人工魚的初始位置隨機(jī)產(chǎn)生，人工魚的視野Visual = 2 ，人工魚的步長step = 40 ，最大迭代次數(shù)max gen = 500 ，嘗試次數(shù)Try_ num =20 ，擁擠度因子δ = 0.33 ，反饋概率Pf= 0.88 ，反饋概率的衰減因子α = 0.95 和執(zhí)行吞食行為的閾值T_ value = 0.1 。標(biāo)準(zhǔn)遺傳算法參數(shù)設(shè)定:初始化種群N = 20 ，最大迭代次數(shù)max gen = 500 ，交叉概率pc= 0.9 ，變異概率pm= 0.02 ，采用路徑編碼。

本文中的實(shí)驗(yàn)是在Intel(R)CoreTMi3 CPU 2.53GHz、內(nèi)存為2.0G、安裝系統(tǒng)為win7 的PC 機(jī)上采用Matlab R2010b 編程實(shí)現(xiàn)。對每個(gè)問題模型都運(yùn)行算法20 次。

表1 訂單中的貨物信息表

表2 模型參數(shù)設(shè)定

結(jié)果分析:GA 和CAFA 求解家電配送問題模型的結(jié)果如表3 所示，GA 求解得到的最優(yōu)解為1 062.202元，CAFA 求解得到的最優(yōu)結(jié)果為986.401 元，所以CAFA 略優(yōu)于GA。其最優(yōu)路線網(wǎng)絡(luò)圖分別為圖2 和圖3。兩種算法求解VRPVC 的一次優(yōu)化過程如圖4 所示，CAFA 在第8 代收斂，GA 在第17代收斂，可見CAFA 比GA 收斂快。

表3 兩種算法求解VRPVC 的最優(yōu)配送路線

圖2 家電配送最優(yōu)路線(GA－VRPVC)

圖3 家電配送最優(yōu)路線(CAFA－VRPVC)

圖4 兩種算法求解VRPVC 的一次優(yōu)化過程

4 結(jié)語

對家電配送問題進(jìn)行分析，構(gòu)建了帶容積約束的VRP 數(shù)學(xué)模型?；煦缢阉鞅灰肴斯~群算法來提高算法的全局收斂性，反饋策略用來指導(dǎo)人工魚的移動(dòng)，這樣就形成了混沌人工魚群算法，應(yīng)用該算法及標(biāo)準(zhǔn)的遺傳算法對所建立的VRPVC 模型求解，證明了VRPVC 模型和CAFA 求解此類模型的有效性。

［1］湯雅連，蔡延光，郭帥，等.單車場關(guān)聯(lián)物流運(yùn)輸調(diào)度問題的混沌遺傳算法［J］.廣東工業(yè)大學(xué)學(xué)報(bào)，2013，30:53－57.

［2］王連鋒，宋建社，王正元，等.帶硬時(shí)間窗的戰(zhàn)場物資配送車輛路徑優(yōu)化［J］.系統(tǒng)工程與電子技術(shù)，2013，35(4):770－776.

［3］陳迎欣.基于改進(jìn)蟻群算法的車輛路徑優(yōu)化問題研究［J］. 計(jì)算機(jī)應(yīng)用研究，2012，29(6):2031－2034.

［4］譚云恩，張亮，楊霞，等.基于ACA 的軍事物流車輛配送路徑優(yōu)化研究［J］.物流科技，2013，36(8):96－98.

［5］施彥，韓力群，陳秀新.基于集成協(xié)同PSO 算法的車輛路徑優(yōu)化仿真［J］.計(jì)算機(jī)仿真，2012，29(6):339－342.

［6］何小年，謝小良.帶裝載量約束的物流配送車輛路徑優(yōu)化研究［J］.計(jì)算機(jī)工程與應(yīng)用，2009，45(34):236－238.

［7］江銘炎，袁東風(fēng).人工魚群算法及其應(yīng)用［M］.北京:科學(xué)出版社，2012.

［8］Hu W，Liang H，Peng C，et al. A hybrid Chaos－Particle swarm optimization algorithm for the vehicle routing problem with time window［J］.Entropy，2013，15(4):1247－1270.

［9］Yue Y X，Wen Z B，Yue Q X. Chaos Optimization Algorithm for Vehicle Routing Problem［J］. Advanced Materials Research，2012，538:2722－2726.