， ，

(浙江理工大學，a.理學院；b.經濟管理學院,杭州 310018)

公路貨運在我國貨物運輸行業(yè)中占有重要地位，目前我國公路貨運量占全國貨運總量的75%左右。以2017年為例，當年全國貨運總量479.4億噸，其中公路貨運量為368.0億噸，占比76.8%[1]。然而，我國公路貨運多年來一直存在著“散、亂、差”的局面：市場中90%為運輸業(yè)個體戶；車輛等待回程貨的平均時間是72小時，平均回程空駛率為44%[2]。公路貨運市場出現(xiàn)如此局面的原因是整個市場中存在嚴重的信息不對稱。雖然貨運中介的出現(xiàn)一定程度上使得這類問題有所緩解，但車貨信息往往經過多個中介的轉手導致信息傳遞緩慢，物流成本增加。隨著互聯(lián)網和智能手機的普及，“平臺+App”車貨匹配模式出現(xiàn)，匹配重心開始由線下向線上移動端轉移，匹配對象從貨運中介變?yōu)檐囍髋c貨主雙方。

雙邊市場是利用一個或多個雙邊平臺實現(xiàn)用戶的交互，并通過對雙方收取合理的費用而將其維持在平臺上的市場[3]。公路貨運市場由車主和貨主兩方進行交互，因此屬于典型的雙邊市場，平臺在其中發(fā)揮著重要作用。Armstrong等[4-5]認為，市場中的某些活動必須借助平臺來完成，平臺通過為雙方提供產品或服務來促成交易并從中獲取利潤，平臺中一方用戶獲得的利益多少取決于另一方用戶的規(guī)模大小。Abrahamsson等[6]認為，物流平臺是信息管理與控制中心，是物流系統(tǒng)非常重要的一部分。宋娟娟等[7]對公路貨運平臺發(fā)展現(xiàn)狀及運營機制進行了分析，指出平臺在發(fā)展過程中應解決好“雞蛋相生”問題。張松[8]對南京市三種貨運配載模式進行了對比分析，發(fā)現(xiàn)基于物流平臺的車貨匹配模式具有一定優(yōu)勢。公路貨運市場中的車貨匹配屬于典型的雙邊匹配問題。Gale等[9]對雙邊匹配問題進行了開創(chuàng)性研究，并用Gale-Shapley算法成功解決了婚姻匹配問題，證明穩(wěn)定的婚姻匹配總是存在的。Zhang等[10]以滴滴出行平臺為例，在考慮司機接單概率的情況下，建立了最大化訂單成交率的滴滴出租車分單模型。陳靜[11]在分析公路貨運平臺訂單分配問題現(xiàn)狀的基礎上，建立了訂單分配模型，提高了運輸資源利用率。陳火根等[12]將配載過程分解為資源分類、資源匹配、交易協(xié)商三個子任務，在此基礎上設計了在線算法對車貨雙方進行匹配，通過原型系統(tǒng)實驗證明：基于網格技術的貨物配載系統(tǒng)不僅可以方便地集成異構系統(tǒng)，而且可以確保配載處理的實時性。李玉花[13]建立了以能力和資源限制為約束條件，以物流供需匹配度大化為目標的流線型優(yōu)化模型。李慧[14]通過把影響車貨雙方匹配的指標劃分為硬指標和軟指標的方法，建立了以匹配度最大為目標的車貨配載多目標匹配排序模型。

