張得志，何亦揚(yáng)，龔浩翔

車(chē)輛路徑問(wèn)題(Vehicle Routing Problem, VRP)[1]自1959首次提出后，一直廣受關(guān)注。傳統(tǒng)VRP研究，一般假設(shè)每個(gè)客戶點(diǎn)的需求確定且小于車(chē)輛裝載量，每個(gè)客戶只能由一輛車(chē)進(jìn)行服務(wù)，客戶訂單不可拆分。但是，這樣的配送策略往往造成一條路徑上只能服務(wù)少量客戶，進(jìn)而占用多臺(tái)車(chē)輛，造成浪費(fèi)。現(xiàn)實(shí)中存在很多不確定因素，受不確定因素的影響，顧客需求往往是隨機(jī)的、不確定的[2]。在客戶需求隨機(jī)情況下，尤其是需求量占比車(chē)輛容量相對(duì)較大時(shí)，如果客戶訂單不能進(jìn)行拆分，服務(wù)路徑上很可能會(huì)發(fā)生一次服務(wù)失敗，甚至有時(shí)會(huì)發(fā)生多次服務(wù)失敗，這無(wú)疑增加了配送成本[3]。此外，傳統(tǒng) VRP研究，一般僅考慮行駛路徑費(fèi)用，以路徑費(fèi)用最小為目標(biāo)，不考慮各個(gè)路徑上車(chē)輛行駛路徑長(zhǎng)度均衡問(wèn)題。但在有些企業(yè)中，司機(jī)收入受行車(chē)距離影響，不能擁有相同的行車(chē)距離，影響司機(jī)收入和福利，這種不公平會(huì)影響司機(jī)的工作熱情和滿意度，降低配送服務(wù)水平、員工忠誠(chéng)度和配送效率[4]，司機(jī)工作量均衡可能成為決策者在進(jìn)行線路規(guī)劃時(shí)一個(gè)重要考量指標(biāo)[5]。所以，本文建立雙目標(biāo)模型，在路徑規(guī)劃時(shí)以路徑均衡和路徑費(fèi)用為目標(biāo)，具有現(xiàn)實(shí)意義。目前，關(guān)于隨機(jī) VPR已經(jīng)有研究報(bào)道。Tillman[6]設(shè)計(jì)一種求解需求隨機(jī) VRP的算法，提出當(dāng)車(chē)輛空駛或超載時(shí)，給予相應(yīng)懲罰值的策略。LIU等[7]提出基于仿真的優(yōu)化方法，并用禁忌搜索算法求解了隨機(jī)需求問(wèn)題。Carlsson[8]設(shè)計(jì)了一種將服務(wù)區(qū)域劃分為子區(qū)域的方法處理隨機(jī)問(wèn)題。對(duì)于需求可拆分的Dror等[9]首次提出需求可拆分VRP，并構(gòu)造可拆分VRP 的k-SDVRP 模型。劉旺盛等[10-11]設(shè)計(jì)求解需求可拆分 VRP 的聚類(lèi)求解算法和三階段禁忌算法。有不少學(xué)者還對(duì)考慮路徑均衡的VRP進(jìn)行研究。Oyola等[4]研究需求確定情況下，考慮路徑均衡的雙目標(biāo) VRP問(wèn)題，并設(shè)計(jì)貪婪隨機(jī)自適應(yīng)搜索算法，獲得了較好解。Carlsson等[12]考慮均衡各個(gè)線路工作量的問(wèn)題，提出一個(gè)基于無(wú)限維優(yōu)化的快速算法。綜上所述，目前已有研究中，同時(shí)考慮需求隨機(jī)、訂單可拆分和各線路均衡等因素，進(jìn)行配送 VRP優(yōu)化的研究成果較少?；诖?，本文以路徑費(fèi)用最小和線路均衡度最好為目標(biāo)，構(gòu)建基于隨機(jī)需求訂單可拆分的多目標(biāo)VRP模型，提出訂單拆分車(chē)輛配對(duì)服務(wù)策略，并設(shè)計(jì)大規(guī)模鄰域自適應(yīng)搜索算法進(jìn)行求解，通過(guò)數(shù)值算例驗(yàn)證所建模型和算法的有效性。

1 問(wèn)題分析與建模

1.1 問(wèn)題描述

本文提出需求隨機(jī)、考慮各線路均衡的需求可拆分服務(wù)車(chē)輛配對(duì)回歸策略，允許服務(wù)發(fā)生失敗一次，且客戶需求可部分先服務(wù)，每個(gè)客戶被指派給1輛車(chē)或者2輛車(chē)進(jìn)行服務(wù)。不同車(chē)輛可進(jìn)行配對(duì)，但每條線路最多只能與其他線路配對(duì)1次。在沒(méi)有進(jìn)行配對(duì)的線路中，所有客戶只能被1輛車(chē)服務(wù)；而在配對(duì)路線中，有些客戶可以被2輛車(chē)進(jìn)行服務(wù)。根據(jù)服務(wù)車(chē)輛數(shù)的不同，將客戶分為2類(lèi)：一般客戶，客戶被1輛車(chē)服務(wù)；需求被拆分的客戶(客戶可以被2輛車(chē)服務(wù))。

