基于點(diǎn)線能力約束的多層級節(jié)點(diǎn)協(xié)同布局優(yōu)化模型及算法研究

劉 杰，黎浩東，張 萌

(1.山東交通學(xué)院交通與物流工程學(xué)院，濟(jì)南250357；2.北京交通大學(xué)交通運(yùn)輸學(xué)院，北京100044)

0 引言

隨著我國物流產(chǎn)業(yè)的飛速推進(jìn)，如何快速滿足用戶運(yùn)輸需求，提升用戶體驗(yàn)，是當(dāng)前物流企業(yè)主要發(fā)展方向.部分電商企業(yè)開始建設(shè)全國性倉儲物流基地、區(qū)域分撥中心及縣級物流中心，多層級軸幅式網(wǎng)絡(luò)架構(gòu)的雛形初步形成.在軸幅式網(wǎng)絡(luò)中，物流節(jié)點(diǎn)布局不僅影響物流成本，同時也對服務(wù)水平產(chǎn)生重要影響，在物流業(yè)降本增效的背景下，研究多級物流節(jié)點(diǎn)布局問題具有重要理論和現(xiàn)實(shí)意義.

國內(nèi)外眾多學(xué)者在物流節(jié)點(diǎn)選址方面取得了豐碩的研究成果：Teixeira等[1]提出了容量限制的嵌套型分層中位模型；Sanhin[2]以最小化物流需求的加權(quán)距離為目標(biāo)函數(shù)，研究了基于網(wǎng)絡(luò)流的多層級車站問題；Redza[3]重點(diǎn)針對多層設(shè)施選址問題的分類、模型及應(yīng)用進(jìn)行了文獻(xiàn)綜述；Nicholas[4]構(gòu)建了多目標(biāo)多層級最大覆蓋集模型；Hamid[5]針對2個分配模式下無容量限制的p中位問題進(jìn)行了系統(tǒng)研究；張贏[6]，李婷婷[7]分別構(gòu)建了多層級客運(yùn)樞紐布局優(yōu)化模型；江志娟[8]綜合考慮成本、時間及溫室氣體排放因素，構(gòu)建了基于可持續(xù)發(fā)展的聯(lián)運(yùn)樞紐選址—分配模型；鄧波爾[9]采用集對分析法及改進(jìn)層次分析法，研究了鐵路客運(yùn)站的選址問題.通過以上成果分析，將點(diǎn)線運(yùn)能融入至多級節(jié)點(diǎn)布局的研究相對較少，隨著“樞紐+通道+網(wǎng)絡(luò)”物流體系的形成，通道運(yùn)能將成為制約節(jié)點(diǎn)布局的重要因素，同時結(jié)合實(shí)際大規(guī)模物流網(wǎng)絡(luò)進(jìn)行網(wǎng)絡(luò)預(yù)處理也是當(dāng)前未涉及的研究.因此，本文從實(shí)際出發(fā)，提出了物流網(wǎng)絡(luò)簡化處理策略，考慮物流節(jié)點(diǎn)與通道運(yùn)能影響，對基于點(diǎn)線能力約束的多層級節(jié)點(diǎn)協(xié)同布局問題展開研究，為運(yùn)輸需求導(dǎo)向下物流節(jié)點(diǎn)布局提供一定決策依據(jù).

1 物流網(wǎng)絡(luò)拓?fù)錁?gòu)建

