王寧，張佳蕊，趙姣

(長安大學(xué)，運輸工程學(xué)院，西安 710064)

0 引言

針對傳統(tǒng)貨運信息不暢、運行效率低下、成本較高等問題，在“互聯(lián)網(wǎng)+物流”的推動下，涌現(xiàn)了以“貨拉拉”“滴滴貨運”為代表的同城貨運“O2O”平臺，以“滿幫”“福佑卡車”為代表的城際貨運“O2O”平臺，由第三方物流企業(yè)發(fā)展而來的貨運平臺，大型生產(chǎn)企業(yè)的自建貨運平臺等眾多類型的貨運平臺。與以時效、服務(wù)質(zhì)量為主的同城單程貨運不同，城際貨運業(yè)務(wù)需要更加科學(xué)有效的車-貨匹配、車輛路徑規(guī)劃模型為支撐，提供多程運輸解決方案。例如，“滿幫”運用大數(shù)據(jù)技術(shù)提高了貨運需求與司機信息的匹配精準(zhǔn)度，提高了運營效率，并從最初的車-貨信息“撮合”，不斷升級為具有多元增值服務(wù)的智能平臺；“福佑卡車”基于大數(shù)據(jù)和人工智能技術(shù)研發(fā)的貨運平臺，包含智能定價、智能分單以及智能服務(wù)三大系統(tǒng)，有效降低了車輛空駛率、異常發(fā)生率，同時，更有效地確保了貨物安全準(zhǔn)時的交付。在此背景下，越來越多的個體司機注冊貨運平臺賬戶，參與線上接單，然而，城際零擔(dān)貨物運輸周期較長、貨物種類較多，途中特別是返程存在車輛空駛率較高、貨物裝卸順序混亂、車-貨匹配不合理等問題，司機和貨主的利益難以保證。

為提高城際多程零擔(dān)貨運平臺的運輸效率，眾多學(xué)者對車輛路徑優(yōu)化和車-貨匹配問題進行研究，于江霞等[1]將客戶分類融入車輛路徑問題中，根據(jù)客戶消費行為將客戶分為多個層級，并按照每層級客戶的特點設(shè)置超時懲罰成本，構(gòu)建基于客戶分類的即時車輛路徑優(yōu)化模型，并設(shè)計了遺傳算法進行求解。賀政綱等[2]結(jié)合車貨匹配度函數(shù)與聯(lián)運匹配度函數(shù)建立多式聯(lián)運流線網(wǎng)絡(luò)的匹配度模型，并結(jié)合算例求解模型，驗證了匹配度模型對多式聯(lián)運方案組織和選擇的有效性。

單獨的車輛路徑優(yōu)化或車-貨匹配優(yōu)化無法同時解決車輛運輸過程中裝卸順序混亂、空駛率高等問題，同時考慮三維裝載問題和車輛路徑問題，即具有三維裝載約束的有容量車輛路徑問題(Threedimensional Loading Capacitated Vehicle Routing Problem,3L-CVRP)更有利于貨運平臺提高車輛空間利用率，避免超限等情況觸發(fā)的安全問題，避免運輸途中的頻繁倒貨，降低物流成本，提高物流效率。BORTFELDT[3]設(shè)計了一種基于禁忌搜索和負(fù)載樹搜索算法的混合算法，求解3L-CVRP 問題；TAO 等[4]將一種改進的浪費啟發(fā)式算法與禁忌搜索相結(jié)合，求解3L-CVRP 問題；王超等[5]考慮配送車輛數(shù)目及路徑總距離兩個目標(biāo)函數(shù)，構(gòu)建了多階段、兩層混合算法架構(gòu)，求解該類問題；CHEN 等[6]考慮具有時間窗約束的訂單可拆分3L-CVRP 問題，并利用禁忌搜索算法求解，結(jié)果表明，分開交付比非分開交付更容易滿足時間窗約束；崔會芬等[7]考慮客戶需求、貨物裝載順序、車輛尺寸、車輛重心等約束，建立了以車輛行駛總距離最短、車輛裝載容積利用率和載重率最大的多目標(biāo)組合優(yōu)化模型，并利用遺傳算法進行了求解。

