特大型城市地下物流多層級網(wǎng)絡(luò)優(yōu)化研究

劉博宇，梁承姬，王 鈺

（上海海事大學(xué) 物流科學(xué)與工程研究院，上海 201306）

0 概述

由于過多的人口持續(xù)進(jìn)入大中城市，造成城市的交通問題與環(huán)境問題日益嚴(yán)峻。根據(jù)2021 年第7 次全國人口普查數(shù)據(jù)顯示，當(dāng)前我國城鎮(zhèn)化率已突破60%［1］，不斷增長的城市人口使得交通基礎(chǔ)設(shè)施承擔(dān)更大的壓力。隨著居民收入的提高和電子商務(wù)的蓬勃發(fā)展，城市貨運壓力不斷增加，調(diào)查顯示主要干道上超過40%的車輛為貨運車輛［2］。貨流的增加一方面加劇了城市周邊和內(nèi)部的交通擁堵，限制了運輸效率，另一方面也加快了基礎(chǔ)設(shè)施的損耗，由此帶來的交通隱患不容忽視。此外，車輛排放已成為空氣污染的重要來源，特別在一些大型城市，移動源對細(xì)顆粒物（PM2.5）濃度的貢獻(xiàn)率接近50%［3］。交通擁堵、土地資源緊張以及環(huán)境污染等問題已經(jīng)成為限制大型城市發(fā)展的關(guān)鍵障礙。

現(xiàn)有的地面交通壓力使得不少學(xué)者將目光轉(zhuǎn)向地下空間，嘗試通過構(gòu)建地下物流網(wǎng)絡(luò)分擔(dān)地面的運輸壓力，從而有效地緩解交通擁堵問題。地下物流系統(tǒng)（Underground Logistics System，ULS）是一種全新的運輸模式，相較于地面運輸，地下運輸?shù)膱鏊鼮榉忾]，消除了天氣因素的干擾，無人化作業(yè)也保障了運輸?shù)陌踩?，可以實現(xiàn)樞紐間高效穩(wěn)定的貨物運輸。由于運輸過程不占用地面資源，因此可以改善地面交通擁堵狀況，提高城市的居住與交通質(zhì)量。同時，地下集約化運輸能夠顯著降低能源成本，也是實現(xiàn)“雙碳”目標(biāo)的重要途徑［4］。目前許多城市都將地下物流系統(tǒng)的規(guī)劃提上議程，提出要建設(shè)城市地下物流系統(tǒng)。

對于特大型城市而言，擁堵問題尤為尖銳，所需要規(guī)劃的地下物流系統(tǒng)也更為復(fù)雜。首先，諸如北京、上海、東京等特大型城市人口數(shù)量均已超過2 000 萬，由此產(chǎn)生的貨物需求尤其是居民日用品需求遠(yuǎn)遠(yuǎn)超過普通城市，成為城市貨流的重要組成部分。其次，此類城市起步時間最早，地面交通資源大多已被充分開發(fā)利用，通過道路擴(kuò)建應(yīng)對逐漸增加的貨流較為困難［5］。但是，通過構(gòu)建地下物流網(wǎng)絡(luò)系統(tǒng)，在拓展運輸方式的同時，能夠更加充分地利用此類城市相對完善的基礎(chǔ)交通設(shè)施，從而在短時間內(nèi)實現(xiàn)多種運輸系統(tǒng)的高效銜接，提高城市貨運能力。

特大型城市構(gòu)建地下物流系統(tǒng)有利于提高貨運效率、改善城市擁堵和環(huán)境污染，但其前期建設(shè)成本較高，所需的配套設(shè)施更加復(fù)雜，因而需要科學(xué)的、專門的網(wǎng)絡(luò)規(guī)劃設(shè)計。本文針對特大型城市的需求特點，考慮地下深層干線隧道運輸和區(qū)域管廊運輸相結(jié)合的地下運輸方式，研究多層級的地下物流網(wǎng)絡(luò)優(yōu)化設(shè)計方法。

1 相關(guān)研究

研究人員對于地下物流的探索已有數(shù)十年，在研究初期，人們更多地將精力放在評估城市地下物流系統(tǒng)的可行性及有效性上。文獻(xiàn)［6］注意到城市內(nèi)接近飽和的地面空間帶來了嚴(yán)重的交通擁堵問題，提出了新增“地下倉庫”與地面運輸相協(xié)同，并論證了該構(gòu)想在提高交通效率與環(huán)境保護(hù)方面的重要意義。文獻(xiàn)［7］在分析了過高的貨運量給機(jī)場周邊帶來的安全隱患后，提出在達(dá)拉斯沃思堡國際機(jī)場建立地下貨運系統(tǒng)的構(gòu)想，以提高道路通行能力與安全性。