物流節(jié)點(diǎn)布局問題，是基于需求節(jié)點(diǎn)特征、備選節(jié)點(diǎn)屬性、物流通道運(yùn)能及各級物流節(jié)點(diǎn)要求綜合確定節(jié)點(diǎn)空間布局結(jié)構(gòu).結(jié)合實(shí)際中需求節(jié)點(diǎn)屬性、并考慮節(jié)點(diǎn)區(qū)位條件、發(fā)展基礎(chǔ)及發(fā)展?jié)摿Γ_定各級物流節(jié)點(diǎn)備選集合，如圖1所示.圖1中一級節(jié)點(diǎn)為物流節(jié)點(diǎn)體系中最高等級節(jié)點(diǎn)，是一個城市物流功能主要載體，如圖中一級備選節(jié)點(diǎn)I1及I2；二級物流節(jié)點(diǎn)是服務(wù)于產(chǎn)業(yè)的功能性節(jié)點(diǎn)，承擔(dān)城市物流中轉(zhuǎn)、倉儲、配送等職能，如圖中二級備選節(jié)點(diǎn)S1～S5.實(shí)際物流網(wǎng)絡(luò)中由于包含需求點(diǎn)(圖1中q1～q12所示)、備選節(jié)點(diǎn)、中間節(jié)點(diǎn)(圖1中n1～n12所示)及眾多弧段，導(dǎo)致網(wǎng)絡(luò)規(guī)模較大，容易產(chǎn)生求解時間過長問題.基于最短路徑、共同弧段及通道運(yùn)能3個因素，對實(shí)際物流網(wǎng)絡(luò)進(jìn)行簡化處理.網(wǎng)絡(luò)簡化處理采用3種策略：當(dāng)需求點(diǎn)集與備選點(diǎn)的最短路徑中，存在共同弧段且共同弧段運(yùn)能為路徑瓶頸時，即該共同弧段運(yùn)能為路徑中所有弧段運(yùn)能最小值，對于瓶頸的識別采用最短路A Star算法進(jìn)行求解，在該種情景下借鑒節(jié)點(diǎn)拆分的思想描述共同弧段運(yùn)能影響[10]，如圖2(a)所示，圖中 I1′為I1節(jié)點(diǎn)拆分后的節(jié)點(diǎn)，通過弧段(I1′,I1)表征共同弧段的能力的影響；當(dāng)需求點(diǎn)集與備選點(diǎn)的最短路徑中，存在共同弧段但共同弧段不為路徑瓶頸時，則將需求點(diǎn)集與備選點(diǎn)相連，弧段運(yùn)能為路徑運(yùn)能，如圖2(b)所示；當(dāng)需求點(diǎn)與備選節(jié)點(diǎn)間不存在共同弧段時，則將需求點(diǎn)集與備選點(diǎn)相連，同樣弧段運(yùn)能為路徑運(yùn)能，如圖2(c)所示.通過對網(wǎng)絡(luò)簡化處理，減少實(shí)際網(wǎng)絡(luò)的中間節(jié)點(diǎn)及弧段數(shù)量，僅保留需求點(diǎn)、路徑瓶頸節(jié)點(diǎn)、備選節(jié)點(diǎn)及相應(yīng)弧段.同時，實(shí)際路徑中能力值通過瓶頸路段、需求點(diǎn)與備選點(diǎn)間弧段的運(yùn)輸能力體現(xiàn)，故拆分后網(wǎng)絡(luò)特征未發(fā)生較大改變，但與實(shí)際物流網(wǎng)絡(luò)相比，網(wǎng)絡(luò)規(guī)模明顯降低，從而能有效提升問題求解速度.

圖1 多級物流節(jié)點(diǎn)及需求點(diǎn)分布圖Fig.1 Hierarchical logistics nodes and demand nodes layout

按照網(wǎng)絡(luò)簡化處理策略，考慮各級節(jié)點(diǎn)最大服務(wù)距離因素，得到圖1簡化處理后的網(wǎng)絡(luò)如圖3所示，圖中I1′及I2′為一級備選節(jié)點(diǎn)拆分后子節(jié)點(diǎn)；S2′、S3′及 S4′為二級備選節(jié)點(diǎn)拆分后的子節(jié)點(diǎn).為避免流量分配過程中，因能力限制陷入死循環(huán)，在網(wǎng)絡(luò)中設(shè)置超級節(jié)點(diǎn)O，將需求點(diǎn)與超級節(jié)點(diǎn)O相連，得到該需求點(diǎn)的超級路徑，將超級路徑設(shè)置為較大費(fèi)用值與能力值，只有其他路徑流量超過能力值時，才分配至超級路徑.本文需求點(diǎn)的超級路徑在問題求解時，根據(jù)需求點(diǎn)數(shù)量自動生成，在此僅展示需求點(diǎn)q1的超級路徑.

