張得志，何亦揚，龔浩翔

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

1 問題分析與建模

1.1 問題描述

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

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

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

1.2 模型假設(shè)

基本假設(shè)：

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

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

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

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

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

6) 所有客戶點的需求di必須得到滿足，但可以由1輛或者2輛車來滿足；

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

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

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

符號表示：

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

V1：未被拆分點的集合；V2：被拆分點的集合；

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

Sij：車輛從客戶i到客戶j的距離；

Cm：車輛m的容量；rm：車輛m的路徑；

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

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

xijm，問題的決策變量；

R：問題的解，是 xijm的向量；wm：車輛所在線路對應(yīng)的路徑長度；

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

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

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

約束：

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

1.4 期望回歸費用的計算

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

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

Ⅰ類服務(wù)失敗回歸費用的計算：02mIiim s s= ；

Ⅱ類服務(wù)失敗回歸費用的計算：

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

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

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

邊界條件如下：

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

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

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

那么對路徑rm，其期望回歸費用如下：

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

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

1.5 雙目標(biāo)處理

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

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

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

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

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

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

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

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

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

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

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

2 求解算法分析

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

算法求解過程如下。

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

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

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

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

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

算法描述如下。

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

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

2) 刪除算子

①均衡度最差刪除

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

②隨機刪除

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

③行駛費用最差刪除

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

④回歸費用最差刪除

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

3) 插入算子

①均衡度最好插入

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

②拆分插入

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

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

③貪婪插入

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

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

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

4) 算子的評分及選擇

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

其中：γij在第j個迭代開始時，取值為0。

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

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

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

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

①若啟發(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次迭代過程中沒有提高，或整個算法總迭代次數(shù)超過1 000次后，算法終止。

3 算例分析

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

算例中車輛的容量取 C=70。當(dāng)客戶的需求量占比車輛的容量較小時，進行訂單拆分對車輛的配送費用降低，效果并不明顯，參考Ho等的研究[16]，本文將算例中各個客戶需求量均轉(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è)計的算法對R，RC，C1和C2 4類算例進行仿真實驗。對各類案例在取不同權(quán)重時，運算 7次，去除運算結(jié)果中的極大極小值，取平均值。結(jié)果如圖2～3所示。

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

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

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

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

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

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

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

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

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

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

圖5 迭代過程中路徑費用變化Fig. 5 Path cost changes during iteration

4 結(jié)論

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

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

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

參考文獻：

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

[2] 魏珂悅. 隨機需求下集送一體化節(jié)能配送線路問題研究[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), 蔡延光. 基于蜂群算法的隨機需求車輛路徑優(yōu)化問題研究[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)模型的超市配送車輛路徑選擇研究[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] 劉旺盛，楊帆，李茂青，等. 需求可拆分車輛路徑問題的聚類求解算法[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] 熊浩, 鄢慧麗. 需求可拆分車輛路徑問題的三階段禁忌算法[J]. 系統(tǒng)工程理論與實踐, 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.