隨著貨運平臺的逐漸增加和競爭的日益激烈，為搶占市場份額，平臺補貼方式層出不窮，主要分為針對貨主的發(fā)單折扣補貼和針對司機的接單獎勵。同時，平臺為保證利潤，常常將補貼總金額控制在某一范圍，若持續(xù)增長補貼金額，則市場份額增長趨緩，無效補貼增加，平臺利潤下降。因此，合理分配有限的補貼金額，增加平臺利潤至關(guān)重要。但是，現(xiàn)有平臺的補貼方案主要通過實驗統(tǒng)計結(jié)果或基于用戶行為的經(jīng)驗決策，尚未挖掘?qū)е掠脩粜袨椴町惢母居绊懸蛩兀?，貨主是否在該平臺上發(fā)單受到運輸時效、司機服務(wù)質(zhì)量、售后保障等因素的影響，司機是否接單受到訂單價值、運輸距離、是否有返程單等因素的影響。因此，需要根據(jù)貨主期望運輸時效作針對性補貼以吸引更多貨主在平臺發(fā)單，根據(jù)訂單價值、運輸時長作針對性補貼以達成更高的司機訂單應(yīng)答率，即在解決3LCVRP問題時，針對貨運平臺城際零擔(dān)貨運問題的特點，同時考慮司機、貨主補貼成本與車輛訪問路徑、貨物裝載順序及貨物三維裝載位置等決策方案的互相影響，但目前暫無此類研究成果。

綜上，本文分析了貨主運輸時長(多程運輸與單程運輸貨物送達時間之差)補貼、高價值訂單(送達位置偏僻、價值高的訂單)補貼、空載(車輛重量剩余與車廂空間剩余)補貼對運輸總成本的影響，在已知訂單收入的情況下，以平臺補貼成本、車輛總成本(與使用車輛數(shù)量相關(guān)的車輛使用固定成本和與車輛總行駛里程相關(guān)的燃油成本)最小化為優(yōu)化目標(biāo)，建立了同時考慮車-貨匹配和三維裝載約束的車輛路徑優(yōu)化模型。利用CPLEX求解小規(guī)模問題，得到最優(yōu)車-貨匹配、車輛路徑、三維裝載結(jié)果以及平臺補貼方案，驗證模型準(zhǔn)確性。針對該問題，設(shè)計了改進的量子粒子群優(yōu)化算法進行求解。在傳統(tǒng)量子粒子群算法的基礎(chǔ)上引入完全學(xué)習(xí)行為，在計算平均最佳位置時根據(jù)各個粒子適應(yīng)度函數(shù)值設(shè)置學(xué)習(xí)權(quán)重，并通過增加啟發(fā)式策略進一步改進算法。通過貨運平臺的實際數(shù)據(jù)驗證所提算法的有效性，并分析了各類補貼上漲對總成本及平臺利潤的影響。

1 問題描述與數(shù)學(xué)模型

1.1 問題描述

本文研究以貨運平臺為媒介的城際零擔(dān)貨物運輸中的貨物裝載與車輛路徑集成優(yōu)化問題。問題描述如圖1所示。

圖1中，橢圓為1組貨源，包括n個貨主和p個貨物(箱子)；灰色圓圈為貨主運輸貨物的目的地；運送貨物的車輛有m輛，每輛車可以匹配多個貨主，每個貨主有若干個貨物需要運輸。假設(shè)，車輛4與貨主1，6，7，8 匹配，裝卸順序為8→7→6→1→1'→6'→7'→8'(n′為貨主n目的地客戶位置)，訪問貨主1時已裝載貨主8、7、6、1 處的貨物，共裝載11 件貨物，裝載位置及坐標(biāo)如圖1所示。若車輛4 選擇多程運輸，從0:00出發(fā)，到達各個貨主目的地時間為：10:00，12:00，13:30，16:00；若車輛4選擇單程運輸，從0:00出發(fā)，各個貨主貨物到達目的地的時間為：9:00，10:00，9:00，8:30 時，因此，貨主時間補貼為：(1+2+4.5+7.5)×(補貼系數(shù))，單位為元?h-1；高價值訂單補貼為：所有貨物價值×(補貼系數(shù))，單位為元?千元-1；空載補貼為：空載率×(補貼系數(shù))，單位為元?(kg?km)-1或元?(m3?km)-1。同時，車輛1 與貨主2，3，4，5 匹配，裝卸順序為4→3→2→5→5'→2'→3'→4'，從0:00 出發(fā)，多程運輸?shù)竭_時間為：8:00，11:00，13:00，14:30；從0:00 出發(fā)，單程到達時間為：7:00，10:00，11:00，9:00，貨主時間補貼為：(1+1+2+5.5)×(補貼系數(shù))，單位為元?h-1。

圖1 問題描述Fig.1 Problem description