圖3 節(jié)點(diǎn)拆分后的物流網(wǎng)絡(luò)Fig.3 Logistics network after nodes splitting

2 多層級物流節(jié)點(diǎn)協(xié)同布局模型

2.1 模型假設(shè)

(1)決策周期內(nèi)物流需求不發(fā)生較大的波動，決策周期為1年.

(2)網(wǎng)絡(luò)中點(diǎn)線條件不發(fā)生較大變化.

2.2 符號定義

(1)集 合.

A為網(wǎng)絡(luò)中弧段集合，a∈A；I為網(wǎng)絡(luò)中需求點(diǎn)集合，i∈I；J為網(wǎng)絡(luò)中備選點(diǎn)集合，j∈J；K={1,2,…}為物流節(jié)點(diǎn)等級的集合，數(shù)字越靠前表明等級越高，k∈K.

(2)參 數(shù).

Cij為節(jié)點(diǎn)對i，j的單位運(yùn)輸費(fèi)用(元)；m(k)為建設(shè)第k級物流節(jié)點(diǎn)的費(fèi)用(萬元)；Qi為需求點(diǎn)i的運(yùn)量(t)；M為一充分大正整數(shù)；n(k)為第k級物流節(jié)點(diǎn)的最大數(shù)量；b(k)為建設(shè)第k級物流節(jié)點(diǎn)運(yùn)力下限值；B(k)為建設(shè)第k級物流節(jié)點(diǎn)的運(yùn)力上限值；dij為節(jié)點(diǎn)對i，j間的距離(km)；Ca為弧段a的運(yùn)輸能力；D(k)為第k級物流節(jié)點(diǎn)的最大服務(wù)距離(km)；為0-1參數(shù)，表示節(jié)點(diǎn)對i,j是否經(jīng)過弧段a，如果節(jié)點(diǎn)對i,j經(jīng)過弧段a，=1，否則，=0；Z為系統(tǒng)總費(fèi)用值.

(3)決策變量.

2.3 模型構(gòu)建

多層級物流節(jié)點(diǎn)協(xié)同布局模型，應(yīng)考慮各級節(jié)點(diǎn)覆蓋距離、節(jié)點(diǎn)及弧段運(yùn)輸能力，確定各級節(jié)點(diǎn)選址，得到需求點(diǎn)與物流節(jié)點(diǎn)間的分配關(guān)系，以更加合理、經(jīng)濟(jì)的方式滿足區(qū)域內(nèi)物流運(yùn)輸需求.以運(yùn)輸費(fèi)用最小化為目標(biāo)，構(gòu)建多層級物流節(jié)點(diǎn)協(xié)同布局模型為

式(1)為目標(biāo)函數(shù)，表示總費(fèi)用最小化.式(2)～式(13)為約束條件：式(2)表示任一需求點(diǎn)至少分配一個物流節(jié)點(diǎn)；式(3)表示任一備選節(jié)點(diǎn)最多只能成為一個物流節(jié)點(diǎn)；式(4)為物流需求總量約束；式(5)為連鎖關(guān)系約束，表示當(dāng)需求節(jié)點(diǎn)i分配給物流節(jié)點(diǎn)j時，備選節(jié)點(diǎn)j必然為物流節(jié)點(diǎn)；式(6)為第k級物流節(jié)點(diǎn)的總量約束；式(7)和式(8)為物流節(jié)點(diǎn)能力約束，物流節(jié)點(diǎn)所服務(wù)需求點(diǎn)應(yīng)滿足最大能力與最小能力的約束；式(9)為物流節(jié)點(diǎn)服務(wù)距離約束；式(10)為弧段運(yùn)輸能力約束；式(11)～式(13)為決策變量邏輯關(guān)系約束.

3 求解算法

