章惠民

福建省煙草公司漳州市公司，信息中心，福建省漳州市薌城區(qū)元光北路19號(hào)金葉大廈 363000

煙草物流配送是現(xiàn)代化物流系統(tǒng)中的一個(gè)重要環(huán)節(jié)?，F(xiàn)代商業(yè)系統(tǒng)卷煙物流強(qiáng)調(diào)快速響應(yīng)，需要不斷提高對(duì)環(huán)境變化和內(nèi)部變化做出相應(yīng)調(diào)整的適應(yīng)能力。在經(jīng)濟(jì)新常態(tài)以及煙草行業(yè)降本增效的大環(huán)境下，著力推進(jìn)精益物流以及智慧物流建設(shè)，提升配送效率、降低物流成本、提高服務(wù)水平，是煙草行業(yè)制勝的法寶。

按照傳統(tǒng)模式，漳州煙草物流在卷煙配送過(guò)程中，為通過(guò)提高車(chē)輛利用率降低物流成本，調(diào)度人員常將地理位置集中的零售戶統(tǒng)一配送。一般都只是根據(jù)行政區(qū)域劃分固定送貨線路，每條送貨線路對(duì)應(yīng)固定送貨車(chē)輛和人員。不論是銷(xiāo)售旺季還是淡季，物流每天所使用的車(chē)輛和人員數(shù)量都沒(méi)有做相應(yīng)的增減。盡管借助軟件系統(tǒng)對(duì)送貨線路進(jìn)行優(yōu)化，但也只是在原有基礎(chǔ)上進(jìn)行靜態(tài)調(diào)整，無(wú)法根據(jù)每天的實(shí)際情況進(jìn)行送貨線路的動(dòng)態(tài)實(shí)時(shí)優(yōu)化，在節(jié)省人力、精簡(jiǎn)車(chē)輛、降低油耗等方面效果都不明顯。

1 綜述

1.1 國(guó)內(nèi)外研究現(xiàn)狀

重慶煙草物流配送區(qū)域劃分為若干個(gè)配送單元，并依據(jù)配送單元的需求量、配送成本、配送中心及中轉(zhuǎn)站的固定成本和變動(dòng)成本, 建立了物流配送區(qū)域劃分規(guī)劃的運(yùn)籌學(xué)模型, 應(yīng)用遺傳算法設(shè)計(jì)了編碼方式和選擇、交叉、變異算子配送區(qū)域劃分的優(yōu)化布局方案[1]。

湖南煙草工業(yè)公司以及湖南煙草商業(yè)系統(tǒng)為優(yōu)化湖南煙草工商物流和商業(yè)系統(tǒng)卷煙配送物流操作流程，運(yùn)用 GPS、GIS 、GPRS 等技術(shù)，采用基于啟發(fā)式的禁忌搜索聚類算法、車(chē)載導(dǎo)航系統(tǒng)等，建立了一套完整的智能化卷煙物流在途動(dòng)態(tài)監(jiān)管系統(tǒng)，大幅提高卷煙商業(yè)配送運(yùn)輸效率，降低配送成本[2]。

日本煙草公司專門(mén)設(shè)置了物流部來(lái)負(fù)責(zé)卷煙配送服務(wù)，物流部的卷煙配送業(yè)務(wù)全部由其卷煙配送服務(wù)網(wǎng)絡(luò)公司TSN（Tobacco Service Net）完成。TSN成功建設(shè)了國(guó)內(nèi)外卷煙共同流通渠道，采用基于最短路徑的網(wǎng)絡(luò)優(yōu)化算法，每輛車(chē)的配送線路、裝載量、配送時(shí)間都由配送系統(tǒng)自動(dòng)做出安排。

1.2 漳州煙草配送區(qū)域及線路優(yōu)化概述

目前漳州煙草配送區(qū)域及線路優(yōu)化借助柔性線路截取算法以及GIS線路優(yōu)化輔助系統(tǒng)，依據(jù)零售戶的地理位置、歷史銷(xiāo)量對(duì)全區(qū)所有零售客戶進(jìn)行線路調(diào)整，改變傳統(tǒng)既定計(jì)劃、線路、車(chē)輛、人員 “以線定車(chē)”的固定配送模式，建立了“以量定車(chē)，以戶定線，戶量均衡，動(dòng)態(tài)優(yōu)化”的彈性送貨新模式。

彈性送貨新模式打破了以往行政區(qū)劃以及配送區(qū)域的概念，支持隨訪隨銷(xiāo)，較大程度地提高了配送方案調(diào)整能力、配送計(jì)劃變更能力、協(xié)同配送能力和配送策略靈活性，力求以最優(yōu)的線路、最短的時(shí)間，最少的精力、最低的成本完成物流作業(yè)，從而達(dá)到半徑最佳、流向最暢、流速最快、流量最優(yōu)的目標(biāo)。

