張 凱，靳 鵬，崔 勇

合肥工業(yè)大學(xué) 管理學(xué)院，合肥230009

傳統(tǒng)物流企業(yè)利用自有車輛為客戶提供攬收/配送服務(wù)。由于自有車輛具有使用成本高、管理難度大等缺點(diǎn)，在共享經(jīng)濟(jì)大背景下，物流企業(yè)開始采用一種基于外部車輛的新型攬收配送模式，利用外部車輛為客戶提供攬收/配送服務(wù)，外部車輛主要是社會(huì)閑置車輛。新型攬收配送模式可以減少企業(yè)自有車輛的使用，降低物流成本，并對(duì)提高社會(huì)閑置車輛利用率和環(huán)境保護(hù)方面具有重要意義。

本文研究了基于新型攬收配送模式下的一種帶時(shí)間窗的多車型需求可拆分?jǐn)埵张渌蛦栴}（Multi-Vehicle Split Pickup and Delivery Problem with Time Windows，MVSPDPTW），使用社會(huì)閑置車輛作為攬收/配送任務(wù)的資源，社會(huì)閑置車輛擁有自己的起點(diǎn)、終點(diǎn)以及最早出發(fā)時(shí)間和最晚返回時(shí)間，車輛必須在最早出發(fā)時(shí)間后從起點(diǎn)出發(fā)為客戶提供攬收/配送服務(wù)，并在最晚返回時(shí)間前返回終點(diǎn)。在服務(wù)客戶的過程中，車輛需要在客戶時(shí)間窗內(nèi)提供服務(wù)，并且允許需求拆分，同一客戶需求可由多輛車完成，以便充分利用車輛的裝載能力。

車輛路徑問題（Vehicle Routing Problems，VRP）[1]自1959 年被提出以來，一直是物流研究領(lǐng)域的熱點(diǎn)問題。目前，在VRP 的研究中一般限制客戶的需求只能由一輛車來完成，屬于需求不可拆分的VRP。文獻(xiàn)[2]在1989年首次研究了需求可拆分的VRP（Split Delivery Vehicle Routing Problems，SDVRP），指出對(duì)客戶需求進(jìn)行合理的拆分有利于提高車輛裝載率和節(jié)約總成本，并在1994 年證明SDVRP 是NP-hard[3]問題。目前已有不少學(xué)者從不同角度對(duì)SDVRP展開了研究。由于客戶通常要求在給定的時(shí)間內(nèi)得到服務(wù)，因此一種考慮時(shí)間窗約束的SDVRP[4-7]得到了研究，文獻(xiàn)[4]首次將時(shí)間限制引入到SDVRP，構(gòu)造了考慮時(shí)間窗約束的SDVRP模型，提出了一種兩階段啟發(fā)式算法進(jìn)行求解。文獻(xiàn)[5]提出一種禁忌搜索算法求解考慮時(shí)間窗約束的SDVRP，設(shè)計(jì)了多種新型鄰域搜索算子。文獻(xiàn)[6-7]研究了考慮軟時(shí)間窗約束的SDVRP，軟時(shí)間窗約束通過添加懲罰函數(shù)允許客戶在給定的時(shí)間窗外被服務(wù)。在SDVRP中只考慮了客戶的配送需求，近些年隨著逆向物流的發(fā)展，客戶往往同時(shí)含有攬收/配送需求，因此一種考慮攬收需求的SDVRP[8-9]得到了研究，文獻(xiàn)[8]首次將需求可拆分引入攬收配送問題，揭示了需求可拆分帶來的好處，證明對(duì)于給定的一組攬收和配送位置，當(dāng)客戶需求量略大于車輛載重量一半時(shí)可以帶來最大的收益。文獻(xiàn)[9]提出了一個(gè)改進(jìn)蟻群算法求解需求可拆分的攬收配送問題，實(shí)驗(yàn)結(jié)果表明該算法可以提高配送中心的運(yùn)作效率。

