張冠湘，劉園園，陳廣文，蔡文學(xué)，鐘慧玲

（華南理工大學(xué) 經(jīng)濟(jì)與貿(mào)易學(xué)院，廣東 廣州510006）

0 引 言

目前電商企業(yè)通過自建干線物流，在配送終端外包給第三方物流的模式得到廣泛應(yīng)用。在這種模式下，電商企業(yè)從倉庫把貨物運(yùn)輸?shù)骄W(wǎng)點(diǎn)，再由第三方物流配送到客戶手中。對(duì)于電商企業(yè)而言其目標(biāo)是運(yùn)輸成本及支付給第三方物流的費(fèi)用盡可能低，對(duì)于第三方物流企業(yè)而言其目標(biāo)是網(wǎng)點(diǎn)建設(shè)及配送成本盡可能低，因此屬于雙目標(biāo)的雙層規(guī)劃問題。本文以電商企業(yè)的網(wǎng)點(diǎn)選址為目的，追求上述配送模式的整體運(yùn)營成本最小化為目標(biāo)構(gòu)建模型。

目前配送網(wǎng)點(diǎn)選址模型按照層次不同可分為單層規(guī)劃模 型［1，2］和 雙 層 規(guī) 劃 模 型［3，4］，按 照 目 標(biāo) 不 同 可 分 為 成 本 最小化模型［5］、快速響應(yīng)模型［6］、混合多目標(biāo)模型［7］。這些模型在現(xiàn)實(shí)中取得了較好的效果，但隨著城市交通限行的實(shí)施，這些模型缺乏考慮道路、車輛的限行約束。因此本文在網(wǎng)點(diǎn)選址雙層規(guī)劃模型的基礎(chǔ)上增加交通限行約束，提出以上層模型網(wǎng)點(diǎn)選址為主要內(nèi)容，以雙層規(guī)劃的總成本最小化為目標(biāo)的雙層模型。

選址雙層規(guī)劃模型具有遞階結(jié)構(gòu)，屬于NP－Hard 難題，不適合使用精確算法求解。目前求解此問題的方法有極點(diǎn) 搜索 法［8］、互 補(bǔ) 旋 轉(zhuǎn) 法［9］、分 支 定 界 法［10］、啟 發(fā) 式 算法［11］等。本文提出的服務(wù)網(wǎng)點(diǎn)選址模型的上層規(guī)劃目標(biāo)函數(shù)內(nèi)含車輛路徑規(guī)劃問題，下層規(guī)劃內(nèi)含集覆蓋問題，因此屬于非線性雙層規(guī)劃。遺傳算法在雙層規(guī)劃求解中應(yīng)用最為廣泛，同時(shí)模型中的0－1變量非常適合轉(zhuǎn)換為遺傳編碼，因此用遺傳算法對(duì)模型進(jìn)行求解。

1 帶限行的城市配送服務(wù)網(wǎng)點(diǎn)選址雙層規(guī)劃模型

經(jīng)典的雙層規(guī)劃模型已經(jīng)很好地描述了電商企業(yè)的網(wǎng)點(diǎn)選址問題［4］，然隨著城市交通擁堵問題的出現(xiàn)，政府針對(duì)貨運(yùn)車輛實(shí)施交通管制：規(guī)定時(shí)段、路段、車型。為使得模型能夠適用于現(xiàn)實(shí)情況，需要在經(jīng)典的模型中添加道路限行約束。對(duì)于上層規(guī)劃，電商公司的配送車輛需要分類為限行車輛和非限行車輛，不同的車輛有不同的能力限制。同時(shí)需要加入限行車輛不得進(jìn)入限行區(qū)域的約束。對(duì)于下層規(guī)劃，第三方物流公司的服務(wù)網(wǎng)點(diǎn)需要分類為非限行區(qū)域的網(wǎng)點(diǎn)和限行區(qū)域的網(wǎng)點(diǎn)。同時(shí)增加限行區(qū)域的服務(wù)網(wǎng)點(diǎn)的實(shí)際服務(wù)顧客總需求不超過非限行車輛總運(yùn)載能力的約束。

