林秀芳，林蔚青，陳國(guó)童，唐耀紅

（1.閩江學(xué)院 物理與電子信息工程學(xué)院，福建 福州 350108；2.寧德師范學(xué)院 信息與機(jī)電工程學(xué)院，福建 寧德 352100；3.閩江學(xué)院 福建省先進(jìn)運(yùn)動(dòng)控制重點(diǎn)實(shí)驗(yàn)室，福建 福州 350108）

隨著中國(guó)城市化的進(jìn)一步加深，城市道路的數(shù)量及里程數(shù)也越來越龐大，車輛在城市道路上行駛的路線選擇就變得多樣化，不同的行駛路線需要不同的時(shí)間代價(jià)和不同的道路資源.而物流領(lǐng)域的快遞行業(yè)也隨著電子商務(wù)的發(fā)展而迅速壯大，并已融入民眾的生活當(dāng)中.快遞車輛是配送環(huán)節(jié)的核心，快遞車輛數(shù)量的猛增對(duì)城市道路的壓力日漸凸顯，因此快遞車輛的使用數(shù)量及行駛路線的優(yōu)化對(duì)城市道路資源的利用,以及快遞公司的效益都有著極其重要的意義.而車輛路徑問題（vehicle routing problem，VRP）[1-3]則是提高快遞車輛配送效率的核心問題.早期學(xué)者采用諸如分割平面法、支定界法、網(wǎng)絡(luò)流或動(dòng)態(tài)規(guī)劃法[4]等算法對(duì)車輛路徑問題進(jìn)行求解，但這些算法都較簡(jiǎn)單且只適用于小規(guī)模的車輛路徑問題.近年來隨著智能啟發(fā)式算法的產(chǎn)生和應(yīng)用，國(guó)內(nèi)外很多學(xué)者利用各種智能啟發(fā)式算法對(duì)快遞配送問題進(jìn)行研究.李玲玉等[5]利用C-W 節(jié)約算法對(duì)快遞配送路徑進(jìn)行優(yōu)化研究，同時(shí)結(jié)合高德地圖開發(fā)了基于Internet的快遞配送路徑優(yōu)化軟件；王華[6]將Dijkstra和Floyd算法結(jié)合求解物流配送的路徑問題；Man?cini[7]通過大規(guī)模領(lǐng)域搜索算法對(duì)多周期多車型問題(multi depot vehicle routing problem,MDVRP)進(jìn)行優(yōu)化；鮑立婷[8]通過粒子群算法優(yōu)化LBS快遞派送路徑問題.

混合蛙跳算法(shuffled frog leaping algorithm,SFLA)最初由Eusuff 等提出并應(yīng)用于水資源網(wǎng)絡(luò)分配領(lǐng)域[9-11]，是一種受自然生物模仿啟示而產(chǎn)生的基于群體的協(xié)同搜索方法.算法模擬青蛙群體尋找食物時(shí)，按族群分類進(jìn)行思想傳遞的過程，將全局信息交換和局部深度搜索相結(jié)合，局部搜索使得思想在局部個(gè)體間傳遞，混合策略使得局部間的思想得到交換.在混合蛙跳算法中，群體(解集)由一群具有相同結(jié)構(gòu)的青蛙(解)組成.整個(gè)群體被分為多個(gè)族群，不同的族群被認(rèn)為是具有不同思想的青蛙的集合.族群中的青蛙按照一定策略執(zhí)行解空間中的局部深度搜索.在已定義的局部搜索迭代次數(shù)結(jié)束之后，思想在混合過程中進(jìn)行了交換.局部搜索和混合過程一直持續(xù)到定義的收斂條件結(jié)束為止.全局信息交換和局部深度搜索的平衡策略使得算法能夠跳出局部極值點(diǎn)，向著全局最優(yōu)的方向進(jìn)行，這也成為混合蛙跳算法最主要的特點(diǎn)，目前已有部分車輛路徑問題使用蛙跳算法.鄭紅劍[12]利用改進(jìn)混合蛙跳算法進(jìn)行優(yōu)化，有效解決了農(nóng)產(chǎn)品物流配送車輛路徑中無(wú)法滿足客戶時(shí)間需求的問題；楊進(jìn)[13]利用蛙跳算法解決了有碳排放要求的車輛路徑問題；段曉紅[14]利用混合蛙跳算法對(duì)應(yīng)急車輛的路網(wǎng)路徑進(jìn)行了優(yōu)化.但目前對(duì)于需要解決快遞配送車輛有時(shí)間、容積和載重限制要求的路徑問題卻較少研究，本文將對(duì)該路徑問題進(jìn)行數(shù)學(xué)建模，同時(shí)采用改進(jìn)的混合蛙跳算法對(duì)該路徑問題進(jìn)行優(yōu)化，并將改進(jìn)混合蛙跳算法與遺傳算法和標(biāo)準(zhǔn)混合蛙跳算法進(jìn)行對(duì)比.