在ULS 逐漸被大眾所認(rèn)識后，人們更多地開始研究ULS 在城市中發(fā)揮的作用。文獻(xiàn)［8］討論了ULS 中貨物和貨運類型的適用性，對比分析了多種集成的ULS 網(wǎng)絡(luò)系統(tǒng)，表示當(dāng)前ULS 在規(guī)劃整合與技術(shù)適應(yīng)方面仍面臨一些困難，并提出跨學(xué)科合作是確保ULS 能夠?qū)崿F(xiàn)的關(guān)鍵因素。文獻(xiàn)［9］分析了城市現(xiàn)有的地下隧道、綜合管廊等設(shè)施，提出了集約化共建方案，并論證了該方案在提高帶狀地下空間的利用率方面的可行性。文獻(xiàn)［10］從城市道路網(wǎng)絡(luò)的角度評估地下物流系統(tǒng)對交通狀態(tài)和排放問題的影響，并以上海外高橋港為例建立了交通分析模型，結(jié)果表明，該系統(tǒng)能夠減少約30%的集裝箱地面運量，有效緩解該區(qū)域的交通運輸壓力。文獻(xiàn)［11］從港口作業(yè)的碳排放方面入手，以碳交易成本為線索構(gòu)建了地下物流優(yōu)化模型，提出通過構(gòu)建地下物流系統(tǒng)實現(xiàn)集裝箱的集疏運，從而有效緩解港口附近主要道路的擁堵問題。文獻(xiàn)［12］考慮了物流過程中的碳排放成本，提出基于地鐵系統(tǒng)建設(shè)城市配送網(wǎng)絡(luò)能夠有效地降低物流成本，豐富了城市物流系統(tǒng)的理論內(nèi)涵。文獻(xiàn)［13］基于系統(tǒng)動力學(xué)提出一種評估ULS 項目發(fā)展和運行的評價模型，并以中國北京市為例，從實證角度出發(fā)證明了ULS 項目具有較好的服務(wù)能力和盈利能力，同時根據(jù)中國正在進(jìn)行的新城區(qū)開發(fā)項目，設(shè)計了綜合地下物流系統(tǒng)［14］，包括網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)、設(shè)施運營、工作流程以及相關(guān)參數(shù)，案例實驗表明，ULS 每年可節(jié)省數(shù)百萬美元的外部成本，進(jìn)一步論證了ULS 的可行性。

隨著對ULS 研究的深入，更多學(xué)者開始嘗試研究地下物流系統(tǒng)的規(guī)劃及管控的優(yōu)化方法，即啟發(fā)式算法完成優(yōu)化過程。文獻(xiàn)［15］規(guī)劃了城市地下物流系統(tǒng)的布局，構(gòu)建了0-1 混合整數(shù)規(guī)劃模型并采用改進(jìn)的蝙蝠算法進(jìn)行求解，證實了該算法的優(yōu)越性。文獻(xiàn)［16］分析了上海外高橋碼頭的交通狀況，提出構(gòu)建地下集裝箱物流系統(tǒng)，基于此建立了地下物流系統(tǒng)混合整數(shù)非線性規(guī)劃模型，并利用啟發(fā)式算法求解。文獻(xiàn)［17］將目光聚焦于集裝箱碼頭的運營層面，以最小化裝卸時間與車輛等待時間為目標(biāo)建立了多目標(biāo)數(shù)學(xué)規(guī)劃模型，并應(yīng)用非支配排序遺傳算法求解，結(jié)果表明，采用車輛分組運輸?shù)姆绞侥軌蝻@著提高ULS 與集裝箱碼頭的運行效率。文獻(xiàn)［18］探討了基于地鐵的ULS 可行性，通過引入地鐵車廂安排和流量分配變量，提出了車廂安排和流量控制的聯(lián)合優(yōu)化問題，并以北京市某地鐵為例進(jìn)行算例分析，驗證了該系統(tǒng)的有效性與高效性。文獻(xiàn)［19］從地鐵系統(tǒng)出發(fā)，提出一種運行決策支持方法，制定了考慮多種標(biāo)準(zhǔn)和出行模式的地鐵貨運機(jī)制，并以南京市為例進(jìn)行了仿真分析，為基于地鐵系統(tǒng)的ULS提供可量化的設(shè)計框架和評估范式。文獻(xiàn)［20］考慮到物流節(jié)點具有不確定性，因此提出基于不確定性圖論的動態(tài)規(guī)劃模型，并通過改進(jìn)模擬退火算法求解以驗證該方法的可行性。文獻(xiàn)［21］從地下隧道流量平衡的角度出發(fā)，引入兩階段聚類法進(jìn)行網(wǎng)絡(luò)設(shè)計，為解決城市ULS 的布局提供了新思路。文獻(xiàn)［22］也以聚類為主要思想，采用迭代自組織數(shù)據(jù)分析法進(jìn)行地下物流節(jié)點的選擇，并通過數(shù)值實驗證明了結(jié)果的合理性。文獻(xiàn)［23］考慮了物流設(shè)施的利用效率，基于成本與節(jié)點轉(zhuǎn)運情況構(gòu)建了多目標(biāo)優(yōu)化模型，并采用層次粒子群算法進(jìn)行求解，驗證了其模型的實用性。