以往對(duì)SDVRP 的研究基本建立在單一車型上，但是在實(shí)際配送中，車輛往往擁有多種車型[10-12]。文獻(xiàn)[10]研究了多車型的SDVRP，車輛的裝載能力與最大行駛里程各不相同，提出了一種模擬退火算法進(jìn)行求解。文獻(xiàn)[11]研究需求可拆分的多車型開放式車輛路徑問題，車輛從不同的配送中心出發(fā)為客戶服務(wù)，在服務(wù)完最后一個(gè)客戶后結(jié)束服務(wù)而不需要返回配送中心，提出了一種禁忌搜索算法進(jìn)行求解。文獻(xiàn)[12]分別研究了單車型和多車型的SDVRP，通過實(shí)驗(yàn)結(jié)果說明了不同裝載能力的車輛更符合實(shí)際需求并且可以有效提高提高車輛的裝載率。

上述多數(shù)文獻(xiàn)大都將攬收需求、配送需求、多車型、客戶時(shí)間窗等單獨(dú)研究，但是隨著物流技術(shù)的快速發(fā)展，用戶需求更加復(fù)雜，這種單一模式研究已經(jīng)難以滿足實(shí)際應(yīng)用需求。因此，本文綜合考慮上述多種要素，研究了一個(gè)帶時(shí)間窗的多車型需求可拆分?jǐn)埵张渌蛦栴}，針對(duì)這個(gè)問題本文以執(zhí)行任務(wù)車輛行駛路徑總長(zhǎng)度最小為目標(biāo)函數(shù)，建立了一個(gè)混合整數(shù)線性規(guī)劃模型，提出了一種高效禁忌模擬退火（Tabu Simulated Annealing，TSA）算法進(jìn)行求解。

1 問題描述

在MVSPDPTW中存在給定的一個(gè)配送中心，一組地理位置不同的客戶和一組多車型車輛，MVSPDPTW的目標(biāo)是選擇合適的車輛執(zhí)行完所有客戶任務(wù)，使得執(zhí)行任務(wù)車輛行駛路徑總長(zhǎng)度最小。

0表示配送中心，T={1,2,…,n}表示客戶點(diǎn)集合，每個(gè)客戶點(diǎn)對(duì)應(yīng)一個(gè)攬收/配送任務(wù)，將對(duì)應(yīng)攬收任務(wù)的客戶點(diǎn)稱為pickup 點(diǎn)，對(duì)應(yīng)配送任務(wù)的客戶點(diǎn)稱為delivery點(diǎn)。對(duì)于客戶點(diǎn)i∈T，[ei,li] 表示i的時(shí)間窗，ei表示最早開始服務(wù)時(shí)間，li表示最遲開始服務(wù)時(shí)間。qi表示i需要攬收/配送的貨物量。每個(gè)客戶點(diǎn)可以被多個(gè)車輛訪問，但只允許被同一車輛至多訪問一次。K={1,2,…,m}表示車輛集合，對(duì)于k∈K，sk、nk、Qk、ok、fk分別表示車輛k的起點(diǎn)、終點(diǎn)、最大容量、最早出發(fā)時(shí)間以及最晚返回時(shí)間。如圖1所示，車輛需要在最早出發(fā)時(shí)間后從起點(diǎn)出發(fā)，在pickup點(diǎn)攬收貨物送回配送中心，在配送中心裝載貨物配送至delivery點(diǎn)，最終在最晚返回時(shí)間前返回終點(diǎn)。車輛執(zhí)行任務(wù)的過程中允許多次訪問配送中心。

圖1 車輛執(zhí)行任務(wù)示意圖

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

2.1 虛擬化處理

由于車輛可能多次訪問配送中心，如果模型中以一個(gè)變量去區(qū)分車輛第幾次訪問配送中心，則建模難度和求解難度都會(huì)顯著增加。為了降低難度，采用了以下處理方式：T={1,2,…,n}表示客戶點(diǎn)集合，n為實(shí)際客戶點(diǎn)的數(shù)量，對(duì)于編號(hào)為i的pickup 點(diǎn)，構(gòu)建一個(gè)編號(hào)為n+i的虛擬delivery點(diǎn)與之對(duì)應(yīng)；對(duì)于編號(hào)為j的delivery點(diǎn)，則重新編號(hào)為n+j，并構(gòu)建一個(gè)編號(hào)為j的虛擬pickup 點(diǎn)與之對(duì)應(yīng)。經(jīng)過上述處理后，T=TP?TD，TP={1,2,…,n} 表示pickup 點(diǎn)集合，TD={n+1,n+2,…,2n}表示delivery點(diǎn)集合，車輛需要從點(diǎn)i(i∈TP)攬收貨物配送至點(diǎn)n+i。該種處理方式將配送中心替換成了n個(gè)虛擬客戶點(diǎn)，所有虛擬客戶點(diǎn)的位置與配送中心位置相同且無服務(wù)時(shí)間窗限制；每個(gè)虛擬客戶點(diǎn)攬收/配送的貨物量與對(duì)應(yīng)實(shí)際客戶點(diǎn)相等。如圖2 所示，圖1中的配送中心經(jīng)過虛擬化處理后替換成了方框內(nèi)的虛擬客戶點(diǎn)，其中i*=n+i。

