基于節(jié)約遺傳算法的電子商務(wù)配送中心選址

唐棣華，衛(wèi) 欣

(1. 杭州電子科技大學(xué)，浙江 杭州 310018；2. 南京林業(yè)大學(xué)，江蘇 南京 210037)

1 引言

信息通信技術(shù)和網(wǎng)絡(luò)技術(shù)的飛速發(fā)展，在一定程度上加快了經(jīng)濟(jì)全球化和一體化的步伐。產(chǎn)品生命周期不斷縮短，客戶需求的個性化、多樣化日益明顯，企業(yè)間的競爭日趨激烈，現(xiàn)階段傳統(tǒng)的商業(yè)模式很難應(yīng)對不斷變化的市場需求。因此，企業(yè)的經(jīng)營模式必須迅速適應(yīng)這些變化。

電子商務(wù)是在這種形勢下出現(xiàn)的一種新的商業(yè)模式。大量跨國公司的出現(xiàn)和全球采購模式的日益普及對電子商務(wù)的商業(yè)模式和服務(wù)效率提出了更高的要求。物流服務(wù)作為實(shí)現(xiàn)電子商務(wù)最終目標(biāo)的重要組成部分，其質(zhì)量和效率對電子商務(wù)企業(yè)的經(jīng)營績效有著重要的影響。研究有效的物流配送方法對于解決電子商務(wù)問題具有重要意義。

郝彩霞等人[1]提出一種基于電動物流車輛的充換電設(shè)施在充換電模式下的選址問題。分別建立了無充電行為的路徑規(guī)劃和車輛調(diào)度模型以及以最小化電費(fèi)、車輛固定行程費(fèi)用、機(jī)會費(fèi)用和懲罰費(fèi)用之和為目標(biāo)的充換電設(shè)施選址模型。對收費(fèi)交換模式下設(shè)施的選址決策和配送總成本進(jìn)行了比較分析。提高收費(fèi)速度或選擇交換模式可以降低配送成本。胡利利等人[2]提出一種基于多冷鏈物流中心選址。根據(jù)冷鏈物流中心的時效性特點(diǎn)，對節(jié)點(diǎn)需求和輻射半徑進(jìn)行約束，以需求為距離權(quán)重，將其納入目標(biāo)函數(shù)，建立相應(yīng)的選址分配數(shù)學(xué)模型。借助生物免疫系統(tǒng)的多樣性和自我調(diào)節(jié)能力，利用部分匹配原理計算抗體之間的親和力，設(shè)計了自適應(yīng)懲罰機(jī)制、免疫變異和精英保留策略，以保持種群的多樣性和優(yōu)良性精英階層。并與文獻(xiàn)對比，證明了該算法的有效性。孟燕萍等人[3]提出一種基于災(zāi)害下應(yīng)急物資的動態(tài)選址問題，通過衡量被害人候補(bǔ)材料的二次運(yùn)輸成本和心理懲罰成本，建立多目標(biāo)混合整數(shù)規(guī)劃模型，以雅安地震為背景，將災(zāi)后72小時劃分為6個時段，每個時段應(yīng)根據(jù)不同的道路恢復(fù)情況而有所不同，并確定了各時段應(yīng)急物資的選址方案，驗(yàn)證了模型的實(shí)用性。

但是上述三種方法選址時間較長、耗費(fèi)較高。提出一種基于節(jié)約遺傳算法的電子商務(wù)配送中心選址方法。

2 節(jié)約遺傳算法

電子商務(wù)的快速發(fā)展為企業(yè)和消費(fèi)者搭建了良好的平臺?，F(xiàn)代物流配送模式可以實(shí)現(xiàn)配送模式的自動化、社會化、合理化和集約化，使貨物暢通無阻，充分發(fā)揮貨物的效用。它不僅可以減少庫存，降低物流成本，加快資金周轉(zhuǎn)，刺激社會需求，而且可以提高全社會的經(jīng)濟(jì)效益。然而，目前電子商務(wù)與物流配送體系的銜接不夠、物流管理體系不完善等問題制約了電子商務(wù)環(huán)境下物流配送的進(jìn)一步發(fā)展。

通過節(jié)約遺傳算法能夠獲取到全局最優(yōu)性能，并且在許多領(lǐng)域得到了廣泛的應(yīng)用。具體算法如下所示：

1)所需信息。根據(jù)訂單分析，可以得到客戶的配送需求，并設(shè)計程序計算出每個客戶的配送需求兩個客戶之間的線性距離(用二維數(shù)組表示)以及每個客戶點(diǎn)到配送中心的距離。

