考慮庫(kù)存與中斷的雙目標(biāo)多式聯(lián)運(yùn)優(yōu)化研究

王能民， 王雪寧， 史瑋璇

（1.西安交通大學(xué) 管理學(xué)院，陜西 西安 710049；2.陜西省制造服務(wù)業(yè)過(guò)程挖掘工程研究中心，陜西 西安 710049）

1 引言

隨著互聯(lián)網(wǎng)的普及、國(guó)家政策的支持以及疫情的傳播，方便、無(wú)接觸的跨境電商［1］得到高速發(fā)展。據(jù)海關(guān)統(tǒng)計(jì)數(shù)據(jù)，2021年我國(guó)跨境電商進(jìn)出口1.98萬(wàn)億元，增長(zhǎng)15%［2］。顧客滿意度是決定電商持續(xù)發(fā)展的重要因素［3］，海外倉(cāng)通過(guò)物流前置極大地縮短顧客的收貨時(shí)間，進(jìn)而提升其購(gòu)物體驗(yàn)，同時(shí)海外倉(cāng)還可以減少因?yàn)榈缆分袛嗟蕊L(fēng)險(xiǎn)因素對(duì)供應(yīng)鏈的沖擊。目前，中國(guó)海外倉(cāng)的數(shù)量超過(guò)2000個(gè)，面積超過(guò)1600萬(wàn)平方米［4］。對(duì)跨境電商企業(yè)而言，同時(shí)考慮海外倉(cāng)管理以及多式聯(lián)運(yùn)路徑規(guī)劃是一個(gè)復(fù)雜系統(tǒng)工程問(wèn)題，如何在降低成本與提升顧客滿意度兩個(gè)目標(biāo)下對(duì)其進(jìn)行高效的求解具有重要的實(shí)際應(yīng)用價(jià)值。

與本研究相關(guān)的研究成果主要包括兩部分：考慮中斷風(fēng)險(xiǎn)的多式聯(lián)運(yùn)的研究，以及考慮庫(kù)存的多式聯(lián)運(yùn)的研究。關(guān)于考慮中斷的多式聯(lián)運(yùn)類的成果以最小化成本的單目標(biāo)研究為主，部分研究采用加權(quán)法將風(fēng)險(xiǎn)、時(shí)間或碳排放等多目標(biāo)轉(zhuǎn)化為單目標(biāo)求解。Wagenaar等［5］考慮中斷風(fēng)險(xiǎn)以及顧客的滿意度，以最小化成本為目標(biāo)，設(shè)計(jì)啟發(fā)式算法進(jìn)行求解。Ke［6］考慮到火車某些節(jié)點(diǎn)出現(xiàn)中斷的情形，以風(fēng)險(xiǎn)和成本為雙目標(biāo)，采用魯棒優(yōu)化模型將成本目標(biāo)轉(zhuǎn)化為約束條件，將風(fēng)險(xiǎn)作為單一目標(biāo)進(jìn)行優(yōu)化?？紤]多式聯(lián)運(yùn)在長(zhǎng)距離運(yùn)輸大批貨物的優(yōu)勢(shì)，Demir等［7］以其為研究對(duì)象，以運(yùn)輸成本、違反時(shí)間窗成本與CO2排放為優(yōu)化目標(biāo)，通過(guò)加權(quán)法轉(zhuǎn)化為單一目標(biāo)進(jìn)行求解，采用隨機(jī)優(yōu)化的方式將運(yùn)輸時(shí)間與需求的不確定性考慮到模型中。

關(guān)于考慮庫(kù)存的多式聯(lián)運(yùn)優(yōu)化的研究，主要以最小化成本的單目標(biāo)為主：賀竹磬等［8］，魏航等［9］雖然在最小化物流費(fèi)用的目標(biāo)函數(shù)中包含了庫(kù)存成本，但只是貨物在規(guī)定的時(shí)間點(diǎn)前送達(dá)而產(chǎn)生的積壓庫(kù)存，是對(duì)違反時(shí)間窗的一種懲罰，而不是對(duì)庫(kù)存的決策優(yōu)化。Marufuzzaman和Eksioglu［10］在以生物質(zhì)能轉(zhuǎn)化為燃料來(lái)供應(yīng)城市為背景的研究中，以最小化成本為單目標(biāo)，由于生物質(zhì)能產(chǎn)生的季節(jié)性，會(huì)在轉(zhuǎn)化工廠進(jìn)行存儲(chǔ)，并將存儲(chǔ)量作為決策變量進(jìn)行優(yōu)化。

