公路貨運(yùn)供需信息的組合匹配模型

張青杰，竇永香，陳 姝

（西安電子科技大學(xué) 經(jīng)濟(jì)與管理學(xué)院，西安 710071）

0 引言

隨著公路貨運(yùn)量的快速增長(zhǎng)，貨運(yùn)市場(chǎng)的匹配問(wèn)題越發(fā)突出，尤其品種多的小件貨物在貨物托運(yùn)中成本較高，這些貨物并未得到承運(yùn)方的有效整合從而造成了車輛的滿載率不高、返程空駛等社會(huì)資源浪費(fèi)的現(xiàn)象[1]。從車輛空載率上看，我國(guó)物流空載率在40%左右，而美國(guó)在10%左右[2]。如何提高物流領(lǐng)域資源的有效利用，物流信息服務(wù)平臺(tái)順應(yīng)了物流行業(yè)資源整合的大趨勢(shì)，為貨運(yùn)市場(chǎng)的信息不對(duì)稱、貨運(yùn)效率低下等問(wèn)題提供了解決手段。目前國(guó)內(nèi)物流信息服務(wù)平臺(tái)眾多，如：阿里物流信息平臺(tái)側(cè)重貨物跟蹤、國(guó)家交通物流公共信息平臺(tái)側(cè)重物流數(shù)據(jù)交換、中國(guó)物通網(wǎng)側(cè)重信息服務(wù)與物流交易等。各個(gè)平臺(tái)的服務(wù)功能側(cè)重點(diǎn)有所不同，但大部分平臺(tái)處于初級(jí)階段，僅限于提供查詢和發(fā)布服務(wù)，并沒(méi)有針對(duì)特定車輛和某類貨物提供相應(yīng)的智能化推薦，這樣就造成了匹配效率低下、匹配度低和匹配不及時(shí)等問(wèn)題。

國(guó)務(wù)院關(guān)于積極推進(jìn)“互聯(lián)網(wǎng)+”行動(dòng)的指導(dǎo)意見(jiàn)中提出要提高物流供需信息對(duì)接和使用效率。完善智能物流配送調(diào)配體系，促進(jìn)人員、貨源、車源等信息高效匹配。目前有學(xué)者進(jìn)行了相關(guān)的匹配研究，陳曦等（2008）[3]所提出的服務(wù)匹配算法建立在Web服務(wù)語(yǔ)義描述的形式化定義基礎(chǔ)上，評(píng)價(jià)候選服務(wù)與服務(wù)模板的匹配程度。歐陽(yáng)小迅和黃福華（2010）[4]對(duì)中國(guó)地區(qū)物流匹配效率進(jìn)行全面測(cè)算。張錦和王坤（2010）[5]定義了匹配度,以描述物流服務(wù)與物流需求在時(shí)間、數(shù)量、費(fèi)用等因素方面的匹配關(guān)系。這些研究主要是以提高單個(gè)貨物匹配度和匹配效率為目標(biāo)，針對(duì)組合匹配研究較少，因此本文提出基于供需信息的組合匹配模型，可以為承運(yùn)方提供合適的貨物組合方案，不僅提高多件貨物的匹配度而且充分考慮了搭乘成功率。

1 一種基于供需信息的組合匹配模型

根據(jù)承運(yùn)方給出的相關(guān)信息搜索符合條件的貨物；得到的貨物集合中貨物之間可能存在不能混裝托運(yùn)的貨物，對(duì)貨物進(jìn)行沖突關(guān)系消除并得到最少數(shù)量的不存在沖突關(guān)系的單獨(dú)貨物集合；將單獨(dú)的貨物集合分別與車輛進(jìn)行匹配，并分別得到每組單獨(dú)貨物集合中運(yùn)費(fèi)最大的貨物組合，每組貨物組合的托運(yùn)意愿越強(qiáng)烈搭乘成功率越高，根據(jù)車輛的實(shí)際情況和承運(yùn)方的偏好從這些組合中進(jìn)行選擇。模型結(jié)構(gòu)如圖1。

圖1模型結(jié)構(gòu)圖

1.1 供需信息分析