定義模型的相關(guān)變量如下：I——顧客需求點(diǎn)集合；J——候選服務(wù)網(wǎng)點(diǎn)集合，J1表示非限行區(qū)網(wǎng)點(diǎn)集合，J2表示限行區(qū)網(wǎng)點(diǎn)集合；di——顧客需求點(diǎn)i的需求量；xij——0，1變量，當(dāng)?shù)趇個(gè)顧客需求點(diǎn)由第j 個(gè)服務(wù)網(wǎng)點(diǎn)配送時(shí)，值為1，否則為0；yj——0，1變量，當(dāng)?shù)趈個(gè)服務(wù)網(wǎng)點(diǎn)被建立時(shí)，值為1，否則為0；α——電商公司支付給第三方物流公司的費(fèi)用；sj——服務(wù)網(wǎng)點(diǎn)的j服務(wù)能力；K——配送中心車輛集合，K1表示限行車輛集合，K2表示不限行車輛集合；CUjk（·）——第k輛配送車輛配送商品到第j 個(gè)服務(wù)網(wǎng)點(diǎn)的廣義物流費(fèi)用函數(shù)；vk——0，1變量，當(dāng)?shù)趉 輛配送車輛有任務(wù)時(shí)，值為1，否則為0；B——電商公司預(yù)期的總自營成本；CLij（·）——服務(wù)網(wǎng)點(diǎn)j配送商品到顧客需求點(diǎn)i的廣義物流費(fèi)用函數(shù)；zjk——當(dāng)?shù)趈個(gè)服務(wù)點(diǎn)由第k 輛配送車配送時(shí)，zjk＝1，否則zjk＝0，由于限行車輛不能配送 至 限 行 區(qū) 域，因 此 當(dāng)k ∈K1，j ∈J2時(shí)，zjk＝0；oUk——配送車輛k 的運(yùn)營成本；wk——配送車輛k 的運(yùn)載能力；oLj——網(wǎng)點(diǎn)j的運(yùn)營成本。

上層模型的目標(biāo)為使得電商企業(yè)的成本最小化，其成本包括運(yùn)輸成本及支付給第三方物流企業(yè)的費(fèi)用

下層模型目標(biāo)函數(shù)g 表示第三方物流公司利潤(rùn)的最大化

2 混合層次遺傳求解算法

2.1 算法概述

遺傳算法因其具有較好的普適性得到了廣泛的應(yīng)用。使用遺傳算法對(duì)帶限行的電商物流配送雙層規(guī)劃模型進(jìn)行求解，為上下層規(guī)劃設(shè)計(jì)GA 編碼方式、定義適應(yīng)度函數(shù)及確定遺傳策略。在得到配送中心選擇的車型及車輛數(shù)后，需要通過求解下層規(guī)劃得出服務(wù)網(wǎng)點(diǎn)的選址及顧客的分配，然后再求解配送中心的車輛路徑規(guī)劃問題，才能計(jì)算上層規(guī)劃的適應(yīng)值。根據(jù)第1節(jié)的雙層模型設(shè)計(jì)對(duì)應(yīng)的混合層次遺傳算法如算法1所示。

?

2.2 編碼方式及適應(yīng)度函數(shù)設(shè)計(jì)

對(duì)于上層規(guī)劃變量，GA 編碼方式設(shè)計(jì)為v ＝［v1，…，vp］，其中當(dāng)?shù)趉輛車有任務(wù)時(shí)vk＝1，否則vk＝0。對(duì)于下層規(guī)劃變量，其GA 編碼方式為y ＝［y1，…，ym］，其中當(dāng)?shù)趈個(gè)服務(wù)網(wǎng)點(diǎn)被建立時(shí)yj＝1，否則yj＝0。

2.3 遺傳策略設(shè)計(jì)

選擇方法采用輪賭選擇法選擇父代染色體。當(dāng)染色體適應(yīng)度越高時(shí)，那么它被選擇到的機(jī)會(huì)就越大。由于在本算法中染色體的適應(yīng)值越低越好，因此在選擇前需要先將適應(yīng)值f 轉(zhuǎn)換為輪賭值r。記C ＝ ｛c1，…，cn｝表示染色體集合，其中ci＝｛fi，ri｝，選擇算法的步驟如算法2所示。

?

?