現(xiàn)有研究大多是針對城市內(nèi)的小范圍區(qū)域，貨流量有限且網(wǎng)絡(luò)結(jié)構(gòu)相對簡單，但是特大型城市的貨流量龐大，需要在滿足運力要求的前提下將運量逐級分散，多層級網(wǎng)絡(luò)便能夠很好地滿足這一要求［24］。此外，與小范圍區(qū)域的貨流不同，特大型城市的貨流路徑也更復(fù)雜，不能僅考慮城市內(nèi)部，需要將供應(yīng)鏈的上下游一同納入到網(wǎng)絡(luò)規(guī)劃中。因此，本文考慮了地下物流系統(tǒng)的規(guī)模與上下游設(shè)施，構(gòu)建多層級地下物流網(wǎng)絡(luò)整數(shù)規(guī)劃模型，并引入均值偏移（Mean-Shift，MS）聚類算法對解空間優(yōu)化分解，設(shè)計基于模擬退火思想的雙層啟發(fā)式算法，為特大型城市的ULS 規(guī)劃提供了新的思路。

2 問題描述

考慮m個位于特大型城市城外的物流園區(qū)作為所有貨物的發(fā)出地，記為L=｛L1，L2，…，Lm｝，n個位于需求點地下的接收站為貨物的目的地，記為I=｛I1，I2，…，In｝，k個擬建造的分撥中心備選點，其集合記為J=｛J1，J2，…，Jk｝。所構(gòu)建的地下物流網(wǎng)絡(luò)為包含集合L與集合I全部元素、集合J部分元素以及連接各節(jié)點的地下通道所構(gòu)成的無向網(wǎng)絡(luò)。

本文構(gòu)建的地下物流系統(tǒng)由干線設(shè)施與支線設(shè)施兩部分組成，如圖1 所示。其中干線部分由位于城外的物流園區(qū)、分撥中心以及貫穿其中的隧道構(gòu)成，記作H1=｛L，S，T｝，支線部分由分撥中心、位于需求點地下的接收站與連接其中的管廊通道，記作H2=｛S，G，C｝。貨流在干線設(shè)施中較為集中且運輸批量大，適宜采用深層隧道的形式，而在支線設(shè)施中較為分散，適宜采用淺層管廊的形式。

地下物流網(wǎng)絡(luò)以城外物流園區(qū)與城內(nèi)需求點之間的貨流為主。該部分貨流從城外物流園區(qū)出發(fā)，經(jīng)由城內(nèi)分撥中心打包與轉(zhuǎn)運，并運至地下接收站處集散，途徑為L→S→C，如圖2 所示。最終貨物由接收站轉(zhuǎn)至地面，完成最后一公里運輸，不占用運力資源。

在上述網(wǎng)絡(luò)規(guī)劃中，主要的決策內(nèi)容包括：1）分撥中心的位置；2）需求點與分撥中心的匹配關(guān)系；3）各節(jié)點間的通道建設(shè)；4）貨流的運輸路徑。其中，各節(jié)點的需求量、節(jié)點間的運輸成本均是已知的，物流設(shè)施的最大服務(wù)能力也是有限制的。由于地下設(shè)施建造費用昂貴，盡可能地降低成本便成為地下物流系統(tǒng)建設(shè)的關(guān)鍵。本文擬在滿足各需求點的需求量、物流設(shè)施服務(wù)能力以及運輸路徑可行等約束的條件下，通過選擇分撥中心并為其分配需求點，為貨流量選擇合適的路徑，使得地下物流系統(tǒng)建設(shè)成本以及運輸成本總和最小。