1.2 符號定義

為建立上述問題的線性規(guī)劃模型，使用的符號定義如下。

(1)已知參數(shù)

m——可用車輛數(shù)；

n——待分配貨主數(shù)；

p——貨主貨物總數(shù)；

mk——貨物k質(zhì)量；

F——每單位行駛距離燃油成本；

vs——車輛s速度；

Ss——車輛s行駛總距離；

Ms——車輛s最大裝載質(zhì)量；

Vs——車輛s最大裝載體積；

(Ls,Ws,Hs)——車輛s最大裝載質(zhì)量長、寬、高；

vk——貨物k體積；

(lk,wk,hk)——貨物k長、寬、高；

K1——貨主補貼成本系數(shù)；

Ak——貨物k高價值補貼成本系數(shù)；

K2、K3——空駛補貼成本系數(shù)；

R——使用車輛的固定成本；

Dij——i點到j(luò)點的距離；

Dsi——車輛s的初始位置到i點的距離；

Nk——貨物k所屬于的貨主編號；

Pk——貨物k的價值；

M——極大值。

(2)中間變量

Ugks——貨物g和貨物k放置于車輛s內(nèi)且貨物k是貨物g上面的貨物時為1，否則為0；

Dgks——貨物g和貨物k放置于車輛s內(nèi)且貨物k是貨物g下面的貨物時為1，否則為0；

Lgks——貨物g和貨物k放置于車輛s內(nèi)且貨物k是貨物g左面的貨物時為1，否則為0；

Rgks——貨物g和貨物k放置于車輛s內(nèi)且貨物k是貨物g右面的貨物時為1，否則為0；

Fgks——貨物g和貨物k放置于車輛s內(nèi)且貨物k是貨物g前面的貨物時為1，否則為0；

Bgks——貨物g和貨物k放置于車輛s內(nèi)且貨物k是貨物g后面的貨物時為1，否則為0；

Yhs——車輛s匹配貨主h時為1，否則為0；

Tis——車輛s到點i的時間；

(uk,sk,tk)——貨物k的右前上角的坐標(biāo)。

(3)決策變量

Xks——車輛s裝載貨物k時為1，否則為0；

Zijs——車輛s先訪問點i后訪問點j時為1；否則為0；

(pk,qk,rk)——貨物k的左后下角的坐標(biāo)。

1.3 目標(biāo)函數(shù)

式(1)使平臺總成本最小化?？偝杀局饕? 部分：貨主時長補貼成本、高價值訂單補貼成本、空載補貼成本組成的平臺補貼成本，與運距相關(guān)的燃油成本，以及與車-貨匹配度相關(guān)的車輛使用固定成本。其中，貨主時長補貼成本為貨主參與多程運輸與單程運輸貨物送達時間之差與系數(shù)K1的乘積，K1為常數(shù)，其取值對總成本及成本構(gòu)成具有一定的影響；高價值訂單補貼為針對目的地遠離訂單集聚范圍，且價值較高的訂單進行的補貼，是訂單價值與系數(shù)Ak的乘積，1表示給予司機的貨物k高價值訂單補貼成本系數(shù)，非高價值訂單貨物此系數(shù)取值為0；空載成本為車輛城際運輸途中車輛剩余載重和車廂剩余空間分別與系數(shù)K2和K3的乘積之和，K2為載重量空載補貼成本系數(shù)，K3為容積空載補貼成本系數(shù)，均為常數(shù)，其取值對總成本及成本構(gòu)成具有一定的影響。

1.4 約束條件

車-貨匹配約束條件為

式(2)表示所有貨物只能被匹配一次；式(3)表示車輛s裝載貨物的總質(zhì)量不能超過車輛的最大載重量；式(4)表示車輛s裝載貨物的總體積不能超過車輛的最大容積；式(5)表示如果車輛s匹配貨物k，則其與貨物k所屬貨主i匹配。

車輛路徑約束條件為

式(6)表示車輛不直接訪問貨主目的地；式(7)表示車輛不返回初始地；式(8)表示車輛不從自身到自身；式(9)表示如果車輛s匹配j點，則必定會到達j點；式(10)表示如果車輛s不匹配i點，則必定不會從i點出發(fā)，但如果匹配，可能因為是最后1個而不從i點出發(fā)；式(11)表示只有車輛s同時匹配i點和j點，才能先后訪問i點和j點；式(12)表示如果車輛s先訪問i點再訪問j點，到達j點的時間為到達i點的時間加上運輸途中耗費的時間；式(13)表示先裝的后卸，后裝的先卸；式(14)表示車輛到貨主處的時間早于到其目的地的時間；式(15)表示車輛s到各點的時間大于0。