我國公路干線貨物運輸具有很強的季節(jié)性和區(qū)域性：春夏季相對于秋冬季而言貨源較少，西部地區(qū)相對于東部地區(qū)而言貨源較少。淡季時貨物數量少，可以利用窮舉的方法求得最優(yōu)匹配調度方案；旺季時貨物數量較多，窮舉方法求解耗時過長，需要利用啟發(fā)式算法進行求解。求解匹配調度問題的算法主要有粒子群算法(Particle swarm optimization，PSO)、禁忌搜索算法(Tabu search，TS)、蟻群算法(Ant colony optimization，ACO)、遺傳算法(Genetic algorithm，GA)，以及各種算法的改進算法、混合算法等。其中TS算法是求解匹配調度問題的常用有效算法。Montané等[15]建立了具有最大行程約束的隨機車輛調度模型，并通過TS算法求解取得了較好的效果。Brandal[16]采用TS算法研究了不同車型對車輛調度問題求解效果的影響。郎茂祥等[17]構造了求解車輛匹配調度問題的新禁忌搜索算法，并通過實驗進行模擬計算，結果表明該算法求解車輛調度問題具有較好的效用。劉興等[18]在TS算法的基礎上提出了一種新算法，將車輛匹配調度問題按不同的車輛和顧客分解成若干子問題，然后用TS算法求解每個子問題，并從所有子問題的最優(yōu)解中選出全局最優(yōu)解。

目前大多數對于平臺車貨匹配的研究是建立在車主和貨主與平臺無合作或從屬關系的背景下，匹配以交易撮合、提高推薦成功率為目的。平臺如何提高車貨雙方的可控性，發(fā)揮宏觀匹配調度作用，提高匹配效率，降低物流成本將是亟待解決的問題。本文提出平臺利用信用評價體系篩選高信用車主，與其合作成立虛擬車隊，進而對車貨雙方進行匹配調度的新思路。建立運力可控情景下的車貨匹配調度模型，給出求解算法，并通過不同算法對比分析來驗證TS算法的求解性能。本文的研究結論可為線上貨運平臺的未來發(fā)展提供理論參考。

一、車貨匹配模型建立

(一)問題描述

從“車多貨少”的實際背景出發(fā)，根據文獻[15]建立的信用評價體系，對車貨雙方信用情況進行評價，淘汰低信用的車主與貨主，篩選出高信用的車貨雙方。對于篩選出的高信用車主，線上平臺與之合作成立虛擬車隊實現(xiàn)運力可控。某時刻某區(qū)域內虛擬車隊中存在不同車型、不同載重水平的車輛，如果只進行一對一整車匹配可能出現(xiàn)較多車輛低滿載的情況，而通過一車對多貨的調度匹配可以有效提高車輛滿載率，降低物流成本。因此，本文在考慮車貨雙方信用的基礎上，建立無配送中心、多車型、先集貨再送貨并以最小匹配成本為目標的一對多車貨匹配調度模型。匹配調度成本分為兩部分，即從車輛當前位置到貨主處的空駛成本和車輛載貨行駛的載貨成本。假設：

a)貨主與目的地一一對應，每個貨主與其對應的目的地都要被匹配且只能匹配一次；

b)貨主給定的時間為要求車主到達目的地的最晚時間，考慮信用評價體系的穩(wěn)定性，平臺匹配時不允許車主遲到；

c)同一車主可以匹配一位或多位貨主，但每階段只允許匹配一次；

d)不同貨主的貨物可以相互拼裝；

e)同一車輛載貨成本僅與車輛單位距離行駛成本和行駛距離有關，與載貨量等無關；

f)不同車輛空駛成本和載貨成本不同；

g)運輸過程中采取“人歇車不歇”的不間斷運輸方式；

h)車輛停留裝卸貨時間為常數，不考慮貨物噸位等因素對車輛裝卸貨時間的影響；

i)車貨雙方經過平臺信用篩選，車主的信用不小于平臺允許其加入虛擬車隊的信用，貨主的信用不小于平臺允許其參加匹配的信用；

j)車輛行駛距離Djk用兩點(Xj,Yj)和(Xk,Yk)之間的經緯度距離表示：

(二)符號說明

V：車主集合；

G：貨主集合；

F：目的地集合；

m：車主數量；

n：貨主數量；

i：車主編號；

j：車主、貨主以及目的地的編號；

k：車主、貨主以及目的地的編號；

