基于聚類與改進蟻群搜索的配送中心車貨匹配方法

摘要：文章針對物流配送中心的配送車輛在運輸過程中的裝卸貨時長、配送車輛行駛時長以及車輛的裝載率等問題，構建以配送中心的運營后成本為目標的車貨匹配模型，在模型中考慮了裝卸貨時長、車輛行駛時長以及車輛的裝載率等現(xiàn)實因素，通過對該模型的求解為配送中心提供最優(yōu)匹配方案。該模型先將貨物的配送點進行聚類，隨后通過對蟻群算法螞蟻選擇下一節(jié)點的概率公式進行了改進，將下一節(jié)點需要配送貨物的重量加入了考量，并采用了一種獎懲機制用作蟻群算法信息素的更新策略和一種隨迭代次數(shù)而變化的信息素揮發(fā)因子，用于提高傳統(tǒng)的蟻群算法的收斂速度。用于求解該車貨匹配模型。然后通過仿真實驗驗證模型和算法的有效性，為物流配送中心的車貨匹配提供了一個新的解決思路。

關鍵詞：車貨匹配；聚類；蟻群算法；信息素

中圖分類號： F49;U492.3" 文獻標志碼： A"" DOI：10.13714/j.cnki.1002-3100.2023.20.012

Abstract： This article focuses on the issues of loading and unloading time， driving time， and loading rate of distribution vehiclesl in logistics distribution centers during transportation. A vehicle cargo matching model is constructed with the goal of post-operationall costs of the distribution center. The model takes into account practical factors such as loading and unloading time， vehicle drivingl time， and vehicle loading rate. By solving the model， the optimal matching scheme is provided for the distribution center. Thel model first clusters the distribution points of goods， and then improves the probability formula of ant colony algorithm ants selectingl the next node， taking into account the weight of goods to be distributed at the next node， and uses a reward and punishmentl mechanism as a new strategy of ant colony algorithm pheromone and a pheromone volatilization factor that changes with the numberl of iterations to improve the convergence speed of traditional ant colony algorithm and to solve the vehicle cargo matching model. Then， the effectiveness of the model and algorithm was verified through simulation experiments， providing a new solution for thel vehicle cargo matching in logisties distribution centers.

Key words： vehicle cargo matching; clustering; ant colony algorithm; pheromone

0引言

隨著社會經(jīng)濟的不斷發(fā)展，越來越多的企業(yè)開始著眼于物流運輸領域的發(fā)展，以滿足不斷增長的物流需求。商品、服務和信息的流通速度也在不斷提升，這對于快速、準確地滿足消費者需求至關重要。而車貨匹配作為物流行業(yè)中的重要環(huán)節(jié)，直接關系到物流成本和服務質量，是物流運作中不可或缺的一部分。

車貨匹配問題是一個NP-hard 問題，它具有很高的復雜度。它需要考慮多種因素，如貨物的重量、體積、數(shù)量，車輛的載重、運輸速度、行駛路線等。不同的貨主和運輸公司對于物流服務的需求也存在差異，需要根據(jù)實際情況進行匹配。除此之外，車貨匹配還需要考慮到實際運營的情況。求解難度大，用于求解該問題的算法的優(yōu)劣也將直接影響求解的優(yōu)劣和效率。為了更好地求解車貨匹配問題，研究者們提出了多種算法和模型。

文獻[1]綜合考慮了車輛和貨物的不同屬性對匹配方案的影響，提出了一種基于車輛和貨物屬性的“一對多”車輛和貨物匹配模型，在滿足每輛車重量限制的情況下獲得最高的整體利潤。文獻[2]將車貨匹配度定義為屬性匹配度和環(huán)境影響度兩部分，并通過AHP （層次分析法）方法量化兩者的重要性，并將車輛、貨物、匹配組合和時間映射到貝葉斯網(wǎng)絡節(jié)點來構建靜態(tài)貝葉斯網(wǎng)絡和動態(tài)貝葉斯網(wǎng)絡，提出了IDBN的求解算法。文獻[3]建立了貨物運輸020平臺的車輛路徑模型。將傳統(tǒng)車輛路徑問題中車輛來源的差異，以及貨主提貨點和交貨點之間的一一對應關系，將半開放、多個倉庫、多車輛類型、起訖點對、裝載限制和軟時間窗約束等約束條件引入所提模型并用一種改進遺傳算法作為求解工具。文獻[4]研究開發(fā)并評估了在車輛貨物匹配（VCM）平臺上聯(lián)合使用改進方法對卡車和貨物進行配對。文獻[5]將車貨匹配問題轉為雙重序列決策問題，提出高效算法。構建數(shù)學模型，抽象成雙重序列決策，應用雙重指針網(wǎng)絡算法求解。文獻[6]在分析車貨匹配參與方需求基礎上，建立了多目標優(yōu)化模型，目標包括最大化送達時效滿意度、最小化運輸成本和最大化平臺收益。采用改進的帶精英保留策略的快速非支配排序遺傳算法，引入精英選擇系數(shù)增加種群多樣性，結合自適應思想調整迭代過程中的交叉變異概率。文獻[7]從多車零擔配送過程中裝卸環(huán)節(jié)對配送影響的角度出發(fā)，研究了裝箱組合問題。在確保車輛容積和載重滿足要求的前提下，采用聚類算法，并根據(jù)配送目的地之間的相對距離對貨物進行組合配送。文獻[8]將公有區(qū)塊鏈的相關技術運用到車貨匹配系統(tǒng)的交易過程，并通過數(shù)據(jù)模擬了在車貨匹配平臺中進行的一次全過程交易。