三維裝載約束條件為

式(16)計算貨物k的右前上角坐標(biāo)；式(17)和式(18)表示相對位置關(guān)系產(chǎn)生的坐標(biāo)變化；式(19)表示貨物的坐標(biāo)范圍(即不能溢出車廂)；式(20)表示大貨物不能壓小貨物；式(21)～式(23)表示只有匹配了同一車輛的兩個貨物才存在相對位置關(guān)系，且兩個貨物之間只存在一種相對關(guān)系，用以約束決策變量Xks與6 個貨物相對位置決策變量之間的關(guān)系；式(24)表示6 個貨物相對位置決策變量之間的關(guān)系。

2 改進的混合量子粒子群算法

采用一般粒子群算法(Particle Swarm Optimization，PSO)求解連續(xù)性問題時，每個粒子包含兩種信息(例如飛行速度和當(dāng)前位置)。它根據(jù)單個和全局最優(yōu)粒子更新其速度和位置。然而，傳統(tǒng)的粒子群優(yōu)化算法需要設(shè)置的參數(shù)較多，難以獲取最優(yōu)參數(shù)。而且，粒子位置的變化缺乏隨機性，容易陷入局部最優(yōu)解。

在量子空間中，粒子的聚集是由粒子運動中心的某個吸引勢所產(chǎn)生的束縛態(tài)來描述的。在一定概率密度的可搜索空間中，量子束縛態(tài)粒子可以出現(xiàn)在任意點，從而在整個可行解空間中搜索具有聚集性質(zhì)的滿意粒子。在一般粒子群算法的基礎(chǔ)上，引入增量勢井場思想的算法，稱為量子粒子群算法(Quantum-behaved Particle Swarm Optimization，QPSO)。該算法增加了粒子位置變化的隨機性，且參數(shù)設(shè)置簡單。

為防止陷入局部最優(yōu)，本文對量子粒子群算法進行兩種改進。在引入完全學(xué)習(xí)行為[8]基礎(chǔ)上，計算平均最佳位置時，根據(jù)各個粒子適應(yīng)度函數(shù)值設(shè)置權(quán)重值，加快收斂速度；在更新粒子位置后，判斷是否更新最優(yōu)解，若未更新最優(yōu)解，則加入基于優(yōu)化解特性的啟發(fā)式策略。算法流程如圖2所示。

圖2 算法流程Fig.2 Overall flow of algorithm

2.1 初始解的生成

本文采用實數(shù)編碼的方法生成粒子。粒子的總長度為p(p代表貨物數(shù)量)，由n(n代表貨主，n′代表貨主的目的地)段組成。

解碼部分，實數(shù)的整數(shù)部分表示貨物的匹配車輛；將匹配同一車輛的貨主中小數(shù)最大的貨物對應(yīng)的值進行排序，由高到低決定車輛訪問貨主順序；同一貨主的不同貨物在同一輛車上的裝載順序由小數(shù)部分的大小決定，小數(shù)部分越大，訪問順序越靠前，之后，根據(jù)裝載順序利用三維裝載啟發(fā)式策略得到貨物裝載位置。

在生成初始解時，為了使粒子群更快地找到優(yōu)化解并保持其全局性，利用貪婪算法生成一部分解。貪婪算法的邏輯是：隨機選取1 個貨主，將其貨物放置于隨機選取出的車輛中，若車輛滿載，則更換車輛；若車輛未滿載，則隨機選取下1 個貨主的貨物置于該車內(nèi)。其余部分解隨機生成。初始化粒子位置如圖3所示，車輛于貨主目的地卸載貨物順序按照“先裝后卸，后裝先卸”原則確定。

圖3 初始化粒子的編碼與解碼Fig.3 Encoding and decoding

2.2 改進的粒子更新策略

更新粒子位置之前，需更新全局最優(yōu)解、粒子的最佳位置以及所有粒子的平均最佳位置。更新平均最佳位置時，考慮各個粒子適應(yīng)度函數(shù)值，綜合考慮各個粒子的位置，避免陷入局部最優(yōu)，具體計算方法為