3 模型建立

3.1 問題假設(shè)

與地面運輸相比，地下物流系統(tǒng)的網(wǎng)絡(luò)設(shè)計需要考慮更多要素：一方面，地下物流系統(tǒng)的相關(guān)設(shè)施造價高昂且建成后無法更改，因此通常在已有設(shè)施的基礎(chǔ)上進(jìn)行拓建以降低成本，同時應(yīng)使地下通道的長度盡可能短；另一方面，地下運輸需要特定的載具，其運輸能力受軌道與載具的嚴(yán)格約束?；谏鲜鎏卣?，本文做出如下假設(shè)：

1）分撥中心只能從現(xiàn)有的候選倉庫中選擇產(chǎn)生，并需要支付一定的費用將其激活，且候選倉庫的數(shù)量和位置是已知的。

2）所有的地下通道均為直線，不考慮地質(zhì)特征對通道建設(shè)的影響。

3）各需求點之間不連通，每個需求點僅與一個分撥中心連通，并依托該分撥中心進(jìn)行貨流交換，同時需求點與分撥中心的管廊隧道總能滿足貨流量的要求。

4）連接城外物流園區(qū)與城內(nèi)分撥中心的隧道作為主要通道，必須保持充足運力，總可以滿足運輸需求。

本文所用符號說明如表1 所示。

表1 符號說明Table 1 Symbol description

3.2 多層級地下物流網(wǎng)絡(luò)整數(shù)規(guī)劃模型

本文考慮以總的建設(shè)成本折舊和運營成本最小為目標(biāo)函數(shù)，其中建設(shè)成本包括干線設(shè)施、支線設(shè)施、建立地下接收站以及激活分撥中心的成本，具體表示為：

地下物流系統(tǒng)運營成本包括貨物在干線隧道運輸、在管廊隧道運輸以及由節(jié)點轉(zhuǎn)運的成本，具體表示為：

因此總的目標(biāo)函數(shù)為：

同時考慮如下約束條件：

分撥中心備選點必須先被激活后，才能為需求點提供服務(wù)，即：

其中：M為一個任意大的數(shù)字。

為保證所有的需求點必須接入地下物流系統(tǒng)，每一個需求點僅能與一個轉(zhuǎn)運節(jié)點相連，且每一個分撥中心被激活后必須服務(wù)至少一個需求點，即：

分撥中心至需求點的運量不能超過自身轉(zhuǎn)運能力限制，即：

分撥中心間的通道運輸能力受載具速度與隧道長度的限制，隧道越長則其運輸批次越少，兩個分撥中心間的日流量不能超過隧道的最大運輸能力，即：

分撥中心間連通需要端點處的分撥中心均被激活，即：

若某分撥中心已被激活，則其必須被接入干線網(wǎng)絡(luò)中，至少有一條干線隧道經(jīng)過該點，即：

貨流與隧道連通具有先后順序，則必須有兩點間隧道連通，才能在其間進(jìn)行貨流輸送，即：

其中：M為一個任意大的數(shù)字。

干線設(shè)施中的所有分撥中心與其余分撥至少有一條連通路徑，即：

考慮到分撥中心的運力限制，一個分撥中心最多只能與一個物流園區(qū)連通，即：

對于每一個物流園區(qū)，有且僅有僅一個分撥中心與其直接相連，即：

若物流園區(qū)經(jīng)由某分撥中心轉(zhuǎn)運貨物，則該分撥中心需被激活，即：

貨流在干線與支線設(shè)施之間的總量是一致的，即：

在本模型中，所有的決策變量均為0-1 變量，即：

研究人員已經(jīng)證實了多層級的網(wǎng)絡(luò)規(guī)劃是典型的NP-hard 問題，問題的復(fù)雜程度主要受到需求點數(shù)量與分撥中心備選點數(shù)量的影響。以4 個物流園區(qū)、10 個分撥中心與50 個需求點規(guī)模為例，可能的節(jié)點分配情況為1050種，這樣的規(guī)模不便于求精確解。

4 算法設(shè)計

