基于基因約束算法的電子商務(wù)物流路徑選取

李 楠

(煙臺職業(yè)學(xué)院 經(jīng)濟(jì)管理系，山東 煙臺 264670)

電子商務(wù)物流路徑選取是電商商家最重要的戰(zhàn)略問題之一，對電商配送的整體績效有顯著影響.其中，正向物流和逆向物流[1]的過程都共享了大量的資源，逆向物流的路徑選取會影響著正向物流路徑選取；反之亦然.由于對正向和逆向物流路徑分別進(jìn)行設(shè)計會產(chǎn)生局部最優(yōu)的結(jié)果，因此在選取物流路徑時，需要聯(lián)合考慮正向和逆向物流過程.

1 問題描述

為了簡化問題，本文考慮圖1所示的電子商務(wù)物流模型，采用混合整數(shù)線性規(guī)劃(Mixed Integer Linear Programming，MILP)[2]對物流過程進(jìn)行建模.物流模型采用三種配送方式：第一種，普通配送，指將商品從一個主體配送至相鄰的主體處；第二種，直接裝運，指廠家直接將商品配送給客戶；第三種，直接配送，指將商品從配送中心配送到客戶或從廠家配送到零售商.本文的電商物流模型是基于以下的假設(shè)：

1)必須滿足客戶的需求；

2)每個主體的設(shè)施數(shù)量都是有限制的；

3)同一主體之間不存在配送關(guān)系；

4)本文的物流模型有6個主體：供應(yīng)商、廠商、配送中心、零售商、客戶以及收集/檢驗中心.

本文研究的物流問題描述如下：

前提條件：

1)配送的可用路徑集合；

2)客戶的需求；

3)需要退貨至收集/檢測中心的商品數(shù)量；

4)從每一個收集/檢測中心運送到工廠的退貨商品的數(shù)量；

5)主體設(shè)施的容量.

輸入：

1)物流網(wǎng)絡(luò)的配置；

2)物流配送的最佳路徑；

3)每個工廠必須生產(chǎn)的商品數(shù)量；

4)將客戶分配到配送中心和收集/檢測中心的分配方案；

5)向工廠分配供應(yīng)商的分配方案.

文本的主要貢獻(xiàn)如下：聯(lián)合正向和逆向物流來優(yōu)化電商物流路徑的選擇；在物流模型中考慮了三種配送方式，即普通配送、直接裝運和直接配送；應(yīng)用文化基因算法，解決帶有容量約束的路徑選擇問題.

圖1 電子商務(wù)物流路徑模型

2 問題建模

物流模型的目標(biāo)是最小化物流路徑和各個主體運作的成本之和，目標(biāo)函數(shù)如式(1)所示.物流路徑的成本是商品在各個主體之間的配送運輸成本，包括正向物流和逆向物流(如退貨、返修)；主體運作成本是指主體建設(shè)和日常運作的成本，本模型僅考慮固定的運作成本.利用混合整數(shù)線性規(guī)劃，建立物流過程的數(shù)學(xué)模型，如下所示：

(1)

(2a)

(2b)

(2c)

(2d)

(2e)

(3a)

(3b)

(3c)

(3d)

(3e)

(4)

αf,βd,ηr,μi∈{0,1},?f,d,r,i

(5)

公式(2～5)是約束條件，約束條件(2a～2e)保證了商品在物流網(wǎng)絡(luò)中能順利流通以及需求能夠被滿足；約束條件(3a-3e)是容量約束，確保了配送到主體的商品不會超過主體的容量；約束條件(4)是為了保證客戶的需求能被滿足；約束條件(5)是變量的取值范圍.

3 基于文化基因算法的模型求解

文化基因算法(Memetic Algorithm)[3]借鑒了遺傳算法的精髓，通過加入額外的局部搜索來提高算法尋優(yōu)的能力.應(yīng)用文化基因算法求解物流模型(1)的過程如下.

3.1 染色體編碼

圖2 某客戶的染色體編碼表示

盡管采用靈活的物流模式可以提高物流配送路徑選取的靈活性和效率，但這也會使配送路徑選取問題更加復(fù)雜.為了解決這樣一個NP-hard問題，采用了基于隨機(jī)路徑的直接編碼方式，如圖2中所示.每個染色體由6個基因構(gòu)成，染色體表示將商品配送到客戶的物流路線，以及從該客戶退貨的路線.

