劉博宇，梁承姬，王 鈺

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

0 概述

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

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

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

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

1 相關(guān)研究

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

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

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

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

2 問(wèn)題描述

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

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

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

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

3 模型建立

3.1 問(wèn)題假設(shè)

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

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

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

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

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

本文所用符號(hào)說(shuō)明如表1 所示。

表1 符號(hào)說(shuō)明Table 1 Symbol description

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

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

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

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

同時(shí)考慮如下約束條件：

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

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

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

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

分撥中心間的通道運(yùn)輸能力受載具速度與隧道長(zhǎng)度的限制，隧道越長(zhǎng)則其運(yùn)輸批次越少，兩個(gè)分撥中心間的日流量不能超過(guò)隧道的最大運(yùn)輸能力，即：

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

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

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

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

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

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

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

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

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

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

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

4 算法設(shè)計(jì)

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

4.1 MS 聚類算法

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

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

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

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

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

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

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

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

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

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

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

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

4.2.1 外層算法設(shè)計(jì)

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

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

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

1）新解的接受

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

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

2）隨機(jī)擾動(dòng)

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

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

3）退火過(guò)程

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

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

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

1）初始方案的生成

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

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

2）期望繁殖率的計(jì)算

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

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

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

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

3）免疫算子

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

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

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

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

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

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

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

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

3）在每一次免疫操作開(kāi)始前更新記憶庫(kù)。

5 數(shù)值實(shí)驗(yàn)與案例分析

5.1 數(shù)值實(shí)驗(yàn)

本文結(jié)合現(xiàn)有的研究［25］，同時(shí)根據(jù)本問(wèn)題的特點(diǎn)，給定地下物流系統(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 實(shí)驗(yàn)結(jié)果

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

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

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

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

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

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

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

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

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

5.2.3 靈敏性分析

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

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

圖8 不同α 值與費(fèi)用變化趨勢(shì)Fig.8 The variation trend of different α values and costs

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

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

5.3 案例分析

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

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

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

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

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

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

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

6 結(jié)束語(yǔ)

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