綜上本文解決的是考慮庫(kù)存管理和道路中斷的雙目標(biāo)多式聯(lián)運(yùn)優(yōu)化的系統(tǒng)工程問(wèn)題，主要?jiǎng)?chuàng)新點(diǎn)包括：（1）問(wèn)題方面，首次考慮海外倉(cāng)對(duì)跨境電商決策的影響，將多式聯(lián)運(yùn)、訂單分配以及道路中斷風(fēng)險(xiǎn)等因素聯(lián)合優(yōu)化。（2）模型方面，以最小化總成本與最大化顧客滿意度為雙目標(biāo)，建立了兩階段的優(yōu)化模型，第一階段采用魯棒優(yōu)化法考慮道路中斷對(duì)路徑選擇的影響，將決策結(jié)果作為第二階段的參數(shù)，對(duì)訂單的滿足方式與時(shí)間進(jìn)行決策，并據(jù)此更新庫(kù)存水平。（3）算法方面，針對(duì)中小規(guī)模算例設(shè)計(jì)精確算法，基于問(wèn)題特點(diǎn)在ε-約束法的基礎(chǔ)上進(jìn)行改進(jìn)：通過(guò)性質(zhì)求ε的下界，規(guī)避不可行路徑以及利用改進(jìn)的標(biāo)號(hào)法求解子問(wèn)題，得到帕累托前沿；針對(duì)大規(guī)模算例在ε-約束法的基礎(chǔ)上設(shè)計(jì)了貪婪隨機(jī)自適應(yīng)搜索與模擬退火的混合啟發(fā)式算法。（4）管理啟示方面，發(fā)現(xiàn)海外倉(cāng)的存在可以極大地降低成本與顧客的等待時(shí)間，而安全庫(kù)存量與補(bǔ)貨量則需要結(jié)合海外倉(cāng)實(shí)際的需求量進(jìn)行合理的制定，在庫(kù)存成本與運(yùn)輸成本之間進(jìn)行平衡。

2 問(wèn)題描述與建模

2.1 問(wèn)題描述

G（V，E，M）代表多式聯(lián)運(yùn)的無(wú)向交通網(wǎng)絡(luò)［11］，其中V＝｛0，1，．．．，n｝為節(jié)點(diǎn)集合，E＝｛（i，j）｜i，j∈V｝為邊集。M為運(yùn)輸方式的集合，每條弧上都有至少一種運(yùn)輸方式，同一條弧上不同運(yùn)輸方式的時(shí)間與成本不同，且遵循時(shí)間越短成本越高的基本規(guī)律［12］，當(dāng)不同的運(yùn)輸方式之間進(jìn)行轉(zhuǎn)換的時(shí)候會(huì)產(chǎn)生轉(zhuǎn)運(yùn)成本與時(shí)間，為了突出重點(diǎn)，本文不考慮運(yùn)量不匹配的問(wèn)題，假設(shè)轉(zhuǎn)運(yùn)成本與時(shí)間為常量［10］。I?V為海外倉(cāng)的節(jié)點(diǎn)集，跨境電商需對(duì)海外倉(cāng)的庫(kù)存進(jìn)行管理。跨境電商處理訂單的周期為TD，期初得到該期顧客訂單集合R，每個(gè)訂單信息包括需求量Qr、起點(diǎn)Or、終點(diǎn)Dr、產(chǎn)生時(shí)間Er以及最晚送達(dá)時(shí)間Lr。企業(yè)根據(jù)當(dāng)期訂單需求與庫(kù)存量決策訂單的滿足方式，當(dāng)顧客需求大于庫(kù)存量時(shí)，一部分訂單采用庫(kù)存方式滿足，根據(jù)訂單的最晚送達(dá)時(shí)間要求，決策由當(dāng)期還是下期庫(kù)存進(jìn)行滿足；一部分訂單采用直郵方式滿足，需對(duì)直郵訂單進(jìn)行路徑規(guī)劃。該階段的決策變量直接影響庫(kù)存，當(dāng)庫(kù)存低于安全庫(kù)存點(diǎn)時(shí)補(bǔ)貨。顧客滿意度與需等待的時(shí)間直接相關(guān)。S為道路中斷的情景集合，不同情景會(huì)改變交通網(wǎng)絡(luò)，本文采用魯棒優(yōu)化的最壞情況分析法［13］，以對(duì)結(jié)果影響最大的中斷情景作為基準(zhǔn)。以總成本最小和顧客滿意度最大為雙目標(biāo)，求解跨境電商如何選擇運(yùn)輸?shù)姆绞脚c路徑以及如何安排訂單的滿足方式。

本文假設(shè)包括：（1）不考慮訂單的分割與合并；（2）訂單只在每期期初產(chǎn)生；（3）不考慮最后一公里問(wèn)題；（4）每周期只了解當(dāng)期需求，無(wú)法預(yù)知未來(lái)；（5）不考慮倉(cāng)庫(kù)之間的補(bǔ)貨；（6）不考慮運(yùn)力不匹配的情況。

2.2 數(shù)學(xué)模型

2.2.1 符號(hào)說(shuō)明

集合。V為節(jié)點(diǎn)集合，E為邊集，M為運(yùn)輸方式的集合，T為時(shí)間集合。