C:匹配的運輸成本；

Eei：車主的車輛單位空駛成本；

Efi：車主的車輛單位滿載成本；

Li：車主的車輛最大載重量；

TGk：貨主給定要求貨物送達目的地的時間；

Tij：車主到j的實際時間；

Tα：車主每次停留裝卸貨時間；

v：車主的車輛平均行駛速度；

Wj：貨主的貨物重量；

RVi：車主信用值；

RGj：貨主信用值；

RVα：平臺允許加入虛擬車隊的最小車主信用值；

RGα：平臺允許參與匹配的最小貨主信用值。

(三)車貨匹配模型

為發(fā)揮平臺宏觀匹配調度的作用，實現(xiàn)提高車貨匹配效率、降低社會物流總成本的目的，本文以最小化匹配成本為目標建立車貨匹配模型，該模型可以用公式表示為：

(1)

aij=ai(j+n)，j∈G

(2)

(3)

(4)

(5)

(6)

(7)

(8)

(9)

(10)

(11)

(12)

(13)

(14)

式(1)是目標函數，匹配總運輸成本最小，成本分為空駛成本和載貨成本；式(2)是貨主與對應目的地匹配，即若車主與貨主匹配，則車主也與貨主對應的目的地也匹配；式(3)是所有貨主均被匹配；式(4)—(5)是目的地的車輛流入流出平衡；式(6)—(10)是車輛行駛路徑約束，即車主不能從當前位置到其他車主位置、不能從當前位置直接到目的地、不能從貨主位置到車主位置、不能從目的地到車主位置、不能從目的地到貨主位置；式(11)是車輛載重約束，與車主匹配的貨物總量不能超過車的載重；式(12)是時間約束，車主運輸到達目的地的時間不能超過貨主給定的時間；式(13)—(14)是決策變量。

二、基于TS算法的模型求解

TS算法最早由Glover于1986年提出，是一種模仿人類記憶功能的算法。它的基本思想是：為了找到“全局最優(yōu)解”，不應執(zhí)著于某一特定區(qū)域，因此在搜索全局最優(yōu)解的過程中，標記對應已搜索的局部最優(yōu)解的對象，在進一步迭代搜索中有意識地避開它，從而獲得更多的搜索區(qū)間。TS算法中有三個重要的概念：禁忌表、禁忌長度和特赦準則。禁忌表是用來存放禁忌對象的容器，禁忌表中的對象在解禁之前不能被再次搜索。禁忌表的大小影響搜索速度和解的質量：禁忌表長度過小，搜索可能進入死循環(huán)；禁忌表過大則限制了搜索區(qū)域，好的解可能不會被搜索到。禁忌長度是指禁忌對象在禁忌表中被禁忌的步數。特赦準則是用來釋放特定解，實現(xiàn)全局優(yōu)化搜索的準則，當全部候選解或優(yōu)于當前最優(yōu)解的候選解被禁時，特赦準則就會發(fā)揮作用。TS算法流程如圖1所示，具體步驟如下：

a)給定禁忌長度等參數，隨機產生一個初始解，并清空禁忌表；

b)判斷是否滿足終止條件，若滿足則停止搜索，輸出最優(yōu)值，否則進行步驟c)；

c)利用當前解的鄰域函數，產生所有或若干鄰域解，從中選定若干解作為候選解；

d)判斷候選解是否滿足特赦準則，若滿足則執(zhí)行步驟f)，否則執(zhí)行步驟e)；

e)判斷候選解的禁忌屬性對候選解所對應的各種對象進行分析，選擇在候選解中且不在禁忌表中的對象對應的最佳狀態(tài)作為新的當前解，并將該對象對應的禁忌對象替換掉原有的禁忌對象；

f)執(zhí)行步驟b)。

圖1 TS算法流程圖