2)初始化填充。需要對N個客戶提供排序，可以表示為0，1，…(N-1)。排序之后，生成一系列，共有Q個組。

3)適應(yīng)度函數(shù)?？梢愿鶕?jù)適應(yīng)度的大小來選擇個體。在分布問題中，最短路徑D是響應(yīng)適應(yīng)度函數(shù)的標(biāo)準(zhǔn)。D越大，適應(yīng)度函數(shù)越??；D越小，適應(yīng)度函數(shù)越大。

4)選擇。根據(jù)適應(yīng)度函數(shù)，選擇每一代的新個體。在自然進(jìn)化過程中，親本通過選擇和競爭對親本的適應(yīng)性進(jìn)行排序。根據(jù)設(shè)定的種群規(guī)模，根據(jù)一定的選擇概率，將一些優(yōu)秀個體保留為下一代，這樣的選擇過程更容易保留優(yōu)秀基因，使具有較大生存能力的個體按照自然規(guī)律進(jìn)入下一代的概率更大化選擇。

5)交叉路口[4]。按交叉概率隨機(jī)選擇當(dāng)代人群中需要交叉的個體，分成X和Y兩個組，將此作為親本進(jìn)一步實(shí)施交叉，會生成X′與Y′兩個后代。本文針對遺傳算法不能遍歷所有用戶的缺點(diǎn)實(shí)施了優(yōu)化，其表達(dá)式下：

X=123|4567

Y=765|4321

(1)

經(jīng)過交叉處理后獲得子代的公式為

X′=123|4567

Y′=765|4321

(2)

該方法在很大程度上提高了算法的效率，可以遍歷所有用戶，并能盡可能地保留好的基因片段。

6)變異。選擇隨人口變化概率而變化的個體進(jìn)行合理轉(zhuǎn)換得到新的個體。在規(guī)劃過程中，需要注意避免全局最優(yōu)解收斂過快的現(xiàn)象，也就是保持種群的多樣性。

7)在隨機(jī)控制參數(shù)進(jìn)行篩選過程中，需要充分考慮參數(shù)范圍，以保證節(jié)約遺傳算法的高效性[5]。一般來說，控制參數(shù)的范圍是N=20～200，pc=0.5～1.0，pm=0～0.05。

8)重復(fù)選擇、交叉、變異三個步驟，在最大進(jìn)化函數(shù)之前完成，按照相應(yīng)的規(guī)格實(shí)施合理排列，得到節(jié)約遺傳算法表達(dá)式為

(3)

節(jié)約遺傳算法的目的是在不受任何限制情況下解決車輛運(yùn)行路徑問題。為解決車輛路徑問題提供了一種簡單可行的基本方法。

3 電子商務(wù)配送中心選址

3.1 物流配送中心模式

伴隨互聯(lián)網(wǎng)的快速發(fā)展和居民消費(fèi)習(xí)慣的改變，電子商務(wù)企業(yè)得到了突飛猛進(jìn)的發(fā)展。物流配送中心具有多種功能，體現(xiàn)在物流服務(wù)的實(shí)現(xiàn)上。通過產(chǎn)生的實(shí)踐，克服空間障礙，促進(jìn)商務(wù)產(chǎn)品完成消費(fèi)者所需的交易活動，實(shí)現(xiàn)配送中心商品的增值。消費(fèi)者對物流配送中心有著不同的需求。由于所提供的服務(wù)不同，整個供應(yīng)鏈的功能也會有很大的不同。但作為物流配送中心，其整體使用有關(guān)聯(lián)。雖然功能不同，但應(yīng)具備商品周轉(zhuǎn)、倉儲管理、流通加工等基本功能[6]。

現(xiàn)代物流運(yùn)輸組織的主要方式是在多式聯(lián)運(yùn)和門到門運(yùn)輸?shù)幕A(chǔ)上形成點(diǎn)對點(diǎn)的網(wǎng)絡(luò)化物流運(yùn)輸。配送中心和物流中心能否成為網(wǎng)絡(luò)化物流運(yùn)輸中的節(jié)點(diǎn)，在很大程度上取決于配送中心是否具有完善的物流服務(wù)功能。

電子商務(wù)配送中心選址是現(xiàn)階段物流發(fā)展的首要任務(wù)，具有較好的空間與前景。在對物品配送時，大量的分銷被用來減少分銷的頻率，從而降低分銷的成本。傳統(tǒng)企業(yè)主要制造產(chǎn)品來獲取利潤，對物流配送服務(wù)方面關(guān)注較少。