式中：N為粒子群的規(guī)模；D為粒子的維數(shù)；pe為粒子e的最佳位置；f(pe)為粒子e最佳位置的適應(yīng)度函數(shù)值；pef為粒子e最佳位置的f維度值；xef(T)為T代粒子e的f維度值；uef為均勻分布在(0,1)中的隨機數(shù)；β稱為收縮膨脹系數(shù)，用于控制算法的收斂速度。在迭代過程中，“±”號由生成的隨機數(shù)決定：當(dāng)隨機數(shù)大于0.5時，式(26)取“+”號；其他情況取“-”。

2.3 適應(yīng)度函數(shù)

在訂單數(shù)量、貨物價值已知的情況下，粒子的適應(yīng)度函數(shù)值為平臺運營總成本，由平臺補貼成本和車輛總成本組成。

(1)平臺補貼成本

貨運平臺補貼分為給予貨主的運輸時長補貼和給予司機的高價值訂單及空載補貼，計算式為

利用k-means聚類算法對貨主貨物目的地位置進行聚類，如圖4所示。

目的地分布為圖4(a)中空心點。根據(jù)數(shù)據(jù)特征將聚類中心點設(shè)置為3，隨機生成聚類中心點后，利用啟發(fā)式算法迭代更新聚類中心點位置，迭代的最終結(jié)果為圖4(a)中實心點。計算每個樣本點(貨主貨物目的地位置)到聚類中心點的距離，為圖4(c)。將遠離聚類中心的點視作離群點(高價值訂單貨物)，為圖(b)中實心五角星點8、10、24、29、31、33、35、36、44、47，該部分訂單的Ak值大于0；非離群點為圖(b)中其余空心點，該部分訂單的Ak值為0，即不作高價值補貼。

圖4 訂單貨物位置離群點選取Fig.4 Select cargoes with outliers

(2)車輛總成本

車輛總成本包括與車輛總行駛里程相關(guān)的燃油成本和與使用車輛數(shù)相關(guān)的車輛使用固定成本，設(shè)置車輛燃油成本F為0.64 元?km-1，車輛固定使用成本R為120 元?(輛?次)-1[9]。

2.4 三維裝載策略

計算適應(yīng)度函數(shù)值后，需要設(shè)計三維裝載啟發(fā)式策略，根據(jù)解碼后得到的貨物匹配和裝載順序結(jié)果，計算每個貨物的裝載位置，以滿足模型中各種裝載約束條件[10]，若所有與某車輛匹配的貨物無法全部裝入車廂中，則該解不可行。啟發(fā)式策略的步驟如下。

(1)將第1批貨物放在車廂的左后下角。此時，第一批貨物的左后下角坐標(biāo)(p1,q1,r1)為(0,0,0)，右前上角的坐標(biāo)(u1,s1,t1)為(l1,w1,h1)。首件貨物放置后，車廂剩余空間(左后下角坐標(biāo)、空間長度、空間寬度、空間高度)分為上部空間((0,0,t1),l1,w1,H-t1)、前部空間 ((0,s1,0),l1,w1-s1,H)、右側(cè)空間((u1,0,0),l1-u1,w1,H)，如圖5所示。

圖5 三維裝載示意Fig.5 3D loading diagram

(2)按上部空間、右側(cè)空間及前部空間的順序，檢查第2 批貨物的長度、寬度及高度是否可以放入。

Step 1 如果貨物放置在上方空間，則貨物左后下角的坐標(biāo)(p2,q2,r2)為(0,0,t1)，右前上角的坐標(biāo)(u2,s2,t2)為(l2,w2,t1+h2)。前部空間和右側(cè)空間保持不變，上部空間變?yōu)?(0,0,t2),l2,w2,H-t2)。

Step 2 如果貨物放在右邊，貨物左后下角的坐標(biāo)(p2,q2,r2)為(u1,0,0)，右前上角的坐標(biāo)(u2,s2,t2)為(u1+l2,w2,h2)，上面的空間和前面的空間不變，右邊的空間變?yōu)?(u2,0,0),L-l2,w2,h2)。

Step 3 如果貨物放在前面空間，貨物左后下角的坐標(biāo)(p2,q2,r2)為(0,s1,0)，右前上角的坐標(biāo)(u2,s2,t2)為(l2,s1+w2,h2)，上面空間和右邊空間不變，前面空間變?yōu)?(0,s2,0),l2,W-w2,t2)。

Step 4 與Step 3一樣，放置剩余的貨物。

Step 5 如果貨物不能放在上、右和前3 個空間，則該輛車的貨物裝載順序不滿足約束條件。開始裝載下一輛車。

2.5 啟發(fā)式策略