參數(shù)。wr為訂單r得到滿足需要等待的時(shí)間。為 每單位FTU的產(chǎn)品從i點(diǎn)到j(luò)點(diǎn)以m方式運(yùn)輸?shù)某杀?。為每單位FTU產(chǎn)品在i點(diǎn)從m運(yùn)輸方式轉(zhuǎn)化為ˉm的成本。為每單位FTU的產(chǎn)品從i點(diǎn)到j(luò)點(diǎn)以m方式運(yùn)輸?shù)臅r(shí)間。為每單位FTU產(chǎn)品在i點(diǎn)從m運(yùn)輸方式轉(zhuǎn)化為ˉm的時(shí)間。為情景s下，從i到j(luò)采用m方式運(yùn)輸?shù)穆范问欠裰袛啵糁袛嗥渲禐?，否則為1。Ii為倉(cāng)庫(kù)i的初始庫(kù)存。INit為倉(cāng)庫(kù)i在t時(shí)的庫(kù)存。Qit為倉(cāng)庫(kù)i在t時(shí)運(yùn)達(dá)的貨物數(shù)量。Qi為倉(cāng)庫(kù)i的補(bǔ)貨量。Hi為倉(cāng)庫(kù)i儲(chǔ)存一個(gè)FEU集裝箱所載產(chǎn)品的單位時(shí)間庫(kù)存成本。Ai為倉(cāng)庫(kù)i的安全庫(kù)存量，低于此值的時(shí)候，發(fā)出補(bǔ)貨請(qǐng)求。Ci為每個(gè)FEU集裝箱產(chǎn)品從起點(diǎn)到倉(cāng)庫(kù)i的補(bǔ)貨運(yùn)輸成本。LTi為每個(gè)FEU集裝箱產(chǎn)品從起點(diǎn)到倉(cāng)庫(kù)i的補(bǔ)貨運(yùn)輸時(shí)間。Bit為倉(cāng)庫(kù)i在t時(shí)是否進(jìn)行補(bǔ)貨。CZr為訂單r采用直郵方式運(yùn)輸時(shí)決策者偏好方案的運(yùn)輸與轉(zhuǎn)運(yùn)成本。TZr為訂單r采用直郵方式運(yùn)輸時(shí)決策者偏好方案的等待時(shí)間。

yrim ˉm，0-1變量，1表示訂單r在i點(diǎn)從運(yùn)輸方式m轉(zhuǎn)化為ˉm，否則為0。Zr，0-1變量，1表示用訂單r由海外倉(cāng)庫(kù)存滿足，0表示用直郵方式滿足。Tr，表示訂單r由庫(kù)存滿足的時(shí)刻，決策由當(dāng)期或是下期庫(kù)存滿足。

2.2.2 第一階段

針對(duì)每個(gè)訂單在保證不違背其時(shí)間窗以及考慮各種道路中斷的情景的前提下，對(duì)其運(yùn)輸路徑以及運(yùn)輸方式進(jìn)行決策，模型如下

目標(biāo)（1）最小化在對(duì)結(jié)果影響最大的中斷情景下每個(gè)訂單由直郵產(chǎn)生的運(yùn)輸與轉(zhuǎn)運(yùn)費(fèi)用，目標(biāo)（2）最小化在對(duì)結(jié)果影響最大的中斷情景下每個(gè)訂單由直郵運(yùn)輸所需的平均等待時(shí)間，（3）每個(gè)中斷情景下的直郵的運(yùn)輸與轉(zhuǎn)運(yùn)費(fèi)用，（4）每個(gè)中斷情景下直郵訂單等待的時(shí)間，（5）節(jié)點(diǎn)i與j之間只能采用一種方式進(jìn)行運(yùn)輸，（6）節(jié)點(diǎn)i最多只能轉(zhuǎn)運(yùn)一次，（7）表示運(yùn)輸服務(wù)的連續(xù)性，（8）保證節(jié)點(diǎn)間流量守恒，（9）保證處于中斷狀態(tài)的路徑不可以通行，（10）和（11）表示不能違背訂單的時(shí)間窗約束，（12）和（13）為決策變量的取值范圍。

2.2.3 第二階段

據(jù)第一階段計(jì)算得出的每個(gè)訂單采用直郵的帕累托前沿，決策者從中選擇一個(gè)偏好方案作為第二階段的參數(shù)，之后需要針對(duì)每個(gè)訂單是否采用庫(kù)存進(jìn)行滿足以及滿足的時(shí)間進(jìn)行決策，并根據(jù)決策結(jié)果對(duì)庫(kù)存水平進(jìn)行更新，模型如下

目標(biāo)（14）最小化總成本，包括海外倉(cāng)產(chǎn)生的庫(kù)存成本，補(bǔ)貨的運(yùn)輸成本以及直郵成本，目標(biāo)（15）最小化總時(shí)間，包括海外倉(cāng)滿足的訂單所需的等待時(shí)間，以及直郵的運(yùn)輸時(shí)間，（16）初始化每個(gè)海外倉(cāng)的庫(kù)存，（17）每個(gè)周期根據(jù)是否有補(bǔ)貨到達(dá)以及訂單需求量來(lái)更新庫(kù)存水平，（18）保證海外倉(cāng)的庫(kù)存水平不為負(fù)值，（19）根據(jù)庫(kù)存水平判斷是否下達(dá)補(bǔ)貨請(qǐng)求，（20）在補(bǔ)貨請(qǐng)求下達(dá)一個(gè)提前期的時(shí)間以后貨物到達(dá)海外倉(cāng)，（21）海外倉(cāng)滿足的訂單不能超過(guò)每個(gè)訂單規(guī)定的時(shí)間窗，（22）和（23）規(guī)定了決策變量的取值范圍。

3 模型分析與求解

本文涉及不同的交通方式間轉(zhuǎn)換的成本與時(shí)間，將現(xiàn)實(shí)的點(diǎn)按其擁有的交通方式轉(zhuǎn)化為幾個(gè)虛擬點(diǎn)［14］，轉(zhuǎn)運(yùn)時(shí)間和成本轉(zhuǎn)化為虛擬點(diǎn)間路徑的時(shí)間與成本，這樣第一階段的子問(wèn)題可以轉(zhuǎn)化為有時(shí)間約束的最短路問(wèn)題，屬于資源約束的最短路問(wèn)題，是NP-hard問(wèn)題［15］。因此本文求解的問(wèn)題也是NP-hard問(wèn)題。

