段征宇 ，雷曾翔 ，孫 碩 ，楊東援

（1.同濟(jì)大學(xué)道路與交通工程教育部重點(diǎn)實(shí)驗(yàn)室，上海 201804；2.上海市城市規(guī)劃設(shè)計(jì)研究院，上海 200040）

車(chē)輛路徑問(wèn)題（vehicle routing problem，VRP）是物流配送的核心問(wèn)題之一，研究如何安排車(chē)輛配送路線(xiàn)，使得配送成本最低.VRP 也是NP-hard（nondeterministic polynomial-time hard）問(wèn)題，吸引眾多學(xué)者進(jìn)行了大量的研究工作.以往研究大多假定路段行程時(shí)間是常數(shù)或確定型時(shí)變函數(shù).然而，隨著城市交通擁堵的日趨嚴(yán)重，交通需求的短期變化、交通事故和惡劣天氣等，導(dǎo)致了路網(wǎng)交通狀態(tài)的不確定性.因此，在物流配送中需要同時(shí)考慮路網(wǎng)交通狀態(tài)的時(shí)變性和隨機(jī)性，以滿(mǎn)足客戶(hù)的時(shí)效性和時(shí)間窗要求，提高客戶(hù)滿(mǎn)意度.

隨機(jī)時(shí)變車(chē)輛路徑問(wèn)題 （stochastic time-dependent vehicle routing problem，STDVRP）是研究在隨機(jī)時(shí)變路網(wǎng)中，如何制定滿(mǎn)足多個(gè)客戶(hù)需求的配送車(chē)輛路徑，使得總配送成本最小.STDVRP 是時(shí)間依賴(lài)型車(chē)輛路徑問(wèn)題 （time-dependent vehicle routing problem，TDVRP）和隨機(jī)車(chē)輛路徑問(wèn)題 （stochastic vehicle routing problem，SVRP）發(fā)展而來(lái)，同時(shí)考慮了路段行程時(shí)間的時(shí)變性和隨機(jī)性.在實(shí)際路網(wǎng)中，STDVRP 需要大量計(jì)算客戶(hù)節(jié)點(diǎn)之間的最優(yōu)路徑，因此，隨機(jī)時(shí)變最優(yōu)路徑問(wèn)題 （stochastic time-dependent optimal path problem，STDOPP）是STDVRP 的基礎(chǔ).

早期STDOPP 研究以最小期望時(shí)間作為優(yōu)化標(biāo)準(zhǔn).比如：Hall[1]提出了分支限界方法與k最短路徑相結(jié)合的求解方法，并發(fā)現(xiàn)由于不滿(mǎn)足Bellman 優(yōu)化原理，傳統(tǒng)最短路徑算法不能直接用于STDOPP；Miller-hooks 等[2]設(shè)計(jì)了求解最小期望時(shí)間路徑的標(biāo)號(hào)擴(kuò)展算法.20 世紀(jì)90年代后，效用理論被引入最優(yōu)路徑的評(píng)價(jià).比如：Wellman 等[3]提出了隨機(jī)一致性條件，根據(jù)效用函數(shù)計(jì)算期望最短路徑；Huang等[4]采用行程時(shí)間的負(fù)效用函數(shù)評(píng)價(jià)隨機(jī)時(shí)變路徑，設(shè)計(jì)了標(biāo)號(hào)修改算法.以上研究以路段行程時(shí)間的概率分布為基礎(chǔ)，求解算法的時(shí)間復(fù)雜度為指數(shù)形式，不適用于大規(guī)模路網(wǎng).另一個(gè)思路是考察路段行程時(shí)間“最壞情況”下的“最優(yōu)路徑”.Sim[5]最早提出了魯棒優(yōu)化模型，將隨機(jī)路網(wǎng)的最優(yōu)路徑問(wèn)題 （stochastic optimal path problem，SOPP）轉(zhuǎn)變?yōu)榇_定型路網(wǎng)的最短路徑問(wèn)題.Sun 等[6-7]將該方法擴(kuò)展到STDOPP，將其轉(zhuǎn)化為確定型時(shí)變網(wǎng)絡(luò)的最優(yōu)路徑問(wèn)題，求解算法的時(shí)間復(fù)雜度為多項(xiàng)式形式.