在一般客戶點(diǎn)發(fā)生服務(wù)失敗時(shí)，執(zhí)行以下的回歸策略：1)當(dāng)客戶的需求超出車(chē)輛剩余容量時(shí)，車(chē)輛先使用剩余的容量對(duì)客戶進(jìn)行服務(wù)，然后返回倉(cāng)庫(kù)，進(jìn)行裝卸，再返回服務(wù)還未完成的客戶，滿足其剩余的需求；2)當(dāng)車(chē)輛剩余容量正好等于客戶需求時(shí)，車(chē)輛服務(wù)完該客戶后，返回倉(cāng)庫(kù)，裝載后直接駛向下一個(gè)客戶。

在需求可拆分的客戶點(diǎn)發(fā)生服務(wù)失敗時(shí)，被指派給服務(wù)此客戶的2輛車(chē)都只關(guān)注在第1階段預(yù)分配給自己的那部分需求，這樣需求可拆分，就轉(zhuǎn)化成了需求不可拆分的問(wèn)題，執(zhí)行和服務(wù)需求未拆分客戶一樣的回歸策略。

1.2 模型假設(shè)

基本假設(shè)：

1) 各個(gè)客戶的需求 di為分布已知的離散隨機(jī)變量；

2) 各個(gè)客戶的需求量di均不超過(guò)車(chē)輛的容量，P{di≤C} ? 1(i∈ V{0})；

3) 任意2個(gè)客戶點(diǎn)間的行駛距離是固定的，即Sij= Sji；

4) 各個(gè)客戶點(diǎn)之間的距離符合三角不等式，即Sik+ Skj＞ Sij；

5) 所有的車(chē)輛都是從倉(cāng)庫(kù)出發(fā)，完成配送任務(wù)后，必須返回原點(diǎn)；

6) 所有客戶點(diǎn)的需求di必須得到滿足，但可以由1輛或者2輛車(chē)來(lái)滿足；

7) 任何一個(gè)客戶點(diǎn)最多只能被拆分到 2條路徑上，且任意一條路徑最多只有一個(gè)客戶需求被拆分服務(wù)；

8) 每條路線最多發(fā)生失敗回歸倉(cāng)庫(kù)一次，也就是說(shuō)任意路徑rm發(fā)生2次失敗的概率是0，路徑上累積的客戶需求量一直小于車(chē)輛容量的 2倍：，當(dāng)路徑上存在訂單拆分的客戶 ，即路徑為配對(duì)路徑之一時(shí)，式中拆分的客戶點(diǎn)配送量為預(yù)優(yōu)化時(shí)，第1階段分配給該路徑上的需求部分，此時(shí)記作，在這里0 ＜＜ 1 ， 而 與此配對(duì)的路徑上承擔(dān)該客戶點(diǎn)剩余的(1 - a的配送量。

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

符號(hào)表示：

V={0, 1, 2, …, n}：其中0表示倉(cāng)庫(kù)，1, 2…表示需要服務(wù)的客服點(diǎn)； S ?V-{0}：客戶點(diǎn)；

V1：未被拆分點(diǎn)的集合；V2：被拆分點(diǎn)的集合；

M={1, 2, 3, … m}：服務(wù)車(chē)輛集合；k=|M|：車(chē)輛的總數(shù)目；

Sij：車(chē)輛從客戶i到客戶j的距離；

Cm：車(chē)輛m的容量；rm：車(chē)輛m的路徑；

μ：保證每條線路服務(wù)失敗次數(shù)最多為1次(即服務(wù)的需求量累計(jì)不超過(guò)車(chē)輛容量的 2倍)的發(fā)生概率閥值；

yim：車(chē)輛在客戶點(diǎn)的服務(wù)需求量，它的取值可以是客戶點(diǎn)的全部需求量，也可能是的一部分(拆分配送)，還可能是零(未進(jìn)行配送)；

xijm，問(wèn)題的決策變量；

R：?jiǎn)栴}的解，是 xijm的向量；wm：車(chē)輛所在線路對(duì)應(yīng)的路徑長(zhǎng)度；

w：各個(gè)線路的平均數(shù)；σ：各個(gè)司機(jī)工作量標(biāo)準(zhǔn)差；

φ(R)：路徑行駛費(fèi)用；

