基于TS算法的公路干線貨運(yùn)平臺(tái)車(chē)貨匹配研究

， ，

(浙江理工大學(xué)，a.理學(xué)院；b.經(jīng)濟(jì)管理學(xué)院,杭州 310018)

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

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

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

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

一、車(chē)貨匹配模型建立

(一)問(wèn)題描述

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

a)貨主與目的地一一對(duì)應(yīng)，每個(gè)貨主與其對(duì)應(yīng)的目的地都要被匹配且只能匹配一次；

b)貨主給定的時(shí)間為要求車(chē)主到達(dá)目的地的最晚時(shí)間，考慮信用評(píng)價(jià)體系的穩(wěn)定性，平臺(tái)匹配時(shí)不允許車(chē)主遲到；

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

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

e)同一車(chē)輛載貨成本僅與車(chē)輛單位距離行駛成本和行駛距離有關(guān)，與載貨量等無(wú)關(guān)；

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

g)運(yùn)輸過(guò)程中采取“人歇車(chē)不歇”的不間斷運(yùn)輸方式；

h)車(chē)輛停留裝卸貨時(shí)間為常數(shù)，不考慮貨物噸位等因素對(duì)車(chē)輛裝卸貨時(shí)間的影響；

i)車(chē)貨雙方經(jīng)過(guò)平臺(tái)信用篩選，車(chē)主的信用不小于平臺(tái)允許其加入虛擬車(chē)隊(duì)的信用，貨主的信用不小于平臺(tái)允許其參加匹配的信用；

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

(二)符號(hào)說(shuō)明

V：車(chē)主集合；

G：貨主集合；

F：目的地集合；

m：車(chē)主數(shù)量；

n：貨主數(shù)量；

i：車(chē)主編號(hào)；

j：車(chē)主、貨主以及目的地的編號(hào)；

k：車(chē)主、貨主以及目的地的編號(hào)；

C:匹配的運(yùn)輸成本；

Eei：車(chē)主的車(chē)輛單位空駛成本；

Efi：車(chē)主的車(chē)輛單位滿載成本；

Li：車(chē)主的車(chē)輛最大載重量；

TGk：貨主給定要求貨物送達(dá)目的地的時(shí)間；

Tij：車(chē)主到j(luò)的實(shí)際時(shí)間；

Tα：車(chē)主每次停留裝卸貨時(shí)間；

v：車(chē)主的車(chē)輛平均行駛速度；

Wj：貨主的貨物重量；

RVi：車(chē)主信用值；

RGj：貨主信用值；

RVα：平臺(tái)允許加入虛擬車(chē)隊(duì)的最小車(chē)主信用值；

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

(三)車(chē)貨匹配模型

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

(1)

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

(2)

(3)

(4)

(5)

(6)

(7)

(8)

(9)

(10)

(11)

(12)

(13)

(14)

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

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

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

a)給定禁忌長(zhǎng)度等參數(shù)，隨機(jī)產(chǎn)生一個(gè)初始解，并清空禁忌表；

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

c)利用當(dāng)前解的鄰域函數(shù)，產(chǎn)生所有或若干鄰域解，從中選定若干解作為候選解；

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

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

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

圖1 TS算法流程圖

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

對(duì)于m個(gè)車(chē)主，n個(gè)貨主，貨主對(duì)應(yīng)的目的地有n個(gè)。為了方便解釋TS算法的編碼與解碼過(guò)程，下面以m=4，n=3為例進(jìn)行演示。

1.編碼方法

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

表1 編碼及其類(lèi)別

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

表2 鄰域解位置

2.解碼方式

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

表3 鄰域解映射

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

表4 分割點(diǎn)

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

表5 匹配解碼

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

表6 貨主路徑解碼

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

表7 目的地路徑解碼

3.更新迭代編碼與解碼

a)對(duì)鄰域解中任意兩個(gè)編碼的位置進(jìn)行互換。當(dāng)編碼長(zhǎng)度較小時(shí)，可以選取并計(jì)算所有編碼兩兩位置互換的鄰域解；當(dāng)編碼長(zhǎng)度較大時(shí)，為減少運(yùn)算量可以選取并計(jì)算部分編碼位置互換的鄰域解。以鄰域解1中編碼2和3的互換為例，如表8所示。

表8 編碼位置互換

b)按照解碼方式對(duì)調(diào)換位置的編碼進(jìn)行解碼，得到新的車(chē)貨匹配方案和新的車(chē)輛行駛路徑：車(chē)主3匹配貨主5、6、7。對(duì)應(yīng)的車(chē)輛行駛路徑為：3→5→6→7→8→10→8，如表9所示。

表9 更新迭代編碼與解碼

若此時(shí)求得的匹配結(jié)果優(yōu)于更新迭代前，則將車(chē)主3與貨主5的匹配加入到禁忌表中，進(jìn)行下一次迭代更新；當(dāng)該禁忌表中的匹配超過(guò)禁忌步長(zhǎng)時(shí)，則將該匹配移出禁忌表。

三、案例分析

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

(一)TS算法模型求解

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

1.小規(guī)模車(chē)貨數(shù)量求解

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

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

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

2.大規(guī)模車(chē)貨數(shù)量求解

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

圖2 TS算法迭代收斂圖像

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

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

(二)算法性能比較分析

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

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

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

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

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

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

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

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

四、結(jié) 論

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

本文建立的車(chē)貨匹配模型適用于公路干線中長(zhǎng)途貨運(yùn)的車(chē)貨匹配，對(duì)于同城以及干線短途車(chē)貨匹配而言，先集貨后送貨的方式往往導(dǎo)致匹配調(diào)度成本增加，因此模型具有一定的應(yīng)用局限性。另外，本文提出的車(chē)貨匹配調(diào)度模型是建立在車(chē)主與平臺(tái)合作基礎(chǔ)上，至于兩者如何建立合作關(guān)系，以及雙方利益分配問(wèn)題將是未來(lái)研究方向之一。