目前STDVRP 的研究相對(duì)較少，主要根據(jù)路段行程時(shí)間的概率分布，采用機(jī)會(huì)約束模型進(jìn)行建模，使得期望行程時(shí)間最小[8-9].無(wú)時(shí)間窗STDVRP 的模型相對(duì)簡(jiǎn)單，但計(jì)算復(fù)雜度仍然較高，例如Nahum等[10]設(shè)計(jì)的遺傳算法，對(duì)于100～200 個(gè)客戶(hù)節(jié)點(diǎn)的STDVRP，平均計(jì)算時(shí)間為3.8 h.對(duì)于有時(shí)間窗STDVRP，需要考慮各客戶(hù)的時(shí)間窗約束，求解更為困難，相關(guān)研究還很少見(jiàn).

目前的STDOPP 和STDVRP 研究，通常需要知道路段行程時(shí)間的概率分布，求解的計(jì)算復(fù)雜度較高.對(duì)于實(shí)際路網(wǎng)的應(yīng)用，要標(biāo)定每個(gè)路段的行程時(shí)間概率分布是比較困難的.魯棒優(yōu)化方法提供了一種新的思路，已被成功應(yīng)用于SOPP[5]、STDOPP[6-7]和SVRP[11].此外，目前大多STDVRP 研究針對(duì)無(wú)時(shí)間窗問(wèn)題，而對(duì)于有時(shí)間窗問(wèn)題，需要考慮各客戶(hù)的時(shí)間窗約束，求解更為復(fù)雜.

本文建立了帶硬時(shí)間窗的STDVRP 的多目標(biāo)魯棒優(yōu)化模型，設(shè)計(jì)了一種蟻群算法進(jìn)行求解.與傳統(tǒng)的STDVRP 模型相比，該模型不需要知道路段行程時(shí)間的概率分布函數(shù)，只要根據(jù)歷史交通數(shù)據(jù)標(biāo)定其波動(dòng)范圍，在實(shí)際路網(wǎng)中使用更為方便.由于基于魯棒優(yōu)化模型的STDOPP，計(jì)算復(fù)雜度為多項(xiàng)式形式，因此，相比于基于路段行程時(shí)間概率分布的STDVRP 模型，魯棒STDVRP 模型的計(jì)算復(fù)雜度更低.此外，該模型考慮了各客戶(hù)的時(shí)間窗約束，與實(shí)際物流配送應(yīng)用的情況更為一致.

1 STDVRP 建模

1.1 隨機(jī)時(shí)變路網(wǎng)的表示和標(biāo)定

對(duì)于隨機(jī)時(shí)變路網(wǎng)G={V,A,T,Cab(t)}，其中：V為節(jié)點(diǎn)集合；A為路段集合；Cab(t)為路段lab在時(shí)段t（t∈T）的行程時(shí)間，如式（1），lab是從節(jié)點(diǎn)a到b的有向路段，lab∈A；T是時(shí)間分段的集合（1，2，· ··,M），M是路段行程時(shí)間函數(shù)Cab(t)的分段數(shù).

式中：Rab(t)在 時(shí)段t是一個(gè)確定值；δab(t)是一個(gè)取值范圍為[0,dab(t)]的 隨機(jī)變量，dab(t)在時(shí)段t也是一個(gè)確定值.

因此，Cab(t) 的取值范圍為 [Rab(t),Rab(t)+dab(t)].

假定隨機(jī)時(shí)變路網(wǎng)G滿(mǎn)足隨機(jī)一致性條件[3].也就是，對(duì)于任意路段lab∈A，若t≤t′（t'為晚于t的另一個(gè)時(shí)段），對(duì)于給定時(shí)間ξ，式（2）成立，也就是出發(fā)時(shí)間早的車(chē)輛早到終點(diǎn)的概率比出發(fā)時(shí)間晚的車(chē)輛大.

隨著浮動(dòng)車(chē)技術(shù)的發(fā)展，獲取城市路網(wǎng)的路段行程車(chē)速也越來(lái)越容易.例如，上海2007年建成的浮動(dòng)車(chē)采集系統(tǒng)，接入了2.5 萬(wàn)輛出租車(chē)GPS 數(shù)據(jù)，可以計(jì)算得到各路段每5 min 時(shí)段的行程車(chē)速[12].采用歷史數(shù)據(jù)，可以標(biāo)定各路段每5 min 時(shí)段的行程時(shí)間的波動(dòng)范圍，從而得到路段行程時(shí)間函數(shù)Cab(t).