根據(jù)問題特征，本文采用MS 聚類算法將原始的解空間進(jìn)行分解，并基于聚類結(jié)果進(jìn)行網(wǎng)絡(luò)設(shè)計。首先通過MS 聚類生成一個分撥中心選址的可行方案，并求解與方案相匹配的成本，接著對聚類參數(shù)進(jìn)行擾動并生成新的布局方案。擾動因子在迭代前期影響能力較強(qiáng)，以此擴(kuò)大搜索范圍，而在迭代后期影響能力較弱，使得算法更傾向于提高搜索精度。上述過程不斷迭代直至得到滿意的網(wǎng)絡(luò)設(shè)計方案。

4.1 MS 聚類算法

MS 聚類算法的計算核心為待聚類點的密度，即每一個類簇中心都將通過迭代移動至需求點最密集的區(qū)域，該算法的思路與地下物流節(jié)點設(shè)施的區(qū)域集中性十分吻合。給定需求點與聚類中心的坐標(biāo)向量分別為xi與x，算法的步驟如下：

1）若為第1 次迭代，則隨機(jī)選取樣本點作為初始點，否則在未被并入類簇的樣本點中隨機(jī)選取一個作為初始點。

2）找到距聚類中心小于搜索半徑的全部需求點，令其為集合H，其元素數(shù)為K。

3）依據(jù)式（18）計算類簇H的中心偏移值M：

4）若M小于聚類收斂閾值，跳轉(zhuǎn)至步驟5），否則按照M更新聚類中心的位置。

5）以更新后的聚類中心為起始點，返回步驟2）。

6）將途徑的全部樣本點并入H，并判斷當(dāng)前聚類中心與其他聚類中心的距離是否小于類簇合并閾值，若是則將兩個類簇合并。

7）若所有樣本點均已被分配至類簇，則停止算法，否則返回至步驟1）。

按照上述方法，所有聚類中心的最終位置都將達(dá)到局部需求點密度最大。因此，經(jīng)過均值偏移聚類算法的計算，便可對解空間進(jìn)行一定程度的優(yōu)化，從而提高啟發(fā)式算法尋優(yōu)速度。

4.2 基于人工免疫與模擬退火的雙層算法

本文構(gòu)造基于人工免疫與模擬退火的雙層算法，在MS 聚類結(jié)果的約束下計算最優(yōu)的布局方案，算法流程如圖3 所示。其中，外層采用模擬退火的思路，用以優(yōu)化均值偏移聚類算法中的超參數(shù)，內(nèi)層采用人工免疫算法，在聚類結(jié)果的約束下搜索使得目標(biāo)函數(shù)最小的節(jié)點分配方案。

圖3 基于模擬退火的雙層算法流程Fig.3 Procedure of two-layer algorithm based on simulated annealing

4.2.1 外層算法設(shè)計

外層算法的優(yōu)化對象為MS 聚類算法中的超參數(shù)，因此采用實數(shù)編碼方式。編碼分為3 個片段，分別代表類簇中心的搜索半徑、聚類收斂閾值以及類簇合并閾值，如圖4 所示。

圖4 外層算法編碼Fig.4 Outer algorithm coding

外層算法的核心為模擬退火機(jī)制，可分為新解的接受、隨機(jī)擾動與退火過程3 個部分：

1）新解的接受

本文采用依概率對新解進(jìn)行選擇接受，其計算方式如式（19）所示：

其中：E為能量值，解的目標(biāo)函數(shù)值越優(yōu)則其能量越低；P為該解被接受的概率。當(dāng)新解的能量更低時，說明新解比原有解更優(yōu)，則以概率1 接受；當(dāng)新解能量高于原有解時，雖然其不如原有解優(yōu)，但為了搜索全局最優(yōu)解，仍會以一定的概率接受新解。

2）隨機(jī)擾動

由于外層算法的編碼方式為實數(shù)型編碼，且各片段的取值范圍差距明顯，因此依照各片段數(shù)值的百分比進(jìn)行擾動，擾動方式如式（20）所示：

其中：E為原解片段的值；E′為新解片段的值。不難看出，當(dāng)r較大時，全局搜索能力較強(qiáng)但局部搜索能力較弱，當(dāng)r較小時，局部搜索能力較強(qiáng)但算法收斂速度會變慢。顯然固定的r值不便于解決問題，故而在本文中r被設(shè)定為服從均值為0、方差為0.15 的正態(tài)分布的隨機(jī)數(shù)。

3）退火過程

