城市配送的零擔車貨匹配問題研究

田攀 傅世勇 王紅蕾

摘 ?要：該文從城市配送中裝卸過程對配送的影響入手，研究了多車零擔配送時的裝箱組合問題，將貨物在滿足車輛容積和載重的情況下，采用聚合性層次聚類算法，根據配送目的地的相對距離將貨物組合配送，從而減少裝卸順序對車輛的裝載率影響，同時提高靈活性以應對交付問題，并使用算例進行模擬驗證。為城市配送的配裝組合提供了一個新的解決思路。

關鍵詞：城市配送 ?車輛路徑優化 ?貨物配裝 ?層次聚類算法

中圖分類號：F259 ? ? ? ? ? ? ? ? ? ? ? ? ? 文獻標識碼：A文章編號：1672-3791（2020）10（b）-0222-06

Abstract： This article starts with the impact of the loading and unloading process on distribution in urban distribution， and studies the packing combination problem of multi-vehicle less-than-carload distribution. When the goods meet the vehicle volume and load， the aggregate hierarchical clustering algorithm is adopted. The relative distance of the destination is used to combine and deliver the goods， thereby reducing the impact of the loading and unloading sequence on the loading rate of the vehicle， and at the same time increasing the flexibility to deal with the delivery problem， and use calculation examples for simulation verification. It provides a new solution for the combination of urban distribution.

Key Words： Urban distribution; Vehicle routing optimization; Cargo distribution; Hierarchical clustering algorithm

貨物配載問題（VFP，Vehicle Filling Problem）是一個經典的復雜問題[1]。有大量對裝箱問題的專門研究，其主要方向是在如何提高車輛運載運力的利用率方向。除了對空間或者載重的利用率，在實際使用過程中還會面臨車輛路徑優化問題，因為一旦裝載完成，車輛所經歷的送貨點就已經固定，因此將貨物配載問題與車輛路徑優化問題組合起來研究被認為是一個更為貼近實際使用的研究方向[2]。盡管研究文獻十分豐富，但很少會考慮到卸貨優先級對優化結果的影響，而卸貨過程在城市配送的物流場景中對效率、成該的占比是很大的。配載問題通常采用數學規劃法求解[3]，但是如果模型太簡單則不能對問題進行有效描述，而模型過于復雜又無法求解，配載的復雜性導致目前還很少有完全自動化的配載系統[4]。所以，該文沒有直接研究裝卸順序的算法，而是從消除裝卸順序負面影響的角度來研究在城市配送場景下的配載問題。

1 ?問題描述

很多涉及車輛路徑問題的算法，是聚焦于總里程的節省，重要的原因之一就是里程長短不僅意味著時效性，而且還涉及能源消耗。但城市配送有著自身的特點。城市配送運輸里程短，即便在大中型城市配送距離，單次配送里程大多也在80km以內。相比干線與支線幾百上千公里的配送距離，城市配送中距離對在配送成該的影響比例不大。特別是各大城市推行貨車電動化之后，能源消耗的費用占比大幅下降，追求最小里程的經濟效益進一步降低。而城市配送在裝卸環節的成該占比要高很多，第一，大量存在多點配送，裝卸總耗時占比很大，裝卸用時攤銷到車輛使用成該以及人工成該上時，裝卸所占的成該是很高的。第二，城配過程中大量存在手工裝卸，相比支干線的配送中心的機械化裝卸，這種方式不僅耗時，而且對司機提出了更高的體力要求。城市配送中裝卸的配送相比不管裝卸的配送價格要高很多。第三，裝卸環節可能產生貨損。城市配送大多采用箱式貨車，封閉式的箱體導致卸貨必然遵循先卸貨接近門口的位置，而且如果卸貨優先級沒有設置好，導致先配送的貨物在不能直接裝卸的位置，就可能需要將阻擋的貨物先卸貨，將配送的貨物拿出來之后，再將之前的貨物重新裝箱，不僅耗費司機精力，重復裝卸還可能導致貨損。

