基于改進遺傳算法的企業(yè)物流配送網(wǎng)絡的構(gòu)建

林　森，洪　偉

（1.福建農(nóng)林大學 交通與土木工程學院，福建 福州 35002；2.福建農(nóng)林大學 林學院，福建 福州 350002）

基于改進遺傳算法的企業(yè)物流配送網(wǎng)絡的構(gòu)建

林森1，洪偉2

（1.福建農(nóng)林大學 交通與土木工程學院，福建 福州 35002；2.福建農(nóng)林大學 林學院，福建 福州 350002）

摘要：以居家通企業(yè)的訂單數(shù)據(jù)和配送網(wǎng)絡為研究對象，采用改進的遺傳算法對其合作店鋪的服務網(wǎng)絡計算，獲得最短配送路線與實際配送路線、標準遺傳算法計算的路線進行對比并通過GIS地圖標注，同時研究當企業(yè)規(guī)模擴大，合作店鋪需配送的酒店數(shù)量增加后在改進遺傳算法計算下的配送路徑。結(jié)果表明：實際配送路線為5.33 km，標準遺傳算法路線為5.04 km，改進遺傳算法路線結(jié)果在GIS地圖上表現(xiàn)最優(yōu)為4.33 km，并且當增加5個配送節(jié)點后，配送路線長為8.5 km。

關鍵詞：居家通企業(yè)；改進遺傳算法；Mat1ab

物流配送是商品流通中至關重要的環(huán)節(jié)，是物流企業(yè)的運作主體，掌握市場的起伏變動，直接接觸客戶最滿意的需求，從而實現(xiàn)整個物流網(wǎng)絡價值，其效率是判斷企業(yè)效率高低的重要指標[1]。了解客戶最終需求，企業(yè)通過構(gòu)建一個較為齊全的物流配送網(wǎng)絡以便更好的為客戶提供服務。以物流節(jié)點為網(wǎng)絡運營貨物的集散載體，運輸路徑為網(wǎng)絡運營貨物的連接橋梁，二者緊密合作，將貨物從供應商到客戶之間形成一條科學合理的動態(tài)運輸鏈[2]。根據(jù)我國2014年統(tǒng)計的5.6萬億元的運輸費用，其中我國總物流費用約占52.9%，而發(fā)達國家對物流流程進行優(yōu)化后，可節(jié)約5%～20%的總運輸成本[3]。因此，是否合理安排配送路徑會影響到企業(yè)的整體效益和客戶滿意度，企業(yè)也急需時效性強、成本低、服務質(zhì)量高且能快速規(guī)劃路線的物流配送平臺。

1　“居家通”商旅服務平臺

“居家通”商旅服務平臺是專門為商旅人士打造的服務性平臺。它由龐大商旅消費群體和酒店周邊能夠提供高產(chǎn)品、快配送、優(yōu)服務的商家組成。入住酒店的客戶可從酒店提供的客戶端在酒店下單，形成委托配送任務，業(yè)務員進行接單匯總處理，通過配送網(wǎng)絡分析客戶的相關信息并且通知周圍的店鋪，由店鋪通過本身所具有的貨物種類進行進貨儲存、分揀、裝載貨物和路線的選擇等安排配送，在客戶需求在規(guī)定時間內(nèi)將貨物送達到地點后，由最終客戶進行確認簽收。

通過調(diào)查2014年3—10月居家通企業(yè)的各個店鋪訂單統(tǒng)計總量（見圖1），總訂單量有406份，而與居家通企業(yè)合作店鋪約97家，合作商旅酒店約394家。目前雖然客戶通過居家通平臺下單情況還未達到較大規(guī)模，但每月均呈現(xiàn)上升趨勢，該企業(yè)正在快速成長階段。居家通企業(yè)做為首家商旅服務企業(yè)仍舊擁有不足之處。

圖1　2014年居家通企業(yè)每月訂單數(shù)量

1.1配送的產(chǎn)品多品種、小批量