ψ(m)：車(chē)輛所在路徑發(fā)生服務(wù)失敗，造成的回歸費(fèi)用；

約束：

式(1)和式(2)是問(wèn)題的目標(biāo)函數(shù)。目標(biāo)(1)是配送車(chē)輛的路徑費(fèi)用，包括2部分：路徑的行駛費(fèi)用、路徑服務(wù)失敗發(fā)生的回歸路徑費(fèi)用。式(3)表示每個(gè)客戶點(diǎn)至少有1輛車(chē)，最多有2輛車(chē)為其服務(wù)(配對(duì)情況下)。式(4)保證網(wǎng)絡(luò)流量輸入輸出平衡。約束(5)保證產(chǎn)生的解中，各個(gè)路徑中不存在子回路。式(6)表示保證在概率閾值為μ的情況下，每條車(chē)輛路徑上發(fā)生服務(wù)失敗的次數(shù)最多為1次。式(7)只有當(dāng)車(chē)輛經(jīng)過(guò)客戶點(diǎn)時(shí)才會(huì)為客戶服務(wù)，并且服務(wù)的量小于等于客戶需求量。式(8)保證客戶需求必須得到滿足，并且是完全滿足。式(9)表明決策變量是二進(jìn)制0～1變量。式(10)表示問(wèn)題的解x向量。式(11)表示配送車(chē)輛m所在路徑長(zhǎng)度。式(12)計(jì)算各個(gè)線路的均值。式(13)是各個(gè)線路長(zhǎng)度方差。

1.4 期望回歸費(fèi)用的計(jì)算

本文中，討論的是無(wú)協(xié)作回歸策略下的期望回歸費(fèi)用，定義服務(wù)失敗分2類(lèi)：當(dāng)車(chē)輛剩余的容量小于客戶的需求量時(shí)，為Ⅰ類(lèi)失??；當(dāng)車(chē)輛剩余容量恰好等于客戶頂點(diǎn)的需求量時(shí)，為Ⅱ類(lèi)失敗。由于本文考慮的是采用無(wú)協(xié)作回歸策略，所以對(duì)于需求發(fā)生拆分的頂點(diǎn)上發(fā)生服務(wù)失敗，各個(gè)配對(duì)車(chē)輛只關(guān)注在第 1階段解時(shí)預(yù)先分配給自己的那部分需求。

2種失敗情況，服務(wù)回歸費(fèi)用的計(jì)算：

Ⅰ類(lèi)服務(wù)失敗回歸費(fèi)用的計(jì)算：02mIiim s s= ；

Ⅱ類(lèi)服務(wù)失敗回歸費(fèi)用的計(jì)算：

服務(wù)失敗概率的計(jì)算：

路徑m上，客戶i的需求量， Dim為路徑rm上到客戶i時(shí)累計(jì)需求量。本文只考慮需求為離散隨機(jī)變量情況。記 PD(t) = P{D = t } 為離散隨機(jī)變量 D的概率函數(shù)。求解運(yùn)算時(shí)， Pdim為已知值。

1) 路徑rm上車(chē)輛m 到客戶i時(shí)，累計(jì)的需求量的發(fā)生概率，可以根據(jù)需求隨機(jī)變量，根據(jù)公式計(jì)算得：

邊界條件如下：

其中：為訂單拆分比例，其取值范圍為(0,1)。

2) 在需求為離散型隨機(jī)變量情況下，路徑 rm在客戶點(diǎn)i 發(fā)生服務(wù)失敗的概率miP 如下：

3) 用τim為Ⅰ類(lèi)服務(wù)失敗發(fā)生的概率，?im為Ⅱ類(lèi)服務(wù)失敗發(fā)生概率。由式(1)～(2)可推得：

那么對(duì)路徑rm，其期望回歸費(fèi)用如下：

對(duì)應(yīng)的解R，總的期望回歸總費(fèi)用為：

在本文案例中，假設(shè)需求服從泊松分布，累計(jì)需求可以直接計(jì)算求得。比如，當(dāng)需求服從泊松分布時(shí)，對(duì)路徑 m 上需求未拆分的客戶點(diǎn)，～，對(duì)需求拆分客戶點(diǎn)，當(dāng)需求服從～Poisson(μm) ，i那么～Poissonm) ，

1.5 雙目標(biāo)處理

多目標(biāo)問(wèn)題往往無(wú)法同時(shí)取得最優(yōu)，需要取較為折中的狀態(tài)。為了對(duì)本文的雙目標(biāo)進(jìn)行量化，本文提出一種改進(jìn)的多目標(biāo)處理方式。