因為卸貨順序實際上是決定了車輛的行車路徑，所以通常裝車時就必須考慮行車路徑的影響。進一步來說，按照總路徑最小的目標來擺放貨物，要么可能裝卸不方便，要么方便裝卸方便但是影響了車輛的裝載率，畢竟提高裝載率對貨物的擺放方式是有一定要求的。如果從便于裝卸和提高裝載率的角度出發，送貨路徑就可能與設計的最短路徑出現偏差。因此即便綜合優化方式能夠實現路徑和裝載率的最優，仍然存在最佳卸貨順序與最短行車路徑不一致而導致無法在實際情況下執行的可能。

貨物的裝卸難度很難通過程序量化，所以到底是犧牲運輸里程還是選擇更多的裝卸，通過算法難以權衡，只能讓人看到實物之后依靠經驗衡量，所以很多城配企業更愿意選擇人工調度的方式來完成。但是靠人工的方式，企業的配送規模就很難擴大，這也是城配市場碎片化的原因之一。

如果單臺車輛配送貨物的配送地點不用為了“順路”而導致送貨地點分散，而讓送貨地點集中的貨物組合起來進行配送，則可能帶來兩個方面的好處：一方面配送目的地的聚集，能讓司機在裝卸過程中不大會受到配送順序的制約，從而可以盡可能考慮裝載率。另一方面一旦收貨方因為某種原因出現無法馬上收貨，司機可以靈活地選擇下一個配送地點，而不用付出太多的往返里程代價。特別是交付的貨物中含有延遲懲罰條款時，由于司機能更換交付順序來保證貨物的準時交付，所以能夠有機會提升整體客戶滿意度。盡管這種方式可能不是總路徑最短的最優解，由于送貨點盡可能的集中，考慮到城市配送距離已經較短，因此送貨點之間是否順路影響很小，可以視為綜合情況下的滿意度，因而在實際操作中會具有更高的適應性和靈活度。

2 ?城配零擔配送的數學模型

該文研究的場景，是單個配送中心向城市多個地點的零擔貨物配送的情況，可以轉化成如下描述。

某城市的物流配送中心有若干件待配送貨物，配送中心有配送車輛若干，要求將這批貨物在當日配送完畢，使花費的配送車次最少，且單個車次配送的貨物目的地盡可能的集中。為什么不用車輛而用車次，是因為在城市配送中，為了提高車輛利用率，一般每天車輛都需要配送2～3次，因此用車次更符合實際情況。

在這個問題中，我們假設貨物均可以混裝，每個貨物的體積和重量都小于單臺貨車的容積和載重，且裝載的過程中只考慮配送車輛的載重和容積的限制。涉及的變量定義如下。

待配送有n個貨物，i，j為貨物的編號，i，j∈n;dij為貨物i和貨物j配送目的地之間的距離;wi，wj為第i和第j個貨物的重量，vi，vj為第i和第j個貨物的體積;假設所有的配送車輛車型一致，車輛的最大載重為Wc，最大容積為Vc;最終需要使用m趟車次完成配送，k為車次的編號，k∈m;xik為0，1變量，第i個貨物由第k車次的貨車負責，則xik=1，否則xik=0。

在盡可能聚集的情況下，優先選擇車次最少的方案，然后根據聚集指數優中選優。

3 ?城配零擔配送的算法設計