由于以最小成本為目標的一對多車貨匹配問題不但涉及車貨雙方是否匹配，還涉及匹配后的路徑規(guī)劃，且路徑中集貨地與送貨地是一一對應的，所以在設計TS算法編碼時采取將編碼分為兩段的方法。車主與貨主段編碼組成第一部分，其作用是判定車貨匹配，并確認車輛在車主與貨主之間以及貨主與貨主之間的行駛路徑。目的地編碼為第二部分，其作用是確認車輛在貨主和目的地之間，以及目的地與目的地之間行駛路徑。

對于m個車主，n個貨主，貨主對應的目的地有n個。為了方便解釋TS算法的編碼與解碼過程，下面以m=4，n=3為例進行演示。

1.編碼方法

a)將編碼(m+2n-1)分為兩部分：編碼第一部分從1至(m+n-1)，編碼長度為(m+n-1)，將這部分編碼的類別設為1；編碼第二部分從(m+n)至(m+2n-1)，編碼長度為n，將這部分編碼的類別設為2。當m=4，n=3時，第一部分編碼為1至6，第二部分編碼為7至9。編碼及其類別如表1所示。

表1 編碼及其類別

b)計算維數為(m+2n-1)的鄰域解位置，設定位置中各維度的取值范圍為[0,1]。經過計算得到各個編碼的取值，編碼取值組成鄰域解的位置，鄰域解位置如表2所示。

表2 鄰域解位置

2.解碼方式

a)根據鄰域解位置中各維度取值的大小進行映射解碼。其中第一部分按照位置取值從小到大的順序分別映射為1至(m+n-1)之間的數字。以鄰域解1位置為例，第一部分1至6的編碼位置取值按從小到大順序的映射為2、4、3、5、6、1，如表3所示。

表3 鄰域解映射

b)從映射后數字1至(m+n-1)中選取最小的(m-1)個數字作為分割點，用Y表示該映射為分割點，N表示該映射為非分割點。鄰域解1共產生三個分割點，對應編碼為1、3、6，編碼分割點如表4所示。

表4 分割點

c)(m-1)個分割點將編碼拆分為m段，對應m輛車。m段按照編碼從小到大的順序再次映射為(m+1)到(m+n)之間的數字，此時映射的數字即為與該車主匹配的貨主。鄰域解1中三個分割點將編碼拆分為四段，第一段車主1無匹配的貨主，第二段車主2匹配貨主5，第三段車主3匹配貨主6、7，第四段車主4無匹配的貨主，匹配解碼如表5所示。

表5 匹配解碼

d)比較與車主匹配的貨主鄰域解位置中各維度取值的大小，按照每段中從小到大的順序，確定車輛行駛路徑。車主2從當前位置到貨主5處，車主3從當前位置先到貨主6再到貨主7的位置，貨主路徑解碼如表6所示。

表6 貨主路徑解碼

e)對于第二部分，由于貨主與目的地位置一一對應且編號相差n，第一部分車貨匹配后，車與目的地也是匹配的，只需按照位置取值從小到大確定行駛順序即可。車主2與貨主5匹配，則車主2與貨主5對應的目的地8也匹配，且路徑順序為：2→5→8。車主3與貨主6和7匹配，則車主3與貨主6、7對應的目的9、10也匹配，且路徑是順序為：3→6→7→10→9。路徑解碼如表7所示。

表7 目的地路徑解碼

3.更新迭代編碼與解碼

a)對鄰域解中任意兩個編碼的位置進行互換。當編碼長度較小時，可以選取并計算所有編碼兩兩位置互換的鄰域解；當編碼長度較大時，為減少運算量可以選取并計算部分編碼位置互換的鄰域解。以鄰域解1中編碼2和3的互換為例，如表8所示。

表8 編碼位置互換

b)按照解碼方式對調換位置的編碼進行解碼，得到新的車貨匹配方案和新的車輛行駛路徑：車主3匹配貨主5、6、7。對應的車輛行駛路徑為：3→5→6→7→8→10→8，如表9所示。