3.1 基于ε-約束法的精確算法

第一階段按不同的中斷情景拆分，分別計(jì)算不同情景對(duì)目標(biāo)函數(shù)的影響，本文的魯棒優(yōu)化采用最壞情況分析法，最后以對(duì)結(jié)果影響最大的中斷情景為基準(zhǔn)。那么原問(wèn)題可以轉(zhuǎn)化為多個(gè)雙目標(biāo)整數(shù)規(guī)劃問(wèn)題P。針對(duì)多目標(biāo)問(wèn)題，加權(quán)法因操作簡(jiǎn)便得到了最廣泛的應(yīng)用，但此方法無(wú)法得到完整的帕累托前沿。因此ε-約束法［16］被提出，其思想為將除一個(gè)目標(biāo)以外的其他所有目標(biāo)轉(zhuǎn)化為約束條件，將多目標(biāo)問(wèn)題轉(zhuǎn)化為多個(gè)單目標(biāo)問(wèn)題。本文基于ε-約束法將多目標(biāo)問(wèn)題P轉(zhuǎn)化為多個(gè)單目標(biāo)問(wèn)題P0。其中ε的取值范圍表示為）和。此后根據(jù)本文問(wèn)題特點(diǎn)，在經(jīng)典ε-約束基礎(chǔ)上做出三處改進(jìn)。

問(wèn)題P

s.t.約束（3）～（13）

問(wèn)題P0

3.1.1 確定ε的取值范圍

對(duì)于ε-約束法，首先需要確定ε的取值范圍，令εU與εL分別代表ε的上下界，其中，其中可通過(guò)求解問(wèn)題P2得到，同理可以通過(guò)求解問(wèn)題P1得到。

問(wèn)題P1

s.t.約束（3）～（13）

問(wèn)題P2

s.t.約束（3）～（13）

經(jīng)典的ε-約束法需求解混合整數(shù)規(guī)劃模型問(wèn)題P1和問(wèn)題P2。本文通過(guò)分析問(wèn)題結(jié)構(gòu)的特殊性得到如下性質(zhì)，可以用一個(gè)時(shí)間復(fù)雜度為O（nlogn）的迪杰斯特拉算法［17］計(jì)算得到fI2。

性質(zhì)問(wèn)題P2是以時(shí)間為權(quán)重的最短路問(wèn)題。

證明每條弧有（時(shí)間，成本）兩個(gè)數(shù)據(jù)，只取弧上的時(shí)間作為權(quán)重，求解起點(diǎn)到終點(diǎn)的最短路徑，即為問(wèn)題P2的解。

3.1.2 確定不可行路徑集合

因?yàn)棣?約束法每次迭代不同的問(wèn)題P0時(shí)，其約束中的ε一直在減小，每次迭代生成的解x*的路徑總是會(huì)因?yàn)棣偶s束的收緊而減少，而被淘汰的路徑在后續(xù)的迭代過(guò)程中一定是不滿足更加嚴(yán)格的ε約束的，因此可以在計(jì)算之前就將這些路徑劃分在不可行路徑集合中，從而在后續(xù)的迭代過(guò)程中縮小搜索范圍，減少算法運(yùn)行時(shí)間。向不可行路徑集合中添加不可行路徑的算法如下。

算法1A第1步 對(duì)于當(dāng)前解x*的路徑集合P*，將所有路徑按照運(yùn)輸時(shí)間降序排列，從集合P*中按順序依次取出路徑，記為pi。第2步 如果T（pi）＞ε，將pi放入不可行路徑集合Pinf中，返回上一步，否則終止算法。

3.1.3 改進(jìn)的標(biāo)號(hào)法

在解決帶資源約束的最短路問(wèn)題的精確算法中，基于動(dòng)態(tài)規(guī)劃的標(biāo)號(hào)法占主導(dǎo)地位［18］。但傳統(tǒng)的標(biāo)號(hào)法沒(méi)有對(duì)不可行路徑的判斷，需在原算法的基礎(chǔ)上改進(jìn)，具體步驟如算法1B所示。

1B輸入：路徑網(wǎng)絡(luò)數(shù)據(jù)，訂單的時(shí)間約束、初始點(diǎn)Or和終點(diǎn)Dr，以及不可行路徑集合P算法inf初始化：集合U←（Or），P←?當(dāng)U≠?時(shí)一直進(jìn)行如下循環(huán)：（路徑擴(kuò)展）選擇一條路徑Q∈U并將其從集合U中移除：對(duì)于以點(diǎn)vQ為起始點(diǎn)的所有的?。╲Q，w）∈A：如果路徑（Q，w）不屬于Pinf也不違反訂單的時(shí)間約束，并且w不在路徑Q中：將路徑（Q，w）添加到集合U中P←P∪｛Q｝（支配檢驗(yàn)）對(duì)于集合U∪P中的路徑應(yīng)用支配規(guī)則從集合P中識(shí)別出總成本最小的路徑并輸出輸出：最短路徑

綜上，在傳統(tǒng)ε-約束法的基礎(chǔ)上做出三處改進(jìn)后的整體求解思路如算法1所示。