由于店鋪提供的商品多種多樣，而且顧客是來自不同地區(qū)的商旅人士，所以對商品需求是多樣的，而且能帶產(chǎn)品重量是有限，這就是“消費多樣化、需求多樣化”，這導致訂單較為分散，每個酒店旅客需要多樣化服務，向不同的店鋪訂購產(chǎn)品，這也對配送提出較高要求。

1.2配送時間不定

根據(jù)訂單分析可知訂單的時間不均衡且數(shù)量少，每家店鋪平均每天不到一份的訂單，為了能提供優(yōu)服務將產(chǎn)品即時的送到顧客手上，店鋪以“客戶第一”為宗旨，再加上顧客下單時間不確定，就導致店鋪配送的時間不確定。因此，店鋪只能根據(jù)經(jīng)驗提供配送服務。

1.3未規(guī)劃配送路徑

調(diào)研過程中發(fā)現(xiàn)在產(chǎn)品配送過程中，部分配送人員對配送路徑?jīng)]有規(guī)劃，甚至部分配送人員根據(jù)訂單順序先到一家賓館后，然后再查找去下一家賓館路徑。這不但增加配送成本，還會導致物流配送路徑變長，加重交通負擔，造成倒流運輸、迂同運輸、單程運輸和空駛等現(xiàn)象[4]。

物流配送是實現(xiàn)居家通企業(yè)規(guī)模效益的關鍵因素，居家通企業(yè)應認識到自身配送尚未形成規(guī)模，抓住我國物流企業(yè)發(fā)展趨勢的機遇，解決物流配送問題，提高配送效率。因此本文從居家通及與其合作店鋪的配送現(xiàn)狀出發(fā)，對配送網(wǎng)絡的需求進行研究，構(gòu)建物流配送網(wǎng)絡模型結(jié)合改進遺傳算法及實際路線狀況，尋求到了多個配送賓館之間的最短配送路徑，這將有效提高提升居家通企業(yè)的綜合競爭力。

2　基于改進遺傳算法構(gòu)建居家通企業(yè)物流配送路線模型

2.1構(gòu)建目標函數(shù)

該企業(yè)的配送路線模型思路為：在每個店鋪接到訂單后，從店鋪中選取車輛裝上商品，將商品送到n個不同的酒店中，再進行酒店內(nèi)各個消費者的配送，最終回到出發(fā)點，因此該配送路線為巡回路徑，采用Grefenstette等提出巡回路徑的整數(shù)編碼方法[5-6]。

假設路線中的全部酒店構(gòu)成列表K，店鋪與每位酒店分別記為1-n并按其順序排列放到表K中，所以該路徑的配送順序是H=（h0，h1，h2，…h(huán)n）并規(guī)定每次配送完一個酒店后就在列表K中把該點除去，用第i （i=1，2，…，n）個所配送酒店，hi在所有未配送酒店列表K-{h0，h1，h2，…h(huán)i-1}對應的位置序列號bi（1≤bi≤ni+1）就可表示為具體配送給哪個酒店，由此直到將K中的需求點全部送完，bi按照配送的先后順序構(gòu)成新的列表：B=（b1，b2，…，bn），就是可表示一條巡回配送路線，即為遺傳算法中一個個的基因。按此規(guī)則偵查所有的路徑長度，尋求最短的配送路線其目標函數(shù)為：

其中：b0為店鋪（配送中心）；bi（i=1，2，…，n）為第i個酒店；d（0，1）為店鋪到第1位酒店之間的距離；d（n，0）為第n個酒店到店鋪的距離；d（i，j）（i= 1，2，…，n）為i到j之間的距離，且d（i，j）=d（j，i）。

2.2改進遺傳算法模型架構(gòu)

（1）初始群體的生成。經(jīng)過編碼將數(shù)據(jù)轉(zhuǎn)換成染色體的基因鏈形式，并對種群規(guī)模進行確定，設進化的代數(shù)計數(shù)器h=0，最大代數(shù)為H，然后隨機產(chǎn)生M個不同的染色體構(gòu)成算法的初始解P（0），并把其當成開始迭代的初始點。