若當(dāng)前迭代更新后未找到更優(yōu)的粒子位置，則依次按照以下3 個策略進行解的優(yōu)化，若某一策略下獲得了比當(dāng)前最優(yōu)解更優(yōu)的解，則更新當(dāng)前粒子群及最優(yōu)粒子的粒子位置，進入下一次迭代；否則，利用下一種策略進行優(yōu)化，直到所有策略使用完畢。

(1)同一貨主的貨物放在同一輛車上。

(2)同一貨主的貨物作為一個整體轉(zhuǎn)移到另一輛未使用的車上。

(3)將貨物集中在貨物較多的車輛上。

3 實驗結(jié)果與分析

為測試算法性能及選取最優(yōu)補貼方案，設(shè)置4類實驗：通過設(shè)計算法參數(shù)實驗確定最優(yōu)參數(shù)組合，并利用最優(yōu)參數(shù)組合后的算法求解小規(guī)模、大規(guī)模算例；通過設(shè)計CPLEX與算法的對比實驗，驗證基于完全學(xué)習(xí)策略的改進QPSO 算法(Comprehensive Learning Quantum-behaved Particle Swarm Optimization，CLQPSO)求解小規(guī)模問題的有效性；通過設(shè)計改進前、后算法的對比實驗，驗證改進量子粒子群算法的有效性和穩(wěn)定性；通過設(shè)計不同平臺補貼方案實驗選取最優(yōu)補貼方案。

3.1 實驗數(shù)據(jù)

針對某物流科技有限公司的貨運物流平臺2018年1月—2019年6月可用車輛、訂單數(shù)據(jù)進行數(shù)據(jù)清洗、數(shù)據(jù)濾除、數(shù)據(jù)集成及數(shù)據(jù)轉(zhuǎn)換等預(yù)處理操作，獲得車輛平均車速、位置信息、剩余裝載能力、剩余噸位等200個可用車輛數(shù)據(jù)和3000個貨主的50000 條貨物數(shù)據(jù)，包括貨主和客戶的位置信息、待運貨物信息、收貨時間及裝卸時間等。

隨機選取5 輛車、8 個貨主及其對應(yīng)的30 個貨物的相關(guān)數(shù)據(jù)，生成5 組小規(guī)模算例SE1～SE5；隨機選取80輛車、80個貨主及其對應(yīng)的300個貨物的相關(guān)數(shù)據(jù)，生成10組大規(guī)模算例LE1～LE10。

3.2 算法參數(shù)設(shè)置

改進后的混合量子粒子群算法涉及的參數(shù)主要包括：粒子群規(guī)模、迭代次數(shù)以及收縮膨脹系數(shù)(β)。調(diào)整參數(shù)重復(fù)運行SE1 算例，得到表1～表3的實驗結(jié)果。通過分析實驗結(jié)果，將粒子群規(guī)模設(shè)置為100，迭代次數(shù)設(shè)置為1000，β從1 線性遞減到0.5。

表1 粒子群規(guī)模實驗結(jié)果Table 1 Experimental results of particle swarm size

表2 算法迭代次數(shù)實驗結(jié)果Table 2 Algorithm iteration times and experimental results

表3 收縮膨脹系數(shù)實驗結(jié)果Table 3 Experimental results of β

3.3 小規(guī)模算例求解結(jié)果

設(shè)置車輛固定使用成本為120 元·輛-1，補貼成本占總收入的6%～8%，通過將已知訂單貨物位置進行聚類分析，如圖6所示。

圖6 SE1算例訂單貨物位置離群點選取Fig.6 Select SE1 example cargoes with outliers

將貨主4、7的貨物設(shè)置為高價值訂單貨物，將粒子群規(guī)模設(shè)置為100，迭代次數(shù)設(shè)置為1000，β從1 線性遞減到0.5。利用上述CLQPSO 算法求解SE1算例，結(jié)果如表4所示。

表4 SE1算例求解結(jié)果Table 4 SE1 example solution results

平臺總成本為4547.07元。相比于直接將貨物送至貨主目的地，多程訂單延長貨主接收時長共86.16 h，需補貼貨主41.12 元，高價值訂單補貼317.28 元，空載補貼596.37 元，所有車輛共行駛5050.5 km，燃油成本為3232.3元，使用3輛車，車輛固定成本360 元，車輛訪問路徑如圖7所示。貨物裝載結(jié)果如圖8所示。

圖7 SE1車輛訪問路徑Fig.7 SE1 Vehicle access path

