高瑞萍，紀(jì)壽文，張永昕

（1.北京交通大學(xué)　城市交通復(fù)雜系統(tǒng)理論與技術(shù)教育部重點實驗室，北京　100044；2.交通銀行日照分行，山東　日照　276800）

?

基于免疫遺傳算法的快遞末端網(wǎng)點優(yōu)化整合

高瑞萍1，紀(jì)壽文1，張永昕2

（1.北京交通大學(xué)城市交通復(fù)雜系統(tǒng)理論與技術(shù)教育部重點實驗室，北京100044；2.交通銀行日照分行，山東日照276800）

在研究末端網(wǎng)點優(yōu)化整合原則的基礎(chǔ)上，建立了以末端網(wǎng)點運營成本和運輸成本最小為目標(biāo)函數(shù)、以滿足客戶群集中點的服務(wù)需求和末端網(wǎng)點的服務(wù)能力為約束條件的優(yōu)化模型，并針對此模型的特點，選擇免疫遺傳算法對快遞分撥中心選址和最終成本進(jìn)行求解。該算法綜合了免疫系統(tǒng)和遺傳算法的優(yōu)點，具有良好的全局收斂能力，通過算例對網(wǎng)點優(yōu)化整合模型進(jìn)行求解，驗證了該算法的有效性。

快遞末端網(wǎng)點；優(yōu)化整合；免疫遺傳算法

1　引言

隨著經(jīng)濟(jì)快速、健康、持續(xù)的發(fā)展，我國快遞行業(yè)也得到了迅速發(fā)展，成為國民經(jīng)濟(jì)發(fā)展的基礎(chǔ)產(chǎn)業(yè)。為了使快遞行業(yè)得到更好的發(fā)展，2014年國務(wù)院出臺了《關(guān)于進(jìn)一步促進(jìn)資本市場健康發(fā)展的若干意見》［1］，鼓勵在市場條件下的各種企業(yè)并購重組以優(yōu)化人力、資源和資金的配置。對于快遞物流企業(yè)來說，在滿足客戶需求的前提下，降低企業(yè)運營成本、提高企業(yè)的競爭力、提高企業(yè)的利潤一直是物流管理領(lǐng)域研究的熱點，其中快遞物流網(wǎng)絡(luò)的基礎(chǔ)和優(yōu)化研究是研究的重點，國內(nèi)外的很多學(xué)者做了相應(yīng)的研究。Mehrsai.A等使用啟發(fā)式算法（遺傳算法和模擬退火方法）和模糊系統(tǒng)混合方法，基于多目標(biāo)建模方法對推拉式混合供應(yīng)鏈物流網(wǎng)絡(luò)中的物流運作進(jìn)行研究［2］。葉耀華等將省際轉(zhuǎn)運網(wǎng)的優(yōu)化問題轉(zhuǎn)變?yōu)閹в袝r間以及容量限制的網(wǎng)絡(luò)優(yōu)化設(shè)計問題，并用拉格朗日松弛法和列生成法進(jìn)行了求解［3］。余明珠基于快遞公司網(wǎng)絡(luò)結(jié)構(gòu)以及快件配送模式的特點，構(gòu)建了一個能夠?qū)崿F(xiàn)裝卸一體化的車輛路徑模型，然后提出了針對該模型的求解方法，實現(xiàn)了運輸成本的最優(yōu)化以及貨物在途時間的加權(quán)最小化［4］。