1.2 STDOPP 和STDVRP 模型的符號(hào)和變量

（1）常量

[0，te0]為配送中心的工作時(shí)間，開(kāi)始時(shí)刻為0，結(jié)束時(shí)刻為te0；[tbi，tei]為客戶(hù)節(jié)點(diǎn)i要求的時(shí)間窗，開(kāi)始時(shí)刻為tbi，結(jié)束時(shí)刻為tei；tsi為客戶(hù)i的服務(wù)時(shí)間；qi為客戶(hù)i的配送需求量；Qk為車(chē)輛k的載重量；B為無(wú)窮大的數(shù).

（2）集合

NS為始發(fā)節(jié)點(diǎn)集合；NE為終到節(jié)點(diǎn)集合；ND為需求節(jié)點(diǎn)集合；NSD為始發(fā)節(jié)點(diǎn)與需求節(jié)點(diǎn)的集合；NDE為需求節(jié)點(diǎn)與終到節(jié)點(diǎn)集合；NSDE為所有節(jié)點(diǎn)的集合；NSC為客戶(hù)點(diǎn)集合的任一子集合，|NSC|為集合NSC的客戶(hù)節(jié)點(diǎn)數(shù)；Λij為從節(jié)點(diǎn)i到j(luò)的可行路徑的集合.

（3）決策變量和參數(shù)

K為使用車(chē)輛數(shù)；xij(t)為若車(chē)輛在時(shí)段t內(nèi)出發(fā)，從i駛向j，值為1，否則為0；ti為配送車(chē)輛到達(dá)節(jié)點(diǎn)i的時(shí)刻；τi為配送車(chē)輛從節(jié)點(diǎn)i的出發(fā)時(shí)刻；vik為若點(diǎn)i由車(chē)輛k訪(fǎng)問(wèn)，值為1，否則為0；tij（τi）為時(shí)刻τi從節(jié)點(diǎn)i出發(fā)到j(luò)的最優(yōu)路徑的行程時(shí)間；λij為從節(jié)點(diǎn)i出發(fā)到j(luò)的一條可行路徑（λij∈Λij）；f~(λi j,τi)為時(shí)刻τi從節(jié)點(diǎn)i出發(fā)到j(luò)，路徑λij在最壞情況下的行程時(shí)間；lab為可行路徑λij中的路段，即lab∈λij；yab(t)為若路徑λij在時(shí)段t內(nèi)經(jīng)過(guò)路段lab，值為1，否則為0；t0k為車(chē)輛k從配送中心出發(fā)的時(shí)刻；tdk為車(chē)輛k返回配送中心的時(shí)刻.

1.3 STDOPP 的魯棒優(yōu)化模型

在STDVRP 中需要計(jì)算各客戶(hù)節(jié)點(diǎn)之間以及客戶(hù)節(jié)點(diǎn)與配送中心之間的最優(yōu)路徑，因此STDOPP是求解STDVRP 的前提.對(duì)于時(shí)刻τi從節(jié)點(diǎn)i到j(luò)的路徑λij，最壞情況下的行程時(shí)間為

所以，根據(jù)最小最大準(zhǔn)則，時(shí)刻τi從節(jié)點(diǎn)i到j(luò)的最優(yōu)路徑的行程時(shí)間為

根據(jù)文獻(xiàn)[6]，結(jié)合式（3），可得

因此，時(shí)刻τi從節(jié)點(diǎn)i到j(luò)的最優(yōu)路徑的行程時(shí)間為

在式（6）中，Rab(t)+dab(t)是路段lab在時(shí)段t的行程時(shí)間上界，是一個(gè)確定值.若令Rab(t)+dab(t)為路段lab在時(shí)段t的行程時(shí)間，那么，可以得到一個(gè)確定型時(shí)變路網(wǎng)G′.可以證明G′是一個(gè)先入先出（first in first out，F(xiàn)IFO）網(wǎng)絡(luò)[6].這樣就將節(jié)點(diǎn)i到j(luò)的最優(yōu)路徑問(wèn)題.轉(zhuǎn)換為FIFO 時(shí)變路網(wǎng)的行程時(shí)間最小路徑問(wèn)題.傳統(tǒng)最短路徑的標(biāo)號(hào)法可以用于求解該問(wèn)題，并且時(shí)間復(fù)雜度為多項(xiàng)式形式.