2 配送線路優(yōu)化算法

卷煙物流配送優(yōu)化是個(gè)非常重要的問(wèn)題[2]。配送線路優(yōu)化的結(jié)果，不僅會(huì)影響送貨的效率和成本，也會(huì)影響其它與之相關(guān)的業(yè)務(wù)和作業(yè)，最終影響卷煙物流企業(yè)的經(jīng)營(yíng)。

2.1 線路優(yōu)化問(wèn)題描述

卷煙配送經(jīng)驗(yàn)線路截取優(yōu)化問(wèn)題可以描述為：已知配送區(qū)域內(nèi)的零售客戶以及其在經(jīng)驗(yàn)線路中的排列次序，給定該區(qū)域可用車(chē)輛及其標(biāo)準(zhǔn)配送能力，根據(jù)零售戶訂單情況，將經(jīng)驗(yàn)線路截取并分配到各可用車(chē)輛中，使配送調(diào)度最優(yōu)化。

考慮到頻繁的零售戶變更和送貨次序?qū)ε渌腿藛T的工作效率影響較大，以往常用的調(diào)度策略是：預(yù)先劃分出統(tǒng)一配送的區(qū)域，并為該配送區(qū)域內(nèi)的零售客戶分配車(chē)輛，同一配送區(qū)域內(nèi)所有的零售戶被編排到一條大線路（稱之為經(jīng)驗(yàn)線路）中。當(dāng)零售戶訂貨量隨時(shí)間發(fā)生變化時(shí)，根據(jù)配送區(qū)域經(jīng)驗(yàn)線路中指定的配送次序和車(chē)輛的配送能力，將當(dāng)日零售戶訂單依次截取并分配給各配送車(chē)輛，生成所有車(chē)輛執(zhí)行的配送小線路（稱之為實(shí)時(shí)線路）。

配送調(diào)度最優(yōu)化表現(xiàn)為以下方面：（1）車(chē)輛利用率最大化；（2）配送里程最小化；（3）工作量均衡化。其中，車(chē)輛利用率最大化和配送里程最小化，通過(guò)節(jié)省車(chē)輛和節(jié)省配送里程 保證了配送成本最小化；工作量均衡化，則通過(guò)減小工作任務(wù)的差異性，保證了 管理成本的最小化。通過(guò)配送成本最小化和管理成本最小化的統(tǒng)一平衡，實(shí)現(xiàn)配 送調(diào)度的最優(yōu)化。

在問(wèn)題求解中，配送里程為參與配送的各部車(chē)輛自物流中心出發(fā)，沿著實(shí)時(shí)線路訪問(wèn)各客戶點(diǎn)，并在配送完成后返回物流中心所產(chǎn)生的行駛里程的總和。任意兩點(diǎn)之間（物流中心到客戶點(diǎn)、客戶點(diǎn)到客戶點(diǎn)，或客戶點(diǎn)到物流中心）的行駛里程為基于兩點(diǎn)坐標(biāo)和實(shí)際電子地圖路網(wǎng)數(shù)據(jù)計(jì)算出的最短路徑長(zhǎng)度。配送車(chē)輛的配送能力表現(xiàn)為配送戶數(shù)和配送貨量?jī)蓚€(gè)方面。在訂貨量波動(dòng)較大的特殊時(shí)期(如春節(jié)、中秋等高峰期），調(diào)度人員可根據(jù)經(jīng)驗(yàn)適當(dāng)調(diào)整車(chē)輛配送能力浮動(dòng)參數(shù)，使優(yōu)化結(jié)果最大程度滿足實(shí)際應(yīng)用需要。

2.2 線路優(yōu)化問(wèn)題分析

全局配送線路優(yōu)化核心問(wèn)題是選取候選車(chē)輛以及依據(jù)候選車(chē)輛參數(shù)截取實(shí)時(shí)線路。

2.2.1 最佳候選車(chē)輛選取

車(chē)輛的配送能力描述為載貨量和服務(wù)客戶數(shù)量?jī)蓚€(gè)方面。對(duì)于候選車(chē)輛i，預(yù)先設(shè)定其標(biāo)準(zhǔn)裝載量為SWi，標(biāo)準(zhǔn)配送客戶數(shù)為SCi，假設(shè)其實(shí)際送貨量為RWi，實(shí)際送貨戶數(shù)為RCi。此時(shí)，車(chē)輛i的工作負(fù)荷指標(biāo)有：貨量滿載率戶數(shù)滿載率車(chē)輛i的任務(wù)滿載率定義為T(mén)Ri=min（CRi，CWi）。