參數(shù)T表示退火過程的實時溫度。T過大會導(dǎo)致退火速度太快，可能還未搜索至全局最優(yōu)就結(jié)束迭代，T過小則會增加計算時間。因此，本文采用退火溫度表進(jìn)行調(diào)整，即在退火初期采用較大的T值，隨著退火的進(jìn)行，逐步降低退火溫度。退火速率選擇指數(shù)式下降，下降參數(shù)為λ，本文取0.9，其計算公式如式（21）所示：

4.2.2 內(nèi)層算法設(shè)計

內(nèi)層算法設(shè)計過程如下：

1）初始方案的生成

抗體編碼涉及分撥中心、需求點以及隧道布局的決策，因此采用實數(shù)編碼與0-1 編碼相結(jié)合的方式，抗體共分為3 層，編碼示例如圖5 所示。第1 層表示分撥中心的激活情況，0 代表該分撥中心未激活，反之為1，同時在MS 聚類的結(jié)果下，每一個類簇中至少會有一個分撥中心被激活。第2 層是根據(jù)已激活的分撥中心序號將需求點進(jìn)行隨機(jī)分配，分配的原則為同類簇相匹配。示例中激活了4 個分撥中心，通過Kruskal 算法求得其最小支撐樹并作為初始解，其鄰接矩陣為4 行4 列的對稱矩陣，將鄰接矩陣上三角部分合并為一排作為抗體的第3 層，表示分撥中心的連通情況。

圖5 抗體編碼Fig.5 Immune body coding

2）期望繁殖率的計算

期望繁殖率是對抗體質(zhì)量的最終評價，受到抗體的濃度與抗體親和力的共同影響，抗體親和力越高，則其期望繁殖率越大，個體濃度越大，則其期望繁殖率越小。

對于抗體x，若設(shè)全部種群數(shù)量為N，S為抗體是否相同的邏輯判別值（若兩個抗體編碼有超過R位相同，則表示這兩個抗體近似相同），則其抗體濃度可定義為：

設(shè)抗體x所對應(yīng)的方案的成本為fi（tx），其親和度為A（x），為了擴(kuò)大搜索范圍，算法允許超出隧道的容量，即不考慮約束式（8）。令超出量為s（x），其計算方式如式（23）所示，同時為超出量增加罰因子τ，并在每次迭代結(jié)束時將罰因子乘以一個大于1 的數(shù)字α，最終抗體親和度與期望繁殖率的計算公式分別如式（24）與式（25）所示。

其中：gen 為當(dāng)前迭代次數(shù)；e（x）代表抗體x的期望繁殖 率；ε∈（0，1）代表算 法對濃 度與親 和力的重視程度。

3）免疫算子

免疫算子具體包括交叉算子、突變算子與記憶細(xì)胞庫。

交叉算子針對第1 層與第2 層抗體，采用單點交叉的方式。給定交叉概率pc，并挑選出歷屆最優(yōu)秀的抗體，對每個待判定抗體均生成介于0～1 之間的隨機(jī)數(shù)r，若有r≤pc，則執(zhí)行交叉操作。具體步驟如圖6 所示，在交叉結(jié)束后，對不符合要求的抗體片段進(jìn)行修復(fù)。

圖6 免疫交叉操作示意圖Fig.6 Schematic diagram of immune crossover operation

突變算子針對第3 層抗體，采用單點變異的方式。給定突變概率pm，對每個抗體依次生成介于0～1之間的隨機(jī)數(shù)r，若有r≤pm，則該個體執(zhí)行變異操作。具體步驟如圖7 所示。具體操作為隨機(jī)選取1 個位點將其變更，若突變后的抗體可行或超出量s（x）減小則保留，否則撤銷該次突變。

圖7 免疫突變操作示意圖Fig.7 Schematic diagram of immune mutation operation

記憶細(xì)胞庫是為了保留親和力最優(yōu)的抗體，同時挑選合適的抗體組成新的種群，具體操作如下：

1）若記憶庫為空，則直接選取當(dāng)前抗體群中期望繁殖率排名前m的個體存入記憶庫。

2）若記憶庫非空，則在免疫過程開始前，將記憶庫與抗體群中的抗體按期望繁殖率進(jìn)行降序排列，取排名前m的個體存入記憶庫中，同時取排名前N的個體作為父代抗體群，N為抗體群數(shù)量。

3）在每一次免疫操作開始前更新記憶庫。

5 數(shù)值實驗與案例分析

5.1 數(shù)值實驗

本文結(jié)合現(xiàn)有的研究［25］，同時根據(jù)本問題的特點，給定地下物流系統(tǒng)與啟發(fā)式算法中一些具體參數(shù)，如表2 所示。算法參數(shù)數(shù)據(jù)如表3 所示。

