考慮隨機行駛時間的商貿物流網絡設計問題研究

景春光

（交通運輸部科學研究院，北京　100029）

?

考慮隨機行駛時間的商貿物流網絡設計問題研究

景春光

（交通運輸部科學研究院，北京100029）

針對商貿物流網絡設計問題，以最小化商貿物流網絡構建成本為優化目標，同時決策商貿物流各級配送中心的選址與商貿物流車輛的配送路徑。在優化過程中考慮物流車輛行駛時間具有隨機特性，以各級配送中心建設成本最小化、物流配送成本期望值最小化為目標，構建了多目標規劃模型。選用遺傳算法提出了設計模型的求解算法并給出了編碼設置，物流配送成本計算等關鍵步驟設計。最后，采取算例驗證了模型與算法的有效性。

運輸經濟；隨機行駛時間；配送中心選址；物流車輛路徑；商貿物流；物流網絡

1　引言

2014年9月24日，中華人民共和國商務部發布了《商務部關于促進商貿物流發展的實施意見》（商流通函［2014］790號），提出“商貿物流是指與批發、零售、住宿、餐飲、居民服務等商貿服務業及進出口貿易相關的物流服務活動，是整個物流過程中對成本影響比較大的環節，新技術應用和商業模式創新最為集中，作為現代物流的重要組成部分，直接關系到生產資料流通和生活資料流通的順利運行”。

在滿足商貿物流需求的前提下對商貿物流網絡體系構建成本最小化，是提升商貿利潤的重要手段。因此，如何使商貿物流網絡體系構建成本最小化，成為了商貿物流可持續發展的關鍵環節。商貿物流網絡構建成本包含兩個方面：各級配送中心的建設成本；各級配送中心之間的物流配送成本。那么，商貿物流網絡體系構建成本最小化就等價于綜合考慮各級配送中心的建設成本最小化、各級配送中心之間的物流配送成本最小化。

各級配送中心構建可以歸屬于設施選址問題（Facility Location Problem，FLP）［1］。設施選址問題可以分為連續設施選址問題［2-3］（Continuous Facility Location Problem）與離散設施選址問題（Discrete FacilityLocation Problem）［4-6］。本文的配送中心選址問題屬于離散設施選址問題。物流配送成本由配送車輛路徑決定，歸屬于車輛路徑問題（Vehicle Routing Problem，VRP），最早由Dantzig和Ramser［7］于1959年提出，該問題可定義［8］為：對于一系列裝貨點和（或）卸貨點，組織適當的行車線路，使車輛有序地通過它們，在滿足一定的約束條件下（如貨物需求量、發送量、交發貨時間、車輛容量限制、行駛里程限制、時間限制等），達到一定的目標（如路程最短、費用最少、時間盡量少、使用車輛數盡量少等）。VRP問題一直是學者們研究的熱門問題［9-11］。

在物流配送系統中，配送中心選址問題與在此基礎上的車輛路徑問題相互影響［12］，可以同時決策設施選址問題與車輛路徑問題。文獻［13］研究了競爭環境下截流設施選址與帶時間窗的多中心車輛路徑問題。文獻［14］構建了報廢汽車回收物流網絡選址－路徑優化模型，旨在解決拆解中心選址問題、中轉場選址問題、拆解中心和中轉場的建設數目以及車輛路徑問題。在文獻［12-14］中物流車輛的行駛時間均為固定時間。在實際過程，給定距離下物流車輛的行駛時間具有不確定特性。不確定行駛時間具有隨機行駛時間、模糊行駛時間等多種形態，本文將研究物流車輛行駛時間為隨機時間的情況，其他類型的不確定行駛時間可以通過擴展本文方法進行研究。綜上，本文將研究隨機行駛時間下商貿物流網絡設計問題，同時優化商貿配送中心選址與商貿物流配送的車輛路徑。

2　問題分析

商貿物流網絡結構示意如圖1所示。整個商貿物流服務范圍被劃分為若干個服務區域，每一個區域由相應的各級物流配送中心構成。圖1中商貿物流的服務范圍被劃分為A1、A2、A3、A44個服務區域，每一個服務區域內存在1級配送中心與若干個2級配送中心，由1級配送中心向本服務區域的所有2級配送中心運輸商貿貨物，例如A1服務區域中存在1級配送中心B1與6個2級配送中心（A1-1、A1-2、A1-3、A1-4、A1-5、A1-6），由B1向A1-1、A1-2、A1-3、A1-4、A1-5、A1-6配送商貿貨物，經過優化后配送路徑為B1→A1-1→A1-2→A1-3→B1、B1→A1-4→A1-5→A1-6→B1，共需要兩輛配送車輛。商貿物流網絡結構可以應用于零售、餐飲等多個領域，例如應用于餐飲時1級配送中心B1與6個相應的2級配送中心（A1-1、A1-2、A1-3、A1-4、A1-5、A1-6）可分別對應餐飲原料配送中心與固定的餐飲店面。在本文的后續研究中，采取1級、2級配送中心的模式（1個1級配送中心與若干個2級配送中心），可以通過增加配送中心等級的形式將本文方法擴展應用到結構更復雜的商貿物流網絡設計研究中，例如1級配送中心→2級配送中心→3級配送中心的商貿物流網絡結構形式。