1.4 STDVRP 的多目標(biāo)魯棒優(yōu)化模型

下面給出帶硬時(shí)間窗的STDVRP 多目標(biāo)優(yōu)化模型.硬時(shí)間窗約束要求在客戶(hù)指定的時(shí)間窗內(nèi)配送，先到必須等待，且不允許遲到.VRP 常用的優(yōu)化目標(biāo)有：使用車(chē)輛數(shù)最少、總行程時(shí)間最少、總等待時(shí)間最少、總行駛距離最小等.傳統(tǒng)方法通常采用加權(quán)求和方法，將多個(gè)目標(biāo)加權(quán)組合為單個(gè)目標(biāo)進(jìn)行求解.但由于量綱不同，多個(gè)目標(biāo)之間往往不能直接比較，權(quán)重也很難確定.

對(duì)于STDVRP，總的配送成本主要由車(chē)輛固定成本、路徑行程成本、客戶(hù)懲罰成本組成.車(chē)輛固定成本與使用車(chē)輛數(shù)有關(guān)；路徑行程成本與總行程時(shí)間有關(guān)；對(duì)于帶硬時(shí)間窗的STDVRP，不允許違反客戶(hù)時(shí)間窗要求，所以，不需要考慮客戶(hù)懲罰成本.因此，在本文中選取使用車(chē)輛數(shù)最少、總行程時(shí)間最少兩個(gè)優(yōu)化目標(biāo)，采用最小最大準(zhǔn)則的魯棒優(yōu)化方法對(duì)STDVRP 進(jìn)行建模.

（1）目標(biāo)函數(shù)

使用車(chē)輛數(shù)最少：

總行程時(shí)間最少：

（2）約束條件

式（9）、（10）表示每個(gè)客戶(hù)需要服務(wù)一次；式（11）、（12）表示同一條路線(xiàn)上的客戶(hù)由同一輛車(chē)服務(wù)；式（13）表示每個(gè)客戶(hù)只能由一輛車(chē)服務(wù)；式（14）表示每輛車(chē)的裝載量不超過(guò)該車(chē)的容量；式（15）表示所有的車(chē)輛必須從配送中心出發(fā)，并返回配送中心；式（16）防止在配送路徑中形成子回路；式（17）、（18）和式（19）分別是客戶(hù)節(jié)點(diǎn)和配送中心的時(shí)間窗約束.

在上述STDVRP 模型中，客戶(hù)點(diǎn)的時(shí)間窗和服務(wù)時(shí)間是固定的，客戶(hù)節(jié)點(diǎn)i到j(luò)的最優(yōu)行程時(shí)間tij(τi)根據(jù)1.3 節(jié)的式（6），采用路段在對(duì)應(yīng)時(shí)段的行程時(shí)間上界計(jì)算，因此，該模型等價(jià)于求確定型時(shí)變路網(wǎng)G′的TDVRP.對(duì)于FIFO 網(wǎng)絡(luò)的TDVRP，可以采用傳統(tǒng)VRP 算法求解[13]，從而降低了STDVRP的求解困難.

2 STDVRP 的算法

Pareto 最優(yōu)解也稱(chēng)為非支配解，是指不能再找到另外一些解，他們的所有目標(biāo)都不差于Pareto 解的相應(yīng)目標(biāo)，且至少有一個(gè)目標(biāo)優(yōu)于Pareto 解的相應(yīng)目標(biāo).Pareto 最優(yōu)解通常是一個(gè)集合.設(shè)xA、xB是多目標(biāo)優(yōu)化問(wèn)題 minY=[f1(x)f2(x) ···fm(x)]T的可行 解，若 ?i1∈{1,2,···,m}，fi1(xA)≤fi1(xB)，且?j1∈{1,2,···,m}，fj1(xA)＜fj1(xB)，則稱(chēng)xA與xB相比是Pareto 占優(yōu)的，記作xA?xB，也稱(chēng)xA支配xB[14].

STDVRP 屬于NP-hard 問(wèn)題，精確求解十分困難，通常采用亞啟發(fā)式算法進(jìn)行求解[10].