（2）評價適應度函數(shù)值。從P（h）群體中進行全局搜索，并從中找出適應度最高或接近最優(yōu)的個體。

（3）選擇。從現(xiàn)有的種群中選出對自然環(huán)境適應能力強大的個體，將其作為父代進一步繁衍后代。為了能夠收斂全局得到最優(yōu)解的個體，選取最佳個體保留與賭輪選擇的方法相互結(jié)合，得到下一代個體。

Step 1：采用改良圈的近似算法，求得一個初始種群P（h）。

Step 2：從初始化群體中P（h）找出適應度最大的個體，保證父代種群中最優(yōu)良的特性遺傳給子代，用b表示。

Step 3：假如種群中的個體q經(jīng)過賭輪選擇的方法求出的選擇概率為P（q）：

Step 4：設Z（0）=0，Z（q）=Z（1）+Z（2）+…+Z（q），（q=1，2，…，n）

通過以上操作后，在[0，1)區(qū)間內(nèi)生成n-1個均勻分布的隨機數(shù)列Ai（i=1，2，…，n-1），每一個隨機序列與群體的各個個體相對應，并對n-1個個體按順序進行選擇檢測，假如Z（q-1）≤Ai≤Zq，則q被選中當成下一個個體。

（4）改進型的單點交叉操作。經(jīng)選擇操作產(chǎn)生新的種群之后，并利用生物學中的有性繁殖的基因重組原理，選擇改進型的單點交叉操作方法，通過染色體配對后產(chǎn)生基因交換，將優(yōu)良基因遺傳到子代個體。

Step 1：以“門當戶對”為原則，對父代個體進行配對并按目標函數(shù)值進行排序，目標函數(shù)值最小的與小的配對，反之，大的目標函數(shù)值與大的進行配對。

Step 2：應用混沌序列確定交叉點的位置。

Step 3：對確定的交叉項基因進行交叉操作。

通過改進遺傳算法，可避免和削弱在算法交叉強度大時而產(chǎn)生的尋優(yōu)抖振問題，提高算法的收斂精度。

（5）改進的變異操作。個體的少數(shù)基因隨機發(fā)生改變其結(jié)構(gòu)或位置，變動的幾率較小，一般在0.001到0.1之間。從初始種群P（h）隨著遺傳算子的不斷進化迭代后中得到新的種群P（h+1），不斷進行繁衍優(yōu)化。遺傳算法經(jīng)過變異實現(xiàn)種群多樣性的一種手段，在遺傳操作過程中保留最優(yōu)良的個體，個體上各個基因位進行變異，使個體的排列順序發(fā)生較大的變化，而配送路徑上的配送點順序?qū)N群的各個個體也會產(chǎn)生很大的變化，所以其相應的基因值也不同[7]。按照給定的變異率，對選定的變異個體，隨機選取三個整數(shù)，1

（6）終止條件。若h≤H,則h=h+1，轉(zhuǎn)到步驟（2）；若h＞H則已經(jīng)達到最大的種群迭代數(shù)的終止原則，將此作為最優(yōu)解，即最短配送路徑。

3　居家通店鋪配送路線仿真

選取居家通企業(yè)其中一個合作店鋪Pizza芝根芝底為例，該店鋪以訂單達到29元為起送價格，以此店為配送中心向周邊酒店實施配送，該店到各個酒店的實際距離（見表1），假設該店鋪只有一輛車和一名配送員工并且能裝下一次巡回路線送的所有訂單。表2為居家通企業(yè)合作店鋪Pizza芝根芝底(59)、南公快捷酒店(37)、如家快捷酒店(74)、紙業(yè)大酒店(82)、麗嘉賓館(211)、小希爾頓源利明珠店(212)、榕盛商務賓館(213)、速8酒店(215)、漢庭酒店(216)。

表1　配送中心、各配送點之間的實際距離　單位：m

3.1店鋪實際配送路徑