托運(yùn)方發(fā)和承運(yùn)方通過(guò)信息平臺(tái)發(fā)布和獲取信息，交流后達(dá)成托運(yùn)合作。供需信息包括貨源信息和車源信息。貨源信息：出發(fā)地、到達(dá)地、貨物名稱、貨物類型、重量、體積、發(fā)布時(shí)間、運(yùn)輸類型、聯(lián)系方式等，其中運(yùn)輸類型分為：整車配送和物流公司配送，整車配送的貨物主要是量大的貨物或危險(xiǎn)物品需要特定車輛托運(yùn)的貨物，針對(duì)整車配送的貨物匹配較為簡(jiǎn)單，只需車輛與貨物相匹配即可。車源信息：車牌號(hào)、出發(fā)地、到達(dá)地、車長(zhǎng)載重、車輛類型、運(yùn)價(jià)、聯(lián)系方式等，其中車輛類型是與貨物匹配的首要條件。本文主要是考慮物流公司配送的貨物，這類貨物品種多、單件貨物量小，所以這類貨物不但需要考慮車輛與貨物的匹配還需考慮貨物與貨物之間的匹配問(wèn)題。

1.2 貨物之間沖突關(guān)系處理

1.2.1 消除貨物之間帶沖突關(guān)系問(wèn)題的描述

貨物運(yùn)輸過(guò)程中由于貨物不同的物理性質(zhì)、化學(xué)性質(zhì)以及生物性質(zhì)導(dǎo)致了某些貨物與其他貨物在同一車輛托運(yùn)時(shí)可能會(huì)對(duì)某類貨物的某種屬性造成影響，就產(chǎn)生了貨物之間沖突關(guān)系[6]，參考《鐵路貨物運(yùn)輸技術(shù)》中不能同一批次托運(yùn)貨物及相關(guān)資料的閱讀，貨物類型之間帶沖突關(guān)系的描述總結(jié)為表1。車輛類型決定了可托運(yùn)貨物類型，參考公路貨物運(yùn)輸?shù)膶Ｓ密囕v分類[7]和相關(guān)資料的閱讀將車輛類型和與之匹配的貨物類型總結(jié)為表2。

表2 車輛類型與之匹配貨物類型

有n件貨物列表I和m個(gè)獨(dú)立貨物集合列表H；I中的每件貨物都包含一個(gè)與其他貨物存在著沖突關(guān)系的列表Li，其中與貨物存在沖突關(guān)系的貨物均不能與 放入同一單獨(dú)貨物集合，在滿足貨物之間獨(dú)立的貨物集合不存在沖突的貨物下，并獲得最少的單獨(dú)貨物集合。為描述貨物種類之間的貨物沖突關(guān)系，引入沖突圖的定義如下。

沖突圖G=（V，E）為一個(gè)無(wú)向圖，表示所有貨物之間的沖突關(guān)系。頂點(diǎn)集合V=｛v1,v2,…,vn｝，邊集E表示兩個(gè)頂點(diǎn)的貨物含有沖突關(guān)系。

為消除貨物之間沖突關(guān)系以便后續(xù)進(jìn)行貨物組合匹配，對(duì)貨物按照表1對(duì)貨物進(jìn)行沖突圖中邊集的擴(kuò)展，對(duì)存在沖突關(guān)系的貨物之間添加一條表。消除沖突關(guān)系數(shù)學(xué)表示如下：

目標(biāo)函數(shù)是求得最少的單獨(dú)貨物集合的分組；約束條件分別表示：同一件貨物只能放入一個(gè)貨物集合中，存在沖突關(guān)系的貨物不能被分到同一獨(dú)立貨物集合中，放入到某貨物集合中的貨物不能重復(fù)放入，獨(dú)立貨物集合選用不能超過(guò)一次。

1.2.2 消除貨物之間沖突關(guān)系求解

沖突關(guān)系的定義和消去可以基于沖突圖來(lái)實(shí)現(xiàn)[8]，其思想源于圖著色模型中的最小色數(shù)問(wèn)題[9]。在有沖突關(guān)系的貨物頂點(diǎn)采用不同顏色著色，就把問(wèn)題轉(zhuǎn)化為頂點(diǎn)作色問(wèn)題，屬于同一種顏色的頂點(diǎn)集合稱為一個(gè)色組，它們彼此不相鄰接，所以又稱為點(diǎn)獨(dú)立集。