圖1　商貿物流網絡示意圖

商貿物流網絡設計的流程包含以下幾個主要步驟：

（1）將服務范圍劃分若干個服務區域，服務區域界限即可以與所在縣市的行政區域保持一致，也可以按照街道、居住小區、商圈的方式進行劃分；

（2）在服務區域劃定后，在每一個服務區域內構建1級、2級配送中心的候選地址集合；

（3）預測2級配送中心點的商貿物流需求；

（4）構建不同的1級、2級配送中心的組合方案，并確定該組合方案下的物流配送路徑；

（5）計算每一個組合方案的配送中心建設成本與物流配送成本，經過比選確定最優方案。

3　數學模型構建

當物流車輛行駛時間具有隨機性且分布概率已知時，每一個行駛時間對應一個情景s。在隨機環境中，每一個情景對應著一個固定的物流車輛行駛時間，情景s可以看作是未來不確定因素的某一種實現，或對不確定因素在未來時間段演化情況的一種描述［15］。

3.1優化目標

按照上節分析，商貿物流網絡設計將首先劃定若干服務區域，那么該問題就變為針對每一個服務區域決策1個1級配送中心和若干個2級配送中心的選址，并決定1級配送中心至所有2級配送中心的物流配送路徑。本節針對給定的服務區域建立數學模型，決策該服務區域內1級與2級配送中心的選址及物流車輛路徑，建模的優化目標為1級與2級配送中心的建設成本、物流配送成本。物流配送成本一般與運輸時間或距離成正比，本文選用物流配送時間衡量物流配送成本。綜上，優化目標為1級與2級配送中心的建設成本、物流車輛的總行駛時間。

3.2模型假設

（1）1級、2級配送中心的選址候選集合已知；

（2）2級配送中心需要修建的數量已知；

（3）2級配送中心所需的物流需求已知，該需求為固定需求；

（4）物流車輛行駛時間具有隨機特性，且概率密度函數已知；

（5）所有配送均采取相同類型的物流配送車輛。

3.3變量說明

M—1級配送中心的選址候選位置集合；

N—2級配送中心的選址候選位置集合；

S—情景s集合，每一個情景s對應一個固定的物流車輛行駛時間；

δ（s）—情景s的概率密度函數；

tijs—情景s下從配送中心i與配送中心j之間的物流車輛行駛時間，其中s∈S，i、j∈M∪N且i≠j；

dn—2級配送中心建設在位置n時需要的配送需求量，該需求量可以通過調研位置n服務范圍內現有與潛在商貿物流企業獲得，n∈N；

qm—1級配送中心在位置m上建設時的建設成本，m∈M；

pn—2級配送中心在位置n上建設時的建設成本，n∈N；

ω—2級配送中心的建設數目；

K—物流配送車輛集合；

g—單輛配送車輛所能承載的最大容量；

κ—2級配送中心需要服務的最小物流需求；

xm—0-1決策變量，當xm=1時在位置m上建設1級配送中心，否則xm=0，m∈M；

yn—0-1決策變量，當yn=1時在位置n上建設2級配送中心，否則yn=0，n∈N；

zijk—0-1決策變量，當車輛k從配送中心i直接到達配送中心j時為1，否則為0，其中i、j∈M∪N且i≠j；

3.4多目標規劃模型

其中，式（1）為目標函數，表示配送中心的建設成本、物流配送成本（物流車輛總營運時間）最小化，β1與β2分別是多目標權重系數，且β1+β2=1。約束（2）表示每一個2級配送中心只被一輛物流配送車輛送貨服務。約束（3）為流量守恒約束，進入配送中心的配送車輛數量與離開配送中心的配送車輛數量相當。約束（4）為物流配送車輛的容量限制約束。約束（5）表示建設的2級配送中心需要滿足一定規模的物流需求。約束（6）、約束（7）為邏輯約束，表示只有配送中心被建造時它才能被配送車輛服務。約束（8）表示2級配送中心的建設數量約束。約束（9）、（10）、（11）為0-1變量邏輯約束。

4　求解算法設計

4.1算法整體描述