1 問題描述與建模

快遞派送問題屬于車輛路徑問題，車輛路徑問題最早由Dantzig和Ramser[15]提出，考慮到配送點(diǎn)的數(shù)量、位置及配送車輛的數(shù)量，通過設(shè)計(jì)一條適合的路線，實(shí)現(xiàn)最短路徑、最低成本的目標(biāo).但快遞配送問題不僅僅是設(shè)計(jì)路線，還需考慮配送車輛的數(shù)量成本、配送時(shí)間的限制，以及配送車輛容積和載重限制等.因此本文將配送時(shí)間、容積和載重限制加入限制因素，同時(shí)根據(jù)配送路徑計(jì)算所需配送車輛數(shù)量.

1.1 參數(shù)定義

配送中心集合S0={v0}，配送點(diǎn)集合S1={v1，…，vn},總配送點(diǎn)集合V=S0∪S1，K為配送車輛集合；tij={i=0,1,…,n;j=0,1,…,n}為配送點(diǎn)集中任意兩點(diǎn)間的快遞配送車輛的行駛時(shí)間；qj(j=1,2,…,l)為配送點(diǎn)j的快遞數(shù)量，mj(j=1,2,…,n)為配送點(diǎn)j的快遞質(zhì)量，rj(j=1,2,…,n)為配送點(diǎn)j的快遞體積，α為每個(gè)快件需要處理的平均時(shí)間，β為每輛快遞車的平均消耗成本，MLimit為快遞車輛最大裝載質(zhì)量，RLimit為快遞車輛最大裝載體積，xijk=1表示配送車輛k的配送路線包含了從配送點(diǎn)i到j(luò)的路徑，xijk=0表示不包含.

1.2 快遞配送路徑優(yōu)化模型

式(1)為優(yōu)化的目標(biāo)函數(shù)，表示最小的配送時(shí)間成本，包含快遞車輛行駛時(shí)間、快遞處理時(shí)間和車輛使用的時(shí)間成本；式(2)為每部快遞車輛配送的快遞體積限制；式(3)為每部快遞車輛的質(zhì)量限制；式(4)為每部快遞車輛配送的總時(shí)間限制；式(5)表示配送車輛k從配送中心出發(fā)，完成配送任務(wù)后需要最終回到原配送中心；式(6)和式(7)保證每個(gè)配送點(diǎn)只有一輛快遞車服務(wù)；式(8)定義了0～1整數(shù)變量，xijk=1表示配送車輛k的配送路線包含了從配送點(diǎn)i到j(luò)的路徑，xijk=0表示不包含.

2 求解算法

2.1 基本混合蛙跳算法數(shù)學(xué)模型

隨機(jī)生成Q只蛙組成初始蛙群S=(X1，X2，…，XQ)，第i只蛙的解表示為Xi=(xi1，xi2，…，xis)，定義適應(yīng)度函數(shù)為f(Xi).計(jì)算蛙群中所有蛙的適應(yīng)度值，并按照適應(yīng)度值大小進(jìn)行排列，將蛙群分為m個(gè)模因組，每個(gè)模因組含有n只蛙，滿足關(guān)系Q=m×n，其中第一只蛙放在第一個(gè)模因組里，第二只蛙放在第二個(gè)模因組，以此類推，第m只蛙分在第m個(gè)模因組里，第（m+1）只蛙分入第二個(gè)模因組中，以此規(guī)律將所有的蛙按序分入各模因組.在第t次搜索中，每個(gè)模因組里適應(yīng)度值最好的蛙為Xb(t)，而適應(yīng)度值最差的蛙為Xw(t)，而群體中具有最好適應(yīng)值的蛙為Xg(t).對(duì)每個(gè)模因組里的最差蛙Xw(t)進(jìn)行更新，更新策略如下