多層級物流節(jié)點(diǎn)協(xié)同布局模型為整數(shù)規(guī)劃模型，模型包括各級節(jié)點(diǎn)選址及分配關(guān)系的0-1決策，也包括流量分配決策值.模型中關(guān)鍵決策變量為分配關(guān)系的決策值.當(dāng)分配關(guān)系確定后，節(jié)點(diǎn)選址決策也隨之確定，模型以分配關(guān)系為重點(diǎn)構(gòu)建初始解結(jié)構(gòu)，采用隨機(jī)策略生成初始解.假設(shè)物流網(wǎng)絡(luò)中有一級備選節(jié)點(diǎn)2個，二級備選節(jié)點(diǎn)2個，需求點(diǎn)4個，隨機(jī)生成的初始解如圖4所示.圖4中“1”表示該需求點(diǎn)分配給相應(yīng)等級的物流備選點(diǎn).

圖4 初始解結(jié)構(gòu)圖Fig.4 Initial solution structure

定義初始解結(jié)構(gòu)后，采用和聲搜索算法進(jìn)行求解.和聲搜索算法廣泛應(yīng)用于車輛路徑問題、VRP等問題研究中，對于求0-1變量問題具有良好的求解效果.重點(diǎn)針對新和聲生成策略進(jìn)行分析，提出改進(jìn)的和聲搜索算法.采用兩種和聲生成策略，分別為接受優(yōu)質(zhì)和聲記憶庫和音調(diào)微調(diào).假設(shè)生成新和聲第i個和聲中第l個音調(diào)決策值，n為模型中決策變量的總數(shù)量；設(shè)置和聲記憶庫取值概率Hm、音調(diào)微調(diào)概率Ac.模型中需求點(diǎn)間的分配關(guān)系具有較強(qiáng)關(guān)聯(lián)性，任一需求點(diǎn)分配關(guān)系的調(diào)整，將導(dǎo)致其余需求點(diǎn)分配關(guān)系的變化，故在接受和聲記憶庫的操作時也采用接受音調(diào)片段及單一音調(diào)的操作.具體操作如下：

(1)隨機(jī)生成一個隨機(jī)數(shù)ra，如果ra＜Hm，則采用接受優(yōu)質(zhì)和聲記庫的操作；否則，以1-Hm的概率對當(dāng)前音調(diào)進(jìn)行取反操作.

(2)在接受和聲記憶庫音調(diào)操作中，生成隨機(jī)數(shù)ra1，如果滿足ra1＜Ac，從當(dāng)前位置至和聲尾部，隨機(jī)生成音調(diào)位置p2，接受和聲記憶庫中當(dāng)前p1～p2位置所有音調(diào)；否則，接受當(dāng)前位置音調(diào).假設(shè)該變量為，新和聲生成的相關(guān)機(jī)制如圖5所示.

圖5 新和聲生成策略Fig.5 Generation strategy for new harmony

確定新和聲生成機(jī)制后，和聲搜索算法的詳細(xì)步驟如文獻(xiàn)[11]所示，不做贅述。

4 算例分析

以山東省某縣物流園區(qū)及配送中心選址為案例，測試模型和算法的適用性.結(jié)合該縣產(chǎn)業(yè)、經(jīng)濟(jì)及人口數(shù)據(jù)確定物流需求點(diǎn)20個，物流需求點(diǎn)屬性信息如表1所示.

按照物流節(jié)點(diǎn)選址原則，在全縣選擇物流園區(qū)備選點(diǎn)2個，配送中心備選點(diǎn)14個，各級備選節(jié)點(diǎn)信息如表2所示.為簡化求解，算例不設(shè)置節(jié)點(diǎn)最小能力約束.

表 1 物流需求節(jié)點(diǎn)屬性特征Table 1 Attribute for logistics demand nodes

實(shí)際物流網(wǎng)絡(luò)中，該縣共有節(jié)點(diǎn)1 020個，弧段2 780條，采用網(wǎng)絡(luò)簡化處理策略進(jìn)行預(yù)處理，設(shè)置物流園區(qū)、配送中心服務(wù)半徑分別為100 km和10 km，對不滿足服務(wù)半徑要求的弧段剪枝處理，得到拆分后的網(wǎng)絡(luò)如圖6所示，各節(jié)點(diǎn)間的距離如表3所示.