圖2 虛擬化示意圖

2.2 模型符號(hào)

經(jīng)過上述處理后，將MVSPDPTW在全有向圖上圖上定義G=(V,A),V={S?N?T?0}表示頂點(diǎn)集，A={(i,j):i,j∈V,i≠j}表示弧集。

S：車輛的起點(diǎn)集合，S={s1,s2,…,sm}；

N：車輛的終點(diǎn)集合，N={n1,n2,…,nm}；

T：客戶點(diǎn)集合，T={1,2,…,2n}；

dij：點(diǎn)i和點(diǎn)j之間的距離，i,j∈V；

tij：點(diǎn)i和點(diǎn)j之間的時(shí)間，i,j∈V；

bik：車輛k到達(dá)點(diǎn)i的時(shí)間，k∈K,i∈T?0；

aik：車輛k在點(diǎn)i的開始服務(wù)時(shí)間，k∈K,i∈T?0；

rik：車輛k在點(diǎn)i的服務(wù)時(shí)長(zhǎng)，k∈K,i∈T?0；

qik：車輛k在點(diǎn)i的裝載/卸載的貨物量，k∈K,i∈T?0；

wik：車輛k經(jīng)過點(diǎn)i后承載貨物容量，k∈K,i∈T?0；

xijk：表示車輛k是否直接從點(diǎn)i到點(diǎn)j，如果是則為1，否則為0；

M：表示非常大的整數(shù)。

2.3 線性模型

其中，公式（1）為目標(biāo)函數(shù)，使得執(zhí)行任務(wù)車輛行駛路徑總長(zhǎng)度最?。还剑?）、（3）表示車輛從起點(diǎn)出執(zhí)行任務(wù)并最終返回終點(diǎn)；公式（4）、（5）表示每個(gè)客戶點(diǎn)可以被多個(gè)車輛訪問，但只允許被同一車輛至多訪問一次；公式（6）、（7）、（8）表示車輛需要從pickup點(diǎn)攬收貨物配送至對(duì)應(yīng)的delivery點(diǎn)；公式（9）表示車輛從起點(diǎn)出發(fā)以及返回終點(diǎn)的承載貨物容量均為0；公式（10）表示容量約束；公式（11）、（12）表示車輛在客戶點(diǎn)承載貨物容量變化；公式（13）表示每個(gè)客戶點(diǎn)的分割貨物量之和等于該客戶點(diǎn)的總貨物量；公式（14）、（15）表示車輛需要在最早出發(fā)時(shí)間后從起點(diǎn)出發(fā)為客戶提供服務(wù)，并在最晚返回時(shí)間前返回終點(diǎn)；公式（16）、（17）表示車輛到達(dá)客戶點(diǎn)時(shí)間和在客戶點(diǎn)開始服務(wù)時(shí)間之間的關(guān)系；公式（18）表示車輛只能在客戶時(shí)間窗內(nèi)提供服務(wù)。

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

為了解決MVSPDPTW，提出了一種禁忌模擬退火算法，設(shè)計(jì)了兩種新的鄰域搜索算子，分別用于修復(fù)違反車輛容量約束以及換車操作。在算法內(nèi)加入禁忌機(jī)制以及違反約束懲罰機(jī)制，實(shí)現(xiàn)了搜索空間的有效裁剪，提高了算法的全局尋優(yōu)能力。首先利用動(dòng)態(tài)貪婪算法生成初始可行解，并將初始可行解作為禁忌模擬退火算法的輸入，最終輸出全局最好解。

3.1 初始解生成

模擬退火算法本質(zhì)上是一種迭代求解算法，初始解決定了迭代的起點(diǎn)，因此一個(gè)好的初始解有助于算法找到較好的最終解，本文參考文獻(xiàn)[5]中初始解的生成方法設(shè)計(jì)了一種簡(jiǎn)單有效的動(dòng)態(tài)貪婪算法生成初始解。