設(shè)候選車(chē)輛列表中有k輛車(chē)，假設(shè)車(chē)輛i（i=1，2，…，k）標(biāo)準(zhǔn)裝載量為SWi，標(biāo)準(zhǔn)配送客戶數(shù)為SCi。依據(jù)車(chē)輛i的標(biāo)準(zhǔn)裝載量和標(biāo)準(zhǔn)客戶數(shù)，得到的實(shí)時(shí)線路中實(shí)際送貨量為RWi，實(shí)際送貨戶數(shù)為RCi，則K輛車(chē)任務(wù)滿載率最高的車(chē)輛j被選為最佳候選車(chē)輛，即滿足TRi=max(TRi)，i=1，2，…,k。

2.2.2 實(shí)時(shí)線路硬性截取法

經(jīng)驗(yàn)線路上的n（n ≥1）戶零售戶以自然數(shù)1…n編號(hào)。對(duì)于候選車(chē)輛i，預(yù)先設(shè)定其標(biāo)準(zhǔn)裝載量為SWi，標(biāo)準(zhǔn)配送客戶數(shù)為SCi。對(duì)車(chē)輛i分配的實(shí)時(shí)線路為經(jīng)驗(yàn)線路中截取的前t戶零售戶（1≤ t ≤ n），t應(yīng)滿足：,且t ≤ RCi。為保證車(chē)輛利用率最高，t還應(yīng)滿足：SCi＜t+1。對(duì)于候選車(chē)輛i，假設(shè)經(jīng)驗(yàn)線路中截取的前s（1≤ s ≤ n）戶零售戶可以滿足t≤ SCi＜ t+1，則將經(jīng)驗(yàn)線路中的前d戶零售戶截取為車(chē)輛i的實(shí)時(shí)線路，其中d=min(s，t)。由于按照此方式，對(duì)車(chē)輛i的實(shí)時(shí)線路截取嚴(yán)格依據(jù)標(biāo)準(zhǔn)裝載量SWi和標(biāo)準(zhǔn)配送客戶數(shù)SCi，該方法被稱為硬性截取法。

2.2.3 實(shí)時(shí)線路柔性截取法

為適應(yīng)節(jié)假日和銷(xiāo)售淡旺季零售戶訂貨量顯著浮動(dòng)的需要，并在配送成本最 小化的基礎(chǔ)上實(shí)現(xiàn)工作負(fù)荷均衡化，在定義車(chē)輛i的標(biāo)準(zhǔn)裝載量SWi和標(biāo)準(zhǔn)配送客戶數(shù)SCi的同時(shí)，定義以下浮動(dòng)參數(shù)：

L_SWi表示標(biāo)準(zhǔn)裝載量下界，有 0＜L_SWi ≤SWi；

U_SWi表示標(biāo)準(zhǔn)裝載量上界，有SWi≤ U_SWi；

L_SCi表示標(biāo)準(zhǔn)配送客戶數(shù)下界，有0＜L_SCi ≤SCi；

U_SCi表示標(biāo)準(zhǔn)配送客戶數(shù)上界，有SCi ≤ ＜U_SCi。

稱[L_SWi，U_SWi]為標(biāo)準(zhǔn)裝載量窗口，[L_SCi，U_SCi]為標(biāo)準(zhǔn)客戶數(shù)窗口，并將依據(jù)標(biāo)準(zhǔn)裝載量窗口和標(biāo)準(zhǔn)客戶數(shù)窗口截取實(shí)時(shí)線路的方法稱為柔性截取法。

柔性截取法的求解思路：首先，依據(jù)標(biāo)準(zhǔn)裝載量下界L_SWi和標(biāo)準(zhǔn)配送客戶數(shù)下界L_SCi進(jìn)行實(shí)時(shí)線路的硬性截取，得到截取線路零售戶的最小值dL；然后，依據(jù)標(biāo)準(zhǔn)裝載量上界U_SWi和標(biāo)準(zhǔn)配送客戶數(shù)上界U_SCi進(jìn)行實(shí)時(shí)線路的硬性截取，得到截取線路零售戶的最大值dU；最后，針對(duì)前兩步得到的零售戶截取窗口[dL , dU]，計(jì)算得出最優(yōu)線路截取零售戶d值d。

截取線路零售戶最小值和最大值的計(jì)算方法參考實(shí)時(shí)線路硬性截取算法。對(duì)于零售戶截取窗口[dL, dU]，有 1≤ dL ≤ dU ≤ n]。