改進(jìn)型非支配排序遺傳算法（non-dominated sorting genetic algorithm II，NSGA-II）是Deb 等[15]于2002年提出的，在多目標(biāo)VRP 問(wèn)題求解中得到了成功的應(yīng)用[16-17].由于本文已將STDVRP 轉(zhuǎn)換為T(mén)DVRP，因此，可以用NSGA-II 算法進(jìn)行求解.

蟻 群 算 法（ant colony optimisation，ACO）在TDVRP 中得到了成功的應(yīng)用，可用于求解客戶(hù)節(jié)點(diǎn)數(shù)量為100～1 000 的大規(guī)模TDVRP，具有較高的計(jì)算效率[18-20].本文將NSGA-II 算法中的基于Pareto占優(yōu)的非支配排序引入ACO 算法，設(shè)計(jì)了求解一種多目標(biāo)STDVRP 的非支配排序蟻群算法（nondominated sorting ant colony optimisation，NSACO）.

2.1 基于Pareto 占優(yōu)的非支配排序

設(shè)解集P的規(guī)模為N，將P按照某種策略進(jìn)行分級(jí)排序?yàn)閙1個(gè)子集（P1、P2、…、Pm1），且滿(mǎn)足：（1）?i2,j2∈{1,2,···,m1}，且i2≠j2，Pi2∩Pj2=φ；（2）Pk1+1中 的可行解受Pk1的 可行解的支配（k1=1，2，…，m1-1）.快速非支配排序算法依據(jù)可行解之間的支配關(guān)系對(duì)P進(jìn)行分級(jí)排序，將P劃分為互不相交的子集.解集P的每個(gè)可行解設(shè)定兩個(gè)參數(shù)ni2和Si2，ni2記 錄支配可行解i2的 可行解數(shù)量，Si2是記錄被可行解i2支 配的可行解的集合，令k1=1.算法步驟如下[21-22]：

步驟1計(jì)算每個(gè)可行解的ni2和Si2，找到解集P中ni2=0 的所有可行解，將其存入當(dāng)前集合Pk1；

步驟2對(duì)當(dāng)前集合Pk1中 每個(gè)可行解j2，考察它所支配的可行解集合S j2，將S j2中的每個(gè)可行解r2的nr2減去1（因?yàn)橹淇尚薪鈘2的 可行解j2已經(jīng)存入Pk1），若nr2-1=0則將可行解存入集合Q；

步驟3將Pk1作 為第k1級(jí) 非支配解集合，Pk1所有可行解的非支配序irank=k1，然后，令k1=k1+1，Pk1=Q；

步驟4若Pk1不為空，則轉(zhuǎn)入步驟2，否則算法停止.

2.2 NSACO 算法

（1）初始化

采用文獻(xiàn)[23]提出的初始解構(gòu)造方法，生成質(zhì)量較高的初始解，由此設(shè)定路段lab的信息素初始值ηab（0）.然后，采用“蟻周模型”更新規(guī)則[24]，對(duì)各路段的信息素進(jìn)行更新.

（2）通過(guò)螞蟻移動(dòng)，構(gòu)造配送路徑，并進(jìn)行局部信息素更新

每只螞蟻從配送中心出發(fā)，根據(jù)“偽隨機(jī)比例規(guī)則”[24]確定的轉(zhuǎn)移概率，選擇下一個(gè)節(jié)點(diǎn)：若滿(mǎn)足約束條件，則選擇該節(jié)點(diǎn)，并記錄到禁忌表中，然后，對(duì)行經(jīng)路段進(jìn)行信息素更新；否則，返回配送中心，重新開(kāi)始一條新的路徑，直至所有客戶(hù)節(jié)點(diǎn)都被訪(fǎng)問(wèn)，則該螞蟻完成一次周游.

（3）全局信息素更新

在所有螞蟻都完成周游以后，將得到的可行解與上次迭代保留的可行解合并，得到解集P；采用快速非支配排序算法，對(duì)P進(jìn)行分級(jí)排序，得到第1 級(jí)非支配解集合P1；保留P1可行解，并對(duì)其行經(jīng)路段進(jìn)行信息素更新.路段lab的信息素ηab的更新方法如下：