圖8 SE1貨物裝載位置Fig.8 SE1 Cargo loading position

3.4 大規(guī)模算例求解結(jié)果

設(shè)置車輛固定使用成本為120 元·輛-1，補貼成本占總收入的6%～8%，通過將已知訂單貨物位置進行聚類分析，將貨主2、6、11、14、25、27、30、32、35、40、41、43、45、63、68、79的貨物設(shè)置為高價值訂單貨物，如圖9所示。

圖9 LE1算例訂單貨物位置離群點選取Fig.9 Select LE1 example cargoes with outliers

將粒子群規(guī)模設(shè)置為100，迭代次數(shù)設(shè)置為1000，β從1 線性遞減到0.5。利用上述CLQPSO算法求解LE1算例，結(jié)果如表5所示。

表5 LE1算例求解結(jié)果Table 5 LE1 example solution results

平臺總成本為6.29 萬元。相比于直接將貨物送至貨主目的地，多程訂單延長貨主接收時長為2124.00 h，需補貼貨主3186 元，高價值訂單補貼2204.6 元，空載補貼1658.88 元，所有車輛共行駛87199.75 km，燃油成本為5.58 萬元，共使用50 輛車，車輛固定成本6000元。

3.5 改進量子粒子群算法與CPLEX的比較

為評價所提出的中間最佳粒子位置選取改進

后的WCLQPSO 算法性能，利用該算法求解得到的算例SE1～SE5 結(jié)果與CPLEX 軟件得到的最優(yōu)結(jié)果進行比較，實驗結(jié)果如表6所示，WCLQPSO算法對應(yīng)每個算例結(jié)果為10 次運行的均值，T為運行時間。

表6表明，WCLQPSO 算法可以獲得小規(guī)模問題的近似最優(yōu)解，且平均值與最優(yōu)解偏差為3.31%。

表6 WCLQPSO與CPLEX的比較Table 6 Comparison between WCLQPSO and CPLEX

3.6 加入啟發(fā)式策略的WCLQPSO算法與其他算法比較結(jié)果

針對大規(guī)模問題，CPLEX 軟件無法獲得優(yōu)化解的情況，采用WCLQPSO算法求解。將粒子群規(guī)模設(shè)置為100，迭代次數(shù)設(shè)置為1000，各類成本值與小規(guī)模算例一致，分別利用傳統(tǒng)QPSO、引入完全學(xué)習(xí)的傳統(tǒng)QPSO(CLQPSO)以及改進后的CLQPSO(WCLQPSO)算法求解LE1～LE5 算例，結(jié)果如圖10所示。

圖10 算法改進前、后結(jié)果比較Fig.10 Comparison of results before and after algorithm improvement

QPSO、CLQPSO 與WCLQPSO 算法求解結(jié)果比較數(shù)值如表7所示。

QPSO，CLQPSO，WCLQPSO 算法的運行時間分別穩(wěn)定在506.71，623.37，811.26 s。表7中QPSO算法、CLQPSO 算法及WCLQPSO 算法求解LE1～LE5 算例的平均求解結(jié)果分別為58869.95，59247.55，58329.12 元；WCLQPSO 算法、CLPSO 算法與及QPSO 算法求解結(jié)果的平均偏差分別為0.65%和-0.91%，表明WCLQPSO 算法獲得的結(jié)果在穩(wěn)定性基本保持不變的情況下具有更好的尋優(yōu)能力。

表7 QPSO、CLQPSO與WCLQPSO算法求解結(jié)果比較Table 7 Comparison of solution results of QPSO,CLQPSO and WCLQPSO

為評價提出的加入啟發(fā)式后的算法性能，將增加啟發(fā)式改進后的WCLQPSO 算法(記為IWCLQPSO)與WCLQPSO 算法對算例LE6～LE10的求解結(jié)果進行比較，結(jié)果如圖11所示。

圖11 IWCLQPSO與WCLQPSO比較Fig.11 Comparison between IWCLQPSO and WCLQPSO

IWCLQPSO 與WCLQPSO 算法求解結(jié)果比較數(shù)值如表8所示。

表8中加入啟發(fā)式策略后的改進粒子群算法和改進粒子群算法求解LE6～LE10 算例的平均求解結(jié)果分別為59512.58元和57103.70元，平均偏差為4.05%，表明加入啟發(fā)式改進后的量子粒子群算法具有更好的尋優(yōu)能力。

表8 IWCLQPSO與WCLQPSO算法求解結(jié)果比較Table 8 Comparison of solution results of IWCLQPSO and WCLQPSO