圖1 零售戶截取窗口及截取前后路程變化示意圖Fig.1 Sketch map of retail customer's interception window and interception distance

圖1截取窗口[dL , dU]中零售戶，當(dāng)截取經(jīng)驗(yàn)線路中前d戶的零售戶作為實(shí)時(shí)線路時(shí)，原來(lái)經(jīng)驗(yàn)線路中連接零售戶d和d+1 的邊將被去除；實(shí)時(shí)線路中配送完零售戶d后，車(chē)輛將返回物流中心，去除實(shí)時(shí)線路后的經(jīng)驗(yàn)線路。

2.3 改進(jìn)的柔性優(yōu)化算法

基本截取算法中采用實(shí)時(shí)線路柔性截取法，能夠滿足任務(wù)負(fù)荷的車(chē)輛配送里程最小化。算法完成后，可能出現(xiàn)兩種情況：（1）車(chē)輛數(shù)過(guò)大。在車(chē)輛數(shù)充足時(shí)，可能最后一輛車(chē)在戶數(shù)和貨量上任務(wù)都過(guò)少；或者在所有車(chē)輛分配完成后，由于經(jīng)驗(yàn)線路剩余少量零售戶和貨量，必須加派車(chē)輛。（2）工作量失衡。某些車(chē)輛在貨量上滿足標(biāo)準(zhǔn)裝載量窗口要求，但零售戶過(guò)少；或者零售戶數(shù)量上滿足標(biāo)準(zhǔn)戶數(shù)窗口要求，但貨量過(guò)少。

為最大程度提高車(chē)輛利用率，降低管理成本，減少上述兩種情況的發(fā)生，在基本截取算法的基礎(chǔ)上進(jìn)行算法改進(jìn)，增加“裝載最大化”和“任務(wù)均衡化”兩個(gè)處理過(guò)程。

（1）裝載最大化

以k部候選車(chē)輛的標(biāo)準(zhǔn)參數(shù)上限U_SW和U_SC為條件執(zhí)行硬性截取算法，得到最優(yōu)車(chē)輛數(shù)k0。

（2）任務(wù)均衡化

若執(zhí)行裝載最大化操作后，經(jīng)驗(yàn)線路上仍有剩余，說(shuō)明可用車(chē)輛數(shù)不足，程序結(jié)束。否則，在不增加車(chē)輛的前提下，循環(huán)多次調(diào)節(jié)車(chē)量標(biāo)準(zhǔn)裝載量窗口和標(biāo)準(zhǔn)客戶數(shù)窗口的上限和下限后執(zhí)行基本柔性截取算法，使車(chē)輛的任務(wù)滿載率均衡化。在調(diào)節(jié)過(guò)程中需保證分配車(chē)輛數(shù)不大于k0，且配送里程增量最小化。

設(shè)窗口壓縮調(diào)節(jié)次數(shù)為T(mén)imes，且第m次調(diào)節(jié)時(shí)，窗口寬度為r。當(dāng)m較小時(shí)，參數(shù)窗口的上限較大，有利于保證車(chē)輛數(shù)最少；當(dāng)m較大時(shí)，參數(shù)窗口的寬度較小，有利于保證工作量均衡化。 當(dāng)r較大時(shí)，參數(shù)窗口寬度較大，有利于保證配送里程最小化；反之，當(dāng)r較小時(shí)，參數(shù)窗口寬度較小，有利于保證車(chē)輛數(shù)最少。為保證結(jié)果的最優(yōu)化r的取值范圍為[0，Times-1]，m的取值范圍為[1，Times]。

2.4 算法主要技術(shù)思路以及創(chuàng)新點(diǎn)

卷煙配送線路為從物流公司出發(fā)，經(jīng)過(guò)配送范圍內(nèi)的所有零售戶節(jié)點(diǎn)，然后返回物流公司的行程。不少學(xué)者雖然提出了構(gòu)造算法、兩階段法、蟻群算法、粒子群算法、混合算法、遺傳算法、禁忌搜索算法、神經(jīng)網(wǎng)絡(luò)、模擬退火等方法，然而這些算法迭代速度緩慢、計(jì)算耗費(fèi)時(shí)間長(zhǎng)，可推廣性和適用性一般[3-9]。針對(duì)這些缺陷，本文提出了一種改進(jìn)的柔性線路截取優(yōu)化算法（簡(jiǎn)稱FOIA算法），宏觀上綜合權(quán)衡裝載量以及配送戶數(shù)，微觀上進(jìn)行配送節(jié)點(diǎn)逐點(diǎn)調(diào)整以及多點(diǎn)交換，建立了“以量定車(chē)，以戶定線，戶量均衡，動(dòng)態(tài)優(yōu)化”的彈性送貨新模式。采用此種方法進(jìn)行優(yōu)化，既解決了現(xiàn)有算法存在的缺陷，又在較大程度上增強(qiáng)了獲取最優(yōu)解的可能性，具有很強(qiáng)的現(xiàn)實(shí)應(yīng)用價(jià)值。