算法1第1步 確定對(duì)結(jié)果影響最大的中斷情景，并以此為基準(zhǔn)進(jìn)行計(jì)算第2步 利用迪杰斯特拉算法求解問(wèn)題P2，利用算法1B求解問(wèn)題P1，得到ε的取值范圍第3步 用算法1A更新不可行路徑集合Pinf第4步 用算法1B求解問(wèn)題P0，得到時(shí)間與成本的最優(yōu)解向量x*，將x*加入到解列表Y′第5步 令ε＝f2（x*）-1，如果ε≥f I2，回到第3步，否則，轉(zhuǎn)到下一步第6步 將Y′中的被支配解刪除，得到帕累托前沿Y，決策者針對(duì)每個(gè)訂單選擇一個(gè)偏好解第7步 將偏好解代入第一階段模型，計(jì)算得到最優(yōu)解

3．2 基于ε-約束法的啟發(fā)式算法

由于帶資源約束的最短路問(wèn)題是NP-hard問(wèn)題，對(duì)于大規(guī)模算例，上述的精確算法無(wú)法求解，因此基于上文的ε-約束算法設(shè)計(jì)了一個(gè)貪婪隨機(jī)自適應(yīng)搜索（GRASP）與模擬退火（SA）的混合啟發(fā)式算法，求解算法2的問(wèn)題P0與問(wèn)題P1。GRASP與SA 被廣泛應(yīng)用于調(diào)度以及車輛路徑等問(wèn)題［19，20］。GRASP有構(gòu)造初始解和局部搜索兩部分，其中局部搜索部分融合SA進(jìn)行優(yōu)化，根據(jù)本文問(wèn)題特點(diǎn)分別對(duì)兩部分進(jìn)行設(shè)計(jì)。

3.2.1 生成初始解

在算法2A中，第6步的參數(shù)α∈［0，1］用來(lái)控制算法貪婪與隨機(jī)的比重，當(dāng)α＝0時(shí)，只選取最優(yōu)的候選元素，是純貪心算法；當(dāng)α＝1時(shí)，所有候選元素都可以隨機(jī)選擇，是純隨機(jī)算法。

算法2A輸入：起點(diǎn)o，終點(diǎn)d，參數(shù)α，時(shí)間矩陣，距離矩陣，時(shí)間約束第1步 初始解s為由起點(diǎn)與終點(diǎn)組成的路徑第2步 初始化候選元素的集合E（指初始解中沒(méi)有的元素）第3步 對(duì)候選集合中的元素e∈E進(jìn)行評(píng)估。計(jì)算將元素e插入路徑s中所導(dǎo)致的目標(biāo)函數(shù)的最優(yōu)改變量c（e），c（e）≥0代表加入e使得成本增加，反之代表使得成本減少第4步 當(dāng)存在e使得c（e）＜0時(shí)，執(zhí)行5至8步，否則返回s并結(jié)束算法第5步 令c min＝min｛c（e）｜c(diǎn)（e）＜0，e∈E｝，c max＝max｛c（e）｜c(diǎn)（e）＜0，e∈E｝第6步 選取滿足c（e）≤c min＋α（c max-c min）的元素e加入限制候選列表RCL中第7步 從RCL中隨機(jī)選取一個(gè)元素e，判斷將其加入s是否會(huì)違反時(shí)間約束，如果不違反則s←s∪｛e｝，并更新候選集合E，否則重新選擇e第8步 對(duì)候選集合中的每個(gè)元素e重新計(jì)算c（e ）

3.2.2 局部搜索

本文采用交換操作中的2＿opt算子，即反轉(zhuǎn)指定區(qū)間內(nèi)的元素順序，作為鄰域動(dòng)作。借鑒模擬退火算法的思想設(shè)計(jì)局部搜索算法，si為當(dāng)前路徑，si＋1為使用2＿opt算子后的路徑，T為系統(tǒng)溫度，Tmin為溫度下界，f1（s）為路徑s的總成本，f2（s）為路徑s的總時(shí)間，TC為時(shí)間約束，r控制降溫的速度，具體如算法2B所示。

2B輸入：初始路徑s0，T，T min，TC，r，時(shí)間矩陣，算法距離矩陣初始化：當(dāng)前路徑si←s0，最優(yōu)解s*←s0第1步 判斷T＞T min是否滿足，若滿足轉(zhuǎn)至第2步，否則結(jié)束算法，返回路徑s*第2步 對(duì)si應(yīng)用2＿opt算子得到si＋1，令Δ＝f（si）-f（si＋1）第3步 若f2（s）≤TC，轉(zhuǎn)至第4步，否則返回第2步第4步 當(dāng)Δ≥0時(shí)，令si←si＋1，轉(zhuǎn)至第6步，否則轉(zhuǎn)至第5步第5步 在［0，1］間隨機(jī)生成數(shù)β，若e Δ T ＞β，令si←si＋1，轉(zhuǎn)至第6步第6步 判斷f（si）＜f（s*），若滿足則更新最優(yōu)解s*←si，轉(zhuǎn)至第7步第7步 降溫，令T←r×T，轉(zhuǎn)至第1步

綜上，混合啟發(fā)式算法的整體思路如下。