本文中路徑費(fèi)用路徑行駛距離和回歸路徑距離之和L來(lái)衡量。各線路均衡度可以用各條路徑的方差σ來(lái)表示。由于兩者不是同一個(gè)物理量，搜索算法啟發(fā)式函數(shù)的選取不能通過(guò)二者的簡(jiǎn)單加減得到。為了得到2個(gè)目標(biāo)側(cè)重程度不同時(shí)的解，對(duì)2個(gè)目標(biāo)進(jìn)行“歸一化”處理。求解時(shí)，對(duì)于迭代過(guò)程的 2個(gè)可行解 R1和 R2，其對(duì)應(yīng)的和分別代表其第 1目標(biāo)取值和分別代表其第2目標(biāo)結(jié)果。

1) 對(duì)第1個(gè)目標(biāo)，當(dāng)時(shí)，認(rèn)為解R2較解R1更優(yōu)。定義g1：

其中： f(11)( R1) ≠ 0 。

當(dāng) g1＜ 0 時(shí)，即( R1) ＞( R2)，解R2較解R1更優(yōu)；

當(dāng) g1＞ 0 時(shí)，有，解R2較解R1更差。

2) 對(duì)第2個(gè)目標(biāo)，當(dāng)( R1) ＞)時(shí)，認(rèn)為解R2較解R1更優(yōu)，且當(dāng)g2=0時(shí)為最優(yōu)。定義g2：

當(dāng)＜ 0 時(shí)，有解R2較解R1更優(yōu)；

當(dāng) g2＞ 0 時(shí)，有，解R2較解R1更差。

如此，將2個(gè)不同量綱的目標(biāo)進(jìn)行了統(tǒng)一，定義啟發(fā)式函數(shù)如下： h = α1? g1+ α2?g2。其中 α1和α2為 2個(gè)目標(biāo)的權(quán)值大小，滿足 0 ≤ α1, α2≤1且α1+α2=1。權(quán)值不同代表對(duì)2個(gè)目標(biāo)重視程度的不同。

在算法迭代過(guò)程中，若 g1＜0, g2＜0，是較優(yōu)解，接受新解；若 g1＞0,g2＞0，是劣解，不接受；若 g1＜0,g2＞0或g1＞0,g2＜0，則根據(jù)其權(quán)重系數(shù)判定是否接受新解。為了豐富解的來(lái)源，本文設(shè)計(jì)的算法以一定的概率接受劣解。

2 求解算法分析

參考Ropke等[13]的研究，設(shè)計(jì)一種大規(guī)模鄰域自適應(yīng)搜索算法。算法通過(guò)不斷對(duì)解路徑中一些頂點(diǎn)進(jìn)行刪除和插入操作，生成一系列新解。新解通過(guò)定義的啟發(fā)式判定是否更優(yōu)，進(jìn)而評(píng)估當(dāng)前選用的刪除算子和插入算子的性能。在每次迭代過(guò)程中，選取刪除和插入客戶個(gè)數(shù)q為0.1n～0.2n區(qū)間的隨機(jī)數(shù)。

算法求解過(guò)程如下。

Step 1：設(shè)置初始參數(shù)，構(gòu)造初始解。將構(gòu)造的初始解設(shè)為當(dāng)前解和當(dāng)前最優(yōu)解；

Step 2：通過(guò)賭盤(pán)原則選擇一個(gè)刪除算子和一個(gè)插入算子，構(gòu)造新解，新解滿足閾值要求；

Step 3：根據(jù)算法的接受準(zhǔn)則判定新解的情況，更新最優(yōu)解和當(dāng)前解。

Step 4：更新各個(gè)算子的評(píng)分和使用的頻率。每隔50代，根據(jù)算子產(chǎn)生新解的情況及評(píng)分準(zhǔn)則，更新算子的評(píng)分和使用頻率。

Step 5：如果滿足算法的終止條件，則輸出當(dāng)前最優(yōu)解和，否則跳回step 2。

算法描述如下。

1) 構(gòu)造初始解

本算法參考 Shaw[14]的研究，采用訂單拆分和路徑配對(duì)方法構(gòu)造初始解。首先將客戶按照期望需求量由小到大排序。選取當(dāng)前需求量最小的客戶插入到解路徑中路徑費(fèi)用最優(yōu)位置?？蛻鬶被插入到路徑 rm上點(diǎn) i的位置后，插入費(fèi)用為：插入過(guò)程中要始終滿足約束(6)要求。若插入后路徑總需求量超過(guò)約束條件，則對(duì)插入客戶需求進(jìn)行拆分。按照0.1倍的需求量逐次遞減嘗試，直到滿足約束。拆分的剩余量歸入剩余未配對(duì)路徑的最佳插入位置，并將需求拆分的兩條路徑進(jìn)行配對(duì)，若不存在則生成新的路徑。

2) 刪除算子

①均衡度最差刪除