公式（20）、（21）分別表示車輛以及客戶點(diǎn)的選擇準(zhǔn)則，車輛的選擇以服務(wù)時(shí)間最大化為原則。客戶點(diǎn)的選擇以當(dāng)前規(guī)劃路徑中最后的訪問對(duì)象i和待選擇客戶點(diǎn)j之間總的旅行時(shí)間和等待時(shí)間最小化為原則。利用公式（21）為當(dāng)前車輛依次選擇服務(wù)的客戶點(diǎn)，檢驗(yàn)所選客戶點(diǎn)是否滿足插入約束，包括時(shí)間窗約束、容量約束、客戶點(diǎn)訪問次數(shù)約束以及需求約束，其中需求約束是指所有配送的貨物來源于配送中心，所有攬收的貨物送回配送中心。如果滿足約束則將客戶點(diǎn)插入到當(dāng)前車輛規(guī)劃路徑中，重復(fù)這個(gè)過程直到所有的客戶需求被滿足。動(dòng)態(tài)貪婪算法的具體流程如下：

輸入：車輛集合K、客戶點(diǎn)集合T、配送中心0。

輸出：初始可行解Sinitial。

步驟1 如果集合T不為空集，轉(zhuǎn)步驟2，否則，算法結(jié)束輸出結(jié)果。

步驟2 利用公式（20）從K中選出當(dāng)前車輛k。

步驟3 構(gòu)造待選擇客戶點(diǎn)集合C=T。

步驟4 如果C不為空集，轉(zhuǎn)步驟5，否則，轉(zhuǎn)步驟9。

步驟5 利用公式（21）從C中選出客戶j。

步驟6 檢驗(yàn)j是否滿足插入約束，如果滿足則將j插入到當(dāng)前車輛規(guī)劃路徑Rk中。

步驟7 檢驗(yàn)j的需求是否全部被滿足，如果滿足則從T中刪除j。

步驟8 將j從C中刪除，轉(zhuǎn)步驟4。

步驟9 檢驗(yàn)Rk最后一個(gè)訪問對(duì)象是否為配送中心0，如果是，轉(zhuǎn)步驟11，否則，轉(zhuǎn)步驟10。

步驟10 檢驗(yàn)0是否滿足時(shí)間窗約束，如果滿足將0插入到Rk中，轉(zhuǎn)步驟3，否則，轉(zhuǎn)步驟11。

步驟11 從K中刪除k，轉(zhuǎn)步驟1。

3.2 違反約束懲罰機(jī)制

在迭代過程中接受不可行解有助于增大鄰域搜索范圍以及提高算法跳出局部最優(yōu)的能力，幫助算法在迭代步驟[13]更好的可行解，因此本文設(shè)計(jì)了一種違反約束懲罰機(jī)制。整體約束懲罰函數(shù)設(shè)計(jì)如公式（22），B表示路徑規(guī)劃解的適應(yīng)度值，β表示參數(shù)懲罰權(quán)重，η(i,k)、φ(i,k)、λ(i,k)分別表示Rk中點(diǎn)i容量約束評(píng)價(jià)值、時(shí)間窗約束評(píng)價(jià)值以及需求約束評(píng)價(jià)值，它們的計(jì)算方式由公式（23）、（24）、（25）給出。Rk={ok,…,nk}表示車輛k的執(zhí)行任務(wù)路徑，它按照車輛的訪問順序排列而成。

3.3 禁忌機(jī)制

禁忌搜索是一種模擬人類思維過程的元啟發(fā)式算法，它的基本思想是避免對(duì)已搜索過的空間進(jìn)行重復(fù)搜索，迫使算法去探索其他新的解決方案。

將每次迭代的當(dāng)前解[14]作為禁忌對(duì)象存儲(chǔ)在禁忌表中，在以后的l（禁忌表的長(zhǎng)度）次迭代中，該對(duì)象被設(shè)置成禁忌狀態(tài)，這與在禁忌結(jié)構(gòu)中常用的邊移動(dòng)禁忌[15-16]不同。禁忌表的長(zhǎng)度指禁忌表儲(chǔ)存對(duì)象的個(gè)數(shù)，當(dāng)儲(chǔ)存對(duì)象個(gè)數(shù)達(dá)到上限，再有對(duì)象加入時(shí)，則采用先進(jìn)先出的原則將前面的對(duì)象從禁忌表中移除，再進(jìn)行加入。