表2 地下物流系統(tǒng)參數(shù)數(shù)據(jù)Table 2 Parameter data of underground logistics system

表3 算法參數(shù)數(shù)據(jù)Table 3 Parameter data of algorithm

5.2 實驗結(jié)果

5.2.1 隨機(jī)算例計算結(jié)果

為研究本文所提算法在不同規(guī)模下的尋優(yōu)能力，本節(jié)設(shè)計并生成了不同規(guī)模的隨機(jī)算例進(jìn)行對比，需求點數(shù)分別為50、100、200 和500 個，相應(yīng)備選點數(shù)量為30、50、90 和150 個，物流園區(qū)數(shù)量分別為4、6、8、10 個，各需求點和物流園區(qū)貨運量根據(jù)實際規(guī)模設(shè)定范圍隨機(jī)生成，其他系統(tǒng)參數(shù)與表2 中相同。本文在維持外層模擬退火部分不變的情況下，額外設(shè)計了包含MS 聚類過程的GA 算法與不包含MS 聚類過程的GA 算法，并且在替換掉外層算法的情況下設(shè)計了雙層GA 算法進(jìn)行對比。每種規(guī)模生成5 個算例，分別采用上述3 種算法進(jìn)行計算，并記錄10 次計算的平均目標(biāo)函數(shù)值。

表4 展示了不同算例規(guī)模下的計算結(jié)果。其中，Z1、Z2、Z3 與Z4 分別表示內(nèi)層算法為基于MS 的IA 算法、內(nèi)層算法為基于MS 的GA 算法、內(nèi)層算法為普通的GA 算法以及雙層GA 算法的目標(biāo)函數(shù)值，T1、T2、T3、T4 分別代 表不同 算法的 計算時 長，GAP1、GAP2、GAP3 表示不同的內(nèi)層算法之間的差距，計算公式如下：

表4 不同規(guī)模算例結(jié)果對比Table 4 Comparison of results of different scale examples

從表4 可以看出，在算例規(guī)模較小時，不同內(nèi)層算法的尋優(yōu)能力差距不大，平均GAP 約為2%，雙層GA 算法的差距約為3%。隨著規(guī)模的不斷擴(kuò)大，普通GA 與基于MS 的IA 算法差距逐漸增加，在最大規(guī)模時差距為7.35%，此時雙層GA 算法的差距已經(jīng)達(dá)到了8%。同時，隨著規(guī)模的擴(kuò)大，算法的計算時長均在增加，但包含MS 過程的算法增加較慢，而普通GA 的計算時長顯著增加，這表明在算法中加入MS聚類過程能夠加快算法的收斂速度。因此，本文所提出的雙層算法在設(shè)計多層地下物流網(wǎng)絡(luò)時能夠得到更優(yōu)結(jié)果，特別當(dāng)需求點規(guī)模不斷擴(kuò)大時雙層算法尋優(yōu)能力更強(qiáng)，效率也更高。

5.2.2 算法穩(wěn)定性分析

為分析基于MS 聚類的雙層算法的求解性能，本文取上述算例進(jìn)行求解測試。對于每一個算例，均使用雙層算法分別計算20 次，分別記錄其平均值、最優(yōu)值與最差值，并計算其之間的百分比差距，具體信息如表5 所示。

表5 算法穩(wěn)定性計算結(jié)果Table 5 Calculation results of algorithm stability

從表5 可以看出，本文構(gòu)造的基于MS 聚類的雙層算法具有較好的穩(wěn)定性。在不同規(guī)模的算例中，最優(yōu)值與平均值的平均差值比例為-1.32%，最差值與平均值的平均差值比例為1.34%。由此可見，本文構(gòu)造的算法具有較好的穩(wěn)定性，能夠針對不同規(guī)模的地下物流網(wǎng)絡(luò)系統(tǒng)進(jìn)行優(yōu)化設(shè)計。

5.2.3 靈敏性分析

為研究基礎(chǔ)設(shè)施參數(shù)的變動對地下物流系統(tǒng)建設(shè)成本的影響，本文選取了分撥中心處理能力α這一主要參數(shù)進(jìn)行靈敏性分析，采用無人化作業(yè)或進(jìn)行設(shè)備革新均會影響分撥中心的處理能力，因而該參數(shù)具有一定的不穩(wěn)定性。