該算子主要是針對(duì)第2個(gè)目標(biāo)，其中均衡程度用方差來(lái)衡量。該算子嘗試對(duì)客戶進(jìn)行循環(huán)刪除操作，優(yōu)先刪除影響線路均衡性最大的客戶。每次循環(huán)時(shí)，首先計(jì)算每個(gè)客戶頂點(diǎn)刪除后，各線路方差變化量： Δ σ = σ ( R ) - σ-i(R)選取變化量最大的頂點(diǎn)進(jìn)行刪除，直到刪除的頂點(diǎn)個(gè)數(shù)達(dá)到期望刪除個(gè)數(shù)q。

②隨機(jī)刪除

隨機(jī)刪除算法一次性隨機(jī)刪除路徑中 q個(gè)頂點(diǎn)，該算法能夠起到多樣化搜索空間的作用，使算法跳出某些情況下的局部搜索。

③行駛費(fèi)用最差刪除

僅考慮路徑費(fèi)用中固定的行駛費(fèi)用。對(duì)客戶嘗試進(jìn)行循環(huán)刪除，每次循環(huán)時(shí)，首先計(jì)算每個(gè)頂點(diǎn)刪除后的行駛費(fèi)用變化量，選取變化量最大的點(diǎn)進(jìn)行刪除。直到刪除的頂點(diǎn)數(shù)滿足要求。線路rm上刪除客戶 i后行駛費(fèi)用的變化量為 Δ φ ( i, m ) = φ (rm)-φ-i(rm)。

④回歸費(fèi)用最差刪除

與行駛費(fèi)用最差刪除算法相似。該算子同樣對(duì)客戶頂點(diǎn)進(jìn)行循環(huán)刪除操作。每次循環(huán)時(shí)，首先計(jì)算每個(gè)頂點(diǎn)刪除后的回歸費(fèi)用變化量：Δ E (ψ (R ) ) = E (ψ (R ) ) - E-i(ψ(R))，選取變化量最大的點(diǎn)進(jìn)行刪除，直到刪除的頂點(diǎn)數(shù)達(dá)到q。

3) 插入算子

①均衡度最好插入

均衡度最好插入算法僅考慮線路均衡程度。算法循環(huán)的將每個(gè)刪除頂點(diǎn)依次插入到路徑當(dāng)中，插入過(guò)程中，始終要優(yōu)先滿足式(6)。每次循環(huán)操作，首先計(jì)算所有可能插入點(diǎn)插入后的線路長(zhǎng)度方差變化量： Δ σ = σ ( R ) - σ+i(R)，選取使方差減小達(dá)到最大的位置進(jìn)行插入操作，直到將所有刪除頂點(diǎn)插入到路徑中。

②拆分插入

該算子是將客戶的需求量進(jìn)行拆分，然后分配到2條未配對(duì)的路徑當(dāng)中。首先窮舉所有可能配對(duì)的路徑組合，針對(duì)每種可能的組合，計(jì)算求出該組合插入頂點(diǎn)后的最小增長(zhǎng)費(fèi)用及最小增長(zhǎng)費(fèi)用插入位置。對(duì)所有可能配對(duì)的路徑組合計(jì)算后，選出增長(zhǎng)費(fèi)用最少的2條路徑進(jìn)行插入，插入過(guò)程中始終滿足式(6)。如此循環(huán)，直到將所有的刪除頂點(diǎn)全部插入到路徑當(dāng)中。若不存在能夠進(jìn)行配對(duì)的2條路徑，則將該頂點(diǎn)整個(gè)插入到新的路徑中。在這些配對(duì)的路徑中，一條線路服務(wù)需求被拆分客戶的部分需求，另一條線路服務(wù)該客戶其余的需求。服務(wù)需求的百分比定義為

其中：n1和n2分別為所選未配對(duì)路徑上客戶總數(shù)。

③貪婪插入

貪婪插入算法首先將刪除頂點(diǎn)按照需求量從大到小依次降序排列，然后順序的將所有刪除的頂點(diǎn)依次插入到路徑當(dāng)中，在滿足約束條件(6)的情況下選取路徑費(fèi)用增加最小的位置進(jìn)行插入，重復(fù)進(jìn)行，直到刪除點(diǎn)都被插入到路徑中。

④服務(wù)失敗概率最小插入

該算子每次插入時(shí)對(duì)所有路徑依照服務(wù)失敗概率進(jìn)行排序，選用排序后的第1條路徑進(jìn)行插入操作，插入位置為服務(wù)失敗概率最小路徑中的最小增長(zhǎng)費(fèi)用的位置。

4) 算子的評(píng)分及選擇