3.4 多鄰域結(jié)構(gòu)

多鄰域結(jié)構(gòu)可以增加解的多樣性，提高算法找到全局最好解的可能性。本文采用了五種鄰域搜索算子，其中遷移算子、遷移分割算子、交換算子來源于經(jīng)典鄰域搜索算子[17]的引用，修復(fù)算子和換車算子針對(duì)本文在迭代過程中接受不可行解以及多車型的特點(diǎn)而設(shè)計(jì)，分別用于修復(fù)違反容量約束和換車操作。

為了更好地解釋算子操作，定義了以下符號(hào)，Rk(k∈K)和Rh(h∈K)分別表示車輛k和車輛h的執(zhí)行任務(wù)路徑，對(duì)于客戶點(diǎn)分別表示在算子操作前后車輛k在客戶i裝載/卸載的貨物量。公式（26）給出了B(Rk)的計(jì)算方式，B(Rk)表示路徑Rk的適應(yīng)度值。

任務(wù)集：在已規(guī)劃好的車輛路徑中，以車輛的起點(diǎn)、終點(diǎn)以及配送中心等非客戶點(diǎn)為界，兩個(gè)相鄰的非客戶點(diǎn)之間連續(xù)的客戶點(diǎn)組成一個(gè)任務(wù)集。如果兩個(gè)相鄰的非客戶點(diǎn)之間不包含客戶點(diǎn)，則不構(gòu)成任務(wù)集。如圖3所示，客戶點(diǎn)1和2組成一個(gè)任務(wù)集，終點(diǎn)與配送中心之間不含客戶點(diǎn)則不構(gòu)成任務(wù)集。

圖3 任務(wù)集示意圖

遷移算子：遷移算子用于將客戶點(diǎn)從原路徑中刪除插入到其他路徑中，如圖4所示，對(duì)于客戶點(diǎn)i∈Rk，將i從Rk中刪除，以B(Rh)最小化為原則將i插入到Rh中。

圖4 遷移算子操作示意圖

遷移分割算子：如圖5所示，客戶i由車輛k和h共同服務(wù)，客戶j由車輛h服務(wù)，i和j屬于路徑Rh中同一個(gè)任務(wù)集。將i從路徑Rk中刪除，然后以B(Rk)最小化原則將j插入到Rk中，此時(shí)i由車輛h服務(wù)，j由車輛k和h共同服務(wù)，k和h在i和j裝載/卸載的貨物量調(diào)整為。

圖5 遷移分割算子操作示意圖

交換算子：交換算子用于交換兩條路徑中的客戶點(diǎn)，如圖6 所示，客戶點(diǎn)i∈Rk，客戶點(diǎn)j∈Rh，將i和j進(jìn)行交換，交換后，i∈Rh,j∈Rk。

圖6 交換算子操作示意圖

修復(fù)算子：修復(fù)算子用于修復(fù)違反車輛容量約束，如圖7 所示，假定車輛k在服務(wù)客戶i時(shí)承載貨物容量超過了車輛的最大容量Qk，此時(shí)在i所屬任務(wù)集中任選一個(gè)客戶點(diǎn)j,j可以為i，任選一條非空路徑Rh，將j以B(Rh)最小化原則插入到Rh中，k和h在j裝載/卸載的貨物量調(diào)整為：的計(jì)算方式由公式（23）給出。

圖7 修復(fù)算子操作示意圖

換車算子：對(duì)于非空路徑Rk以及空路徑Rh，將Rk中的所有客戶點(diǎn)構(gòu)成客戶點(diǎn)集合C，然后按照初始解中路徑的生成方式，將C中的客戶點(diǎn)插入到Rh中。如果C中所有的客戶點(diǎn)都成功插入到Rh中，那么路徑Rk清空，否則的話將插入到Rh的客戶點(diǎn)從Rk中刪除。

圖8 換車算子操作示意圖

由于單個(gè)客戶點(diǎn)只允許被同一車輛至多訪問一次，所以在算子操作后，如果出現(xiàn)如圖9所示情況，Rk中含有兩個(gè)客戶點(diǎn)i，則以B(Rk)最小化原則選擇一個(gè)i從Rk中刪除，將k兩次服務(wù)i裝載/卸載的貨物量合并。

圖9 合并客戶點(diǎn)示意圖

3.5 禁忌模擬退火算法描述