表9 更新迭代編碼與解碼

若此時求得的匹配結果優(yōu)于更新迭代前，則將車主3與貨主5的匹配加入到禁忌表中，進行下一次迭代更新；當該禁忌表中的匹配超過禁忌步長時，則將該匹配移出禁忌表。

三、案例分析

貨車幫是一個互聯(lián)網貨車車庫平臺，成立于2011年，2013年貨車幫App發(fā)布。該平臺通過“貨車幫車主”端整合車主、“貨車幫貨主”端整合貨主的方式，現(xiàn)已積累了大量的用戶。貨車幫的車貨匹配模式主要有主動、被動、推薦三種。主動模式下，貨主可以利用車庫功能，主動篩選所需車輛并聯(lián)系車主溝通運價達成交易；而車主可以通過對貨源進行篩選并主動聯(lián)系貨主溝通運價的方式找貨。被動模式下，貨主可以選擇將出發(fā)地、目的地、需要車長車型、貨物類型、貨物重量、運費金額、裝車時間、裝卸方式、付款方式等信息發(fā)布到平臺，等待車主聯(lián)系達成交易；車主則可以通過車主端發(fā)布出發(fā)地、目的地、重量等貨物需求信息的方式找貨。推薦模式下，當貨主需要發(fā)貨時，平臺會優(yōu)先向貨主推薦與其發(fā)生過交易的車主；而除了車主可以通過訂閱路線功能及時收到訂閱路線上的貨運信息外，平臺還會根據車主出發(fā)地和目的信息將周邊貨源推薦給車主。貨車幫作為信息交互平臺，并不實際參與到車貨雙方匹配交易中去，車主與貨主將交易信息發(fā)布到平臺后，雙方根據需要進行自由匹配交易。

(一)TS算法模型求解

從貨車幫平臺采集某時刻浙江到京津冀地區(qū)所有車源和貨源信息。由于貨物本身的價值通常高于運費的價格，交易中貨主承擔的風險高于車主，因此取RVα=0.9,RGα=0.7。篩選所有車主與貨主后剔除低信用者，剩余共60位車主和35位貨主。假設經過篩選的車主均同意與平臺建立合作關系，加入虛擬車隊成為可控運力。

1.小規(guī)模車貨數量求解

選取10位車主和7位貨主作為求解數據。其中，車主編號為1—10，貨主編號為11—17，貨主對應的目的地編號為18—24。最大迭代次數設置為200，禁忌長度設置為20，選取全部的鄰域解作為候選解。Matlab R2016a在配置為i5-3337U，CPU@1.8GHz的環(huán)境下運行38.74 s，得到最小匹配成本23966.92元。車貨匹配結果如表10所示。

表10 小規(guī)模TS算法匹配結果

從表10可以看出，共用5位車主即可匹配完全部7位貨主，且車輛載重率均較高，減少了運力浪費。通過與Lingo窮舉思想下求得的“精確解”對比，發(fā)現(xiàn)其求解結果與“精確解”結果完全一致，證明TS算法在求解小規(guī)模車貨匹配問題上具有較好性能。

2.大規(guī)模車貨數量求解

對車主與貨主以及目的地進行編號：車主編號為1—60，貨主編號為61—95，目的地編號為96—130。最大迭代次數設置為200，禁忌長度設置為20，由于鄰域解數量較大，為了減少求解時間，僅選取4%的鄰域解作為候選解。Matlab運行127.95 s，得到最小匹配成本115000.86元，其迭代收斂圖像如圖2所示。

圖2 TS算法迭代收斂圖像

在大規(guī)模車貨數量情況下，TS算法在第15次迭代中出現(xiàn)可行解，并持續(xù)搜索在第140次迭代中得到最終解，說明該算法具有較好的全局和局部搜索能力。得到的最終匹配中，23位車主將35位貨主匹配，車主車輛載重率均較高，有效地減少了車輛空載或非滿載造成的資源浪費。匹配結果相關信息如表11所示。