總共設(shè)計(jì)4個(gè)刪除和4個(gè)插入算子，每個(gè)算子i權(quán)重用ρi表示，每次進(jìn)行刪除插入操作時(shí)，算子i被選中的概率為，初始條件時(shí)取ρi=1。在運(yùn)算過(guò)程中，每隔 50代，各算子的權(quán)重會(huì)更新 1次。算子i在第j個(gè)50次迭代的權(quán)重為ρij=(1 - κ )ρi(j-1)+ κ γij/ βij，其中 κ 在試驗(yàn)中取 0.1，γij為算子i在第j個(gè)50次的得分，βij為算子i在第j個(gè)50次迭代時(shí)被選中的次數(shù)。

其中：γij在第j個(gè)迭代開(kāi)始時(shí)，取值為0。

5) 解的接受準(zhǔn)則

根據(jù)以上提出的算法執(zhí)行步驟，記第k-1步(k≥1)得到的可行解集為Nk-1，那么可以得第k步的搜索域 Nk*為：

其中：s,t∈{1, 2, 3, 4}，函數(shù) Inss()和 Delt()分別對(duì)應(yīng)4個(gè)插入算法和刪除算法。對(duì)于當(dāng)前解Ri，其鄰域可表達(dá)為：

算法中新解的接受采用 Dueck[15]提出的record-to-record travel(RRT)準(zhǔn)則定義；假設(shè)經(jīng)過(guò) i次迭代后R*為當(dāng)前全局最優(yōu)解，其對(duì)應(yīng)的第1目標(biāo)值為 f(*1)，第2目標(biāo)值為 f(*2)。Ri為當(dāng)前解，對(duì)應(yīng)的第 1，第 2目標(biāo)值為，。那么在 i+1次迭代時(shí)：

①若啟發(fā)式函數(shù)則第 i+1 次產(chǎn)生的解為可接受解，更新當(dāng)前解。

②若啟發(fā)式函數(shù)0，則第i+1次產(chǎn)生的解優(yōu)于當(dāng)前解。

③若啟發(fā)式函數(shù)，則第i+1次產(chǎn)生的解優(yōu)于當(dāng)前最優(yōu)解，更新最優(yōu)解的記錄。

6) 算法的終止條件

采用以下解接受及算法終止標(biāo)準(zhǔn)：當(dāng)解的質(zhì)量在300次迭代過(guò)程中沒(méi)有提高，或整個(gè)算法總迭代次數(shù)超過(guò)1 000次后，算法終止。

3 算例分析

以solomon 標(biāo)準(zhǔn)算例為基礎(chǔ)，因本文中未考慮時(shí)間窗，將案例中客戶的服務(wù)時(shí)間信息和時(shí)間窗去除掉后，solomon 案例變成 4類(lèi)：R，RC，C1和C2。本文只選取 solomon案例中每類(lèi)客戶的前 25個(gè)和前50個(gè)客戶進(jìn)行分析。圖1為25個(gè)點(diǎn)時(shí)客戶的位置分布信息?？蛻舻男枨骴i服從泊松分布，各客戶的期望需求E(di)等于4類(lèi)實(shí)例中的客戶確定的需求量。

算例中車(chē)輛的容量取 C=70。當(dāng)客戶的需求量占比車(chē)輛的容量較小時(shí)，進(jìn)行訂單拆分對(duì)車(chē)輛的配送費(fèi)用降低，效果并不明顯，參考Ho等的研究[16]，本文將算例中各個(gè)客戶需求量均轉(zhuǎn)換到區(qū)間[lC,uC]范圍內(nèi)，在本案例中取 l=0.5，u=0.7。重新定義客戶的需求量

其 中 ：E(d ) = min ｛ E (di),i ∈V ｝ ，E(d ) = max{E(di),i∈V}。

圖1 客戶位置分布圖Fig. 1 Information of customer distribution

用設(shè)計(jì)的算法對(duì)R，RC，C1和C2 4類(lèi)算例進(jìn)行仿真實(shí)驗(yàn)。對(duì)各類(lèi)案例在取不同權(quán)重時(shí)，運(yùn)算 7次，去除運(yùn)算結(jié)果中的極大極小值，取平均值。結(jié)果如圖2～3所示。

由圖2～3可知，隨著第1目標(biāo)權(quán)重的增加，第2目標(biāo)權(quán)重減小，對(duì)各類(lèi)客戶，整體上看，第1目標(biāo)數(shù)值是減小的，第2目標(biāo)是增加的，即第1目標(biāo)路徑費(fèi)用是變好的，第2目標(biāo)均衡度是變差的，兩者大體上呈負(fù)相關(guān)。