經(jīng)調(diào)查店鋪一般以10分鐘為時間段，結(jié)合實際交通擁堵情況和客戶下單時間對各配送點進行配送。配送路徑基本固定為1-3-2-9-5-7-6-4-8-10，即Pizza芝根芝底(59)-如家快捷酒店(74)-南公快捷酒店(37)-漢庭酒店 (216)-麗嘉賓館 (211)-榕盛商務賓館(213)-小希爾頓源利明珠店(212)-紙業(yè)大酒店(82)-速8酒店(215)-PIZZA芝根芝底(59)的巡回路徑，總路徑長度為5.330 km。

3.2遺傳算法模擬居家通店鋪配送路徑

利用遺傳算法，各參數(shù)設置為：種群規(guī)模為50，迭代次數(shù)為100，交叉率為1，變異率為0.02。經(jīng)Mat1ab分別計算標準遺傳算法和改進的遺傳算法的最短配送路徑(見表2)并將配送結(jié)果用GIS地圖標注(見圖2)以便將來GPS導航系統(tǒng)的開發(fā)。

表2　實際配送路線與算法配送路線對比

圖2　遺傳算法(左)和改進遺傳算法(右)求得的配送路徑（按1:200比例）

從表2和圖2可知改進遺傳算法求得的路線長度最短為4.33 km并且在GIS地圖上可以明顯看出其回程的路線更短則有效減少運輸返程的空載，更合理的安排配送路徑，縮短配送時間。

3.3企業(yè)規(guī)模增加，修改配送路徑

隨著居家通企業(yè)的快速發(fā)展，不斷有新的酒店采用該平臺時，即周圍再增加新銀河酒店公寓(45)、福州華億賓館(262)、速8酒店（工業(yè)路寶龍店）(276)、福州鹽業(yè)快捷酒店(303)、福州匯雄商務賓館(307)五個酒店時，如表3為增加的配送點的位置坐標。

表3　新增配送點的坐標

結(jié)合表1和表3，當?shù)赇佋诒?訂單8個配送點的基礎上再新添5個配送點時，用Mat1ab編程求出配送的最短路徑為8.50 km，配送路徑為1-8-10-12-14-11-6-4-7-5-13-9-2-3-1的巡回路徑（見圖8）。

圖3　配送路徑地圖（按1:200比例）

由圖3可知，當?shù)赇伵渌头秶鷥?nèi)出現(xiàn)新的配送點時，原有的單巡回路線則會變長，造成空載時間長、運輸距離長、配送時間增加等現(xiàn)象，影響訂單配送時效承諾。此時，店鋪在配送時需根據(jù)訂單情況，適當增加配送人員和運輸車輛，然后對配送路線進行重新規(guī)劃，實現(xiàn)多批次、小批量的配送，盡最大限度滿足客戶對時效的需求。

3.4結(jié)果分析

（1）完善配送網(wǎng)絡，聯(lián)合居家通企業(yè)共同配送。

由企業(yè)現(xiàn)有狀況來看，在這個區(qū)域范圍內(nèi)，當每個店鋪訂單數(shù)量較少時，可通過該區(qū)域范圍內(nèi)的店鋪進行合作或交給居家通企業(yè)統(tǒng)一配送，先由每個店鋪構(gòu)成一條取貨路線收集各個店鋪的訂單產(chǎn)品，再規(guī)劃各個酒店配送的一條巡回路線。

未來隨著企業(yè)發(fā)展，合作的酒店和店鋪不斷增加時，會產(chǎn)生大量的訂單，店鋪自營物流較難完成居家通企業(yè)的“15或30分鐘送達”送貨時間承諾，影響配送服務質(zhì)量。這時，居家通企業(yè)應當建立配送團隊和配送中心幫助店鋪完成訂單配送服務，實現(xiàn)雙方的共贏，提高配送服務質(zhì)量。

（2）對訂單定時段進行統(tǒng)計分析，增加目標函數(shù)的約束條件

企業(yè)在以客戶為考慮起點的同時也要對店鋪和酒店的利益方面考慮，在實際情況中并不能單方面考慮客戶需求，損失店鋪及旅店的利益。所以居家通在接到客戶訂單的時候，在一定的時間段內(nèi)對訂單進行統(tǒng)計分析，并將信息傳遞給給店鋪統(tǒng)計可同時配送的訂單，不至于影響配送效率。同時對于模型中目標函數(shù)可加入車輛配送限制載重和時效要求的約束條件，以尋找最適合的配送路徑。

