張青杰，竇永香，陳 姝

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

0 引言

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

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

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

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

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

1.1 供需信息分析

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

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

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

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

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

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

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

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

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

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

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

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

步驟1：基于G的鄰接矩陣，計算當前還未被著色的每個頂點的度數(shù)值。

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

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

步驟4：這時C當中的所有頂點為無沖突關(guān)系的獨立貨物集存儲，清空C。

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

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

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

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

1.3.1 問題描述

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

（1）目標函數(shù)，考慮托運方的滿載率，用托運費用最高作為衡量標準

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

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

1.3.2 貨物組合與車輛匹配問題的求解

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

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

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

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

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

1.3.3 基于托運意愿的組合選擇

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

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

2 組合匹配模型實證

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

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

表3 貨物托運路程

2.2 消除貨物之間沖突

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

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

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

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

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

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

表6 托運方的托運意愿

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

表7 貨物組合托運意愿期望方差

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

3 結(jié)束語

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