由圖2可知，對(duì)R類(lèi)城市分布，隨著路徑費(fèi)用權(quán)重的增加，路徑費(fèi)用在平穩(wěn)減少，雖然路徑均衡方差整體上是增長(zhǎng)的，但是存在異常點(diǎn)。比如對(duì)R類(lèi)，當(dāng)α1取0.4時(shí)，各線路的方差達(dá)到最小，均衡性最好。在α1取0.5，0.6時(shí)雖然路徑費(fèi)用在減小，但是均衡性并沒(méi)有變差。這可能是因?yàn)閷?duì)于R類(lèi)分布，客戶均勻分布在倉(cāng)庫(kù)周?chē)^好的配送路徑方案比較多。各類(lèi)配送方案，路徑費(fèi)用相差并不是很大。而對(duì) RC類(lèi)客戶，當(dāng) α1取值范圍在0.2～0.8之間時(shí)，雖然路徑費(fèi)用在減少，但是，均衡度對(duì)權(quán)重變化并不敏感。

由圖3可知，對(duì)C1類(lèi)客戶分布，在α1<0.8時(shí)，2個(gè)目標(biāo)對(duì)權(quán)重系數(shù)變化均不敏感。當(dāng)α1>0.8，第1目標(biāo)和第2目標(biāo)都出現(xiàn)大幅度變化，呈現(xiàn)負(fù)相關(guān)變化，具體的原因還需要進(jìn)一步的研究。對(duì)C2類(lèi)客戶分布，隨著權(quán)重系數(shù)的變化，第1個(gè)目標(biāo)路徑費(fèi)用大體上在緩慢降低，第2個(gè)目標(biāo)均衡度此時(shí)對(duì)權(quán)重系數(shù)并不敏感，雖然也有變化，但變化很小。

圖2 R和RC類(lèi)客戶分布在各種權(quán)重下的目標(biāo)解Fig. 2 Target solution of R, RC class customers in a variety of weigh

圖3 C1和C2類(lèi)客戶在各權(quán)值下目標(biāo)函數(shù)值Fig. 3 Target solution of C1, C2 class customers in a variety of weigh

圖4 α1取值0和1時(shí)的配送路徑圖(RC)Fig. 4 Distribution path map when α1 values 0 and 1 (RC)

由圖4(a)可知，當(dāng)α1=1，即僅關(guān)注第1個(gè)目標(biāo)，車(chē)輛的配送路徑基本都是在區(qū)域內(nèi)配送，只有1個(gè)車(chē)輛進(jìn)行了跨區(qū)配送，這個(gè)時(shí)候路徑的配送費(fèi)用是最低的，結(jié)合圖2可知，此時(shí)各個(gè)線路的均衡性很差。由圖4(b)可知，當(dāng)α1=0，即僅考慮第2個(gè)目標(biāo)時(shí)，配送車(chē)輛中，有多輛車(chē)進(jìn)行了跨區(qū)服務(wù)，這顯然會(huì)增加配送成本。

本文研究的考慮需求隨機(jī)訂單可拆分的雙目標(biāo)VRP，現(xiàn)有的研究中，目前并不存在和本文研究?jī)?nèi)容完全一樣的參考內(nèi)容，無(wú)法進(jìn)行直接比較。故本文選取α1=1，即只關(guān)注路徑費(fèi)用，轉(zhuǎn)化為單目標(biāo)問(wèn)題進(jìn)行比較。為了方便比較，本文將設(shè)計(jì)的算法中，拆分算子刪除，這樣就成了需求隨機(jī)訂單不可拆分的VRP問(wèn)題。對(duì)比表1中不拆分隨機(jī)VRP和本文設(shè)計(jì)算法的結(jié)果可知，在需求隨機(jī)情況下，進(jìn)行訂單拆分，可以降低配送的路徑費(fèi)用。將本文設(shè)計(jì)算法運(yùn)算結(jié)果與文獻(xiàn)[17]進(jìn)行對(duì)比，可以看出算法在求解單目標(biāo)問(wèn)題時(shí)效果良好，能得出較滿意的解。

圖5是算法在α1=1時(shí)，服務(wù)客服點(diǎn)數(shù)為50個(gè)時(shí)，4類(lèi)客戶類(lèi)型在運(yùn)算次數(shù)為5 000情況下，目標(biāo)函數(shù)收斂情況。

表1 結(jié)果與比較Table 1 Results and comparisons

圖5 迭代過(guò)程中路徑費(fèi)用變化Fig. 5 Path cost changes during iteration

4 結(jié)論

1) 考慮到社會(huì)對(duì)公平性越來(lái)越重視，司機(jī)薪酬和福利受行車(chē)距離限制，提出線路均衡的問(wèn)題；以需求隨機(jī)且可拆分為前提，以路徑成本和線路均衡度為目標(biāo)函數(shù)，建立基于隨機(jī)需求訂單可拆分的雙目標(biāo)車(chē)輛路徑問(wèn)題模型，并設(shè)計(jì)大規(guī)模鄰域自適應(yīng)搜索算法進(jìn)行求解。