3.7 各類平臺補貼對總成本的影響分析

多車程的城際零擔(dān)貨物運輸必然會導(dǎo)致貨主收貨時間延后，為使更多貨主選擇多程運輸，從而降低整體物流成本，根據(jù)多車程中預(yù)估到達每個貨主及貨主目的地處的時間與直接到達時間之差，考慮給予貨主的運輸時長補貼K1；部分高價值訂單位置偏遠，訂單價值高，但返程可接單少，司機接單意愿低，導(dǎo)致平臺收入降低，因此，考慮進行針對性補貼Ak；車輛空駛率高會影響司機的接單意愿，考慮進行針對性補貼K2和K3，補貼總金額受每段行程的行駛距離以及空載率影響。為表現(xiàn)4 類補貼金額變化對總成本以及最優(yōu)解的影響，依次將4類補貼設(shè)置為變量，分4 組，每組10 次運行小規(guī)模(SE1)和大規(guī)模(LE1)算例，得到的結(jié)果如圖12和圖13所示。

圖12 4類補貼對總成本結(jié)構(gòu)影響(SE1算例)Fig.12 Impact of four types of subsidies on total cost structure(SE1 example)

圖13 4類補貼對總成本結(jié)構(gòu)影響(LE1算例)Fig.13 Impact of four types of subsidies on total cost structure(LE1 example)

通過分析上述實驗可得，混合補貼模式獲得的經(jīng)濟效益最優(yōu)。貨主補貼取K1=(5,6]元?h-1時，車輛行駛總距離減少，平臺減少了8.35%燃油成本，降低了6.31%總成本。隨著貨主補貼系數(shù)的不斷增加，小規(guī)模問題中為避免產(chǎn)生過多補貼，車-貨匹配階段，通過減少車輛一次接單數(shù)減少貨主等待時間，使貨主補貼金額無顯著線性增長，總成本無較大波動，表明，貨主補貼有較優(yōu)的反饋調(diào)節(jié)能力，但大規(guī)模問題中該現(xiàn)象并不明顯，因此，實際規(guī)劃時應(yīng)避免計劃周期過長；高價值訂單補貼無上述貨主補貼系數(shù)的反饋調(diào)節(jié)能力，但該類補貼對平臺收入影響較大，應(yīng)在穩(wěn)定毛利增長的同時最大程度發(fā)揮補貼金額效果，因此，小規(guī)模問題取高價值訂單補貼A2=(1,2]元?千元-1，大規(guī)模問題取高價值訂單補貼A2=(0.1,0.2]元?千元-1；空載補貼系數(shù)存在與貨主補貼系數(shù)同樣的反饋調(diào)節(jié)能力，合適的空載補貼可有效降低車輛使用成本，小規(guī)模問題取K2=(2×10-6,3×10-6]元?(kg?km)-1，K3=(2×10-6,3×10-6]元?(kg?km)-1時車輛利用率提高25%并減少4.33%空駛距離，大規(guī)模問題取K2=(2×10-8,3×10-8]元?(kg?km)-1，K3=(2×10-9,3×10-9]元?(kg?km)-1時車輛利用率提高10%并減少1.67%空駛距離。

4 結(jié)論

本文主要得到的結(jié)論如下：

(1)提出的改進量子粒子群算法實驗結(jié)果表明：針對小規(guī)模城際零擔(dān)貨運問題，改進量子粒子群算法得到的優(yōu)化解與CPLEX軟件獲得的最優(yōu)解的平均偏差為3.31%；針對大規(guī)模城際零擔(dān)貨運問題，改進量子粒子群算法與傳統(tǒng)量子粒子群算法相比，在保持其穩(wěn)定性基本不變的情況下，尋優(yōu)能力提升0.91%；加入啟發(fā)式策略后，改進后的量子粒子群算法尋優(yōu)能力提升4.05%。

(2)提出的平臺補貼方案對比實驗結(jié)果表明：合適的貨主時長補貼在吸引貨主發(fā)單的同時影響車輛路徑規(guī)劃及三維裝載結(jié)果，可使總成本降低6.31%。高價值訂單補貼和空載補貼在吸引車輛入駐平臺的同時，能夠激勵司機接受周期較長的高價值訂單，針對小規(guī)模問題進行求解，減少4.33%空駛距離，提高25%車輛利用率；針對大規(guī)模問題進行求解，減少1.67%空駛距離，提高10%車輛利用率。