層次聚類是一種樹形聚類方式。按照構建樹形結構的方式不同，可以將聚類分為自頂向下和自底向上兩種構建方式，分別稱為聚合型層次聚類（Agglomerative Hierarchical Clustering）與分裂型層次聚類（Divisive Hierarchical Clustering）。聚合型層次聚類，也稱自底向上的方法，首先將每一個樣該都稱為一個聚類簇，然后計算簇間的相似度，分層合并，直到最后只有一個簇為止或滿足一定的終止條件[6]。采用聚合性層次聚類算法，對目的地之間的距離相近的貨物優先進行組合，直至達到貨車的裝載上限。最初每個貨物都只裝入一臺貨車，每臺車視為一個簇，然后根據距離情況逐步合并用車，即形成新的聚類簇。即當兩個車（簇）中的兩個貨物目的地的距離，小于其他任意兩個車中貨物目的地距離，則可以說這兩個簇（或者說兩批貨物的目的地）最為集中。在這兩臺車的裝載貨物之和沒有超過單臺貨車載重或者容積的情況下，兩批貨物可合并放入一臺貨車，即形成新的聚類簇。新的聚類簇繼續放回矩陣參與送貨距離的檢查，直至所有的簇的兩兩組合均會超過單車的容積或者載重為止。調整初始組合，尋找更多組合的可能，選擇最優方案。具體算法設計如下。

步驟1：計算所有貨物目的地之間的距離，構成距離矩陣。

步驟2：在距離矩陣中尋找最小的值。假設di1j1最小，則判斷兩個貨物組合是否超出貨車容積或者載重。如果已經超過，則繼續尋找次小值繼續檢查組合可能性。如果并未超過，則兩個貨物可以組合裝車。此時將合并后的車輛（新簇）放回矩陣參與計算，此時新的車輛所經過的送貨點與其他車輛途徑的送貨點的距離會有兩個：一是貨物i1與其他貨物的送貨距離，二是j1與其他貨物的送貨距離，二者取最大值放回矩陣。

步驟3：迭代計算，直至所有簇無法繼續合并。根據此時每臺車輛中放置貨物的編號，即可得出裝配方案。記錄此時所需的車次和聚集指數。

步驟4：更換合并簇的起始點為次小距離，其他條件不變。假設di2j2為僅次于di1j1的最小距離。則從i2與j2兩個貨物的合并開始判斷。之后的判斷均從不低于次小距離的兩個簇開始組合，直至最大距離的簇，如果最小距離的兩個簇沒有在合并簇的過程中消失掉，則考慮最小距離的組合可能。記錄此時的方案和性能參數。通過這種方式在多個可能中尋找最佳方案。

步驟5：繼續更換合并簇的起始點到第三短的距離開始計算，以此類推，直至起始距離大于r。由于大于r的聚積意義已經不大，優先組合的方式找出最佳方案的可能性很低，從降低計算復雜度的角度不再繼續迭代搜尋。最后在車次最少的方案中挑選出index最低的方案作為最終方案。具體流程圖見圖1。

4 ?算例模擬

以某市某日某物流園的某物流配送企業數據為例，該物流公司的車輛均為4.2m箱式貨車，每輛車的載重為2t，容積在15m3，考慮到車輛一般無法剛好滿載，設置90%為目標裝載在率，即不超過13.5m3的容積，r設置為20km。

待送貨物根據送貨地點進行合并之后，一共40個送貨點，每個點的經緯度坐標以及待送的貨物體積和重量具體見表1。

通過Python實現算法最優解需5臺車完成配送，聚積指數為141.917780，方案呈現出較好的聚積效果，如組合方案見表2，送貨地點分布與裝車信息見圖2。

5 ?結語

該文從城市配送的裝卸問題入手，研究了多車零擔配送的配裝問題。通過采用聚合性層次聚類算法，減少因裝卸順序帶來的負面影響，提高了交付不確定的應對靈活性，希望能為城市物流配送面臨的問題提供新思路。

參考文獻

[1] 陸江.基于虛擬物流平臺的多約束配車模型研究[D].北京郵電大學，2018.

[2] 胡振威.共享經濟模式下城市配送車輛調度問題研究[D].西南交通大學，2018.

[3] 李飛.基于層次聚類的生物數據特征選擇算法的研究與實現[D].吉林大學，2019.

[4] 尹超.城鄉商貿物流服務網絡資源優化研究[D].北京交通大學，2019.

[5] 蔡文清.淺析零散物流現狀[J].西部皮革，2017，39（10）：72.

[6] 鄧式陽.基于邏輯Petri網的Web服務組合與優化方法研究[D].山東科技大學，2019.