在電子商務(wù)模式下，選址是否合理，會嚴(yán)重影響物品配送的合理化和實(shí)時性，導(dǎo)致企業(yè)收益較低的現(xiàn)象發(fā)生。許多物流配送中心選址只考慮到選址的成本，以及總收益最大化，而不是關(guān)心消費(fèi)者。但實(shí)際生活中，有很多消費(fèi)者喜愛網(wǎng)絡(luò)購物，并且分散地域十分廣闊，配送效果需求旺盛，對配送中心的選址影響很大。需要確定物流配送中心選址方案確定最優(yōu)選址策略的規(guī)劃模型[7]。

圖1 物流配送中心選址策略圖

3.2 物流配送中心選址模型約束條件

配送中心選址作為某一區(qū)域內(nèi)所有消費(fèi)者的地址集[8]，選擇一定數(shù)量的地址建立配送中心，從而建立出一系列的配送區(qū)域，實(shí)現(xiàn)各個需求點(diǎn)的配送任務(wù)，使在某一區(qū)域內(nèi)建立的配送系統(tǒng)的總配送成本最小化選擇點(diǎn)和每個需求點(diǎn)。因此，在現(xiàn)有的客觀條件下，使整個系統(tǒng)的物流成本最低，使客戶體驗(yàn)較好的服務(wù)效果。

所謂可變成本，通常來說是指物流配送中心在產(chǎn)品配送過程中所發(fā)生的管理成本。在許多模型中，把可變成本當(dāng)作線性函數(shù)，由于物流配送中心的實(shí)際成本難以與實(shí)際情況相匹配，運(yùn)算出的最優(yōu)方案與實(shí)際的最優(yōu)狀態(tài)結(jié)果相差甚遠(yuǎn)，特別是在電子商務(wù)環(huán)境下，當(dāng)物流配送批量較小且多批次時，可變成本將不作為線性函數(shù)[9]。

電子商務(wù)中心選址模型充分考慮了時間約束，能夠在許多方面實(shí)現(xiàn)最優(yōu)選擇，也可以優(yōu)化運(yùn)營商的利益。進(jìn)一步將商品的需求、流通和生產(chǎn)在正確的時間、地點(diǎn)、價格和方便的方式結(jié)合起來，以消費(fèi)者為中心，最大限度地保護(hù)消費(fèi)者的權(quán)益[10]。物流配送是制約電子商務(wù)發(fā)展的瓶頸。在某一地區(qū)的需求點(diǎn)的地址，其中，由已建成的物流配送中心和客戶構(gòu)成的物流配送系統(tǒng)總成本最小，以備選地址的數(shù)量為配送中心?？偝杀景Ｐ椭形锪髋渌椭行募霸O(shè)施建設(shè)或租賃的一次性投資、配送中心可變成本、固定管道管理成本、運(yùn)輸成本等多層次物流配送中心選址，從工廠到配送中心的運(yùn)輸包括二次運(yùn)輸，即從工廠到物流配送中心的運(yùn)輸和物流配送[11]，即tij+Tki≤fk。

因此，對于電子商務(wù)環(huán)境下物流配送中心選址的重要性，對傳統(tǒng)的多層次物流配送中心選址模型進(jìn)一步實(shí)施改進(jìn)，結(jié)合節(jié)約遺傳算法，提出了一種適合電子商務(wù)環(huán)境下物流配送中心選址的非線性混合模型0-1編程，cij作為配送中心i至用戶j的運(yùn)輸單價，hki作為k廠至i配送中心的運(yùn)輸單價，ui作為i配送中心的貨物流通單價；fi作為i配送中心的固定運(yùn)營成本，tij作為i廠至j物流配送中心的運(yùn)輸時間，Tjk作為i物流配送中心的運(yùn)輸時間j到用戶k，fk作為用戶k對配送時間的限制，aj作為用戶j的需求；bi作為配送中心i的容量，ck作為工廠k的供給，m作為備用配送中心的數(shù)量，n作為用戶數(shù)量，P作為備用配送中心的最大數(shù)量，l作為工廠數(shù)量，具體約束條件表達(dá)式如下

(4)

(5)

上述公式代表配送中心能夠滿足用戶的需求。

(6)

式(6)代表配送中心的采購數(shù)量小于配送中心的能力

(7)