2) 用修正的 Solomon算例，驗(yàn)證了本文設(shè)計(jì)的算法在求解 VRP時(shí)的有效性和收斂性。結(jié)果表明:本文設(shè)計(jì)的大規(guī)模鄰域搜索算法在求解本文問(wèn)題時(shí)，能得出較好解，算法收斂性和穩(wěn)定性良好。

3) 仿真結(jié)果對(duì)比發(fā)現(xiàn)，4類(lèi)客戶類(lèi)型，對(duì)路徑費(fèi)用及路徑均衡度權(quán)重的敏感度和敏感區(qū)間都不同。企業(yè)可以根據(jù)自己客戶分布類(lèi)型特點(diǎn)以及企業(yè)自身對(duì)2個(gè)目標(biāo)的權(quán)衡，參考本文仿真實(shí)驗(yàn)的結(jié)果，選取適合企業(yè)自身的權(quán)重。

參考文獻(xiàn)：

[1] Dantzing G B. The truck dispatching problem[J].Management Science, 1959, 1(6): 50-53.

[2] 魏珂悅. 隨機(jī)需求下集送一體化節(jié)能配送線路問(wèn)題研究[J]. 商, 2016, 6(8): 258-258.

WEI Keyue. Study on the problem of integrated energy-saving distribution line under random demand[J].Business, 2016, 6(8): 258-258.

[3] 王連穩(wěn), 蔡延光. 基于蜂群算法的隨機(jī)需求車(chē)輛路徑優(yōu)化問(wèn)題研究[J]. 電子世界, 2013, 2(2): 85-87.

WANG Lianwen, CAI Yanguang. Research on vehicle routing optimization problem with stochastic demands based on artificial bee colony algorithm[J]. Electronics World, 2013, 2(2): 85-87.

[4] Oyola J, L?kketangen A. GRASP-ASP: An algorithm for the CVRP with route balancing[J]. Journal of Heuristics,2014, 20(4): 361-382.

[5] 梅灼情. 基于多目標(biāo)模型的超市配送車(chē)輛路徑選擇研究[D]. 福州: 福建農(nóng)林大學(xué), 2012.

MEI Zhuoqing. Research on routing choice of the supermarket’s distribution vehicle based on the multiple objective model[D]. Fuzhou: Fujian Agriculture and Forestry University,2012

[6] Tillman F A. The multiple terminal delivery problem with probabilistic demands[J]. Transportation Science, 1969,3(3): 192-204.

[7] LIU R, TAO Y, HU Q, et al. Simulation-based optimisation approach for the stochastic two-echelon logistics problem[J]. International Journal of Production Research, 2016, 55(1): 1-15.

[8] Carlsson J G. Dividing a territory among several vehicles[J]. Informs Journal on Computing, 2012, 24(4):565-577.

[9] Dror M, Trudeau P. Savings by split delivery routing[J].Transportation Science, 1989, 23(23): 141-145.

[10] 劉旺盛，楊帆，李茂青，等. 需求可拆分車(chē)輛路徑問(wèn)題的聚類(lèi)求解算法[J]. 控制與決策，2012, 27(4): 535-540.

LIU Wangsheng, YANG Fan, LI Maoqing, et al.Clustering algorithm for split delivery vehicle routing problem[J]. Control and Decision, 2012, 27(4): 535-540.

[11] 熊浩, 鄢慧麗. 需求可拆分車(chē)輛路徑問(wèn)題的三階段禁忌算法[J]. 系統(tǒng)工程理論與實(shí)踐, 2015, 8(5): 1230-1235.

XIONG Hao. YAN Huili. A three-phase tabu search heuristic for the split delivery vehicle routing problem[J].Systems Engineering—Theory & Practice, 2015, 8(5):1230-1235.

[12] Carlsson J G, Carlsson E, Devulapalli R. Balancing workloads of service vehicles over a geographic territory[C]// Ieee/rsj International Conference on Intelligent Robots and Systems. IEEE, 2013: 209-216.

[13] Ropke S, Pisinger D. An adaptive large neighborhood search heuristic for the pickup and delivery problem with time windows[J]. Transportation Science, 2006, 40(4):455-472.

[14] Shaw P. A new local search algorithm providing high quality solutions to vehicle routing problems[J].Transportation Science, 1997, 25(28): 132-138.

[15] Dueck G. New optimization heuristics: The great deluge algorithm and the record-to-record travel[J]. Journal of Computational Physics, 1993, 104(1): 86-92.

[16] Ho S C, Haugland D. A tabu search heuristic for the vehicle routing problem with time windows and split deliveries[J]. Computers & Operations Research, 2004,31(12): 1947-1964.

[17] Lei H, Laporte G, Guo B. The vehicle routing problem with stochastic demands and split deliveries[J].Information Systems & Operational Research, 2012,50(2): 59-71.