式中：Dw(t)表示某模因組中最差蛙向組內(nèi)最好蛙移動(dòng)的距離；rand( )為0到1之間的隨機(jī)值.通過對(duì)Xw(t)更新得到新的位置Xw(t+1)，其中Rmin為允許的最小步長(zhǎng)，Rmax為允許的最大步長(zhǎng).當(dāng)蛙Xw(t+1)優(yōu)于原來的蛙Xw(t)，則進(jìn)行取代.否則就用Xg(t)取代Xb(t)，得到新的步長(zhǎng)計(jì)算式(10)，并對(duì)最差蛙進(jìn)行更新.即有

再次比較Xw(t+1)與Xw(t)的適應(yīng)度值，當(dāng)Xw(t+1)優(yōu)于Xw(t)，用Xw(t+1)進(jìn)行替換，否則將隨機(jī)產(chǎn)生1個(gè)新的蛙來取代原來的Xw(t).重復(fù)更新操作，直到達(dá)到設(shè)定的局部搜索迭代次數(shù)，當(dāng)所有模因組局部搜索完成后，將所有蛙重新混合，排序劃分新的模因組，直到達(dá)到設(shè)定的混合次數(shù)C.最后蛙群中適應(yīng)度最佳的蛙即為解.

2.2 改進(jìn)型混合蛙跳算法

混合蛙跳算法的基本更新方法是更新最差蛙，所以每次混合循環(huán)中只能更新m只蛙，更新效率較低，同時(shí)由于最差蛙所含的解參數(shù)中有可能有較好的信息片段，因此本文將增加每個(gè)模因組參加更新的蛙數(shù)，從而提高搜索效率.具體策略為每只蛙計(jì)算二項(xiàng)分布概率如

同時(shí)引入1個(gè)隨機(jī)數(shù)r∈[0,1]，在模因組中依次選擇每只蛙，若其概率值P[Xi(t)])小于r，則這只蛙將被改變.式(11)中，μ的取值為每個(gè)模因組中的最佳蛙的函數(shù)值TA[Xg(t)]，σ取值0.4.

改進(jìn)型混合蛙跳算法通過二項(xiàng)分布概率選擇要改變的蛙，依據(jù)式(9)和式(10)改變蛙的位置，完全改進(jìn)后，進(jìn)行混合操作，再進(jìn)入下一次循環(huán)，重新分組更新.算法流程圖如圖1.

圖1 改進(jìn)蛙跳算法流程圖

2.3 路徑編碼及解碼

以配送點(diǎn)為編碼Xi=(xi1,xi2，…，xis)，通過判斷配送車輛能否滿足下一配送點(diǎn)快遞的質(zhì)量和體積在極限范圍內(nèi)，同時(shí)處理完成快遞能在截止時(shí)間內(nèi)回到配送點(diǎn).假設(shè)編碼Xi=(6，4，2，5，8，3，7，1，4，9，10)，首先判斷第一輛車路徑(0，6，4，0)“.0”表示配送中心，計(jì)算按此路徑，是否存在超體積、超重和超時(shí)，若無(wú)則繼續(xù)增加路徑點(diǎn)，即(0，6，4，2，0)；如果存在，則第一輛車的路徑即為(0，6，0).然后判斷第二輛車的路徑(0，4，2，0)，是否存在超體積、超重和超時(shí)，以此類推，可將路徑編碼解碼，解碼的信息包含車輛數(shù)量、各車輛行駛路徑、各車輛的載重和運(yùn)載快遞體積信息，同時(shí)也可以計(jì)算出車輛到達(dá)各配送點(diǎn)及配送中心的時(shí)間、駛離配送點(diǎn)的時(shí)間和在各配送點(diǎn)處理快遞的時(shí)間.

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