首先利用動(dòng)態(tài)貪婪算法生成初始可行解，并將其設(shè)置為第0代的當(dāng)前解Snow和全局最好解Sbest，然后開始迭代，在每次迭代中，利用設(shè)計(jì)的準(zhǔn)則更新Snow和Sbest。最后當(dāng)當(dāng)前溫度小于設(shè)置的最低溫度時(shí)，算法終止輸出Sbest，具體算法流程如下：

輸入：初始溫度T0、終止溫度Tend、冷卻速率RT、迭代步長(zhǎng)L、鄰域解數(shù)量Nu、初始可行解Sinitial。

輸出：全局最好解Sbest。

步驟1 將Sinitial設(shè)置為Snow以及Sbest。

步驟2 初始化當(dāng)前溫度T'=T0，初始化當(dāng)前溫度下迭代次數(shù)L'=0。

步驟3 初始化禁忌表，將Snow加入到禁忌表中。

步驟4 如果T'>Tend，轉(zhuǎn)步驟5，否則，算法結(jié)束輸出結(jié)果。

步驟5 如果L'

步驟6 從五個(gè)鄰域算子中隨機(jī)選擇一個(gè)鄰域算子轉(zhuǎn)換當(dāng)前解生成鄰域解。

步驟7 重復(fù)步驟6直到鄰域解的數(shù)量達(dá)到Nu。

步驟8 從Nu個(gè)鄰域解中選出最優(yōu)的沒有被禁忌的鄰域解Scan。

步驟9 如果Scan

步驟10 如果>Random(0,1),Scan將成為新的Snow,Random(0,1)用于生成（0，1）上均勻分布的隨機(jī)數(shù)據(jù)，否則保留Snow。

步驟11 如果Scan為可行解并且滿足Scan

步驟12 如果Snow發(fā)生變化，則將Snow加入禁忌表。

步驟13 轉(zhuǎn)步驟5。

4 仿真算例

本文利用文獻(xiàn)[18]使用的考慮時(shí)間窗約束的VRP（Vehicle Routing Problem with Time Windows，VRPTW）數(shù)據(jù)集、文獻(xiàn)[19]使用的考慮時(shí)間窗約束的VPRSD（Split Delivery Vehicle Routing Problem with Time Windows，SDVRPTW）數(shù)據(jù)集以及構(gòu)造的MVSPDPTW 仿真數(shù)據(jù)集對(duì)TSA 算法進(jìn)行了測(cè)試并對(duì)實(shí)驗(yàn)結(jié)果進(jìn)行對(duì)比分析，每個(gè)算例都運(yùn)行20 次。所有實(shí)驗(yàn)均在i5-8500 CPU 3.0 GHz、內(nèi)存16 GB 的臺(tái)式計(jì)算機(jī)上、myeclipse2017的環(huán)境下進(jìn)行。

4.1 參數(shù)設(shè)置方法

通過設(shè)置合理的參數(shù)可以有效提高算法的性能[20]，首先參考文獻(xiàn)[21-22]中的參數(shù)設(shè)置確定本文各個(gè)參數(shù)的測(cè)試區(qū)間，然后選取不同規(guī)模算例，通過更改參數(shù)組合進(jìn)行多組測(cè)試，最后確定參數(shù)的最佳組合。

各參數(shù)取值范圍以及步長(zhǎng)具體參考表1，為簡(jiǎn)化計(jì)算復(fù)雜度，本文采用控制變量法依次確定各參數(shù)的最佳值。TSA 參數(shù)設(shè)置的最終結(jié)果如下所示：初始溫度T0=100、終止溫度Tend=0.1、迭代長(zhǎng)度L=30、降溫速率RT=0.93、懲罰權(quán)重β=4、鄰域解數(shù)量Nu=2n+150（n為客戶數(shù)量）、禁忌表的長(zhǎng)度l=8。

表1 算法參數(shù)組合

4.2 基于VRPTW、SDVRPTW數(shù)據(jù)集的數(shù)值實(shí)驗(yàn)

由于目前在MVSPDPTW 領(lǐng)域沒有公認(rèn)的數(shù)據(jù)集可供使用，導(dǎo)致沒有辦法對(duì)本文算法直接進(jìn)行測(cè)試，MVSPDPTW 是經(jīng)典VRPTW 以及SDVRPTW 的拓展，問題中很多約束條件相似，因此如果本文算法可以很好地解決VRPTW 以及SDVRPTW，那么有理由相信本文算法也可以有效地求解MVSPDPTW。