研究者們采用了不同的方法對車貨匹配問題進行了研究，不僅提高了車輛和貨物匹配的效率，還為物流企業(yè)提供了理論參考?？傮w來看，發(fā)現(xiàn)車貨匹配的研究難點主要在于如何建立高效的匹配模型和匹配算法，同時兼顧運輸成本和運輸效率的優(yōu)化，解決實時匹配的問題，提高匹配的準確性和效率等方面。而當下眾多研究集中在物流信息平臺上，主要聚焦于技術架構和商業(yè)運營等領域，平臺核心的車貨匹配業(yè)務方面的探討相對較少。特別是目前車貨匹配研究主要聚焦在物流配送、貨物運輸、整車運輸和城市配送等領域，對于配送中心的末端配送研究較少，且考慮因素大多也較為簡略。大部分研究實際應用效果并不明顯，存在著與實際情況的脫節(jié)，這一方面可能與模型構建不足和算法設計的不夠成熟有關。因此本文針對配送中心現(xiàn)存的問題進行分析，從而提出一種基于聚類與改進蟻群搜索的車貨匹配方法。

1模型構建

1.1問題描述

本文研究單個配送中心向多地點進行貨物配送，因其具有分散性、差異性和多樣性等特點，這種配送存在大量的人工裝卸、高裝卸成本、高耗時、對司機身體素質考驗大以及貨損等問題。卸貨順序很大程度上會影響車輛行駛路線，因此針對這種情況下的車貨匹配應綜合考慮卸貨順序和裝載率等因素，制定合理送貨路線，提高效率降低成本。當下的物流中心配送區(qū)域性較強、交通條件較好，運輸里程相較于其他物流運輸短，特別是在當下新能源汽車在物流行業(yè)中應用廣泛。配送過程中可以不用太過關注單次配送的里程對用車成本的影響問題，應著重關注裝載率、裝卸時長等因素，針對以上情況，本文構建了一個考慮集中送貨的車貨匹配模型，該模型先將貨物的配送點用DBSCAN聚類算法“進行聚類，然后再將聚類的結果合理地分配到各配送車輛。在該模型中，司機在選擇下一個配送點時更加具有靈活性，因為他們不需要花費太多時間在往返路程上，這可以減少總里程和提高司機靈活性。

1.2模型假設

為了方便構建數(shù)據(jù)模型，針對上述問題作出如下假設：貨物均可以混裝；每個貨物的體積和重量都小于單臺貨物的載重和容積；待匹配車輛的運輸能力等性質已知；待匹配貨物的運輸需求等性質已知；待匹配貨物的出發(fā)地和目的地均在待匹配車輛的行駛能力范圍內；過程中除了要考慮配送車輛的載重和容積的限制還要考慮裝卸貨的順序；某單個配送中心有若干件待配送的貨物；配送中心有配送中心所屬車輛若干，社會車輛若干；要求將這批貨物在當日配送完畢。

1.3模型參數(shù)及變量的定義

本文模型構建需要的參數(shù)說明如表1所示。

假設某貨物物流平臺有p輛待匹配的車輛，記車輛集合C={c?，c?，…，c，}， 每輛貨車c，的最大載重為W， 最大容積為;有；個待匹配的貨物，記貨物集合G={G，G?，…，G，…，G}，" 記貨物i與貨物j配送目的地之間的距離為d， 記車輛c，和貨物i之間的一個匹配關系為X。