貪心算法是一種改進(jìn)了的分級(jí)處理算法，根據(jù)某個(gè)優(yōu)化目標(biāo)保證每一步都有局部最優(yōu)解[10]。消除貨物沖突關(guān)系步驟如下：

步驟1：基于G的鄰接矩陣，計(jì)算當(dāng)前還未被著色的每個(gè)頂點(diǎn)的度數(shù)值。

步驟2：選取當(dāng)前度數(shù)值最大的頂點(diǎn)插入到C當(dāng)中，并且將U中所有的與v存在沖突關(guān)系的頂點(diǎn)移到UU中。

步驟3：如果當(dāng)前的U仍為非空，則選取U與UU鄰接點(diǎn)數(shù)量最多的頂點(diǎn)v，將v添加到C當(dāng)中并重復(fù)步驟2。

步驟4：這時(shí)C當(dāng)中的所有頂點(diǎn)為無(wú)沖突關(guān)系的獨(dú)立貨物集存儲(chǔ)，清空C。

步驟5：將UU中頂點(diǎn)移至U中并轉(zhuǎn)至步驟1，直至UU中為空。

其中C：當(dāng)前迭代步驟當(dāng)中已著色的頂點(diǎn)集合。U：還未被著色，與當(dāng)前節(jié)點(diǎn)存在沖突關(guān)系的節(jié)點(diǎn)。UU：還未被著色且與當(dāng)前節(jié)點(diǎn)存在沖突的節(jié)點(diǎn)。

1.3 不含沖突關(guān)系的貨物組合與車輛匹配問(wèn)題

貨物組合與車輛匹配的目的是在滿足貨物與貨物之間可以共同托運(yùn)、貨物與車輛相匹配的前提下盡可能使承運(yùn)方滿載率最高，以減少社會(huì)資源的浪費(fèi)。實(shí)現(xiàn)聯(lián)運(yùn)是提升物流績(jī)效指標(biāo)的重要舉措[11]。

1.3.1 問(wèn)題描述

承運(yùn)方給出行駛路線，根據(jù)路線從物流信息平臺(tái)上搜索途徑沿線的貨物，并按照發(fā)布時(shí)間順序?qū)ω浳镞M(jìn)行編號(hào)。對(duì)搜索到的貨物運(yùn)用圖著色模型進(jìn)行沖突關(guān)系消除，消除后獲得獨(dú)立不相關(guān)的貨物集合。分別從獨(dú)立的貨物集合中選擇出可以使承運(yùn)方獲得最大利益的貨物組合。數(shù)學(xué)規(guī)劃如下：

（1）目標(biāo)函數(shù)，考慮托運(yùn)方的滿載率，用托運(yùn)費(fèi)用最高作為衡量標(biāo)準(zhǔn)

（2）約束條件說(shuō)明：某一路線上中間分成若干個(gè)節(jié)點(diǎn)，使得每個(gè)節(jié)點(diǎn)之間均滿足車輛的最大載重和最大體積。

Qi=max{P1Vi，P2Vi} ，t為貨物數(shù)量，l為節(jié)點(diǎn)數(shù)，Lm為節(jié)點(diǎn)m與起始點(diǎn)的距離，貨物i體為Vi，重量為Wi，車的固定容積W、載重V，按照體積計(jì)算運(yùn)費(fèi)單價(jià)P1，按照重量計(jì)算運(yùn)費(fèi)單價(jià)P2。

1.3.2 貨物組合與車輛匹配問(wèn)題的求解

回溯法是一種系統(tǒng)的搜索問(wèn)題的方法[12]，求解時(shí)要回溯到根，且根結(jié)點(diǎn)的所有子樹(shù)都已被搜索遍才結(jié)束[13]。由于經(jīng)過(guò)貨物沖突關(guān)系的消除，時(shí)間復(fù)雜度大大降低，利用回溯法求解能快速找到最優(yōu)解。該問(wèn)題的解由x分別取0或1的2n個(gè)不同的n元向量組成的二叉樹(shù)樹(shù)結(jié)構(gòu)。回溯方法步驟設(shè)計(jì)如下：

步驟1：貨物按照單位運(yùn)價(jià)從大到小排列，并按照順序?qū)⑦@些數(shù)據(jù)存放到二叉樹(shù)結(jié)構(gòu)的容器中，樹(shù)結(jié)構(gòu)的每一層為一件貨物。