4.2.1 基于VRPTW數(shù)據(jù)集的數(shù)值實(shí)驗(yàn)

從文獻(xiàn)[18]使用的VRPTW數(shù)據(jù)集中有針對(duì)性地選擇了27 個(gè)VRPTW 算例進(jìn)行測(cè)試，VRPTW 算例中車輛容量皆為200。表2記錄了TSA算法求解每一個(gè)算例結(jié)果Rbest和算例已知最好解Kbest對(duì)比，Gap表示Rbest與Kbest之間差距，Gap=(Rbest-Kbest)/Kbest。Kbest數(shù)據(jù)來源于http：//web.cba.neu.edu/～msolomon/problems.htm。

表2 TSA算法求解結(jié)果與已知最好解對(duì)比

根據(jù)表2中數(shù)據(jù)可知，TSA算法更新了4個(gè)VRPTW算例（算例編號(hào)C101，客戶數(shù)量25；算例編號(hào)C102，客戶數(shù)量50；算例編號(hào)C107，客戶數(shù)量50；算例編號(hào)C109，客戶數(shù)量50）的已知最好解。在剩余23個(gè)VRPTW算例中，TSA 算法的求解結(jié)果雖然劣于已知最好解，但是它們之間的差距均保持在1%之內(nèi)。實(shí)驗(yàn)結(jié)果說明了TSA算法求解VRPTW效果好。

4.2.2 基于SDVRPTW數(shù)據(jù)集的數(shù)值實(shí)驗(yàn)

從文獻(xiàn)[19]使用的SDVRPTW 數(shù)據(jù)集中有針對(duì)性地選擇了12 個(gè)SDVRPTW 算例進(jìn)行測(cè)試，SDVRPTW算例中車輛容量皆為100。表3記錄了TSA算法和分支與價(jià)格和削減[19（]Branch and Price and Cut algorithm，BPC）算法求解12 個(gè)SDVRPTW 算例結(jié)果對(duì)比。Gap表示TSA 算法求解每一個(gè)算例結(jié)果(Rbest)和BPC 算法求解每一個(gè)算例結(jié)果(Cbest)之間的差距，Gap=(Rbest-Cbest)/Cbest。

從表3中數(shù)據(jù)可知，TSA算法在客戶數(shù)量為25的小規(guī)模算例下的求解結(jié)果與BPC算法相同。隨著客戶數(shù)量的增大，雖然TSA算法的求解結(jié)果劣于BPC算法，但是它們之間的差距均保持1%以內(nèi)。在求解時(shí)間方面，在小規(guī)模算例下，BPC算法求解時(shí)間小于TSA算法，但是隨著客戶數(shù)量的增大，BPC算法求解時(shí)間遠(yuǎn)超TSA算法，并且在相同客戶數(shù)量下不同算例的求解時(shí)間上，TSA 算法基本保持不變而BPC 算法則差異明顯。實(shí)驗(yàn)結(jié)果充分說明了TSA 算法求解SDVRPTW 效果接近BPC算法。

表3 TSA算法與BPC算法求解結(jié)果對(duì)比

4.3 基于仿真數(shù)據(jù)集的數(shù)值實(shí)驗(yàn)

基于4.2.2 節(jié)的12 個(gè)SDVRPTW 算例構(gòu)建12 個(gè)MVSPSPTW 仿真算例，不改變SDVRPTW 算例中配送中心位置、客戶位置、客戶貨物量以及客戶時(shí)間窗，僅隨機(jī)選擇半數(shù)客戶將其配送任務(wù)改為攬收任務(wù)，對(duì)于車輛的起點(diǎn)和終點(diǎn)不再設(shè)置為配送中心，而是在客戶所屬100×100的正方形區(qū)域內(nèi)隨機(jī)生成；車輛的開始服務(wù)時(shí)間為0～800間隨機(jī)生成的整數(shù)，結(jié)束服務(wù)時(shí)間等于500～900間隨機(jī)生成的整數(shù)加上車輛的開始服務(wù)時(shí)間；車輛最大容量為70～120 間隨機(jī)生成的整數(shù)。此外，當(dāng)客戶數(shù)量為25時(shí)隨機(jī)生成15輛車，當(dāng)客戶數(shù)量為50時(shí)隨機(jī)生成30輛車，保證車輛資源充足。