某快遞配送中心服務(wù)19 個(gè)配送點(diǎn)，配送區(qū)域交通圖如圖2.每個(gè)圓表示一個(gè)區(qū)域，數(shù)字為配送點(diǎn)的編號(hào)，編號(hào)為“0”的圓為配送中心，各區(qū)域間的連接線表示道路，連接線上的數(shù)字表示距離，單位為km.

圖2 配送區(qū)域交通圖

快遞車輛配送完后回到配送中心的總時(shí)間不能超過8 h，快遞車輛的載質(zhì)量限制為300 kg，容量為1.5 m3，單次配送的最多快件量為70 件，快件簽收前的平均準(zhǔn)備時(shí)間、等待時(shí)間和簽收時(shí)間分別為2、2、1 min.快遞車輛的載質(zhì)量限制為300 kg，容量限制為4.5 m3，快遞車輛平均速度為30 km·h-1，每輛車每天對(duì)應(yīng)的消耗時(shí)間成本為10 h，各配送點(diǎn)的快遞質(zhì)量和體積信息見表1.

表1 配送點(diǎn)情況表

算法代碼采用Matlab R2014b軟件編寫，種群為20，迭代次數(shù)為1 000.為驗(yàn)證算法的有效性，在同等條件下將該算法與遺傳算法及混合蛙跳算法的優(yōu)化結(jié)果進(jìn)行對(duì)比，對(duì)比結(jié)果見表2.表中數(shù)據(jù)說明本文提出的改進(jìn)混合蛙跳算法的優(yōu)化結(jié)果比混合蛙跳算法更優(yōu)越，總時(shí)間成本降低了3.6%，相比遺傳算法，總時(shí)間成本降低了14.2%.

表2 車輛配送路徑算法優(yōu)化結(jié)果對(duì)比

優(yōu)化結(jié)果體現(xiàn)了快遞配送的總時(shí)間成本、各車輛的配送時(shí)長(zhǎng)，以及誤點(diǎn)成本.優(yōu)化后的配送路徑如圖3，路徑信息包含每輛車到達(dá)、離開配送點(diǎn)和回到配送中心的時(shí)間，以及所需配送的總體積和總質(zhì)量.

圖3 優(yōu)化結(jié)果圖

算法迭代曲線對(duì)比如圖4，表明該算法解決了混合蛙跳算法搜索效率低的天然缺陷.

圖4 迭代曲線對(duì)比圖

4 結(jié)論

本文針對(duì)快遞配送車輛數(shù)量及配送路徑影響配送成本的問題，建立了包含時(shí)間、載重、快遞體積限制的快遞車輛配送路徑數(shù)學(xué)模型，并提出一種適應(yīng)于該優(yōu)化模型的改進(jìn)混合蛙跳算法.通過對(duì)算例的求解，得出了有效的配送方案，并通過與標(biāo)準(zhǔn)遺傳算法和混合蛙跳算法的對(duì)比，驗(yàn)證了算法的優(yōu)越性.本文提出的算法及建立的模型對(duì)物流配送企業(yè)及管理部門具有一定的現(xiàn)實(shí)意義.通過研究得出以下結(jié)論.

1）本文所建立的數(shù)學(xué)模型不僅考慮了快遞車輛的配送時(shí)間限制，還考慮到車輛的載重和配送快遞體積的限制，具有一定的實(shí)踐性.

2）將配送時(shí)間節(jié)點(diǎn)規(guī)劃加入快遞配送路徑節(jié)點(diǎn)中，可以為快遞配送的細(xì)化管理提供依據(jù)，進(jìn)一步增強(qiáng)了研究的實(shí)際意義.

3）為改進(jìn)混合蛙跳算法搜索效率較低的問題，本文所提出的改進(jìn)混合蛙跳算法增加了每一輪的蛙數(shù)，根據(jù)二項(xiàng)分布概率更新選中的蛙，從而提高了算法的搜索效率.仿真實(shí)驗(yàn)結(jié)果表明，利用本文所提出的改進(jìn)混合蛙跳優(yōu)化算法，快遞配送總成本比遺傳算法節(jié)約了14.2%，比混合蛙跳算法節(jié)約了3.6%.