步驟2：從樹(shù)的當(dāng)前節(jié)點(diǎn)開(kāi)始遍歷，貨物i如果可行（分別將把貨物的體積和重量加到wm-1,wm,…wn-1和vm-1,vm,…vn-1）則進(jìn)入左子樹(shù)，并更新betterValue（最高的托運(yùn)費(fèi)用）。

步驟3：循環(huán)步驟2直到某個(gè)容器超出固定值則退回上一節(jié)點(diǎn)，并將加到wm-1,wm,…wn-1和vm-1,vm,…vn-1中的值進(jìn)行還原，判斷右子樹(shù)總費(fèi)用是否大于betterValue，若小于則不進(jìn)入右子樹(shù)退回上一節(jié)點(diǎn)，并將該點(diǎn)的右子樹(shù)進(jìn)行剪枝處理；若大于則循環(huán)步驟2。

步驟4：當(dāng)循環(huán)至最后一層則輸出betterValue，并把相應(yīng)的貨物選擇輸出。

1.3.3 基于托運(yùn)意愿的組合選擇

由于從承運(yùn)方的角度來(lái)考慮單程承運(yùn)費(fèi)用最大化，但忽略了托運(yùn)方的意愿，所以如果能夠考慮托運(yùn)方托運(yùn)意愿，那么顯然能夠提高搭乘成功率。

托運(yùn)意愿的衡量本文認(rèn)為有主要的三個(gè)因素：貨物等待時(shí)間、路線的距離差、托運(yùn)方的需求容量。認(rèn)為托運(yùn)方的等待時(shí)間越長(zhǎng)、距離差越小、托運(yùn)方需求容量越小，承運(yùn)方能和托運(yùn)方達(dá)成托運(yùn)協(xié)議的成功率就越高。每組獨(dú)立的貨物集合中的每件貨物均與車輛有一個(gè)托運(yùn)意愿，且當(dāng)單獨(dú)貨物集合中運(yùn)費(fèi)最高的一組貨物滿意度期望越大、方差越小則認(rèn)為這一組組合在滿足運(yùn)費(fèi)最高的情況下，承運(yùn)方與托運(yùn)方達(dá)成的托運(yùn)協(xié)議成功率就越高。

2 組合匹配模型實(shí)證

2.1 數(shù)據(jù)整理

從中國(guó)物通網(wǎng)上抓取數(shù)據(jù)，抓取時(shí)間2016年12月6日20:00。貨車A從陜西西安市轄區(qū)去往河南鄭州市轄區(qū)，普通箱式貨車載重10噸，車長(zhǎng)6.8米，容積是39.1立方。由于該車為普通車輛，所以抓取貨物類型為百貨、醫(yī)藥、食物、紡織品、化工制品、五金電子機(jī)械、儀器及機(jī)器零件、電子產(chǎn)品等普通類型貨物。通過(guò)百度地圖可知，從西安到鄭州途徑三門(mén)峽市和洛陽(yáng)市路線。從中國(guó)物通網(wǎng)上抓取貨物類型為物流公司配送、路線為西安至鄭州以及沿線的普通貨物，共抓取近48小時(shí)內(nèi)共50條數(shù)據(jù)，對(duì)每條數(shù)據(jù)進(jìn)行編號(hào)并添加屬性值，按貨物托運(yùn)路程整理見(jiàn)表3。

表3 貨物托運(yùn)路程

2.2 消除貨物之間沖突

根據(jù)貨物的屬性，對(duì)不能共同搭載的貨物添加一對(duì)沖突關(guān)系，對(duì)與其他貨物不存在沖突關(guān)系的貨物先行剔除，本文所有的算法細(xì)節(jié)均采用Java語(yǔ)言來(lái)實(shí)現(xiàn)，相應(yīng)的虛擬機(jī)版本為Java Development Kit 1.7.0，最終的到3類獨(dú)立的貨物分類，把與其他貨物不含沖突關(guān)系的貨物分別加入這3個(gè)獨(dú)立類中最終的到結(jié)果如表4。

表4 不含沖突關(guān)系的貨物集

2.3 貨物組合與車輛匹配的求解

本文采用回溯法對(duì)組合匹配模型求解，算法細(xì)節(jié)均采用Java語(yǔ)言來(lái)實(shí)現(xiàn)，相應(yīng)的虛擬機(jī)版本為Java Development Kit 1.7.0，最終求得結(jié)果如下頁(yè)表5。