式中：ηab（u）為第u次循環(huán)的當(dāng)前信息素值；ηab（u+ 1）為更新后的信息素值；Δηab（u，u+ 1）為信息素增量；LP（u）為第u次循環(huán)，P1集合的可行解對(duì)應(yīng)的總行程時(shí)間的平均值；ρ為信息素?fù)]發(fā)系數(shù).

為了避免出現(xiàn)“過(guò)早收斂”，采用“最大-最小螞蟻系統(tǒng)”[25]的信息素更新策略，將路段信息素限制在[ηmin，ηmax]范圍內(nèi).

式中：n為客戶(hù)節(jié)點(diǎn)數(shù)；θb為選擇最優(yōu)解的概率，取0.05[25]；h（u）為第u次循環(huán)P1的可行解中最小的總行程時(shí)間.

（4）判斷是否達(dá)到預(yù)定最大迭代次數(shù)，若符合，則輸出最優(yōu)解并結(jié)束計(jì)算；否則，返回步驟2.

3 算例分析

3.1 算例構(gòu)建

Solomon 基準(zhǔn)算例[26]在傳統(tǒng)VRP 中被廣泛使用，包括6 組共56 個(gè)算例.每個(gè)算例包括100 個(gè)客戶(hù)節(jié)點(diǎn)，根據(jù)客戶(hù)的空間分布，可分為3 類(lèi)：C 類(lèi)算例（聚集分布）、R 類(lèi)算例（隨機(jī)分布）和RC 類(lèi)算例（混合分布）.參照文獻(xiàn)[19]的方法，基于Solomon基準(zhǔn)算例構(gòu)建TDVRP 算例，然后，增加路段行程車(chē)速的波動(dòng)范圍，得到STDVRP 算例.具體如下：

將算例的路段分為5 類(lèi)，路段lij的類(lèi)型由g（i，j）表示，由式（24）確定.

表1給出了各類(lèi)路段在4 個(gè)等分時(shí)段的行程車(chē)速.對(duì)時(shí)段1、3 的行程車(chē)速，增加±20%的波動(dòng)范圍；對(duì)時(shí)段2、4 的行程車(chē)速，增加±10%的波動(dòng)范圍，由此得到STDVRP 算例.為了方便仿真測(cè)試時(shí)計(jì)算期望行程時(shí)間和期望等待時(shí)間，假定路段行程車(chē)速的波動(dòng)服從均勻分布.事實(shí)上本文的魯棒優(yōu)化模型和算法只與行程車(chē)速的波動(dòng)范圍有關(guān)，而與行程車(chē)速的概率分布形式無(wú)關(guān).

表1 各類(lèi)路段的行程車(chē)速Tab.1 Travel speed of various links

3.2 Pareto 最優(yōu)解集合及邊界解

以擴(kuò)展Solomon 基準(zhǔn)算例R201 為例，采用NSACO 算法求解，得到的Pareto 最優(yōu)解集合的分布情況，如圖1所示.

Pareto 最優(yōu)解集包含多個(gè)非支配解，為便于比較NSACO 算法和NSGA-II 算法的結(jié)果，僅選取邊界解進(jìn)行比較.為表述方便，將Pareto 最優(yōu)解集中“最壞行程時(shí)間”最小的邊界解稱(chēng)為“邊界解A”，將“車(chē)輛數(shù)”最小的邊界解稱(chēng)為“邊界解B”.

3.3 算例求解

采用試算法確定NSACO 算法和NSGA-II 算法的參數(shù)，即每次給出某參數(shù)的一組取值，固定其它參數(shù)，根據(jù)算例的計(jì)算結(jié)果確定該參數(shù)的最優(yōu)取值.得到NSACO 算法的參數(shù)：信息強(qiáng)度參數(shù)α= 1；能見(jiàn)度參數(shù)β= 2；信息素?fù)]發(fā)系數(shù)ρ= 0.2；偽隨機(jī)比例參數(shù)ω= 0.9；螞蟻數(shù)量γ= 10.NSGA-II 算法的參數(shù)：交叉率取0.8；變異率取 0.2.兩種算法的初始解均采用文獻(xiàn)[23]提出的初始解構(gòu)造方法生成.

圖1 R201 算例的Pareto 最優(yōu)解的分布Fig.1 Distribution of R201’s Pareto optimal solutions