2.4.1 主要技術(shù)思路

算法主要技術(shù)思路：（1）逐點(diǎn)調(diào)整，即對(duì)已有配送線路中的各節(jié)點(diǎn)進(jìn)行位置調(diào)整，如果節(jié)點(diǎn)調(diào)整位置后總路程減少，則用節(jié)點(diǎn)新位置替代原節(jié)點(diǎn)位置，并進(jìn)行不斷的循環(huán)改進(jìn)，直到對(duì)所有節(jié)點(diǎn)的位置調(diào)整均不能減少總路程為止。（2）多點(diǎn)交換，逐點(diǎn)調(diào)整僅能調(diào)整鄰近節(jié)點(diǎn)位置的缺陷，利用結(jié)構(gòu)體狀態(tài)集合窮舉可調(diào)整任意多個(gè)節(jié)點(diǎn)的位置，從而使得優(yōu)化結(jié)果計(jì)算更加快速高效。（3）交替使用，即交替使用逐點(diǎn)調(diào)整法以及多點(diǎn)交換進(jìn)行計(jì)算，并增加配送節(jié)點(diǎn)調(diào)整及交換隨機(jī)因子，能夠快速得出更優(yōu)的節(jié)點(diǎn)順序，保證啟發(fā)算法結(jié)果的完整和高效。（4）適當(dāng)控制，即通過(guò)適當(dāng)控制迭代次數(shù)（搜索半徑），能夠較快地完成線路劃分，將全部客戶合理分配給各配送線路，并保證各線路內(nèi)部遍歷路徑較短。（5）有效結(jié)合，統(tǒng)籌考慮結(jié)合局部最優(yōu)以及全局最優(yōu)，避免出現(xiàn)最臨近法構(gòu)造線路存在的運(yùn)算時(shí)間增長(zhǎng)，散點(diǎn)數(shù)量增加和分布分散的不足，也可以克服遺傳算法、禁忌搜索算法、神經(jīng)網(wǎng)絡(luò)、模擬退火等啟發(fā)式算法無(wú)效迭代（搜索）過(guò)多導(dǎo)致計(jì)算耗費(fèi)時(shí)間長(zhǎng)的缺陷。

2.4.2 創(chuàng)新點(diǎn)

主要?jiǎng)?chuàng)新點(diǎn)有：（1）一種改進(jìn)的柔性線路截取優(yōu)化算法，綜合進(jìn)行配送節(jié)點(diǎn)逐點(diǎn)調(diào)整以及多點(diǎn)交換完成線路優(yōu)化。（2）建立了“以量定車(chē)，以戶定線，戶量均衡，動(dòng)態(tài)優(yōu)化”的彈性送貨新模式，打破了以往行政區(qū)劃以及配送區(qū)域的概念，支持隨訪隨銷(xiāo)，較大程度地提高了配送方案調(diào)整能力、配送計(jì)劃變更能力、協(xié)同配送能力和配送策略靈活性。（3）提出了“以量定車(chē)，以戶定線”的思路，并綜合權(quán)衡裝載量以及配送戶數(shù)，實(shí)現(xiàn)配送線路動(dòng)態(tài)優(yōu)化。（4）優(yōu)化已分配給線路的全部客戶的訪問(wèn)次序，生成線路客戶最優(yōu)或近似最優(yōu)的排序序列。（5）使用相應(yīng)的管理手段來(lái)保障和提升線路優(yōu)化結(jié)果，形成一個(gè)完整性的物流配送線路動(dòng)態(tài)優(yōu)化體系和全面有效的配送監(jiān)管機(jī)制，實(shí)現(xiàn)技術(shù)與管理的相輔相成。

2.5 算法分析及運(yùn)行效果

2.5.1 收斂性與復(fù)雜度分析

本文算法（FOIA算法）從問(wèn)題的狀態(tài)空間中隨機(jī)選取的可行初始解著手，采用改進(jìn)的迭代運(yùn)算，逐步逼近問(wèn)題的最優(yōu)解。