表11 大規(guī)模TS算法匹配結果

(二)算法性能比較分析

PSO算法是求解匹配調度問題的常用算法之一。為驗證TS算法在求解大規(guī)模車貨數量上的性能是否具有優(yōu)越性，本文引入PSO算法和PSO-TS混合算法(Particle swarm optimization and tabu search hybrid algorithm，PSO-TS)進行對比分析。取采集到的全部60位車主和35位貨主作為大規(guī)模車貨匹配數據，最大迭代次數設置為800，某次求解三種算法迭代收斂圖像如圖3所示。

圖3 不同算法迭代收斂圖像

TS算法在第21次迭代中開始出現(xiàn)可行解，在第651次迭代中得到最終解；PSO算法在第148次迭代中開始出現(xiàn)可行解，在第725次迭代中得到最終解；PSO-TS算法在第166次迭代中開始出現(xiàn)可行解，在第718次迭代中得到最終解。從圖3可以看出，與PSO和PSO-TS算法相比，TS算法不但搜索能力強，收斂速度快，而且最終得到的匹配成本也更小。

為了減小單次求解帶來的隨機性影響，相同數據下利用三種算法分別進行多次求解，從求得可行解概率、求解平均時間、最小匹配成本均值三個方面對算法在大規(guī)模車貨數量情況下的求解性能進行統(tǒng)計。

a)求得可行解概率：TS算法在多次求解中均能得到可行解；PSO算法得到可行解的概率僅為10%；PSO-TS算法求得可行解的概率為85%。

b)求解平均時間：TS算法求解平均時間為499.12 s；PSO算法在10%的概率求得可行解情況下，求解平均時間為81.19 s；PSO-TS算法在85%的概率求得可行解情況下，求解平均時間為570.26 s。

c)最小匹配成本均值：TS算法最小匹配成本均值為121027.47元；PSO算法在10%的概率求得可行解情況下，最小匹配成本均值為144224.07元；PSO-TS算法在85%的概率求得可行解情況下，求得最小匹配成本均值為131874.02元。

從統(tǒng)計結果來看，TS算法求解性能最好，PSO-TS算法次之，PSO算法求解性能最差。TS算法在大規(guī)模車貨數量求解中，不但可以在相對短的時間內求得“滿意解”，且在求解穩(wěn)定性和求解結果上明顯優(yōu)于PSO和PSO-TS算法。

四、結 論

本文針對公路干線貨運平臺在車貨匹配效率不高，且現(xiàn)有研究大都以撮合雙方提高交易成功率為目的的問題，提出了基于信用評價體系掌握可控運力，并以最小匹配成本為目標的車貨匹配新模式。在新模式下，由于運力是可控的，因此車貨雙方交易成交概率為100%。在建立模型的基礎上，利用TS算法對從貨車幫平臺采集到的不同規(guī)模車主與貨主數據進行求解。通過與Lingo“精確解”對比，發(fā)現(xiàn)TS算法在小規(guī)模車貨數量情況下具有較好的求解性能；通過與PSO和PSO-TS混合算法求“滿意解”性能上的表現(xiàn)，發(fā)現(xiàn)TS算法在大規(guī)模車貨數量情況下具有相對更好的求解性能。實驗結果表明，新車貨匹配模式和TS算法在提高車貨匹配效率，降低車輛空載率，減少物流成本上具有有效性，為公路貨運平臺發(fā)展提供了一定的理論參考。

本文建立的車貨匹配模型適用于公路干線中長途貨運的車貨匹配，對于同城以及干線短途車貨匹配而言，先集貨后送貨的方式往往導致匹配調度成本增加，因此模型具有一定的應用局限性。另外，本文提出的車貨匹配調度模型是建立在車主與平臺合作基礎上，至于兩者如何建立合作關系，以及雙方利益分配問題將是未來研究方向之一。