快遞末端網(wǎng)點是快遞企業(yè)運營的空間集聚點，其數(shù)量和規(guī)模既可以反映出快遞企業(yè)可提供服務(wù)水平和服務(wù)能力的大小，也決定了快遞企業(yè)的生存發(fā)展空間。因此，末端網(wǎng)點優(yōu)化整合對于快遞企業(yè)兼并重組后的發(fā)展有著舉足輕重的作用。上述文獻(xiàn)中基于物流網(wǎng)絡(luò)基礎(chǔ)研究集中于定性的對物流整合各環(huán)節(jié)進(jìn)行論述，對其定量的深入研究較少；而基于物流網(wǎng)絡(luò)的優(yōu)化研究大多數(shù)都集中在滿足營運限制、道路能力限制等約束條件下總成本或總收益等為評價指標(biāo)的物流網(wǎng)絡(luò)的路徑優(yōu)化方面。而本文主要研究的是針對兩個快遞企業(yè)發(fā)生兼并重組［5］之后快遞物流末端網(wǎng)點的優(yōu)化整合問題，通過優(yōu)化整合達(dá)到滿足客戶需求、減少不必要的網(wǎng)點、優(yōu)化資源配置、減少成本的目的。從定量出發(fā)，在某一城市建立發(fā)生兼并重組的兩快遞企業(yè)間的末端網(wǎng)點優(yōu)化整合的數(shù)學(xué)模型。為克服標(biāo)準(zhǔn)遺傳算法早熟收斂問題，將免疫系統(tǒng)與遺傳算法相結(jié)合，形成免疫遺傳算法，并利用免疫遺傳算法具有良好的全局收斂能力這一優(yōu)點對其進(jìn)行求解，并最后確定滿足顧客需求下成本最小的網(wǎng)點優(yōu)化整合方案，從而建立起高效率、低費用、高服務(wù)水平的末端網(wǎng)點網(wǎng)絡(luò)［6］。

2　快遞末端網(wǎng)點優(yōu)化整合問題的數(shù)學(xué)模型

快遞末端網(wǎng)點優(yōu)化整合模型就是對兩企業(yè)現(xiàn)有的末端網(wǎng)點進(jìn)行重新優(yōu)化整合。該問題可以描述為：在客戶群和需求量已知的情況下，在現(xiàn)有的末端網(wǎng)絡(luò)中選出最少的末端網(wǎng)點，這些網(wǎng)點能夠服務(wù)所有的顧客需求點，而且所選網(wǎng)點的運營費用和顧客聚集點到達(dá)這些末端網(wǎng)點所需運輸費用的總和最小，并滿足以下條件：

（1）有兩個快遞公司發(fā)生兼并重組，需要對這兩個公司現(xiàn)有的末端網(wǎng)點進(jìn)行優(yōu)化整合，這里可以把這兩個公司在某一區(qū)域的末端網(wǎng)點看成一個整體進(jìn)行整合，兩公司的末端網(wǎng)點分布情況如圖1所示。

圖1　末端網(wǎng)點分布圖

（2）保留一個末端網(wǎng)點需要一定的運營費用，盡量用最少的網(wǎng)點去覆蓋所有需求點。

（3）假定所有末端網(wǎng)點有最大的服務(wù)半徑，超過這個范圍，顧客聚集點就不在該末端網(wǎng)點的服務(wù)范圍內(nèi)。

（4）顧客群聚集點到末端網(wǎng)點的運輸單價用兩點的距離表示。

設(shè)研究區(qū)域內(nèi)有n個顧客群聚集點，兩個企業(yè)共有m個待選末端網(wǎng)點，顧客群聚集點集合為A，待選末端網(wǎng)點集合為B。顧客群聚集點i的業(yè)務(wù)量為 pi（i=1，2，…，n），該業(yè)務(wù)量中被分配給待選末端網(wǎng)點j的部分為yij，從顧客群聚集點i到達(dá)待選末端網(wǎng)點j的單位運量的成本為cij，能夠服務(wù)顧客群聚集點i的待選末端網(wǎng)點的集合為B（i）。待選末端網(wǎng)點j的服務(wù)能力為qj（j= 1，2，…，m），其運營的固定成本為 fj，該網(wǎng)點服務(wù)范圍內(nèi)的顧客群聚集點的集合為A（j）。定義變量xi為0-1變量，該變量取值為1時，說明保留待選末端網(wǎng)點j，將其選為新網(wǎng)絡(luò)的網(wǎng)點，取值為0時，說明舍棄待選末端網(wǎng)點j?？山⑷缦驴爝f末端網(wǎng)點優(yōu)化整合問題的數(shù)學(xué)模型：