按照上文分析，商貿物流網絡設計問題被分解為設施選址問題與車輛路徑問題，這兩個問題均可以用遺傳算法（Genetic Algorithm，GA）有效求解［16-17］。選用遺傳算法進行求解設計。由于車輛路徑優化方案依托于配送中心選址方案，因此針對每一個配送中心選址方案都要決策其車輛路徑優化方案才能計算目標函數（式（1））。將整個商貿物流網絡設計的算法簡稱為NDPGA，給定配送中心選址方案下求解配送方案的子算法簡稱為VRP-GA。整個求解算法步驟如圖2所示，NDP-GA的染色體適應度按照式（1）計算。

圖2　算法計算流程

4.2NDP-GA關鍵步驟設計

（1）染色體編碼設計。決策變量xm、yn均為0-1整數變量，染色體編碼選用0-1編碼的形式，每一個配送中心候選位置對應一個染色體編碼，當染色體編碼為1時表示該位置上被建設相應級別的配送中心，為0表示不建設。圖3為具體示例，1級配送中心候選位置有4個，2級配送中心候選位置有8個，解碼表示：在位置2修建了1級配送中心、在位置7/9/10/12修建了2級配送中心。

圖3　NDP-GA編碼設計示意

（2）選擇、交叉與變異操作。選擇操作采取輪盤賭的形式。交叉操作為了保持染色體的可行性（1級配送中心數量為1個，2級配送中心建設數量為ω個），在進行交叉操作時交換兩個染色體全部xm編碼，交換yn相同位置的基因，判斷2級配送中心的建設數量是否為ω個，如果不是，對染色體的yn編碼進行修正。交叉算子采取單點變異算子操作，隨機選擇兩個位置的基因（要么都是xm的編碼，要么都是yn的編碼）進行交換，同樣需要判斷2級配送中心的建設數量是否為ω個，如果不是，對染色體的yn編碼進行修正。

4.3NDP-GA關鍵步驟設計

（1）染色體編碼設計。染色體編碼選取整數編碼的形式，表示物流車輛按照次序服務的2級配送中心序列，-1表示1級配送中心，其他正數表示相應的2級配送中心序號。例如，編碼（-1，1，4，5，-1，6，3，2，-1）解碼后表示有兩輛車配送，車輛1依次對2級配送中心1、4、5進行配送服務，車輛2依次對2級配送中興6、3、2進行配送服務。

（2）物流配送成本計算。物流配送成本由物流車輛總運輸時間表示，而物流車輛行駛時間具有隨機特性，因此采用隨機模擬的方式計算物流配送成本。首先，設定生成情景樣本的數量為ξ。接著，根據隨機車輛運營時間的概率分布模擬生成ξ個情景，計算每一個情景s下的物流車輛總運輸時間。最后，選用文獻［18］的方法，假設所有情景s發生的概率均相同，計算物流車輛總運輸時間F2，具體公式如下：

5　算例分析

算例包含12個結點，其相互位置關系如圖4所示。其中，結點1-3為1級配送中心候選地址，結點4-12為2級配送中心候選地址。表1為各結點之間的物流車輛行駛時間，設定隨機運輸時間符合正態分布，表中數據格式為（μ，σ），μ，σ分別表示物流車輛行駛時間的均值與方差。表2為各位置配送中心的建設成本與運輸需求。ω取6，出于2級配送中心均勻分布的考慮，限定結點4、5、6至少要建造2個2級配送中心，結點7、8至少要建造1個2級配送中心，結點9、10至少要建造1個2級配送中心，結點11、12至少要建造1個2級配送中心。2級配送中心需要服務的最小物流需求κ為11.5t。單輛物流配送車輛所能承載的最大容量g取7t/車。NDP-GA染色體種群設定為50個，交叉概率與變異概率各為0.6、0.15，最大迭代計算次數為300次。VRP-GA染色體種群設定為80個，交叉概率與變異概率各為0.7、0.2，最大迭代計算次數為500次。

式（1）的多目標權重系數β1與β2取多組值進行計算，分別是β1=0.9、β2=0.1，β1=0.7、β2=0.3，β1=0.4、β2= 0.6，β1=0.1、β2=0.9。優化結果見表3。圖5為β1=0.9、β2=0.1時的迭代曲線，算法在63次迭代后計算獲得最優值，驗證了設計算法的有效性。從表3中可以看出，隨著不同β1與β2的組合，優化結果不同，隨著β1的降低、β2的升高，優化結果更偏向于選擇運輸成本更低的方案。

表1　結點之間的隨機行駛時間（h）

表2　結點的配送中心建造成本與物流需求

表3　優化結果

圖4　算例示意圖

圖5　當β1=0.9、β2=0.1時的迭代曲線

6　結語