選取擴(kuò)展Solomon 基準(zhǔn)算例的C101、C201、R101、R201、RC101 和RC201，分別采用NSACO 算法和NSGA-II 算法進(jìn)行求解，兩種算法均迭代200次，得到各算例的Pareto 最優(yōu)解集合.由于Pareto 最優(yōu)解集合包含多個(gè)非支配解，為便于比較，這里僅給出“邊界解A”和“邊界解B”.

采用Monte Carlo 仿真的方法，根據(jù)表1的路段行程車(chē)速及波動(dòng)范圍，對(duì)最優(yōu)解的配送執(zhí)行過(guò)程進(jìn)行模擬仿真，計(jì)算100 次，得到最優(yōu)解的行程時(shí)間和等待時(shí)間的期望值.計(jì)算結(jié)果如表2所示.

表2 STDVRP 算例的計(jì)算結(jié)果Tab.2 Computational results of STDVRP instances

為了方便比較，將NSACO 算法最優(yōu)解的結(jié)果除以對(duì)應(yīng)的NSGA-II 算法最優(yōu)解的結(jié)果，得到NSACO算法最優(yōu)解的相對(duì)值，如表3所示.

根據(jù)表2、3，NSACO 算法的優(yōu)化結(jié)果總體比NSGA-II 算法好.對(duì)于“邊界解B”，盡管NSACO算法的最壞行程時(shí)間和期望行程時(shí)間比NSGA-II算法大4%左右；但NSACO 算法的車(chē)輛數(shù)比NSGAII 算法小3.33%.對(duì)于“邊界解A”，NSACO 算法的車(chē)輛數(shù)、最壞行程時(shí)間和期望行程時(shí)間分別比NSGA-II 算法小11.98%、17.49%和23.03%.特別是對(duì)于C 類(lèi)算例（C101 和C201），NSACO 算法的優(yōu)化結(jié)果明顯優(yōu)于NSGA-II 算法.這是由于C 類(lèi)算例的客戶(hù)節(jié)點(diǎn)呈現(xiàn)聚集分布特征，能夠更好地發(fā)揮NSACO 算法的信息素正反饋?zhàn)饔茫啾扔贜SGAII 算法的隨機(jī)搜索，NSACO 算法能更快搜索到最近的客戶(hù)點(diǎn).

表3 NSACO 算法最優(yōu)解的相對(duì)值Tab.3 Relative values of NSACO algorithm’s optimal solutions

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

本文針對(duì)帶硬時(shí)間窗的STDVRP，提出了一種多目標(biāo)魯棒優(yōu)化模型，并基于Pareto 占優(yōu)的非支配排序方法設(shè)計(jì)了一種NSACO 算法進(jìn)行求解.主要結(jié)論如下：

（1）多目標(biāo)STDVRP 魯棒優(yōu)化模型可以轉(zhuǎn)換為T(mén)DVRP，與基于路段行程時(shí)間概率分布的STDVRP模型相比，求解難度更低，適用于大規(guī)模實(shí)際網(wǎng)絡(luò)的應(yīng)用.

（2）STDVRP 測(cè)試算例表明，與常用的多目標(biāo)NSGA-II 算法相比，NSACO 算法的優(yōu)化結(jié)果更好.特別是對(duì)客戶(hù)節(jié)點(diǎn)聚集分布的情況，NSACO 算法的收斂速度更快.

本文的STDVRP 魯棒優(yōu)化模型，只需要標(biāo)定路段行程時(shí)間在各時(shí)段的波動(dòng)范圍，可以保證客戶(hù)的時(shí)間窗要求，適用于大規(guī)模實(shí)際網(wǎng)絡(luò)的物流配送應(yīng)用.進(jìn)一步的研究和改進(jìn)包括：

（1）魯棒優(yōu)化模型主要考慮路段行程時(shí)間最壞的情況，得到的優(yōu)化解偏保守，下一步研究將適度放寬時(shí)間窗約束和路段行程時(shí)間波動(dòng)的上下界，綜合考慮配送成本和準(zhǔn)點(diǎn)送達(dá)率進(jìn)行建模和優(yōu)化.

（2）粒子群算法、魚(yú)群算法等智能搜索算法在多目標(biāo)優(yōu)化領(lǐng)域也具有良好的性能，下一步工作將探索更好的多目標(biāo)STDVRP 優(yōu)化算法.