以上3組貨物組合是在保證貨物之間不存在沖突關(guān)系的前提下能夠使托運(yùn)方獲得最大承運(yùn)價(jià)格。根據(jù)加權(quán)的托運(yùn)意愿分別求得獨(dú)立貨物集合中每件貨物的托運(yùn)意愿如表6，表6中第1、第2列代表第0組獨(dú)立貨運(yùn)組合中每件貨物的編號(hào)和托運(yùn)意愿，第3、第4列代表第1組獨(dú)立貨運(yùn)組合中每件貨物的編號(hào)和托運(yùn)意愿，第5、第6列代表第2組獨(dú)立貨運(yùn)組合中每件貨物的編號(hào)和托運(yùn)意愿。其中托運(yùn)意愿越接近于1表示該件貨物的托運(yùn)意愿越強(qiáng)烈。

表5 與車輛相匹配的貨物組合

表6 托運(yùn)方的托運(yùn)意愿

根據(jù)每件貨物的托運(yùn)意愿可求得每組貨物組合托運(yùn)意愿的期望和方差如表7。

表7 貨物組合托運(yùn)意愿期望方差

可知貨物組合1運(yùn)價(jià)最高且總體托運(yùn)意愿最大、方差最小，說(shuō)明組合1中貨物可同時(shí)托運(yùn)的前提下，承運(yùn)方運(yùn)費(fèi)總額最大，托運(yùn)方的總體托運(yùn)意愿最大，且該組合每件貨物的托運(yùn)方托運(yùn)意愿差別較小，所以認(rèn)為該貨物集合能夠達(dá)成托運(yùn)合作的成功率較高。該車方在中國(guó)物通網(wǎng)上整車報(bào)價(jià)2400元，使用該方案遠(yuǎn)遠(yuǎn)大于承運(yùn)方報(bào)價(jià)。托運(yùn)方案為：在西安托運(yùn)的貨物9、10、12、22、27、28、31、32、33、34到達(dá)三門(mén)峽市后9、10、27、28、31號(hào)貨物卸車19、41、42號(hào)貨物裝車，到達(dá)洛陽(yáng)市后12、32、33、34、42號(hào)貨物卸車45、47、48、49號(hào)貨物裝車。由于貨物托運(yùn)意愿和承運(yùn)人獲得的托運(yùn)費(fèi)用不一定同時(shí)達(dá)到最高，可根據(jù)承運(yùn)方的偏好進(jìn)行選擇。

3 結(jié)束語(yǔ)

供需信息的有效使用不僅能解決車輛運(yùn)輸過(guò)程中裝載率低還可以大大降低整個(gè)物流活動(dòng)中的等待時(shí)間。本文根據(jù)托運(yùn)方的運(yùn)輸路線獲得沿線所有以運(yùn)輸屬性為物流公司配送的貨物信息，然后利用頂點(diǎn)著色模型對(duì)存在沖突關(guān)系的貨物進(jìn)行沖突消除，將貨物分成幾組獨(dú)立的貨物集合；通過(guò)車輛與貨物組合的匹配獲得沿線各節(jié)點(diǎn)需要裝卸貨物的方案；將托運(yùn)方的等待時(shí)間、托運(yùn)方和車輛的路線差、托運(yùn)貨物所占比重，作為托運(yùn)意愿的衡量指標(biāo)。根據(jù)模型所獲得的方案不僅在承運(yùn)費(fèi)用上高于承運(yùn)方的整車報(bào)價(jià)且兼顧了托運(yùn)方的意愿，還保證了貨物在承運(yùn)過(guò)程的安全性。由于物流問(wèn)題的復(fù)雜性需要考慮的因素眾多所以本文還存在很多不足，在后續(xù)的研究中主要在以下兩個(gè)方面進(jìn)行深入研究：（1）針對(duì)存在沖突關(guān)系的貨物種類進(jìn)行細(xì)分；（2）對(duì)承運(yùn)方的運(yùn)輸習(xí)慣、運(yùn)輸偏好進(jìn)行挖掘，在進(jìn)行車輛貨物組合匹配時(shí)，不僅考慮車輛與貨物之間的匹配還要充分考慮承運(yùn)方的承運(yùn)偏好，從而提高匹配度。