由所有匹配關系X 構成的p行j列的矩陣為車貨匹配問題的一個匹配方案，即為問題的一個解，記作

的第p 行向量表示車輛c，的匹配方案，第j列向量表示貨物；的匹配方案。

從上文的問題分析中可知，對于這一問題，我們在車貨匹配過程中，要盡可能使匹配方案中的貨物集中，可對貨物的配送點進行聚類，本文采取DBSCAN聚類，聚類后，原貨物集合G則可表示為g={gy，g?，…，g}。其中g.表示聚類后的某一個簇，根據(jù)DBSCDN聚類的規(guī)則，將輸出的每一個噪聲點都當作一個簇，則該簇中可能有多個配送點或者只有一個配送點，并計算含有多個貨物點的簇中心坐標。

對于某一輛車，其裝載率（ZR）， 這里定義滿載為1，其計算公式如下。

而對于某一匹配方案S的裝載率（SZR）為所有貨車的裝載率之和與匹配關系之和的比，具體計算公式如下。

通過上文的分析，對于某一配送車輛，因為其配送貨物的聚集程度較高，在配送的過程中可以忽略其裝卸時間對車輛配送時長的影響，可將時長問題簡化為僅考慮車輛的行駛時長。則有，某一車輛的行駛時長！公式為：

某一方案的行駛時長為St，，

1.4 模型建立

本節(jié)以降低物流配送中心車貨匹配的運營成本作為主要研究方向，通過上文的分析，本節(jié)主要就配送中心配送車次、配送車輛的行駛時長以及配送車輛的裝載率來衡量配送中心的運營成本。以配送中心發(fā)出車次最少、配送車輛的行駛時長最短和配送車輛的最大裝載率作為目標。設一共可供選擇的方案個數(shù)有n個。優(yōu)化目標為最小化車次乙、最少配送時長Z?和最大化裝載率Z， 模型如式（6）—（17） 所示。

在模型的約束條件中，式（8）和式（9）表示在匹配的過程中，將聚類簇當成一個配送點進行匹配，該簇中的所有貨物的體積和重量不能超過當前車輛的剩余載重和容積。式（10）表示對于每一輛貨車，所裝載的貨物的總質量，不超過貨車的額定載重；式（11）表示對于每一輛貨車，所裝載的貨物的總體積，不超過貨車的額定容積。式（12）表示所有貨物必須裝載完畢。式（13）和（14）表示車輛合并到不能合并為止，即任意兩臺車無法繼續(xù)合并，任意車輛cn、C 貨物合并后其裝載貨物的體積不超過c 、Cz的額定容積或者額定載重。式（15）表示納入車貨匹配的車輛必須在調度中心的可調度范圍之內。式（16）表示每一貨物只能裝入一輛車。

2算法設計

2.1算法選擇分析

結合本文提出的車貨匹配模型的特點選取蟻群算法（AOC）作為模型求解的基礎算法，并在算法信息素的更新過程中提出了一種獎懲機制來對其進行優(yōu)化。

蟻群算法（AOC）四的基本思想是利用信息素來引導螞蟻選擇路徑，從而找到優(yōu)化問題的最優(yōu)解。螞蟻尋找食物的行為是蟻群算法的基礎。螞蟻在搜索過程中會根據(jù)環(huán)境中的信息素強度做出決策，同時在其行走的路徑上釋放信息素，從而影響其他螞蟻的選擇。信息素的強度會根據(jù)路徑的優(yōu)劣進行更新，使得經(jīng)過優(yōu)質路徑的信息素強度增加，從而吸引更多螞蟻走同樣的路徑。

2.2傳統(tǒng)的蟻群算法

蟻群算法的基本思想是利用信息素來引導螞蟻選擇路徑，在t 時刻螞蟻k從節(jié)點i轉移到節(jié)點j的概率為

其中， r（t） 為信息素濃度；α為信息素啟發(fā)因子，β為期望啟發(fā)因子，η，=1/d， 為啟發(fā)信息，d， 為路徑長度。η，為城市i到城市j的啟發(fā)式因子； allowed.為螞蟻k下一步被允許訪問的節(jié)點集合。

螞蟻會在行走的路徑上釋放信息素，從而影響其他螞蟻的選擇，因此需要對信息素進行更新，更新公式如下。

式中，p 為信息素揮發(fā)因子，△r（t） 為螞蟻的信息素的整量，m為螞蟻數(shù)量，式中Q為常量表示信息素的強度，△r（t） 為第k只螞蟻的信息素整量，L?為螞蟻在本次迭代中所走過的路徑長度。

2.2算法改進策略