雜交方法采用的是雙親遺傳算法，ci＝ ［gi1，…，gin］表示染色體i；c1，c2，c3，c4分別表示雙親染色體和子代染色體，m 表示雜交位置，則由父代雜交得到子代的方式為

變異方法采用閥值法，記v 表示變異率0.01 ≤v ≤0.2；對(duì)于染色體ci上的每一個(gè)基因cij，產(chǎn)生0～1之間隨機(jī)εj，當(dāng)εj＜v時(shí)cij＝ （cij＋1）%2。

在上層規(guī)劃中若經(jīng)遺傳操作產(chǎn)生的個(gè)體所表示的派出車輛其總運(yùn)載能力不能滿足總的顧客需求，則舍去該個(gè)體。在下層規(guī)劃中若經(jīng)遺傳操作產(chǎn)生的個(gè)體所表示的建立的服務(wù)網(wǎng)點(diǎn)其總服務(wù)能力不能滿足總的顧客需求，則舍去該個(gè)體。經(jīng)夭折機(jī)制舍去個(gè)體后，隨機(jī)生成一個(gè)能力滿足顧客總需求的新個(gè)體作為替代。

對(duì)當(dāng)前種群、雜交種群、變異種群中所有的個(gè)體按適應(yīng)值升序排序，取前10%的個(gè)體直接進(jìn)入下一代種群，剩下的個(gè)體中使用輪賭選擇法選擇進(jìn)入下一代種群。

3 實(shí)例驗(yàn)證

3.1 實(shí)證數(shù)據(jù)描述

為了驗(yàn)證本文所提模型和算法的有效性，在本節(jié)中以某著名電商企業(yè)在廣州的營業(yè)情況作為實(shí)例應(yīng)用的背景數(shù)據(jù)。廣州市現(xiàn)行交通管制數(shù)據(jù)詳見據(jù)廣州市公安局的 《關(guān)于進(jìn)一步調(diào)整市區(qū)貨車交通管制措施的通告穗公 （2010）269號(hào)》。該電商公司在廣州的配送中心及服務(wù)網(wǎng)點(diǎn)信息見表1。

表1 現(xiàn)有設(shè)施信息

該電商公司現(xiàn)統(tǒng)一使用依維柯得意車進(jìn)行配送，滿載約能裝1500個(gè)訂單。依維柯得意為非限行車輛，為考慮限行政策對(duì)服務(wù)網(wǎng)點(diǎn)布局的影響，本文另外加入江淮威鈴作為候選配送車型。網(wǎng)購貨物的體積重量比往往大于1，因此使用貨箱空間確定江淮威鈴的運(yùn)載能力。根據(jù)通用的1米物流筐的尺寸 （長(zhǎng)寬高 （mm）：1050＊550＊680），依維柯得意能裝12筐，江淮威鈴能裝24筐，因此江淮威鈴的運(yùn)載能力設(shè)定為依維柯得意的兩倍。日常運(yùn)營費(fèi)用按車輛參考價(jià)格，使用平均折舊法，以通用的10年年限折算，依維柯得意的綜合油耗為12.13L／100 KM，貨箱尺寸 （mm）為2460＊1820＊1690，運(yùn)載能力為1500單，日均運(yùn)營成本為28.47元；而江淮威鈴的綜合油耗為17.3L／100 KM，貨箱尺寸 （mm）為4870＊2000＊2000，運(yùn)載能力為3000單，日均運(yùn)營成本為33.37元。

該電商公司目前使用依維柯得意對(duì)每一服務(wù)網(wǎng)點(diǎn)單獨(dú)配送，行駛總距離為236.3公里，油費(fèi)222.43元。車輛總運(yùn)營成本為113.88元／日。

該電商公司的部分候選服務(wù)網(wǎng)點(diǎn)信息如表2所示，具體位置如圖1中的三角形。

表2 各候選服務(wù)網(wǎng)點(diǎn)信息

圖1 各候選服務(wù)網(wǎng)點(diǎn)位置