收斂性分析方面，F(xiàn)OIA算法所求解目標(biāo)問(wèn)題的狀態(tài)空間S是有限集，算法的運(yùn)行過(guò)程是隨機(jī)過(guò)程，并可以用馬爾可夫鏈來(lái)表示。FOIA算法的尋優(yōu)過(guò)程的狀態(tài)轉(zhuǎn)移概率以概率1收斂于全局最優(yōu)解，算法收斂性證明如下：

定義1.設(shè)算法在第t次迭代時(shí)結(jié)構(gòu)體狀態(tài)集合為X（t）={xt,i…,xt,n}，其中xt,i S, n＜∞，x和S分別表示可行解向量和解空間，n為結(jié)構(gòu)體中搜索元的個(gè)數(shù)。{X(t)，t＞ 0}構(gòu)成一個(gè)離散時(shí)間的隨機(jī)過(guò)程，其狀態(tài)空間為E=|S|n。

定義2.算法優(yōu)化問(wèn)題的全局最優(yōu)解集合為E*=令表示結(jié)構(gòu)體中包含的最優(yōu)解的個(gè)數(shù)。

定義3.若對(duì)任意初始狀態(tài)X0均有則稱FOIA算法以概率1收斂于全局最優(yōu)解。

定理1. FOIA算法尋優(yōu)過(guò)程{X(t),t＞ 0}是有限齊次馬爾可夫鏈。

證明：令t=0，結(jié)構(gòu)體狀態(tài)集合隨機(jī)產(chǎn)生初始狀態(tài)X(0)={x0,1，x0,2…,x0,n}。之后迭代遍歷計(jì)算過(guò)程中，算法會(huì)基于當(dāng)前結(jié)構(gòu)體狀態(tài)集合記憶的信息搜索解的空間, 并更新結(jié)構(gòu)體集合狀態(tài)。設(shè)t時(shí)刻結(jié)構(gòu)體的狀態(tài)為X(t),t+1時(shí)刻結(jié)構(gòu)體的狀態(tài)為X（t+1），解的空間使結(jié)構(gòu)體集合狀態(tài)以概率P(X(t+1) |X(t))轉(zhuǎn)移至t+1 狀態(tài)，P(X(t+1) |X(t))依賴于X(t)且是一個(gè)與時(shí)間無(wú)關(guān)的常量：

公式（1）中，Xm和Xn表示兩個(gè)任意的結(jié)構(gòu)體狀態(tài)，所以{X(t),t＞ 0}有齊次馬爾可夫性質(zhì)。因?yàn)榻Y(jié)構(gòu)體集合狀態(tài)有限，這樣狀態(tài)轉(zhuǎn)移構(gòu)成的馬爾可夫過(guò)程的狀態(tài)空間有限, 所以算法尋優(yōu)過(guò)程{X(t),t＞ 0}是有限齊次馬爾可夫鏈。

定理2. FOIA算法的結(jié)構(gòu)體狀態(tài)集合中最優(yōu)解個(gè)數(shù)序列是不遞減且單調(diào)的，即t ≥ 0，有

證明：因?yàn)樽顑?yōu)解的路徑結(jié)果距離值小于其他搜索結(jié)果，而算法的選擇策略為留存任意時(shí)刻的最優(yōu)解結(jié)果，所以迭代計(jì)算中上一輪的結(jié)構(gòu)體狀態(tài)集合中最優(yōu)解肯定在新一輪結(jié)構(gòu)狀態(tài)集合體中，即在任意t時(shí)刻結(jié)構(gòu)體狀態(tài)集合中最優(yōu)解的個(gè)數(shù)為k（k ＞ 0）的條件下，t+1時(shí)刻結(jié)構(gòu)體中最優(yōu)解的個(gè)數(shù)小于k的概率是0。

定理3. FOIA算法計(jì)算過(guò)程中在任意時(shí)刻t都會(huì)得到全局最優(yōu)解, 即

證明：根據(jù)FOIA算法的計(jì)算過(guò)程可知，全局優(yōu)化路徑在全部計(jì)算空間中是隨機(jī)生成，所以任意t時(shí)刻全局計(jì)算結(jié)果為任意可能解的概率不為0，那么任意t時(shí)刻全局計(jì)算結(jié)果為全局最優(yōu)解的概率也不為0。所以在迭代計(jì)算中上一輪的結(jié)構(gòu)體狀態(tài)集合中最優(yōu)解的個(gè)數(shù)為0的情況下，新一輪結(jié)構(gòu)狀態(tài)集合體中最優(yōu)解的個(gè)數(shù)不為0的概率大于0。

定理4. FOIA算法以概率1收斂于全局最優(yōu)解，即有