上述模型中，公式（1）為目標(biāo)函數(shù)保證保留的末端網(wǎng)點運營成本和顧客群聚集點與末端網(wǎng)點之間的運輸成本最小，約束（2）滿足每個客戶群集中點［7］的服務(wù)需求，約束（3）對保留末端網(wǎng)點的服務(wù)能力進(jìn)行限制，變量xi的約束保證了在原末端網(wǎng)點處最多保留一個末端網(wǎng)點。公式（4）表示變量xj的取值為0或1，公式（5）確保送達(dá)某點的業(yè)務(wù)量在客戶集聚區(qū)的總量以下。

3　快遞末端網(wǎng)點優(yōu)化整合問題的免疫遺傳算法

免疫遺傳算法［8］是通過利用生物免疫機(jī)制的一種改進(jìn)的遺傳算法，它主要是通過模擬和反映生物機(jī)體免疫系統(tǒng)的機(jī)理來達(dá)到優(yōu)化的目的。用求解問題的目標(biāo)函數(shù)表示免疫遺傳算法中的抗原，免疫系統(tǒng)產(chǎn)生的抗體作為對應(yīng)問題的解，利用抗原和抗體之間的親和力來表示可行解與最優(yōu)解的逼近程度。

假設(shè)免疫系統(tǒng)由N個抗體組成，采用符號集大小為S（若用二進(jìn)制進(jìn)行編碼，S=2，即采用0、1兩種字符），每個抗體基因長度為M。

免疫遺傳算法具體實現(xiàn)步驟如下：

（1）抗原輸入。把需要求解問題的目標(biāo)函數(shù)和各種約束作為免疫遺傳算法抗原輸入。

（2）產(chǎn)生初始群體。在免疫系統(tǒng)發(fā)生初次免疫應(yīng)答之后，初始抗體就隨機(jī)產(chǎn)生。當(dāng)免疫系統(tǒng)再次遇到抗原發(fā)生應(yīng)答時，免疫機(jī)制中的記憶功能就會啟動，部分初始抗體可以從記憶細(xì)胞中獲取，由于記憶細(xì)胞中抗體的適應(yīng)度值較高，通過免疫記憶功能可以提高算法收斂速度。

（3）計算抗體適應(yīng)度。分別計算出抗原和抗體之間、抗體與抗體之間的親和度。

（4）記憶細(xì)胞更新。找出與抗原親和度高的抗體，由于記憶細(xì)胞數(shù)目是有限制的，要用新找出的抗體取代記憶細(xì)胞中與其親和度最高的原有抗體，并將其加到記憶細(xì)胞中，完成記憶細(xì)胞更新。

（5）抗體生成的促進(jìn)和抑制。在尋找問題最優(yōu)解的過程中，如果抗體在種群中濃度過大超過一定范圍時，會導(dǎo)致求解過程停滯不前，造成算法過早的收斂，得不到全局最優(yōu)解，所以用控制抗體濃度的方法來解決抗體或相似抗體數(shù)量的問題。

用抗體和群體中與其相似抗體之間的比值來表示抗體濃度，即：

其中λ為相似度常數(shù)，一般取0.9≤λ≤1。計算出抗體濃度后，找出濃度較大的個體，記為個體1，2，...，t，

則定義該t個個體的濃度概率為：

其它N-t個個體的濃度概率為：

采用輪盤賭選擇法計算個體的適應(yīng)度概率pf。適應(yīng)度概率Pf和濃度概率Pd兩部分加權(quán)計算得到個體的選擇概率p，即：