2C輸入：距離矩陣，時(shí)間矩陣，最大迭代次數(shù)M，起點(diǎn)o，終點(diǎn)d，算法時(shí)間約束初始化：解s←?，最優(yōu)解s*←?，迭代次數(shù)k＝0第1步 判斷當(dāng)前迭代次數(shù)k≤M，若滿足轉(zhuǎn)至第2步，否則結(jié)束算法，返回最優(yōu)解s*第2步 更新迭代次數(shù)k←k＋1，用算法2A生成初始可行解，并賦值給s第3步 用算法2B對(duì)s進(jìn)行鄰域搜索，得到一個(gè)最優(yōu)解s第4步 判斷f1（s）＜f1（s*），若滿足更新最優(yōu)解s*←s，轉(zhuǎn)至第1步

將算法2C與ε-約束法結(jié)合，得到的整體算法2框架如下。

算法2第1步 確定對(duì)結(jié)果影響最大的中斷情景，并以此為基準(zhǔn)進(jìn)行計(jì)算第2步 利用迪杰斯特拉算法求解問(wèn)題P2，利用算法2C求解問(wèn)題P1，得到ε的取值范圍第3步 用算法2C求解問(wèn)題P0，得到時(shí)間與成本的最優(yōu)解向量x*，將x*加入到解列表Y′第4步 令ε＝f2（x*）-1，如果ε≥f I2，回到第3步，否則，轉(zhuǎn)到下一步第5步 將Y′中的被支配解刪除，得到帕累托前沿Y，決策者針對(duì)每個(gè)訂單選擇一個(gè)偏好解第6步 將偏好解代入第一階段模型，計(jì)算得到最優(yōu)解

4 算例分析

4.1 隨機(jī)算例

本文借助慕尼黑工業(yè)大學(xué)研發(fā)的在線帶資源約束的最短路問(wèn)題工具包，隨機(jī)生成不同規(guī)模算例，分別為6個(gè)小規(guī)模算例（1～6），4個(gè)中規(guī)模算例（7～10），6個(gè)大規(guī)模算例（11～16）。隨機(jī)生成8個(gè)周期的訂單數(shù)據(jù)，其需求量符合高斯分布。通過(guò)Python 3.8.5和Gurobi（Version 9.5.0）編程求解，所有測(cè)試均在一臺(tái)個(gè)人電腦上進(jìn)行（1.80 GHz CPU，16.0 GB，Windows 11）。

4.1.1 精確算法效果分析

用精確算法1計(jì)算1～10并將計(jì)算時(shí)間與用Gurobi求解的傳統(tǒng)ε-約束法進(jìn)行對(duì)比，每個(gè)算例運(yùn)行5次，取均值作為最終結(jié)果，如表1所示。

表1 傳統(tǒng)算法與精確算法1的計(jì)算時(shí)間

在所有算例中，精確算法1的計(jì)算時(shí)間均小于傳統(tǒng)算法，平均為傳統(tǒng)算法的50.52%，其中表現(xiàn)最好的為算例6，僅為傳統(tǒng)算法計(jì)算時(shí)間的33.96%。因此本文提出的精確算法可以有效地加速求解進(jìn)程。

4.1.2 啟發(fā)式算法效果分析

用啟發(fā)式算法2對(duì)算例7～16進(jìn)行計(jì)算，與傳統(tǒng)算法、精確算法1和NSGA-II進(jìn)行對(duì)比。其中算法2中的參數(shù)參考文獻(xiàn)［21，22］設(shè)定為：α＝0.75，T＝f1（s0），Tmin＝0.01，r＝0.9。選定計(jì)算時(shí)間，解的數(shù)量，與最優(yōu)解的平均偏離以及超體積作為衡量算法效果的指標(biāo)。其中超體積指標(biāo)通過(guò)計(jì)算非支配解集與參照點(diǎn)圍成的目標(biāo)空間中區(qū)域的體積［16］，來(lái)評(píng)估給定前沿的收斂性與多樣性，其值越高代表解的質(zhì)量越好。參考相關(guān)文獻(xiàn)［23］，本文選擇采用前文確定的作為參照點(diǎn)。

如表2所示，本文的啟發(fā)式算法計(jì)算速度遠(yuǎn)遠(yuǎn)快于精確算法，并且精確算法無(wú)法得到大規(guī)模算例的結(jié)果；而至于計(jì)算結(jié)果，啟發(fā)式算法與精確算法的成本與時(shí)間的平均偏離分別為2.15%與1.34%，超體積偏離大約在0.05～0.23之間。如表3所示，在大規(guī)模算例中，為了檢驗(yàn)本文啟發(fā)式的計(jì)算效果，我們將其與經(jīng)典算法NSGA-Ⅱ的結(jié)果進(jìn)行對(duì)比，可以發(fā)現(xiàn)在保證相同的計(jì)算時(shí)間的前提下，本文啟發(fā)式算法的效果更優(yōu)。

表2 傳統(tǒng)算法與精確算法1同啟發(fā)式算法2的計(jì)算效果對(duì)比

表3 啟發(fā)式算法2與NSGA-Ⅱ效果對(duì)比

4.2 現(xiàn)實(shí)算例

4.2.1 數(shù)據(jù)說(shuō)明