證明：設(shè)Pr(t)=P(F(X(t))=r)表示t時(shí)刻結(jié)構(gòu)體狀態(tài)集合中最優(yōu)解的個(gè)數(shù)為r的概率，根據(jù)貝葉斯條件概率公式有

根據(jù)定理2有：P(F(X(t+1))=0 |F(X(t))≠0)=0，所以

又根據(jù)定理 3得出：P(F(X(t+1)) ＞ 0 |F(X(t))=0) ＞0， 設(shè)，φ=min(P(F(X(t+1)) ＞ 0 |F(X(t))=0)?,t=0,1,…),則有

根據(jù)公式（5）可知：

因此由于且故當(dāng) t→∞時(shí)有所以，因此，綜上所述

所以

時(shí)間復(fù)雜性分析方面，給出FOIA算法的期望收斂時(shí)間的估算。

定義4.設(shè)算法可以表示的馬爾可夫過(guò)程和最優(yōu)狀態(tài)空間若μ是一個(gè)隨機(jī)非負(fù)整數(shù)的變量且滿足：當(dāng)且當(dāng)，則稱μ為算法收斂時(shí)間，μ的期望E(μ)稱算法的期望收斂時(shí)間。

定義5. 對(duì)于任意t時(shí)刻，設(shè)馬爾可夫過(guò)程和最優(yōu)狀態(tài)空間τ是一個(gè)隨機(jī)變量且滿足：當(dāng)t=τ時(shí) ,{η(t)∈E*；當(dāng) 0≤ t ＜τ 時(shí)，{η(t)∈E*，則稱τ的期望E(τ)是首次獲得最優(yōu)解的期望時(shí)間。

引理1. FOIA算法的收斂時(shí)間μ等于首次獲得最優(yōu)解的期望時(shí)間τ。

證明：對(duì)于任意t時(shí)刻，當(dāng)t=τ時(shí) ,η(t)∈E*。因?yàn)槭俏諔B(tài)馬爾可夫過(guò)程，則又因?yàn)镻{η(t)∈E*}=1 ，所以P{η(τ+1)∈E*}=1。同理可證，當(dāng)t＜τ時(shí)，P{η(t)∈E*}=1.根據(jù)定義5，當(dāng)t＜τ時(shí) ,P{η(t)∈E*}＜1 根據(jù)定義 4,有μ=τ。

定理5.設(shè)馬爾可夫過(guò)程和最優(yōu)狀態(tài)空間其期望收斂時(shí)間是

證明：對(duì)于任意t時(shí)刻，有

根據(jù)引理1，有

假設(shè)總共有m輛車(chē)，客戶數(shù)量為n，i表示最大迭代次數(shù)，算法搜索過(guò)程劃分為幾個(gè)步驟:初始化所有客戶兩兩之間的距離以及車(chē)輛信息參數(shù)的時(shí)間復(fù)雜度為O（n2+m）;構(gòu)造結(jié)構(gòu)體狀態(tài)集合及更新解的空間時(shí)間復(fù)雜度為O（n2m），清空結(jié)構(gòu)體狀態(tài)集合的時(shí)間復(fù)雜度為O（nm）。使用時(shí)間復(fù)雜度的漸進(jìn)表示法，則FOIA算法總的時(shí)間復(fù)雜度為T(mén)（n）=O（i×n2×m）。

空間復(fù)雜性分析方面，假設(shè)總共有m輛車(chē)，客戶數(shù)量為n，則FOIA算法總的空間復(fù)雜度為S（n）=O（n2）+O(n×m)，具體分析如表1所述。

圖2 算法MATLAB實(shí)驗(yàn)結(jié)果圖Fig.2 Algorithm experiment result diagram by MATLAB tool

2.5.2 運(yùn)行效果

FOIA算法打破了以往行政區(qū)劃以及配送區(qū)域的概念，使物流配送管理能夠主動(dòng)地適應(yīng)變化，并在漳州煙草物聯(lián)網(wǎng)系統(tǒng)中成功實(shí)現(xiàn)，較大程度上降低了配送里程，節(jié)約了成本。配送線路變化詳細(xì)如圖3所示：

圖3 配送線路前后變化示意圖Fig.3 Sketch map of distribution line before and after distribution

2.6 彈性送貨模式應(yīng)用成效