4　結(jié)論

本文以居家通企業(yè)為例展開分析，針對該企業(yè)的路徑問題，構(gòu)建居家通企業(yè)配送網(wǎng)絡的路線，建立相應的改進遺傳算法模型，避免種群在追求最優(yōu)解時產(chǎn)生尋優(yōu)抖振問題，加速收斂速度。最后，結(jié)合居家通合作企業(yè)的實際配送狀況進行模擬分析，實現(xiàn)快速配送，達到供需的雙贏。但對于構(gòu)建企業(yè)物流配送網(wǎng)絡應該考慮到的因素還不夠完全，尤其未來當企業(yè)規(guī)模擴大時，本文構(gòu)建模型的約束條件還不能滿足于企業(yè)的發(fā)展，將來的研究方向應當考慮到批量配送點、時間效能、車輛配載、績效評價等配送因素，模型將更符合企業(yè)的實際運作，提高企業(yè)的物流配送效率，有效降低物流成本，提高企業(yè)的綜合競爭力。

參考文獻:

[1]許婧.電子商務環(huán)境下物流配送體系研究:以特能中國公司為例[J].經(jīng)營管理者,2011(19):296-296.

[2]張旭鳳.第三方物流企業(yè)配送網(wǎng)絡演化規(guī)律及路徑優(yōu)化研究[D].北京:北京工業(yè)大學,2012.

[3]劉洋.城市路網(wǎng)中的集送貨一體化車輛路徑問題研究[D].重慶:重慶交通大學,2013.

[4]徐軍輝.基于核心競爭力的綠色物流管理研究:以CW公司為例[J].商業(yè)經(jīng)濟,2011(23):37-39.

[5]葉歡,經(jīng)亞枝.Grefenstette編碼法的MATLAB實現(xiàn)[J].中國測試技術,2004(2):58-60.

[6]孫慧平,李健,郭偉剛.改進遺傳算法求解旅行商問題[J].數(shù)學的實踐與認識,2009(4):127-133.

[7]王會云,肖建祿,劉登泰,等.基于遺傳算法的配送路線優(yōu)化[J].后勤工程學院學報,2008(3):91-94.

（責任編輯：葉麗娜）

中圖分類號：F253.9

文獻標識碼：A

文章編號：1674-2109(2015)12-0084-05

收稿日期：2015-10-26

作者簡介：林森（1986-），男，漢族，博士研究生，助教，主要從事現(xiàn)代物流管理研究。

通訊作者：洪偉（1947-），男，漢族，博士生導師，教授，主要從事數(shù)理統(tǒng)計、系統(tǒng)工程研究。

Construction on Lmprovement-based Genetic Algorithm of Enterprise Logistics Distribution Network

LIN Sen1，HONG Wei2

(1.Schoo1 of Transportation，F(xiàn)ujian Agricu1ture and Forestry University,Fuzhou，F(xiàn)ujian 350002; 2.Forestry Co11ege，F(xiàn)ujian Agricu1ture and Forestry University,Fuzhou，F(xiàn)ujian 350002)

Abstract:To the order data of JOJTOM enterprise and distribution network as the research object,using the improved genetic a1gorithm for the cooperation the store service network ca1cu1ation,get the shortest de1ivery route and the actua1 distribution route,the standard genetic a1gorithm is app1ied to ca1cu1ate the route of the contrast and through GIS maps.When enterprise sca1e,the cooperation after the shops need to increase in the number and distribution of hote1 under the improved genetic a1gorithm is the distribution of path.Resu1ts show that the actua1 distribution route is 5.33 km,the standard genetic a1gorithm(ga)route is 5.04 km,improved genetic a1gorithm performance optima1 route resu1ts in GIS map of 4.33 km,and after five distribution nodes are added,the distribution of path is 8.5 km.

Key words：JOJTOM enterprises;improved genetic a1gorithm;Mat1ab