從4 種不同規(guī)模的算例中各隨機(jī)選擇1 例進(jìn)行實驗，實驗結(jié)果取4 組算例的平均值。參數(shù)α的取值范圍從集合｛0.5α，0.75α，α，1.25α，1.5α｝中選取，具體的計算結(jié)果如圖8 與圖9 所示。

圖8 不同α 值與費用變化趨勢Fig.8 The variation trend of different α values and costs

圖9 不同α 值與總成本變化趨勢Fig.9 The variation trend of different α values and total cost

可以看出，隨著分撥中心處理能力的增加，運輸費用與基礎(chǔ)設(shè)施的折舊費用均有下降的趨勢。當(dāng)分撥中心的轉(zhuǎn)運能力提高后，服務(wù)全部需求點所需的分撥中心數(shù)量降低，因此會減少造價較高的干線總長度，同時增加造價較低的支線建設(shè)長度。隨著干線網(wǎng)絡(luò)的簡化，貨物的運輸距離也會降低，進(jìn)而降低了總運輸費用。靈敏度分析結(jié)果表明，分撥中心處理能力的提升可以降低地下物流網(wǎng)絡(luò)系統(tǒng)的運營成本，其中對于運輸費用的影響較為明顯。

5.3 案例分析

上海市中心共有7 個行政區(qū)，總面積289.44 km2，約占全市面積的5%，常駐人口為687.14 萬人，約占全市人口的27.6%，其龐大的人口密度與日用品需求是特大型城市的典型代表。本文以上海市中心區(qū)域為例，設(shè)計了基于MS 聚類的雙層啟發(fā)式算法用以求解地下物流網(wǎng)絡(luò)的布局，同時根據(jù)表2的信息隨機(jī)生成各需求點的貨運量作為實驗數(shù)據(jù)。

MS 聚類算法中的超參數(shù)“搜索半徑”與最終的網(wǎng)絡(luò)成本關(guān)系如圖10 所示。通過分析可知，當(dāng)搜索半徑較小時，類簇數(shù)量增多進(jìn)而增加了激活分撥中心的成本，而當(dāng)搜索半徑較大時，類簇內(nèi)需求點增多，聚類算法的功能被削減，解空間的分解效果較差。在本問題中，當(dāng)MS 聚類的搜索半徑約為6.5 km時具有較好的解空間分解效果。

圖10 搜索半徑與最終成本變化圖Fig.10 Change diagram of search radius and final cost

經(jīng)本文構(gòu)造的雙層優(yōu)化算法計算可得出近似最優(yōu)的地下物流系統(tǒng)布局方案，具體布局如圖11 所示。在同一次退火過程中，本文構(gòu)造的算法與普通的GA 算法對比如圖12 所示。

圖11 上海市地下物流系統(tǒng)布局示意圖Fig.11 Schematic diagram of the underground logistics system layout in Shanghai

圖12 兩種算法優(yōu)化過程對比圖Fig.12 Comparison diagram of optimization process of two algorithms

由上述對比可以看出，在結(jié)合MS 聚類的操作后，無論是初始解的質(zhì)量還是算法的尋優(yōu)速度均得到一定程度的優(yōu)化，證明了本文所構(gòu)造的基于MS 聚類的雙層啟發(fā)式算法在求解地下物流網(wǎng)絡(luò)布局中具有一定的參考意義。

6 結(jié)束語

本文通過分析特大型城市的交通與物流現(xiàn)狀，提出建造多層級地下物流系統(tǒng)以緩解擁堵和環(huán)境污染等城市發(fā)展矛盾。以地下通道與分撥中心為規(guī)劃對象，構(gòu)建基于兩種地下運輸模式的多層級地下物流網(wǎng)絡(luò)模型，并設(shè)計基于MS 聚類的雙層啟發(fā)式算法對該問題進(jìn)行求解。實驗結(jié)果表明，本文多層級地下物流系統(tǒng)能夠有效分擔(dān)地面貨運壓力，大幅減少運輸過程中的貨物損耗，同時提高運輸效率，在很大程度上能夠緩解城市的交通擁堵與空氣污染問題，為當(dāng)前囿于擁堵難題的特大型城市交通結(jié)構(gòu)升級提供了新思路。目前特大型城市均已具有完善的地鐵運輸系統(tǒng)，考慮到ULS 前期投入巨大，若能依托于城市現(xiàn)有的地鐵系統(tǒng)，將極大地降低ULS 的建設(shè)與運營成本。因此，如何充分利用現(xiàn)有的城市運輸資源，將是下一步研究的方向。