商貿物流是我國物流未來發展的重要方向。本文研究商貿物流網絡設計問題，將該問題拆解為配送中心選址決策與物流配送路徑決策。基于物流車輛行駛時間具有隨機特性，將該變量設置為隨機變量，以各級配送中心建設成本最小化、物流配送成本期望值最小化為目標，構建了多目標規劃模型。結合遺傳算法給出了求解模型的求解步驟，并給出了編碼設置、物流配送成本計算等關鍵步驟設計。通過算例驗證了本文模型與算法的有效性。

［1］秦進.多商品物流網絡設計相關優化模型及算法研究［D］.長沙：中南大學，2006.

［2］Durmaz E，Aras N，Altinel I.Discrete approximation heuristics for the capacitated continuous location-allocation problem with probabilistic customer locations［J］.Computersamp;Operations Research，2009，36（7）：2 139-2 148.

［3］Dinler D，Tural M K，Iyigun C.Heuristics for a continuous multi-facility location problem with demand regions［J］.Computersamp;Operations Research，2015，62：237-256.

［4］Harkness J，ReVelle C.Facility Location with Increasing Production Costs［J］.European Journal of Operational Research，2003，145（3）：1-13.

［5］Wu T H，Lin J N.Solving the competitive discretionary service facility location problem［J］.European Journal of Operational Research，2003，144（2）：366.378.

［6］Murat A，Laporte G，Verter V.A global shooting algorithm for the facility location and capacity acquisition problem on a line with dense demand［J］.Computersamp;Operations Research，2016，71：1-15.

［7］Dantzig G，Ramser R.The truck dispatching problem［J］.Management Science.1959，（6）：80-91.

［8］李軍，郭耀煌.物流配送車輛優化調度理論與方法［M］.北京：中國物資出版社，2001.

［9］Scheuerer S.A tabu search heuristic for the truck and trailer routing problem［J］.Computersamp;Operations Research，2006，33：894-909.

［10］Avci M，Topaloglu S.A hybrid metaheuristic algorithm for heterogeneous vehicle routing problem with simultaneous pickup and delivery［J］.Expert Systems with Applications，2016，53（1）：160-171.

［11］Figliozzi M A.The time dependent vehicle routing problem with time windows：Benchmark problems，an efficient solution algorithm，and solution characteristics［J］.Transportation Research Part E：Logistics，2012，48（3）：616-636.

［12］曾慶成，楊忠振，蔣永雷.配送中心選址與車輛路徑一體優化模型與算法［J］.武漢理工大學學報（交通科學與工程版），2009，33（2）：267-270.

［13］王道平，徐展，楊岑.基于競爭環境的截流設施選址與車輛路徑問題［J］.控制與決策，2015，30（6）：1 054-1 058.

［14］賀政綱，鄒曄，楊曉.報廢汽車物流網絡選址-路徑問題建模與求解算法研究［J］.公路交通科技，2016，33（3）：138-145.

［15］張人千，王如平.隨機能力規劃的Scenario模型及其決策風險分析［J］.系統工程理論與實踐，2009，29（1）：55-63.

［16］Fernandes D R，Rocha C，Aloise D，Ribeiro G M，Santos E M，Silva A.A simple and effective genetic algorithm for the twostage capacitated facility location problem［J］.Computersamp; Industrial Engineering，2014，75：200-208.

［17］Razali N M.An Efficient Genetic Algorithm for Large Scale Vehicle Routing Problem Subject to Precedence Constraints［J］. Procedia-Social and Behavioral Sciences，2015，195（3）：1 922-1 931

［18］Yin Y F，M Madanat S，L X Y.Robust improvement schemes for road networks under demand uncertainty［J］.European Journal of Operational Research，2009，198（2）：470-479.

Study on Trade Logistics Network Design with Stochastic Traveling Time Consideration

Jing Chunguang
（China Academy of Transportation Sciences， Beijing 100029， China）

In this paper， in view of the issues in the design of the trade logistics network and with the minimal network establishmentcost as the target， we attempted to finalize the location of the various levels of distribution centers on the network and the running route of thelogistics vehicles. During the optimization process， we considered the stochasticity of the traveling time of the logistics vehicles andestablished the programming model targeting at minimizing the total distribution center construction cost and the expected logisticsdistribution cost. Then we adopted the genetic algorithm to solve the model and presented the programming and calculation steps. At the end，through a numerical example， we demonstrated the validity of the model and algorithm.

transportation economy； stochastic traveling time； location allocation of distribution center； routing of logistics vehicle；trade logistics； logistics network

F224；F253.9

A

1005-152X（2016）08-0064-06

10.3969/j.issn.1005-152X.2016.08.018

2016-07-04

景春光（1976-），男，山東東營人，高級工程師，研究方向：交通規劃。