表4 記錄了TSA 算法、傳統(tǒng)模擬退火（Simulated Annealing，SA）算法、粒子群算法（Particles Swarm Optimization，PSO）求解MVSPDPTW 仿真算例結(jié)果對(duì)比，PSO算法的設(shè)計(jì)參考了文獻(xiàn)[23-24]中的處理方式，傳統(tǒng)SA 算法與PSO 算法的參數(shù)通過4.1 節(jié)參數(shù)設(shè)置方法來確定。Gap1、Gap2 分別表示TSA算法求解每一個(gè)算例結(jié)果(Rbest)與SA算法求解每一個(gè)算例結(jié)果(Tbest)、PSO算法求解每一個(gè)算例結(jié)果(Pbest)之間的差距，Gap1=(Tbest-Rbest)/Rbest，Gap2=(Pbest-Rbest)/Rbest。

根據(jù)表4中數(shù)據(jù)可知，本文所提出的TSA算法對(duì)比傳統(tǒng)SA 算法和PSO 算法求解性能更優(yōu)。主要體現(xiàn)在：（1）TSA算法的求解結(jié)果最優(yōu)，相比傳統(tǒng)SA算法最高提升了2.40%，平均提升了1.14%；相比于PSO算法最高提升了5.19%，平均提升了3.52%。（2）在求解時(shí)間方面，SA 算法最長(zhǎng)，TSA 算法次之，PSO 算法最短，但TSA 算法與PSO算法耗時(shí)總體差距不大。此外，TSA算法求解相同客戶數(shù)量算例的時(shí)間基本保持不變，具有較好的穩(wěn)定性。TSA 算法求解性能更優(yōu)的原因主要在于：（1）由于本文多車型的特點(diǎn)，因此選車結(jié)果會(huì)對(duì)最終解的優(yōu)劣產(chǎn)生至關(guān)重要的影響，換車算子有利于尋找到最合適的車輛執(zhí)行任務(wù)。除此之外多種算子配合的方式有利于擴(kuò)大鄰域搜索范圍，提高算法的全局尋優(yōu)能力。（2）TSA算法內(nèi)加入了禁忌機(jī)制以及違反約束懲罰機(jī)制，實(shí)現(xiàn)了搜索空間的有效裁剪，避免算法陷入局部最優(yōu)的同時(shí)節(jié)約了求解時(shí)間，相比之下傳統(tǒng)SA 算法和PSO 算法易陷入局部最優(yōu)。

表4 TSA、SA、PSO算法求解結(jié)果對(duì)比

5 總結(jié)展望

本文研究了基于新型攬收配送模式下的一種帶時(shí)間窗的多車型需求可拆分?jǐn)埵张渌蛦栴}。針對(duì)這個(gè)問題建立一個(gè)混合整數(shù)線性規(guī)劃模型。在構(gòu)造模型的過程中，通過為每個(gè)客戶點(diǎn)構(gòu)建一個(gè)對(duì)應(yīng)虛擬攬收/配送點(diǎn)的方式減少模型中部分變量的增加，并使用大M法對(duì)非線性約束做了線性化處理。設(shè)計(jì)了一種高效TSA 算法，TSA 算法在傳統(tǒng)SA 算法框架內(nèi)加入了禁忌機(jī)制以及違反約束懲罰機(jī)制，實(shí)現(xiàn)了搜索空間的有效裁剪，提高了算法的全局尋優(yōu)能力。TSA 算法更新了27 個(gè)VRPTW算例中4個(gè)算例的已知最好解；12個(gè)SDVRPTW算例的求解結(jié)果中，TSA算法與BPC算法的差距均不超過1%，且求解時(shí)間更短；就12個(gè)MVSPDPTW仿真算例而言，TSA 求解結(jié)果均不差于傳統(tǒng)SA 算法以及PSO 算法，且分別最高提升了2.40%和5.19%。實(shí)驗(yàn)結(jié)果充分證明了本文所提出的TSA 算法求解MVSPDPTW 的可行性和有效性。

本文所研究的內(nèi)容依舊有許多亟待解決的問題，將來的研究工作可以從以下兩個(gè)方面展開：（1）考慮需求依訂單拆分而不是任意連續(xù)拆分；（2）考慮使用外部車輛和自有車輛共同配送方式。