遺傳算法求解帶限行約束配送網點選址模型

張冠湘，劉園園，陳廣文，蔡文學，鐘慧玲

（華南理工大學 經濟與貿易學院，廣東 廣州510006）

0 引 言

目前電商企業通過自建干線物流，在配送終端外包給第三方物流的模式得到廣泛應用。在這種模式下，電商企業從倉庫把貨物運輸到網點，再由第三方物流配送到客戶手中。對于電商企業而言其目標是運輸成本及支付給第三方物流的費用盡可能低，對于第三方物流企業而言其目標是網點建設及配送成本盡可能低，因此屬于雙目標的雙層規劃問題。本文以電商企業的網點選址為目的，追求上述配送模式的整體運營成本最小化為目標構建模型。

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

選址雙層規劃模型具有遞階結構，屬于NP－Hard 難題，不適合使用精確算法求解。目前求解此問題的方法有極點 搜索 法［8］、互 補 旋 轉 法［9］、分 支 定 界 法［10］、啟 發 式 算法［11］等。本文提出的服務網點選址模型的上層規劃目標函數內含車輛路徑規劃問題，下層規劃內含集覆蓋問題，因此屬于非線性雙層規劃。遺傳算法在雙層規劃求解中應用最為廣泛，同時模型中的0－1變量非常適合轉換為遺傳編碼，因此用遺傳算法對模型進行求解。

1 帶限行的城市配送服務網點選址雙層規劃模型

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

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

上層模型的目標為使得電商企業的成本最小化，其成本包括運輸成本及支付給第三方物流企業的費用

下層模型目標函數g 表示第三方物流公司利潤的最大化

2 混合層次遺傳求解算法

2.1 算法概述

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

?

2.2 編碼方式及適應度函數設計

對于上層規劃變量，GA 編碼方式設計為v ＝［v1，…，vp］，其中當第k輛車有任務時vk＝1，否則vk＝0。對于下層規劃變量，其GA 編碼方式為y ＝［y1，…，ym］，其中當第j個服務網點被建立時yj＝1，否則yj＝0。

2.3 遺傳策略設計

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

?

?

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

變異方法采用閥值法，記v 表示變異率0.01 ≤v ≤0.2；對于染色體ci上的每一個基因cij，產生0～1之間隨機εj，當εj＜v時cij＝ （cij＋1）%2。

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

對當前種群、雜交種群、變異種群中所有的個體按適應值升序排序，取前10%的個體直接進入下一代種群，剩下的個體中使用輪賭選擇法選擇進入下一代種群。

3 實例驗證

3.1 實證數據描述

為了驗證本文所提模型和算法的有效性，在本節中以某著名電商企業在廣州的營業情況作為實例應用的背景數據。廣州市現行交通管制數據詳見據廣州市公安局的 《關于進一步調整市區貨車交通管制措施的通告穗公 （2010）269號》。該電商公司在廣州的配送中心及服務網點信息見表1。

表1 現有設施信息

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

該電商公司目前使用依維柯得意對每一服務網點單獨配送，行駛總距離為236.3公里，油費222.43元。車輛總運營成本為113.88元／日。

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

表2 各候選服務網點信息

圖1 各候選服務網點位置

最終參與選址的服務網點包括現有的4個服務網點與9個候選服務網點。使用該電商公司提供的2014 年2 月24日的配送數據，共400 個顧客需求點，總需求量為4016。根據上述案例數據，下面將使用提出的模型及算法對服務網點選址及車輛路徑規劃進行求解，并對結果進行分析。

3.2 應用平臺與基礎數據

本文中的應用算法均采用C＃ （.NET 2.0）實現，電腦配置為Intel Xeon （R）CPU E5520 2.26GHz×2，4G 內存，操作系統為Windows Server 2008。

本文使用廣東省廣州市道路網絡數據作為基礎網絡數據，該道路網絡包含114 935條邊與55 357個節點，其中邊信息中包含了其起點，終點以及邊的長度信息 （邊的平均長度為0.20km），點信息中包含了與之相連的出邊、入邊的信息，節點的平均出入邊數量為2.1。

3.3 實驗參數

使用第2節遺傳算法對該電商公司配送網絡服務網點選址問題進行求解，方案1不考慮道路限行，使用城市配送服務網點選址雙層規劃模型，方案2考慮道路限行，使用帶限行的城市配送服務網點選址雙層規劃模型，具體參數如下：

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

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

3.4 實驗結果及分析

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

方案1的最優解為建立2、3、9 號服務網點，保留東湖站，見表3。

表3 方案1服務網點選址結果

配送中心的配送方案為派出4輛依維柯得意，對每個服務站點單獨配送，行駛總距離為227.6 公里，油費214.24元。車輛總運營成本為113.88元／日。

方案2的最優解為建立1、3、5 號服務網點，保留東湖站，見表4。

表4 方案2服務網點選址結果

配送中心的配送方案為派出兩輛江淮威鈴，一輛負責配送1、3號服務網點，一輛負責配送5號服務網點與東湖站，行駛總距離為132.4公里，油費177.75元。車輛總運營成本為66.74元／日。

方案1選址結果與現有方案對比如圖2所示。

圖2 方案1選址結果與現有方案對比

從圖2中看出，方案1的選址結果相當于把原4號服務網點康王站向東遷移2.8公里左右，把原2號服務網點寶崗站向東南遷移3.7公里左右，把原1號服務網點區莊站向東北遷移2.6公里左右。各服務網點原服務的顧客群在位置調整后仍處于其覆蓋范圍內，并不會對電商公司配送計劃的制定及商品的配送速度造成太大的影響。

方案2選址結果與現有方案對比如圖3所示。

圖3 方案2選址結果與現有方案對比

從圖3中看出，方案2的選址結果相當于把原4號服務網點康王站向北遷移2.9公里左右，把原2號服務網點寶崗站向東遷移1.9公里左右，把原1號服務網點區莊站向東北遷移2.6公里左右。各服務網點原服務的顧客群在位置調整后仍處于其覆蓋范圍內，并不會對電商公司配送計劃的制定及商品的配送速度造成太大的影響。

兩方案成本與現有方案成本對比見表5。

表5 方案間成本對比／元

通過表5可看出，不考慮限行的方案1相比現有方案，日均成本節省8.19元，下降了2.4%；對于整個配送系統，方案1相比現有方案，日均成本節省18.19元，下降了1.3%。可見在不考慮城市道路限行的情況下，某電商公司的現有城市配送方案已經接近最優解，進一步的優化效果并不明顯。

考慮限行的方案2相比現有方案，日均成本節省91.82元，下降了27.3%；對于整個配送系統，方案2相比現有方案，日均成本節省71.82元，下降了5.2%。可見在考慮限行的情況下，本文的研究成果能實現電商公司城市配送成本的明顯壓縮。

4 結束語

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

［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）.［關菲，張強.模糊多目標物流配送中心選址模型及其求解算法［J］.中國管理科學，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）.［馮利朋.帶偏好的區域物流配送中心選址方法及應用 ［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）.［王軍，艾云飛，王美蓉.基于雙層規劃的競爭性選址問題研究 ［J］.武漢理工大學學報 （交通科學與工程版），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）. ［慶艷華，左小德.考慮服務懲罰的配送中心選址的雙層規劃模型 ［J］.華南理工大學學報 （社會科學版），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環境下的物流配送中心選址模型研究 ［J］.測繪與空間地理信息，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）.［史偉.考慮時效約束的物流系統選址研究 ［J］.云南民族大學學報 （自然科學版），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－Ⅱ算法的雙目標服務網點選址優化 ［J］.物流技術，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.