最終參與選址的服務(wù)網(wǎng)點(diǎn)包括現(xiàn)有的4個(gè)服務(wù)網(wǎng)點(diǎn)與9個(gè)候選服務(wù)網(wǎng)點(diǎn)。使用該電商公司提供的2014 年2 月24日的配送數(shù)據(jù)，共400 個(gè)顧客需求點(diǎn)，總需求量為4016。根據(jù)上述案例數(shù)據(jù)，下面將使用提出的模型及算法對(duì)服務(wù)網(wǎng)點(diǎn)選址及車輛路徑規(guī)劃進(jìn)行求解，并對(duì)結(jié)果進(jìn)行分析。

3.2 應(yīng)用平臺(tái)與基礎(chǔ)數(shù)據(jù)

本文中的應(yīng)用算法均采用C＃ （.NET 2.0）實(shí)現(xiàn)，電腦配置為Intel Xeon （R）CPU E5520 2.26GHz×2，4G 內(nèi)存，操作系統(tǒng)為Windows Server 2008。

本文使用廣東省廣州市道路網(wǎng)絡(luò)數(shù)據(jù)作為基礎(chǔ)網(wǎng)絡(luò)數(shù)據(jù)，該道路網(wǎng)絡(luò)包含114 935條邊與55 357個(gè)節(jié)點(diǎn)，其中邊信息中包含了其起點(diǎn)，終點(diǎn)以及邊的長(zhǎng)度信息 （邊的平均長(zhǎng)度為0.20km），點(diǎn)信息中包含了與之相連的出邊、入邊的信息，節(jié)點(diǎn)的平均出入邊數(shù)量為2.1。

3.3 實(shí)驗(yàn)參數(shù)

使用第2節(jié)遺傳算法對(duì)該電商公司配送網(wǎng)絡(luò)服務(wù)網(wǎng)點(diǎn)選址問題進(jìn)行求解，方案1不考慮道路限行，使用城市配送服務(wù)網(wǎng)點(diǎn)選址雙層規(guī)劃模型，方案2考慮道路限行，使用帶限行的城市配送服務(wù)網(wǎng)點(diǎn)選址雙層規(guī)劃模型，具體參數(shù)如下：

方案1：在上層規(guī)劃中，配送中心只使用依維柯得意車型，車輛數(shù)為16輛，GA 編碼長(zhǎng)度為4，種群規(guī)模為6，最大迭代次數(shù)為20，雜交概率為80%，變異概率為10%。在下層規(guī)劃中，參與選址的候選服務(wù)網(wǎng)點(diǎn)共13個(gè)，GA 編碼長(zhǎng)度為13，種群規(guī)模為100，最大迭代次數(shù)為2000，雜交概率為80%，變異概率為10%，配送至顧客的廣義物流費(fèi)用采用平均訂單成本5元／單。

方案2：在上層規(guī)劃中，配送中心的兩個(gè)車型的車輛數(shù)各16輛，GA 編碼長(zhǎng)度為8，種群規(guī)模為32，最大迭代次數(shù)為200，雜交概率為80%，變異概率為10%。在下層規(guī)劃中，參與選址的候選服務(wù)網(wǎng)點(diǎn)共13個(gè)，GA 編碼長(zhǎng)度為13，種群規(guī)模為100，最大迭代次數(shù)為2000，雜交概率為80%，變異概率為10%，配送至顧客的廣義物流費(fèi)用采用平均訂單成本5元／單。

3.4 實(shí)驗(yàn)結(jié)果及分析

以下分別將不考慮限行的方案1和考慮限行的方案2與某電商公司現(xiàn)有城市配送方案進(jìn)行對(duì)比，分析本文研究成果的合理性及實(shí)用性。

方案1的最優(yōu)解為建立2、3、9 號(hào)服務(wù)網(wǎng)點(diǎn)，保留東湖站，見表3。

表3 方案1服務(wù)網(wǎng)點(diǎn)選址結(jié)果

配送中心的配送方案為派出4輛依維柯得意，對(duì)每個(gè)服務(wù)站點(diǎn)單獨(dú)配送，行駛總距離為227.6 公里，油費(fèi)214.24元。車輛總運(yùn)營成本為113.88元／日。

方案2的最優(yōu)解為建立1、3、5 號(hào)服務(wù)網(wǎng)點(diǎn)，保留東湖站，見表4。

表4 方案2服務(wù)網(wǎng)點(diǎn)選址結(jié)果