2.2.1選擇概率改進

在配送中心配送貨物的過程中，一般來說車輛都是從配送中心出發(fā)，配送完貨物之后再回到配送中心，所以在用蟻群算法對其進行求解的時候，不能簡單地直接用歐式距離求解當前時刻的位置到終點的距離。同時，配送的時候僅僅考慮距離問題是遠遠不夠的，因為當前配送點距離接下來的兩個配送點距離相同或接近，出于對車輛節(jié)能的考慮，應當先派送較重的貨物。故此，本文將蟻群算法的選擇概率進行了改進，公式如下。

μ、λ是對傳統(tǒng)蟻群算法中螞蟻k在t 時刻選擇下一個節(jié)點的概率和考慮下一個節(jié)點貨物重量的影響設置的權重，滿足μ+λ=1。p（（t） 是綜合考慮后螞蟻選擇下一個節(jié)點的概率，p（t） 是僅考慮貨物的總量從而選擇下一個節(jié)點的概率。m，表示下一個節(jié)點j的待配送貨物的重量， W 為配送車輛的額定載重。

2.2.2改進信息素更新策略

為了改善蟻群算法的收斂速度，本文提出了一種獎懲機制來更新路徑上的信息素。具體來說，我們采用獎勵措施來增加最優(yōu)路徑上的信息素，同時采取懲罰措施來減少最差路徑上的信息素。這種方法可以加速算法的收斂速度。其信息素更新策略公式如下。

其中，L?、L%分別為當前迭代中最優(yōu)路徑和最差路徑的長度， L，為當前迭代的第k只螞蟻走過的路徑長度，Q為常量。

2.2.3改進信息素揮發(fā)因子

因為路徑規(guī)劃具有特殊性，所以在不同的階段中，需要采用不同的信息素揮發(fā)因子p的取值。如果p 取值過大，會導致路徑上的信息素揮發(fā)過快，從而不利于算法的收斂。相反，如果信息素長時間積累，算法則可能會陷入局部最優(yōu)解。因此，本文采用一種動態(tài)調整的方法來改進p 的取值。在算法的初始階段，設定一個較大的p 值，以擴大搜索范圍；在后續(xù)的迭代中，則采用不斷減小p 的方式，以加快算法的收斂速度。改進公式如下。

其中， p…為信息素揮發(fā)因子的最小值，N為當前迭代， N.為最大迭代數(shù)。

2.3算法步驟

改進的蟻群算法具體步驟如下，算法流程如圖1所示。

Stepl：初始化算法中的各個參數(shù)。

Step2：將所有螞蟻置于起點，并將該點加入禁忌表。

Step3：利用式（21）計算轉移轉態(tài)概率，并選擇下一個節(jié)點，如果該節(jié)點滿足模型Z?、Z?、Z，約束條件，則選擇，并將該節(jié)點加入禁忌表，反之不選。并記錄每只螞蟻走的路徑L。

Step4：計算本次迭代的最優(yōu)解，并對在對應的匹配矩陣中的X;賦值為X，=1， 得到第n次迭代中第a 個螞蟻的匹配方案，若優(yōu)于歷次迭代，則替代當前的最優(yōu)解。

Step5：按照式（23）更新路徑的信息素，按照式（25）更新信息素揮發(fā)系數(shù)。

Step6：判斷是否達到最大迭代次數(shù)，若是，輸出最優(yōu)解。若否，返回Step2。

Step7：輸出匹配方案。

3實驗分析

3.1實驗設置

實驗的運行環(huán)境為Windows10操作系統(tǒng)、CPU3.3GHz、內存12GB， 使用python的sklearn對上文提到的車貨匹配模型進行仿真求解。本文選取一個配送中心，共有配送車輛5輛，每輛車的信息如表2所示，有50件不同的待配送的貨物，由于數(shù)據(jù)較多，只展示部分數(shù)據(jù)如表3所示。算法參數(shù)設置如表4所示。

送貨地點分布如圖2所示，中心位置點為配送中心所在位置。

3.3結果分析

首先聚類結果如圖3所示。

圖中黑色點表示聚類輸出的噪聲點，即在該配送點附近，沒有與之集中的貨物。根據(jù)算法步驟的設計，使用改進的蟻群算法對其進行求解，得出最優(yōu)匹配方案，匹配結果如表5所示。

為了驗證模型和改進的AOC算法的有效性，選取標準的蟻群算法和遺傳算法與本文提出改進的算法進行對比。算法迭代對比如圖4所示。

各算法計算的匹配方案配送貨物的車輛行駛時長、車次、裝載率見表6，行駛時長與裝載率對比如圖5所示。

