基于節約遺傳算法的電子商務配送中心選址

唐棣華，衛 欣

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

1 引言

信息通信技術和網絡技術的飛速發展，在一定程度上加快了經濟全球化和一體化的步伐。產品生命周期不斷縮短，客戶需求的個性化、多樣化日益明顯，企業間的競爭日趨激烈，現階段傳統的商業模式很難應對不斷變化的市場需求。因此，企業的經營模式必須迅速適應這些變化。

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

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

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

2 節約遺傳算法

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

通過節約遺傳算法能夠獲取到全局最優性能，并且在許多領域得到了廣泛的應用。具體算法如下所示：

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

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

3)適應度函數?？梢愿鶕m應度的大小來選擇個體。在分布問題中，最短路徑D是響應適應度函數的標準。D越大，適應度函數越??；D越小，適應度函數越大。

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

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

X=123|4567

Y=765|4321

(1)

經過交叉處理后獲得子代的公式為

X′=123|4567

Y′=765|4321

(2)

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

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

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

8)重復選擇、交叉、變異三個步驟，在最大進化函數之前完成，按照相應的規格實施合理排列，得到節約遺傳算法表達式為

(3)

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

3 電子商務配送中心選址

3.1 物流配送中心模式

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

現代物流運輸組織的主要方式是在多式聯運和門到門運輸的基礎上形成點對點的網絡化物流運輸。配送中心和物流中心能否成為網絡化物流運輸中的節點，在很大程度上取決于配送中心是否具有完善的物流服務功能。

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

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

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

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

配送中心選址作為某一區域內所有消費者的地址集[8]，選擇一定數量的地址建立配送中心，從而建立出一系列的配送區域，實現各個需求點的配送任務，使在某一區域內建立的配送系統的總配送成本最小化選擇點和每個需求點。因此，在現有的客觀條件下，使整個系統的物流成本最低，使客戶體驗較好的服務效果。

所謂可變成本，通常來說是指物流配送中心在產品配送過程中所發生的管理成本。在許多模型中，把可變成本當作線性函數，由于物流配送中心的實際成本難以與實際情況相匹配，運算出的最優方案與實際的最優狀態結果相差甚遠，特別是在電子商務環境下，當物流配送批量較小且多批次時，可變成本將不作為線性函數[9]。

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

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

(4)

(5)

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

(6)

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

(7)

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

(8)

(9)

上述公式描述了，貨物從工廠K運出物流配送中心I內的貨物數量應不超出其生產能力。

tij+Tjk≤fk

(10)

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

Xij≥0，wki≥0

(11)

Yi∈[0，1]

(12)

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

4 實驗分析

假設在一定的時間段內，從一個區域內隨機選擇的多個客戶，接收到配送需求訂單，最大迭代次數為200次。采用節約遺傳算法對每個訂單實施準確分析，從而實現配送中心最優選址。每個客戶從零開始用十進制數字編號，每個客戶的需求是已知的。

為了檢驗該算法的有效性，將文獻[1]方法、文獻[2]方法與所提方法的結果進行了比較，具體內容如下所示。

表1 所提方法計算結果

表2 文獻[1]方法計算結果

表3 文獻[2]方法計算結果

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

從電子商務環境下物流配送中心選址評價指標體系可以看出，各指標從不同角度反映了選址方案的合理性。客戶數優化過程如下所示。

圖2 客戶數優化過程

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

當客戶數不同時，程序運行時間與隨機選擇的客戶數的關系如下所示。

圖3 程序運行時間與隨機選擇的客戶數的關系

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

5 結論

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