配送中心的配送方案為派出兩輛江淮威鈴，一輛負(fù)責(zé)配送1、3號(hào)服務(wù)網(wǎng)點(diǎn)，一輛負(fù)責(zé)配送5號(hào)服務(wù)網(wǎng)點(diǎn)與東湖站，行駛總距離為132.4公里，油費(fèi)177.75元。車輛總運(yùn)營成本為66.74元／日。

方案1選址結(jié)果與現(xiàn)有方案對(duì)比如圖2所示。

圖2 方案1選址結(jié)果與現(xiàn)有方案對(duì)比

從圖2中看出，方案1的選址結(jié)果相當(dāng)于把原4號(hào)服務(wù)網(wǎng)點(diǎn)康王站向東遷移2.8公里左右，把原2號(hào)服務(wù)網(wǎng)點(diǎn)寶崗站向東南遷移3.7公里左右，把原1號(hào)服務(wù)網(wǎng)點(diǎn)區(qū)莊站向東北遷移2.6公里左右。各服務(wù)網(wǎng)點(diǎn)原服務(wù)的顧客群在位置調(diào)整后仍處于其覆蓋范圍內(nèi)，并不會(huì)對(duì)電商公司配送計(jì)劃的制定及商品的配送速度造成太大的影響。

方案2選址結(jié)果與現(xiàn)有方案對(duì)比如圖3所示。

圖3 方案2選址結(jié)果與現(xiàn)有方案對(duì)比

從圖3中看出，方案2的選址結(jié)果相當(dāng)于把原4號(hào)服務(wù)網(wǎng)點(diǎn)康王站向北遷移2.9公里左右，把原2號(hào)服務(wù)網(wǎng)點(diǎn)寶崗站向東遷移1.9公里左右，把原1號(hào)服務(wù)網(wǎng)點(diǎn)區(qū)莊站向東北遷移2.6公里左右。各服務(wù)網(wǎng)點(diǎn)原服務(wù)的顧客群在位置調(diào)整后仍處于其覆蓋范圍內(nèi)，并不會(huì)對(duì)電商公司配送計(jì)劃的制定及商品的配送速度造成太大的影響。

兩方案成本與現(xiàn)有方案成本對(duì)比見表5。

表5 方案間成本對(duì)比／元

通過表5可看出，不考慮限行的方案1相比現(xiàn)有方案，日均成本節(jié)省8.19元，下降了2.4%；對(duì)于整個(gè)配送系統(tǒng)，方案1相比現(xiàn)有方案，日均成本節(jié)省18.19元，下降了1.3%?？梢娫诓豢紤]城市道路限行的情況下，某電商公司的現(xiàn)有城市配送方案已經(jīng)接近最優(yōu)解，進(jìn)一步的優(yōu)化效果并不明顯。

考慮限行的方案2相比現(xiàn)有方案，日均成本節(jié)省91.82元，下降了27.3%；對(duì)于整個(gè)配送系統(tǒng)，方案2相比現(xiàn)有方案，日均成本節(jié)省71.82元，下降了5.2%?？梢娫诳紤]限行的情況下，本文的研究成果能實(shí)現(xiàn)電商公司城市配送成本的明顯壓縮。

4 結(jié)束語

通過對(duì)電商物流城市配送現(xiàn)狀及問題的分析，提出適用于在限行條件下電商物流城市配送服務(wù)網(wǎng)點(diǎn)選址的雙層規(guī)劃模型及其求解算法，并利用某電商公司的實(shí)際配送任務(wù)案例對(duì)模型及算法進(jìn)行了驗(yàn)證，驗(yàn)證結(jié)果表明了本文所提模型和算法的有效性，能實(shí)現(xiàn)電商公司配送中運(yùn)輸成本的壓縮，進(jìn)而降低企業(yè)的運(yùn)營成本，提升企業(yè)的競(jìng)爭(zhēng)力。然在考慮服務(wù)網(wǎng)點(diǎn)的能力限制時(shí)使用的是靜態(tài)能力限制，而在實(shí)際的選址規(guī)劃中可以采取租用臨近的多個(gè)鋪位，調(diào)整配送人員的數(shù)量等手段調(diào)節(jié)服務(wù)網(wǎng)點(diǎn)的配送能力。因此在模型中可以進(jìn)一步考慮服務(wù)網(wǎng)點(diǎn)的分級(jí)，建立服務(wù)網(wǎng)點(diǎn)等級(jí)調(diào)整機(jī)制。同時(shí)，目前遺傳算法采用串行計(jì)算方法，計(jì)算效率相對(duì)較低，未來考慮從并行計(jì)算方面展開研究。