以南京為起點(diǎn)，以歐洲的不萊梅、斯武比采、巴黎與羅馬為終點(diǎn)。節(jié)點(diǎn)間的距離以谷歌地圖數(shù)據(jù)為基準(zhǔn)，速度以及運(yùn)費(fèi)參數(shù)參照文獻(xiàn)進(jìn)行設(shè)定［24］，F(xiàn)EU集裝箱公路運(yùn)輸速度按照平均值55km／h，運(yùn)輸費(fèi)用國(guó)內(nèi)以9元／箱公里，歐盟以16元／箱公里計(jì)算，鐵路運(yùn)輸速度按照35km／h，運(yùn)輸費(fèi)用分為獨(dú)聯(lián)體區(qū)段、國(guó)內(nèi)段以及歐盟段，分別按照不同的價(jià)格進(jìn)行計(jì)算。水運(yùn)為便于計(jì)算，運(yùn)輸時(shí)間統(tǒng)一按照28天，運(yùn)輸費(fèi)用按照26000元／箱進(jìn)行計(jì)算。庫(kù)存成本為每天308元／箱。不同運(yùn)輸方式之間轉(zhuǎn)運(yùn)時(shí)間與價(jià)格：公路與鐵路為1h，110元／箱；公路與飛機(jī)為2h，180元／箱；鐵路與飛機(jī)為3h，220元／箱。以14天為一個(gè)周期，共計(jì)算8個(gè)周期。海外倉(cāng)的補(bǔ)貨方式采用水運(yùn)。所有庫(kù)存以及運(yùn)輸單位均以FEU箱為單位，每個(gè)海外倉(cāng)初始庫(kù)存均為30箱，安全庫(kù)存點(diǎn)為15箱，每次補(bǔ)貨量為20箱。所有訂單數(shù)據(jù)隨機(jī)產(chǎn)生，其中需求量符合高斯分布。

4.2.2 現(xiàn)實(shí)算例分析

用傳統(tǒng)算法與精確算法1同啟發(fā)式算法2進(jìn)行求解，每個(gè)算例計(jì)算5次，結(jié)果取均值。如表4，啟發(fā)式算法的計(jì)算速度遠(yuǎn)大于精確算法，但是精確算法的計(jì)算效果要優(yōu)于啟發(fā)式算法。例如啟發(fā)式算法的目標(biāo)函數(shù)f1與f2平均偏離分別為2.6%與2.1%，超體積偏離在0.09～0.26之間。

表4 計(jì)算效果對(duì)比

4.2.3 不同中斷情景對(duì)結(jié)果的影響

計(jì)算幾個(gè)連接亞歐的長(zhǎng)途路徑中斷對(duì)最優(yōu)解的影響，發(fā)現(xiàn)只有蘇州華沙鐵路，杭州—列日空運(yùn)，杭州—華沙公路的中斷會(huì)產(chǎn)生影響，因此只展示這三種中斷與無(wú)中斷時(shí)的最優(yōu)解對(duì)比。以不萊梅為終點(diǎn)，結(jié)果如圖1所示。其中代表杭州—華沙中斷的黑線之所以在無(wú)中斷的紅線之下，是因?yàn)楹诰€得出的結(jié)果數(shù)量較少導(dǎo)致的，而不是占優(yōu)于紅線。顧客的滿意度隨著成本的增大而提升，針對(duì)每個(gè)訂單，決策者有多種選擇可以達(dá)到不同水平的顧客滿意度，因此需在成本和顧客滿意度之間權(quán)衡。從圖1可以看出，蘇州—華沙的鐵路中斷對(duì)結(jié)果影響最大。因此本文的魯棒優(yōu)化的最差情景為蘇州-華沙的鐵路中斷。

圖1 不同中斷情景的影響

4.2.4 模型魯棒性檢驗(yàn)

對(duì)比魯棒模型與原模型得出的帕累托前沿路徑方案在不同的中斷情景下的表現(xiàn)效果。無(wú)中斷情景下，原模型的表現(xiàn)效果更優(yōu)，但一旦中斷，原模型的結(jié)果波動(dòng)明顯，相比之下，魯棒模型在多種不同的中斷情景中，結(jié)果的平穩(wěn)性大大優(yōu)于原模型。深入分析原因我們發(fā)現(xiàn)，魯棒模型的路徑搭配更加多樣，但是原模型的路徑方案大部分都選用單一路段，因此抗風(fēng)險(xiǎn)性大大降低。由此可知，本文的魯棒模型路徑方案可以有效應(yīng)對(duì)道路中斷風(fēng)險(xiǎn)。

4.3 靈敏度分析

4.3.1 有無(wú)海外倉(cāng)的結(jié)果對(duì)比

以不萊梅為終點(diǎn)，結(jié)果如圖2所示。由圖2可知，海外倉(cāng)可以大幅度減少時(shí)間與成本。因?yàn)榕c直郵多花費(fèi)的運(yùn)輸成本相比，因海外倉(cāng)存在而增加的庫(kù)存成本是很小的。這也解釋了海外倉(cāng)近幾年越來(lái)越多的社會(huì)現(xiàn)象。

圖2 有無(wú)海外倉(cāng)的影響

4.3.2 安全庫(kù)存量不同的結(jié)果對(duì)比