式（10）中，a為親和系數(shù)，a＞0，pd，pf＜1。其中如果個體適應(yīng)度值越大，則該個體被選擇的概率也越大，而個體濃度越大，其選擇概率越小。利用這種方式不僅可以將適應(yīng)度高的個體保留，同時又能夠確保個體的多樣性。免疫遺傳算法采用傳統(tǒng)遺傳算法的選擇方式，計算出選擇概率p后，選擇合適的個體進(jìn)入下一代進(jìn)行遺傳操作。

（6）群體更新。免疫遺傳算法中變異和交叉操作與遺傳算法中方法相同。隨機(jī)挑出兩個抗體按照前面步驟中設(shè)定的變異概率進(jìn)行變異，之后相互之間再進(jìn)行交叉。重復(fù)執(zhí)行步驟3至步驟6步，直到符合算法的終止條件。

（7）終止條件判斷。所定參數(shù)滿足算法的終止條件，則算法結(jié)束并輸出最優(yōu)解；否則轉(zhuǎn)向步驟3。

4　算例分析

有兩個快遞公司A和B發(fā)生兼并重組，需要將其在城市C的末端網(wǎng)點進(jìn)行優(yōu)化整合，達(dá)到減少成本，并能最大限度地滿足客戶需求服務(wù)的目的。兩公司現(xiàn)有末端網(wǎng)點信息見表1，顧客聚集群信息見表2。

表1　末端網(wǎng)點信息

表2　顧客聚集群信息

根據(jù)算例條件進(jìn)行免疫遺傳算法求解該問題：

李吉林老師的情境教學(xué)告訴我們：“情感是語文教學(xué)的根”。學(xué)生主動參與，樂于參與，才是獲得高效、保持長久的情感體驗。而這種主動的情感需要教師去調(diào)動，培養(yǎng)。

（1）初始種群規(guī)模設(shè)定。從理論上講，群體規(guī)模越大種群的多樣性越高，找到越接近真實值的最優(yōu)解的概率越大。但如果群體的規(guī)模過大則會影響計算的效率，權(quán)衡計算分析效率和群體種群多樣性的需要，將初始群體規(guī)模取為50。

（2）解碼與編碼規(guī)則。本算法中采用實數(shù)進(jìn)行編碼，編碼長度由末端網(wǎng)點數(shù)量決定（假定有最后結(jié)果N個末端網(wǎng)點，編碼的長度就為N）。每個位置上的數(shù)字是由計算機(jī)隨機(jī)生成的1-11（有11個待整合的末端網(wǎng)點）之間的一個整數(shù)表示末端網(wǎng)點的編號。個體編碼示例如圖2所示，表明保留的1-N末端網(wǎng)點分別是3、5…8。

圖2　編碼示例

（3）優(yōu)化參數(shù)設(shè)定。對于免疫遺傳算法的參數(shù)見表3。

由matlab實現(xiàn)的算法計算后的結(jié)果如下［9］：

使用2個網(wǎng)點的最小成本為：3.816 8e+07；

使用3個網(wǎng)點的最小成本為：3.187 8e+07；

使用4個網(wǎng)點的最小成本為：2.928 8e+07；

使用5個網(wǎng)點的最小成本為：2.741 6e+07；

表3　算法參數(shù)表

使用6個網(wǎng)點的最小成本為：2.542 9e+07；

使用7個網(wǎng)點的最小成本為：2.451 4e+07；

使用8個網(wǎng)點的最小成本為：2.451 8e+07；

使用9個網(wǎng)點的最小成本為：2.476 3e+07；

使用10個網(wǎng)點的最小成本為：2.510 7e+07；

使用11個網(wǎng)點的最小成本為：2.547 5e+07。

根據(jù)計算結(jié)果得到最優(yōu)方案為保留7個網(wǎng)點，總成本為2.451 4e+07，所保留的末端網(wǎng)點分別為1號、2號、3號、5號、6號、8號、9號，保留末端網(wǎng)點結(jié)果如圖3所示。