彈性送貨模式算法在漳州物聯(lián)網(wǎng)系統(tǒng)實(shí)現(xiàn)并投入運(yùn)行5年來(lái)，在周配送戶數(shù)從25000戶增加到30000戶，卷煙銷(xiāo)量從19萬(wàn)多箱增加到24萬(wàn)多箱的情況下，實(shí)現(xiàn)了送貨車(chē)輛、配送人員減少、裝載量及送貨戶數(shù)增加的效果，實(shí)現(xiàn)了提高卷煙配送效率、降低配送成本的建設(shè)目標(biāo)，主要效果有：（1）配送日常使用車(chē)輛從79部減少到62部，配送車(chē)數(shù)下降了21.5%；（2）送貨員工人數(shù)由158人減少至 124人，用工人數(shù)下降了21.5%；（3）單車(chē)日均配送量由49件增加到 74件，增加了 51%；（4）單車(chē)日均送貨戶數(shù)由 63戶增加到97戶左右，增長(zhǎng)了 53.9%；（5）卷煙單件配送成本由244元 /箱下降為 189元 /箱，下降了 22.5%。

3 結(jié)論

本文分析了配送線路優(yōu)化問(wèn)題,針對(duì)這些問(wèn)題給出了相應(yīng)的解決思路,并闡述了柔性配送線路優(yōu)化算法以及改進(jìn)措施。此外，本文算法在漳州煙草物聯(lián)網(wǎng)系統(tǒng)中成功實(shí)現(xiàn)。

漳州煙草打破以往行政區(qū)劃以及配送區(qū)域的概念，建立了“以量定車(chē)，以戶定線，戶量均衡，動(dòng)態(tài)優(yōu)化”的彈性送貨新模式，使物流配送管理能夠主動(dòng)地適應(yīng)變化，增強(qiáng)自身在動(dòng)態(tài)環(huán)境和過(guò)程中的競(jìng)爭(zhēng)性，縮短響應(yīng)時(shí)間，提升服務(wù)質(zhì)量。5年的實(shí)際應(yīng)用表明，在周配送戶數(shù)從25000戶增加到30000戶、卷煙銷(xiāo)量從19萬(wàn)多箱增加到24萬(wàn)多箱的情況下，送貨線路卻從79條減少到62條，在企業(yè)經(jīng)營(yíng)降本增效上取得了良好的成效。

[1]王勇,池潔，樊建新. 基于遺傳算法的煙草物流配送區(qū)域劃分優(yōu)化研究[J]. 重慶交通大學(xué)學(xué)報(bào)(自然科學(xué)版)，2009，28(3):619-621.WANG Yong, CHI Jie, FAN Jianxin, Optimization of cigarette logistics deliver region partition based on genetic algorithm [J].Journal of Chongqing Jiaotong University (NATURAL SCIENCE EDITION), 2009, 28 (3):619-621.

[2]徐智，陳軍，唐萍. 卷煙商零物流動(dòng)態(tài)線路優(yōu)化和在途監(jiān)控的研究及實(shí)現(xiàn)[J].中國(guó)煙草學(xué)報(bào)， 2014, 20(1)：71-73.XU Zhi, CHEN Jun, TANG Ping. Study of dynamic route optimization and monitoring in cigarette distribution [J]. ACTA TABACARIA SINICA, 2014, 20(1):71-73.

[3]Taniguchi E, Noritake M, Yamada T, et al. Optimal size and location planning of public logistics terminals[J]. Transportation Research Part E: Logistics and Transportation Review, 1999, 35(3): 207-222.

[4]Bramel J, Levi D. A location based heuristic for general routing problems [J]. Loca tion Science, 1997, 5(1): 60-60.

[5]Fuellerer G, Doerner K F, Hartl R F, et al. Ant colony optimization for the two-dimensional loading vehicle routing problem[J].Computers & Operations Research, 2009, 36(3): 655-673.

[6]Goksal F P，Karaoglan I，Altiparmak F. A Hybrid Discrete Particle Swarm Optimization for Vehicle Routing Problem with Simultaneous Pickup and Delivery[J].Computers & Industrial Engineering，2013, 65(1): 39-53.

[7]Morais V W C，Mateus G R，Noronha T F. Iterated Local Search Heuristics for the Vehicle Routing Problem with Cross-Docking[J].Expert Systems with Applications，2014, 41(16).

[8]胡紅春，吳耀華，廖莉. 物流配送車(chē)輛線路的優(yōu)化及其應(yīng)用[J].山東大學(xué)學(xué)報(bào)(工學(xué)版)，2007, 37(4):104-107.HU Hongchun, WU Yaohua, LIAO Li. Routing optimization for logistics distribution and its application [J]. Journal of Shandong University (ENGINEERING SCIENCE), 2007, 37(4):104-107.

[9]Cheikh M, Ratli M, Mkaouar O, et al. A Variable Neighborhood Search Algorithm for the Vehicle Routing Problem with Multiple Trips[J].Electronic Notes in Discrete Mathematics，2015, 47 : 277-284.