由圖3可知，巴黎、羅馬與不萊梅三個(gè)海外倉(cāng)的安全庫(kù)存量越高越好，而斯武比采安全庫(kù)存量值越小越好。因?yàn)榍叭叩男枨罅看?，?dāng)安全庫(kù)存量較低時(shí)不能及時(shí)補(bǔ)貨，部分訂單需直郵，雖安全庫(kù)存量值較高會(huì)增加庫(kù)存成本，但與增加的直郵的運(yùn)輸費(fèi)用與時(shí)間相比是微不足道的。而對(duì)于斯武比采而言，該地的需求量較少，因此增加安全庫(kù)存量，只會(huì)導(dǎo)致庫(kù)存的增加，安全庫(kù)存量值在一定程度上減少是有利的。綜上對(duì)于需求量較小的產(chǎn)品，應(yīng)適當(dāng)降低安全庫(kù)存量，通過(guò)減少補(bǔ)貨次數(shù)，降低貨物積壓從而降低成本。而對(duì)于需求量較大的產(chǎn)品，則需適當(dāng)?shù)靥岣甙踩珟?kù)存量，通過(guò)增加補(bǔ)貨次數(shù)來(lái)減少直郵，從而降低成本與等待時(shí)間。

圖3 安全庫(kù)存點(diǎn)對(duì)結(jié)果的影響

4.3.3 補(bǔ)貨量不同的結(jié)果對(duì)比

對(duì)于巴黎、羅馬與不萊梅，補(bǔ)貨量20好于30好于10，而斯武比采則是補(bǔ)貨量10好于30好于20。因?yàn)榍叭叩男枨罅看?，因此補(bǔ)貨10單位不足以滿足需求，需花費(fèi)更多的成本與時(shí)間直郵，因此其結(jié)果最差；補(bǔ)貨20可減少大部分直郵從而減少等待時(shí)間與成本；而當(dāng)增加補(bǔ)貨量為30時(shí)，雖可以進(jìn)一步消除直郵，但無(wú)法抵消由此造成的庫(kù)存成本的增加，導(dǎo)致總成本上升。而斯武比采的需求量較小，因此增加補(bǔ)貨只會(huì)增加其庫(kù)存從而增加成本，雖本文結(jié)果是補(bǔ)貨量30好于20，但分析發(fā)現(xiàn)是由研究時(shí)間較短所致，若從長(zhǎng)期的眼光來(lái)看，補(bǔ)貨量20好于30。綜上，對(duì)于需求較少的產(chǎn)品，需一定程度上降低補(bǔ)貨量。而對(duì)于需求量較大的產(chǎn)品，需在一定范圍內(nèi)提高補(bǔ)貨量，但要把握好補(bǔ)貨的度，過(guò)高的補(bǔ)貨量同樣會(huì)導(dǎo)致產(chǎn)品積壓，從而增加總成本。

5 結(jié)論與啟示

本文基于跨境電商海外倉(cāng)的背景，以最小化總成本與最大化顧客滿意度為目標(biāo)，考慮海外倉(cāng)、中斷以及多式聯(lián)運(yùn)，對(duì)其進(jìn)行兩階段優(yōu)化建模。針對(duì)小規(guī)模算例設(shè)計(jì)了精確算法；對(duì)于大規(guī)模算例設(shè)計(jì)了GRASP-SA的混合啟發(fā)式算法。

首先用隨機(jī)算例測(cè)試模型與算法，對(duì)于中小規(guī)模算例，將本文精確算法1與傳統(tǒng)算法進(jìn)行對(duì)比，證明本文算法可以加快求解速度。對(duì)于大規(guī)模算例，將啟發(fā)式算法與NSGA-Ⅱ進(jìn)行對(duì)比，驗(yàn)證啟發(fā)式算法的可行性與可靠性。之后基于現(xiàn)實(shí)數(shù)據(jù)，運(yùn)用本文精確算法與啟發(fā)式算法求解，通過(guò)靈敏度分析發(fā)現(xiàn)：海外倉(cāng)可以極大降低成本與等待時(shí)間，而安全庫(kù)存量與補(bǔ)貨量則需結(jié)合實(shí)際需求量合理地制定，對(duì)于需求較少的應(yīng)適當(dāng)降低安全庫(kù)存量以及補(bǔ)貨量，通過(guò)減少庫(kù)存來(lái)降低總成本，而對(duì)于需求較大的產(chǎn)品，應(yīng)適度增加安全庫(kù)存與補(bǔ)貨量，通過(guò)減少運(yùn)輸成本來(lái)降低總成本。

本文的不足為沒(méi)有考慮未來(lái)需求，會(huì)導(dǎo)致決策的短視性，也因?yàn)樾畔⒌牟蛔銦o(wú)法對(duì)庫(kù)存補(bǔ)貨量進(jìn)行直接的優(yōu)化決策。隨著信息時(shí)代的到來(lái)，企業(yè)越來(lái)越重視大數(shù)據(jù)的應(yīng)用［25］，未來(lái)研究可以利用機(jī)器學(xué)習(xí)預(yù)測(cè)需求來(lái)進(jìn)一步對(duì)庫(kù)存進(jìn)行優(yōu)化以提升優(yōu)化效果。此外，本文沒(méi)有考慮訂單的合并、海外倉(cāng)間的補(bǔ)貨以及轉(zhuǎn)運(yùn)時(shí)的運(yùn)力不匹配等問(wèn)題，可以在未來(lái)補(bǔ)充研究。最后，可以針對(duì)這類問(wèn)題開發(fā)更高效的算法。