圖3　保留的末端網(wǎng)點

5　結(jié)語

在快遞企業(yè)兼并重組的條件下，對快遞的末端網(wǎng)點優(yōu)化整合問題進(jìn)行研究對于快遞企業(yè)的長遠(yuǎn)發(fā)展有重要的意義。本文提出了在滿足各顧客群聚集點的服務(wù)需求和各末端網(wǎng)點的服務(wù)能力的前提下，建立快遞末端網(wǎng)點優(yōu)化整合模型。在對模型求解過程中選用免疫遺傳算法，并介紹免疫遺傳算法的相關(guān)原理、特點以及算法步驟。最后運用算例對網(wǎng)點優(yōu)化整合模型進(jìn)行求解驗證，表明了該算法的可行性。

［1］國務(wù)院.關(guān)于進(jìn)一步促進(jìn)資本市場健康發(fā)展的若干意見［EB/ OL］.2014-05-08.

［2］Mehrsai A，Karimi H R，Thoben K D，et al.Using metaheuristic and fuzzy system for the optimization of material pull in a push-pull flow logistics network［J］.Mathematical Problems in Engineering，2013.

［3］葉耀華，王律，楊文濤，等.我國郵政網(wǎng)絡(luò)的優(yōu)化設(shè)計方法［J］.管理工程學(xué)報，2004，18（2）：39-43.

［4］余明珠，李建斌，雷東.裝卸一體化的車輛路徑問題及基于插入法的新禁忌算法［J］.中國管理科學(xué)，2010，18（4）：89-95.

［5］王曉東.中國民營快遞企業(yè)現(xiàn)狀與發(fā)展建議［J］.企業(yè)導(dǎo)報，2010，（3）：129-130.

［6］張洪斌，聶玉超.中國快遞企業(yè)的網(wǎng)絡(luò)系統(tǒng)分析［J］.物流技術(shù)，2009，（9）：35-37.

［7］國家發(fā)改委經(jīng)濟(jì)運行司，南開大學(xué)物流研究中心，中國物流市場發(fā)展報告［M］.北京：機(jī)械工業(yè)出版社，2005.

［8］龔非.人工免疫算法及SOPC實現(xiàn)［D］.哈爾濱：哈爾濱工程大學(xué)，2009.

［9］陳麗安.免疫遺傳算法在MATLAB環(huán)境中的實現(xiàn)［J］.福州大學(xué)學(xué)報，2004，（5）：554-559.

Optimization and Integration of Express Delivery Terminals Based on Immunity GA

Gao Ruiping1，Ji Shouwen1，Zhang Yongxin2
（1. MOE Key Laboratory for Urban Traffic Complex System Theories Technologies， Beijing Jiaotong University， Beijing 100044；2. Bank of Communication Rizhao Branch， Rizhao 276800， China）

In this paper， on the basis of the principle in the optimization and integration of the terminal network， we established theoptimization model with the minimization of the terminal operational cost and transportation cost as the objective and the satisfaction of theservice demand of the customer groups and the service capacity of the terminals as the constraint， and then in view of the characteristics of themodel， selected the immunity genetic algorithm to derive the location and ultimate cost of the express parcel sorting center. At the end，through a numerical example， we demonstrated the validity of the algorithm in this field.

express delivery terminal； optimization and integration； immunity genetic algorithm

F224；F252.24

A

1005-152X（2016）07-0083-04

10.3969/j.issn.1005-152X.2016.07.019

2016-05-23

科技部支撐計劃課題“供應(yīng)鏈物流實時監(jiān)測、跟蹤與管理技術(shù)研究”（2014BAH23F01）

高瑞萍，北京交通大學(xué)碩士研究生，研究方向：物流信息化；紀(jì)壽文（1967-），博士后，副教授，研究方向：物流工程、物流信息化。