圖2中，染色體的前兩個基因是逆向物流的路徑，后4個基因是正向物流的路徑，基因中的數(shù)字是所選主體的編號.使用這種編碼方式可能會產(chǎn)生一個不可行的解決方案，即所選的物流路徑有可能違反主體的容量約束.因此，在產(chǎn)生物流路徑的染色體后必須判斷路徑的有效性；對于不可行的路徑，需要對其進(jìn)行修復(fù).為了滿足客戶的需求，每一條物流路徑都必須包含至少一個廠商.如果客戶的總需求超過了廠商的容量，該客戶就會選擇另一個容量較大的廠商，這樣的分配方式能夠?qū)崿F(xiàn)較低的運輸成本.

3.2 染色體解碼

通過采用基于隨機(jī)路徑的直接解碼方法，可以從染色體中解碼出正向和逆向物流的路徑.解碼的過程如圖3所示，使用這種方法可以加快算法的速度.

圖3 染色體解碼

3.3 文化基因算子

采用的文化基因算法算子包括：交叉算子、局部搜索以及選擇算子.

交叉算子：本文應(yīng)用了在遺傳算法和文化基因算法中最常用的交叉算子：兩點交叉算子(two-point crossover)[4].具體的操作是，首先隨機(jī)產(chǎn)生兩個交叉點，然后將兩個染色體中位于交叉點之間的基因進(jìn)行交換.

局部搜索：在交叉后，會產(chǎn)生兩個后代.在隨后的局部搜索過程中，利用適應(yīng)度函數(shù)計算后代的適應(yīng)度值，選擇一個更好的后代來進(jìn)一步改進(jìn).利用組合局部搜索，為客戶計算最經(jīng)濟(jì)的物流路徑，選擇成本最低的路徑.

選擇算子：采用比例選擇算子(又稱輪盤賭選擇)來從舊種群中產(chǎn)生下一個種群，使染色體被選擇的概率與它的適應(yīng)度成正比.

4 性能評估

本節(jié)通過實驗將所提出算法與LINGO軟件[5]、ILOG-CPLEX軟件[6]進(jìn)行對比，以評估算法的效率.我們通過將每個階段的節(jié)點數(shù)量加倍以產(chǎn)生不同大小的測試集，如表1所示.算法將在每個測試集上運行10次，共進(jìn)行了50次實驗.其他參數(shù)使用均勻分布隨機(jī)生成.實驗所采用的PC配置如下：處理器采用Intel酷睿i5 8400 2.8 GHz，內(nèi)存是金士頓DDR4 2400 GB.

表1 本實驗使用的測試樣例

為了評估本文算法的有效性和準(zhǔn)確性，我們使用功能強(qiáng)大的LINGO軟件和CPLEX優(yōu)化軟件求解模型(1)，然后與本文算法的結(jié)果進(jìn)行比較，結(jié)果如表2所示.對于測試樣例3和測試樣例4，在進(jìn)行了2 000 s的計算后，LINGO軟件仍然未能成功求解模型(1)；對于測試樣例5也是如此.從表2可以看出，即使是功能強(qiáng)大的LINGO軟件也未能解決此類大規(guī)模模型，而本文算法卻能夠做到這一點.采用分支定界法的LINGO并不能解決大規(guī)模的優(yōu)化問題.因此，本文算法還與采用分支裁剪法的CPLEX進(jìn)行比較，進(jìn)一步顯示本文算法的有效性和準(zhǔn)確性.

表2 本文算法與LINGO、CPLEX的實驗結(jié)果對比

5 結(jié)語

本文以最小化物流配送和物流主體運營建設(shè)的總成本為目標(biāo)，建立了物流路徑選取的最優(yōu)化模型；為了解決大規(guī)模的物流路徑選擇問題，采用基于基因約束算法求解該優(yōu)化模型；分別利用本文的基于基因約束算法、LINGO和CPLEX優(yōu)化軟件求解本文的物流模型，并對結(jié)果進(jìn)行比較，驗證算法的準(zhǔn)確性和效率.未來的研究集中在以下方面：選擇更合適的目標(biāo)函數(shù)，提高物流模型的魯棒性、時效性等；約束條件需要添加對物流不確定性的考慮；設(shè)計更加合理的染色體編碼和解碼方案等.