式(7)作為選擇的配送中心數(shù)量不大于最大數(shù)量P。

(8)

(9)

上述公式描述了，貨物從工廠K運(yùn)出物流配送中心I內(nèi)的貨物數(shù)量應(yīng)不超出其生產(chǎn)能力。

tij+Tjk≤fk

(10)

式(10)描述了從工廠到物流配送中心的運(yùn)輸時間和從物流配送中心到用戶的運(yùn)輸時間之和，應(yīng)小于或等于用戶對產(chǎn)品的配送時間限制。

Xij≥0，wki≥0

(11)

Yi∈[0，1]

(12)

其中：i=1，2，…m，j=1，2，…n，k=1，2，…l。Xij作為配送中心i至用戶j的運(yùn)輸量，wki作為k廠至配送中心i的運(yùn)輸量[12]。

4 實(shí)驗(yàn)分析

假設(shè)在一定的時間段內(nèi)，從一個區(qū)域內(nèi)隨機(jī)選擇的多個客戶，接收到配送需求訂單，最大迭代次數(shù)為200次。采用節(jié)約遺傳算法對每個訂單實(shí)施準(zhǔn)確分析，從而實(shí)現(xiàn)配送中心最優(yōu)選址。每個客戶從零開始用十進(jìn)制數(shù)字編號，每個客戶的需求是已知的。

為了檢驗(yàn)該算法的有效性，將文獻(xiàn)[1]方法、文獻(xiàn)[2]方法與所提方法的結(jié)果進(jìn)行了比較，具體內(nèi)容如下所示。

表1 所提方法計算結(jié)果

表2 文獻(xiàn)[1]方法計算結(jié)果

表3 文獻(xiàn)[2]方法計算結(jié)果

從表中可以看出，當(dāng)用戶數(shù)為30、60以及100時，其平均最優(yōu)值和最優(yōu)結(jié)果均小于文獻(xiàn)[1]方法、文獻(xiàn)[2]方法，說明所提方法獲得最優(yōu)路徑的效果較好。所提方法的相對誤差小于文獻(xiàn)[1]方法、文獻(xiàn)[2]方法，說明波動結(jié)果較小，更容易快速有效地確定優(yōu)化的分布路徑，減少了分布距離。

從電子商務(wù)環(huán)境下物流配送中心選址評價指標(biāo)體系可以看出，各指標(biāo)從不同角度反映了選址方案的合理性?？蛻魯?shù)優(yōu)化過程如下所示。

圖2 客戶數(shù)優(yōu)化過程

從圖2中可知，當(dāng)用戶數(shù)為N=30和N=60時，三種算法在迭代過程中的配送路徑長度的收斂性。其趨勢呈現(xiàn)逐漸收斂現(xiàn)象。所提方法的收斂次數(shù)比文獻(xiàn)[1]方法、文獻(xiàn)[2]方法更少。當(dāng)所提方法運(yùn)行到200次時，獲得的最短路徑有了顯著的改進(jìn)。得出節(jié)約遺傳算法具有較高的進(jìn)化起點(diǎn)，易于找到最優(yōu)解

當(dāng)客戶數(shù)不同時，程序運(yùn)行時間與隨機(jī)選擇的客戶數(shù)的關(guān)系如下所示。

圖3 程序運(yùn)行時間與隨機(jī)選擇的客戶數(shù)的關(guān)系

在圖3中，從實(shí)際值的連接可以看出，程序的運(yùn)行時間隨著客戶數(shù)量的增加而增加。因此，客戶數(shù)量與程序的運(yùn)行時間成正比。

5 結(jié)論

針對電子商務(wù)環(huán)境下物流配送中心的選址問題，其運(yùn)算過程較為復(fù)雜，為了驗(yàn)證本文所提方法的高效性。依據(jù)節(jié)約型遺傳算法對電子商務(wù)配送路徑進(jìn)行優(yōu)化，得到全局最優(yōu)路徑。獲取物流配送中心的具體模式，使其滿足現(xiàn)實(shí)需求。構(gòu)建電子商務(wù)配送中心選址模型，利用目標(biāo)函數(shù)計算了配送中心的可變成本和時間約束，能夠減少配送時耗費(fèi)的成本。其對電子商務(wù)配送中心的模式進(jìn)行了合理改進(jìn)，使之更加實(shí)用化，可以大大提高物流配送系統(tǒng)的服務(wù)水平。實(shí)驗(yàn)結(jié)果表明該方法具有高效性和優(yōu)越性。