［1］GUAN Fei，ZHANG Qiang.A fuzzy multi－objective logistics distribution center location model and its solution algorithm ［J］.Chinese Journal of Management Science，2013，21 （S1）：57－62 （in Chinese）.［關(guān)菲，張強(qiáng).模糊多目標(biāo)物流配送中心選址模型及其求解算法［J］.中國管理科學(xué)，2013，21 （S1）：57－62.］

［2］FENG Lipeng.Take preference of regional logistics distribution center location method and application ［J］.Statistics ＆ Decision，2012 （14）：179－181 （in Chinese）.［馮利朋.帶偏好的區(qū)域物流配送中心選址方法及應(yīng)用 ［J］.統(tǒng)計(jì)與決策，2012（14）：179－181.］

［3］WANG Jun，AI Yunfei，WANG Meirong.Study the competitive location problems based on the bi－level programming model［J］.Journal of Wuhan University of Technology（Transportation Science ＆Engineering），2013，37 （5）：970－973 （in Chinese）.［王軍，艾云飛，王美蓉.基于雙層規(guī)劃的競(jìng)爭(zhēng)性選址問題研究 ［J］.武漢理工大學(xué)學(xué)報(bào) （交通科學(xué)與工程版），2013，37 （5）：970－973.］

［4］QING Yanhua，ZUO Xiaode.Bi－level model for the distribution center location problem with service punishment［J］.Journal of South China University of Technology（Social Science Edition），2014，16 （3）：56－62 （in Chinese）. ［慶艷華，左小德.考慮服務(wù)懲罰的配送中心選址的雙層規(guī)劃模型 ［J］.華南理工大學(xué)學(xué)報(bào) （社會(huì)科學(xué)版），2014，16 （3）：56－62.］

［5］LIU Xuan，YANG Minhua，HU Bing.Study of site selection model of physical distribution center based on GIS environment［J］.Geomatics ＆Spatial Information Technology，2012，35（7）：138－141. ［劉璇，楊敏華，胡兵.GIS環(huán)境下的物流配送中心選址模型研究 ［J］.測(cè)繪與空間地理信息，2012，35（7）：138－141.］

［6］SHI Wei.On locating the distribution center of the logistics system with a consideration of time restriction ［J］.Journal of Yunnan Nationalities University （Natural Sciences Edition），2009，18 （1）：89－91 （in Chinese）.［史偉.考慮時(shí)效約束的物流系統(tǒng)選址研究 ［J］.云南民族大學(xué)學(xué)報(bào) （自然科學(xué)版），2009，18 （1）：89－91.］

［7］YANG Jianhao，YAO Zhigang，BAI Pengxia，et al.Study on optimal location for double－objective service point based on NSGA－II algorithm ［J］.Logistics Technology，2011，30 （8）：98－100 （in Chinese）. ［楊劍浩，姚志剛，白鵬霞，等.基于NSGA－Ⅱ算法的雙目標(biāo)服務(wù)網(wǎng)點(diǎn)選址優(yōu)化 ［J］.物流技術(shù)，2011，30 （8）：98－100.］

［8］Carboni M，Abney CW，Liu S，et al.Highly porous and stable metal－organic frameworks for uranium extraction ［J］.Chemical Science，2013，4 （6）：2396－2402.

［9］Saharidis GKD，Conejo AJ，Kozanidis G.Exact solution methodologies for linear and（mixed）integer bilevel programming ［M］／／Metaheuristics for Bilevel Optimization.Berlin：Springer Berlin Heidelberg，2013：221－245.

［10］Nessah R，Kacem I.Branch－and－bound method for minimizing the weighted completion time scheduling problem on a single machine with release dates［J］.Computers ＆ Operations Research，2012，39 （3）：471－478.

［11］Davidovic＇T，Ramljak D，elmic＇M，et al.Bee colony optimization for the p－center problem ［J］.Computers ＆ Operations Research，2011，38 （10）：1367－1376.