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

高瑞萍，紀壽文，張永昕

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

?

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

高瑞萍1，紀壽文1，張永昕2

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

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

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

1　引言

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

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

2　快遞末端網點優(yōu)化整合問題的數學模型

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

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

圖1　末端網點分布圖

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

（3）假定所有末端網點有最大的服務半徑，超過這個范圍，顧客聚集點就不在該末端網點的服務范圍內。

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

設研究區(qū)域內有n個顧客群聚集點，兩個企業(yè)共有m個待選末端網點，顧客群聚集點集合為A，待選末端網點集合為B。顧客群聚集點i的業(yè)務量為 pi（i=1，2，…，n），該業(yè)務量中被分配給待選末端網點j的部分為yij，從顧客群聚集點i到達待選末端網點j的單位運量的成本為cij，能夠服務顧客群聚集點i的待選末端網點的集合為B（i）。待選末端網點j的服務能力為qj（j= 1，2，…，m），其運營的固定成本為 fj，該網點服務范圍內的顧客群聚集點的集合為A（j）。定義變量xi為0-1變量，該變量取值為1時，說明保留待選末端網點j，將其選為新網絡的網點，取值為0時，說明舍棄待選末端網點j。可建立如下快遞末端網點優(yōu)化整合問題的數學模型：

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

4　算例分析

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

表1　末端網點信息

表2　顧客聚集群信息

根據算例條件進行免疫遺傳算法求解該問題：

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

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

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

圖2　編碼示例

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

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

使用2個網點的最小成本為：3.816 8e+07；

使用3個網點的最小成本為：3.187 8e+07；

使用4個網點的最小成本為：2.928 8e+07；

使用5個網點的最小成本為：2.741 6e+07；

表3　算法參數表

使用6個網點的最小成本為：2.542 9e+07；

使用7個網點的最小成本為：2.451 4e+07；

使用8個網點的最小成本為：2.451 8e+07；

使用9個網點的最小成本為：2.476 3e+07；

使用10個網點的最小成本為：2.510 7e+07；

使用11個網點的最小成本為：2.547 5e+07。

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

圖3　保留的末端網點

5　結語

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

［1］國務院.關于進一步促進資本市場健康發(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］葉耀華，王律，楊文濤，等.我國郵政網絡的優(yōu)化設計方法［J］.管理工程學報，2004，18（2）：39-43.

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

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

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

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

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

［9］陳麗安.免疫遺傳算法在MATLAB環(huán)境中的實現(xiàn)［J］.福州大學學報，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

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

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