由以上可知，相較于遺傳算法和傳統(tǒng)的蟻群算法，在改進的蟻群算法求解出的匹配方案中，每輛貨車的裝載率更高、配送總路徑在保證裝載率的同時也相對更短，配送車輛的行駛時長也較短。

3.3.1匹配結果分析

如表5所示，改進蟻群算法求解該問題，從匹配結果來看，每輛車的裝載率足夠大，同時通過貨物的配送順序以及貨物的分布圖，也可直觀地看到，在配送過程中，距離當前配送點相近的配送點之間的配送順序是先配送重量大的貨物，由此可知，算法的改進是有效的。

3.3.2收斂分析

圖4為三種算法求解該模型的收斂對比圖，由此可以看出，本文采用的隨迭代次數(shù)自適應變化的放大系數(shù)，在求解該問題時，相較于遺傳算法、傳統(tǒng)的蟻群算法有良好的效果。算法的收斂速度較之更快。

4結語

本文以城鄉(xiāng)配送中心車輛的配送行駛時長、車輛的裝載率以及配送中心發(fā)出的車次為優(yōu)化目標，提出了一種基于城鄉(xiāng)配送中心的車貨匹配模型，進而提出了一種基于聚類與改進蟻群搜索的車貨匹配方法，將聚類的思想和蟻群算法相結合，并對螞蟻選擇下一節(jié)點的概率公式做了改進，將下一節(jié)點需要配送貨物的重量加入了考量，并采用了一種獎懲機制用作蟻群算法信息素的更新策略和一種隨迭代次數(shù)而變化的信息素揮發(fā)因子，用于提高傳統(tǒng)的蟻群算法的收斂速度，在很大程度上增加了螞蟻選擇最優(yōu)路徑的可能性。算法后期，可以減小啟發(fā)信息帶來的影響，有效避免了局部最優(yōu)情況的發(fā)生。

實驗結果表明，本文提出的基于聚類改進蟻群搜索的車貨匹配方法擁有良好的求解效率，同時能夠得到比傳統(tǒng)的蟻群算法更優(yōu)的匹配方案，能夠在節(jié)約配送成本的基礎上，提高配送中心的配送效率。并為配送中心的車貨匹配業(yè)務提供了技術支撐。

參考文獻：

[1] HE Xinyun，ZHANGYuan，LEZhu，etal.Research on \"one-to-many\"vehicle and cargo matching optimization problem based on improved genetic algorithm[C]/20227th International Conference on Intelligent Information Technology.NewYork：Association for Computing Machinery，2022：7-15.

[2] TIAN Ran，WANGChu，MAZhongyu，etal.Research on vehicle-cargo matching algorithm based on improved dynamic Bayesian network[J/OL].Computers amp;Industrial Engineering，2022，168.[2023-02-23].https：//doi.org/10.1016/j.cie.2022.108039.

[3] LIU M L，ZHANG C，WU Q L，etal.Vehicle routing problem with soft time windows of cargo transport O20 platforms[J].International Journal of Simulation Modelling，2021，20（2）：351-362.

[4] ZHONG Jiuwu，YANGZhaojun，SUNJun.A hybrid approach with joint use of tag and rating for vehicle and cargo matching [C]/2021 IEEE International Conference on Industrial Engineering and Engineering Management （IEEM）.IEEE，2021：1397-1401.

[5]蔡岳，王恩良，孫哲，等.基于雙重指針網(wǎng)絡的車貨匹配雙重序列決策研究[J].計算機科學，2022，49（S2）：111-119.

[6]倪少權，羅軒，肖斌.考慮三方利益的車貨匹配優(yōu)化[J].西南交通大學學報，2023，58（1）：48-57.

[7]田攀，傅世勇，王紅蕾.城市配送的零擔車貨匹配問題研究[J].科技資訊，2020，18（29）：222-227.

[8] 王維祺，葉春明.區(qū)塊鏈技術在車貨匹配平臺上的應用[J].計算機系統(tǒng)應用，2019，28（11）：72-78.

[9] ESTER M，KRIEGEL H P，SANDER J，etal.A density based algorithm for discovering clusters in large spatial databases with noise[C]/Proceeding of the 2nd the International Conference on Knowledge Discovery and Data Mining.Portland： AAAI Press，1996，226：231.

[10]DORIGO M，GAMBARDELLA L M.Ant colony system：A cooperative learning approach to the traveling salesman problem J].IEEE Transactions on evolutionary computation，1997，1（1）：53-66.