設(shè)置單位運(yùn)輸費(fèi)用為0.6元/(km?t)，物流園區(qū)單位建設(shè)成本為1 000萬元，配送中心單位建設(shè)成本為100萬元，超級路徑費(fèi)用為10 000萬元；設(shè)置物流園區(qū)最大數(shù)量為1，配送中心最大數(shù)量為10；設(shè)置和聲記憶庫取值概率Hm=0.8，接受音調(diào)概率Ac=0.7，和聲記憶庫Hs=5；最大創(chuàng)作次數(shù)Tm=100，計算得到該縣多級物流節(jié)點(diǎn)協(xié)同布局的總費(fèi)用值為2 412.61萬元，目標(biāo)值迭代曲線如圖7所示.

表 2 各級物流節(jié)點(diǎn)備選集合信息Table 2 Information for set of hierarchical nodes

圖6 多級節(jié)點(diǎn)選址網(wǎng)絡(luò)拓?fù)銯ig.6 Network topology for hierarchical nodes location

表 3 網(wǎng)絡(luò)中弧段屬性特征Table 3 Attribute for links in logistics network

通過與傳統(tǒng)和聲搜索算法對比，兩者均收斂于同一值，但是改進(jìn)的和聲搜索算法在新和聲生成操作中增加了和聲記憶庫指導(dǎo)，收斂速度更快.計算得到各級物流節(jié)點(diǎn)選址及分配方案如圖8所示.該方案下物流園區(qū)選址于P2，該節(jié)點(diǎn)與鐵路貨運(yùn)站及公路客運(yùn)樞紐距離較近，具備良好的多式聯(lián)運(yùn)條件.基于成本因素選取10個配送中心.

圖7 算法收斂迭代圖Fig.7 Algorithm convergence iterative graph

圖8 各層級物流節(jié)點(diǎn)選址及分配方案Fig.8 Location and assignment for hierarchical nodes

物流園區(qū)及配送中心最大數(shù)量變化時，分析其對節(jié)點(diǎn)布局方案及費(fèi)用的影響，得到不同情景下物流選址費(fèi)用如表4所示.當(dāng)物流園區(qū)最大數(shù)量為2個時，節(jié)點(diǎn)布局方案與情景3相同，說明1個物流園區(qū)數(shù)量為最優(yōu)方案；當(dāng)物流園區(qū)數(shù)量保持不變，配送中心最大數(shù)量為9時，總費(fèi)用值明顯上升，這是因?yàn)椴糠中枨蠊?jié)點(diǎn)難以滿足配送中心服務(wù)半徑要求，需求分配到超級路徑，帶來運(yùn)輸費(fèi)用激增；當(dāng)配送中心最大數(shù)量為11時，節(jié)點(diǎn)布局方案與情景3相同，說明10個配置中心為最優(yōu)方案.通過情景分析，物流園區(qū)1個，配送中心10個為最佳節(jié)點(diǎn)配置數(shù)量.

表 4 不同情景下物流選址費(fèi)用Table 4 Cost of nodes location under different scenarios

5 結(jié)論

本文從實(shí)際物流網(wǎng)絡(luò)出發(fā)，提出物流網(wǎng)絡(luò)簡化處理的3個策略；結(jié)合多分配模式下物流節(jié)點(diǎn)選址模型，構(gòu)建了基于點(diǎn)線能力約束的多級節(jié)點(diǎn)協(xié)同布局優(yōu)化模型；鑒于模型0-1決策變量的特征，采用改進(jìn)的和聲搜索算法進(jìn)行求解；最后采用實(shí)際案例驗(yàn)證進(jìn)模型及算法具有良好適應(yīng)性，能夠?qū)Χ嗉壩锪鞴?jié)點(diǎn)的布局問題提供良好決策依據(jù).本文在模型構(gòu)建時，對于需求節(jié)點(diǎn)逆向物流特征的考慮相對較少，模型中如何結(jié)合需求點(diǎn)的逆向物流特征是下一步研究方向.