基于供需匹配優化的多貨品可拆分車輛路徑問題

摘" 要：針對供應鏈上下游企業原料生產運輸問題，提出了供需匹配優化策略，并將部分客戶對不同原料的需求分批次配送，可以確保滿足客戶需求并降低車輛空載率、提高運輸效率，建立了以車輛固定成本和行駛成本之和最小為目標的取送貨車輛路徑優化模型。采用遺傳算法進行求解，設計了供需匹配對編碼策略和車輛路徑調整策略，可以增強全局搜索能力，更有可能獲得最優解。通過算例分析得出最小總成本和最優車輛路徑，并驗證了文章匹配策略和需求拆分策略的有效性，研究成果對生產運輸企業的實際運營具有一定的參考價值。

關鍵詞：供需匹配優化；多貨品可拆分；車輛路徑；遺傳算法

中圖分類號：F253" " 文獻標志碼：A" " DOI：10.13714/j.cnki.1002-3100.2025.03.005

Abstract： Aiming at the production and transportation problem of raw materials for upstream and downstream enterprises in the supply chain， the optimization strategy of supply and demand matching was proposed， and some customers' demand for different raw materials was distributed in batches， which could ensure that customer demand could be met， vehicle empty load rate could be reduced， and transportation efficiency could be improved. A pickup and delivery vehicle routing optimization model aiming at the minimum sum of fixed cost and running cost of vehicles was established. Genetic algorithm is used to solve this problem. The supply and demand matching pair coding strategy and vehicle routing adjustment strategy are designed， which can enhance the global search ability and more likely to obtain the optimal solution. The minimum total cost and the optimal vehicle routing are obtained through experiments and the effectiveness of the matching strategy and demand splitting strategy is verified. The research results have certain reference value for the actual operation of production and transportation enterprises.

Key words： supply and demand matching optimization; multi-commodity split; vehicle routing; genetic algorithm

0" 引" 言

我國現代經濟的發展帶動了以生產和運輸為經營鏈條的供應鏈上下游企業走向規?；?、立體化，客戶的需求也不斷增長。例如在原油生產運輸企業中，石油需要通過多種類型的原油生產得到，而有些客戶只能生產一部分類型的原油，需要別的客戶提供所需原油，同時也能為其他客戶提供自身生產的原油，同時取送貨車輛路徑問題SPDVRP（Simultaneous Pickup and Delivery Vehicle Routing Problem）隨之開始出現。Min[1]于1989年首次提出同時取送貨車輛路徑問題。

企業實際生產運輸中存在客戶之間自行調撥原料的情況，導致配送過程經常出現多批次、少批量運輸，造成車輛空載率較高，因此就需要建立物流管控中心，從全局角度協調上下游客戶之間的原料調撥，對客戶的供應和需求關系進行匹配，以滿足客戶個性化需求，提高運輸效率。于是基于供需匹配優化的取送貨車輛路徑問題BSDMOPDVRP（Based on Supply and Demand Matching Optimization Pickup and Delivery Vehicle Routing Problem）開始被重視。徐倩等[2]基于外賣配送問題建立了成對出現的取送餐節點，設計了自適應大鄰域搜索算法，為實際調度優化提供了理論支持；Dominik[3]設計了取送貨地點一一對應的車輛運輸策略，采用了禁忌搜索算法研究該策略下電動汽車配送的優勢；任騰等[4]將電子商務和取送貨問題結合，設計了個人和電商客戶在同城訂單中的一對一配送策略，來降低車輛空載率；Chemla et al.[5]針對共享單車系統中供需匹配關系未知的問題，建立了調節系統對各站點自行車進行供需分配，確保實時滿足客戶需求；敬鵬程[6]基于眾包外賣配送問題設計了配送員搶單的策略來進行供需匹配，在保證提成和客戶滿意度的情況下優化配送路徑。

此外，由于企業的規模逐漸增大，多種原料的調撥問題開始出現，普通的供需匹配方式顯然無法滿足客戶的實際需求，很多客戶需要車輛分批次配送，由此對基于供需匹配優化的多貨品可拆分取送貨車輛路徑問題BSDMOMCSPDVRP（Based on Supply and Demand Matching Optimization Multi-Commodity Split Pickup and Delivery Vehicle Routing Problem）的研究也開始進入學者們的視野。Chen et al.[7]針對多商品取送貨問題，設計了對頂點處物料需求進行拆分并由多個車輛分批次配送的策略，最大程度降低總成本；張穎鈺等[8]研究了需求可拆分的車輛路徑問題，設計了客戶點能被多次訪問的運輸策略，采用大變異鄰域遺傳算法求解；徐東洋等[9]基于煙草公司卷煙生產和原料調撥問題研究了供需匹配關系不確定的取送貨問題，建立了客戶對多種貨品的需求可任意拆分滿足的優化模型；Hernandez et al.[10]引入多次訪問客戶點的策略來提高車輛的裝載率，并采用變鄰域搜索算法求解最小成本；高振迪等[11]研究了對不同商品可分批次取送貨的車輛路徑問題，設計了可多次服務客戶點的配送策略，并考慮了配送失敗時從倉庫補貨，采用改進的遺傳禁忌算法求解。

綜上所述，雖然學術界對MCSVRPBSDMO問題的各個方面都有一定涉及，但詳細考慮多貨品的供需匹配策略、需求拆分策略的研究相對較少，且鮮有將生產運輸與調度配送問題相結合的研究。本文針對車輛空載率較高問題提出了基于客戶點間距的供需匹配策略，針對多種原料的運輸問題提出了拆分策略和車輛路徑調整策略，并以生產運輸問題為背景進行算例分析，研究成果可以為企業實際運營提供參考。

1" 基于供需匹配優化的多貨品可拆分車輛路徑問題模型

1.1" 問題描述

車輛路徑問題的供需匹配策略主要有一對一訂單匹配、司機（騎手）搶單匹配等，本文設計了基于客戶點間距的供需匹配策略，即在眾多匹配方案中選擇總間距較小的，得到較優的匹配策略。而多貨品問題的需求拆分策略主要有遍歷拆分、據貨品種類或數量拆分等，本文采取的是部分拆分策略，即將同時具有取送貨需求的部分客戶點進行需求拆分，從而更有可能在滿足客戶需求的情況下得到較優的車輛路徑。具體需求拆分策略如圖1所示，假設有兩種原料分別用正方形和圓表示，拆分節點的原料用梯形表示，節點1和節點3分別為客戶1和客戶3的拆分節點，“+”表示送貨需求，“-”表示取貨需求，箭頭表示車輛行駛路線。圖1中客戶1至客戶4均為具有取送貨需求的客戶點，車輛從配送中心出發后訪問客戶1和客戶3時只能滿足其取貨需求，因此就需要將其送貨需求拆分，在訪問客戶2和客戶4之后再去滿足客戶1和客戶3的送貨需求，最終返回配送中心。

本文研究的是基于供需匹配優化的多貨品可拆分車輛路徑問題，假設有一個配送中心來統一調度車輛運輸路徑，一個客戶可能對多種原料有取貨或送貨需求，并且可以由車輛分批次配送。遵循盡可能減少車輛調撥次數和行駛距離的原則進行原料配送方案的規劃，最終基于供需匹配策略來建立以車輛固定成本和行駛距離成本之和最小為目標的優化模型。

1.2" 模型假設

（1）道路交通順暢，天氣晴朗，車輛的行駛速度恒定；

（2）客戶對同一原料的取貨或送貨需求應當一次性滿足，對不同原料的取送貨需求可以由車輛通過多次訪問來滿足；

（3）所有車輛的載重量是恒定且相同的；

（4）每種原料的總需求量不能多于其總供應量。

1.3" 符號說明

A：車輛集合，A=1，2，…，k；V：配送中心和所有客戶點集合，V=0，1，…，i；F：所有客戶點集合，F=1，2，…，i；F：所有客戶節點和拆分節點集合，F=1，2，…，im；E：供需匹配對集合，E=1，2，…，g；N：原料種類集合，N=1，2，…，h；W：訪問次數集合，W=1，2，…，m；v：車輛行駛速度；Q：車輛的最大裝載量；T：車輛最大工作時間；b：客戶i和j之間的距離；c：車輛固定使用成本；c：單位距離的行駛成本；d：客戶i對原料h的送貨需求量；p：客戶i對原料h的取貨需求量；

t：車輛k在供需匹配對g的取貨節點im開始服務的時間；t：車輛k在供需匹配對g的送貨節點jn開始服務的時間；y：0～1變量，如果供需匹配對g由車輛k配送，則其值為1，否則為0；x：0～1變量，如果車輛k第m次訪問客戶點i后直接行駛到客戶點j（第n次訪問），則其值為1，否則為0；L：車輛k第m次離開客戶i后直接行駛到客戶j（第n次訪問）時裝載原料h數量；q：車輛k在第m次訪問客戶i時投放原料h的數量；r：車輛k在第m次訪問客戶i時取出原料h的數量。

1.4" 模型建立

minZ=cx+cbx， m∈W， n∈W" " " " " " " " " " " " " " "（1）

s.t. x=x=1， k∈A， m∈W， n∈W" " " " " " " " " nbsp; " " " " " " " "（2）

x-x=0， j∈V， k∈A， m∈W， n∈W" " " " " " " " " " " " " " " （3）

x≤1， j∈F， m∈W， n∈W" " " " " " " " " " " " " " " " " " " "（4）

Lx≤Q， j∈V， h∈N， m∈W， n∈W" " " " " " " " " " " " " " "（5）

L-q+r-L-Qx≥-Q， j∈F， k∈A， h∈N， m，n∈W" " " " "（6）

L-q+r-L+Qx≤-Q， j∈F， k∈A， h∈N， m，n∈W" " " " "（7）

q=d， i∈F， h∈N， m∈W" " " " " " " " " " " " " " " " " " " " " "（8）

r=p， i∈F， h∈N， m∈W" " " " " " " " " " " " " " " " " " " " " "（9）

y=1， g∈E" " " " " " " " " " " " " " " " " " " " " " " " " " " " （10）

t≤t， k∈A， im∈F， jn∈F， g∈E" " " " " " " " " " " " " " " " " " "（11）

x≤T， k∈A， h∈N， m∈W， n∈W" " " " " " " " " " " " " " "（12）

L=0， i∈V， j∈V， k∈A， h∈N， m∈W， n∈W" " " " " " " " " " " " " "（13）

L=0， i∈V， j∈V， k∈A， h∈N， m∈W， n∈W" " " " " " " " " " " " " "（14）

x≤S-1， k∈A， S？奐V， m∈W， n∈W" " " " " " " " " " " " " "（15）

x∈0，1， y∈0，1， i∈V， j∈V， k∈A， m∈W， n∈W， g∈E" " " " " " "（16）

L≥0， i∈V， j∈V， k∈A， h∈N， m∈W， n∈W" " " " " " " " " " " " " （17）

q，r≥0， i∈F， k∈A， h∈N， m∈W" " " " " " " nbsp; " " " " " " " " " " （18）

式（1）是目標函數，表示車輛的固定使用成本和單位距離的行駛成本之和最??；式（2）表示車輛k的起點和終點都是配送中心；式（3）表示車輛進出平衡約束，即車輛訪問了某個客戶點之后必須離開；式（4）表示每個拆分節點只能被訪問一次；式（5）表示車輛k在運輸過程中任意節點的載重量都不能超過車輛的最大載重；式（6）和式（7）表示裝載平衡約束，即車輛k在第n次離開客戶點j時的裝載原料h的數量等于第n次到達客戶點j時裝載原料h的數量減去在客戶點j投放原料h的數量并加上在客戶點j取走原料h的數量（若沒有需求記為0）；式（8）和式（9）表示要保證滿足客戶所有的取送貨需求；式（10）表示同一供需匹配關系中的取送貨需求節點及其拆分出的需求節點必須由同一車輛進行訪問；式（11）表示同一供需匹配關系中到達取貨需求節點的時間必須早于到達送貨需求節點的時間；式（12）表示車輛k的行駛時間不能超過最大工作時間；式（13）和式（14）表示車輛從配送中心空車出發，完成配送后空車返回；式（15）表示消除子回路約束；式（16）表示0～1決策變量約束；式（17）和式（18）表示非負的連續變量約束。

2" 算法設計

求解MCSVRPBSDMO問題需分析如何在保證滿足供需匹配策略的情況下制定成本較小的車輛路徑，此問題較為復雜。本文首先基于需求拆分策略和供需匹配策略構造初始解，然后采用遺傳算法優化配送路徑。同時引入了車輛路徑調整策略，在滿足供需匹配策略的基礎上，通過擴大解空間增加產生最優解的可能性，算法流程如圖2所示。本文的適應度函數[12]根據式（1）的目標函數變形得到；精英種群選擇采用二元錦標賽選擇策略[13]；交叉采用OX交叉策略[14]；變異采用兩點基因互換的策略[15]。

2.1" 編" 碼

本文采用整數編碼方式對包含多個供需匹配對的解進行編碼，每個供需匹配對包含多個節點。以10個客戶點（編號為1～10）、兩種原料為例，可以構造如表1所示編碼。

其中客戶1至客戶6表示具有取送貨需求的客戶點，按照圖1的需求拆分策略選取了客戶1、客戶3、客戶5的需求進行拆分，拆分節點依次編碼為11、12、13。而客戶7、客戶9表示對兩種原料都只有取貨需求的客戶點，客戶8、客戶10表示只有送貨需求的客戶點。因此可以形成1，2，11、7，8等供需匹配對。

2.2" 初始解的形成

本文根據客戶點之間的供需匹配策略構建初始解，將對不同原料都只有一種需求和具有取送貨需求的客戶點及其拆分出的需求節點分別進行供需匹配，生成初始供需匹配對后儲存到新的解空間中并根據客戶點間距擇優保留。然后打亂供需匹配對應關系，根據總成本最小的優化目標生成一定規模的高質量初始解。

2.3" 車輛路徑調整策略

本文不同于普通取送貨問題的操作都是在確保符合配送約束的情況下進行，為了能夠產生較優解，本文首先不在取送貨的約束范圍內進行迭代，而是先在較大的解空間中不斷優化，最后再根據供需匹配策略對車輛運輸路徑進行調整，從而滿足配送約束。以表1中的10個客戶點為例：

（1）根據載重進行分車后可能會出現同一供需匹配關系中的取送貨需求節點及其拆分出的需求節點不在同一路徑中。

調整前：1-2-7-5-6-（12）-13-（10），3-4-9-（8）-（11）；調整后：1-2-7-5-6-（11）-13-（8），3-4-9-（10）-（12）。

上述例子中，調整前供需匹配對1，2，11、3，4，12、7，8、9，10均出現了取送貨需求節點不在同一路徑中的情況，因此需要將客戶節點11、12互換，將客戶8、10互換，以滿足配送約束。

（2）交叉、變異后，可能會出現同一供需匹配關系中到達取貨需求節點的時間晚于到達送貨需求節點的時間。

調整前：3-7-4-8-1-（11）-5-（10）-12-（2）-（9）-6-13；調整后：3-7-4-8-1-（2）-5-（9）-12-（11）-（10）-6-13。

上述例子中，調整前供需匹配對1，2，11、9，10均出現了到達取貨需求節點的時間晚于到達送貨需求節點的時間的情況，因此需要將客戶節點2、11互換，將客戶9、10互換，以滿足配送約束。

3" 算例分析

3.1" 算例描述

本文采用的數據以Solomon數據集中的RC101為基礎，將其修改為針對多貨品的可拆分取送貨需求數據，據此構建了基于供應鏈上下游企業的生產配送算例。企業設有一個配送中心，同一型號的配送車輛3臺，已知需要服務的客戶有20個，需要配送的原料有兩種，車輛固定成本為50元/輛，燃油消耗成本為1元/單位里程，供需匹配成本為1元/單位里程。

3.2" 參數分析

本文利用Python編寫程序對算例進行模擬，采用遺傳算法求解，其參數設置如表2所示。

3.3" 算例結果

求解結果：車輛固定成本100元（兩輛車），行駛成本530.736 6元，總成本630.736 6元。最優車輛路徑如表3所示（其中0～19為客戶節點，20～24為拆分出的需求節點），最優車輛路徑圖如圖3所示，三角形代表客戶點，橫縱坐標代表客戶點所在位置。最優車輛路徑對應的供需匹配成本為573.874 08，供需匹配結果如表4所示，供需匹配結果圖如圖4所示，正方形代表客戶點，橫縱坐標代表客戶點所在位置。

結合表2、表3和圖3、圖4可以得到車輛最優配送路徑中各客戶點都盡可能和離自己較近的客戶點進行路徑連接，而不一定完全按照供需匹配順序配送。同時供需匹配結果中各客戶點也都盡可能以就近原則進行供需匹配，因此能得到較優的供需匹配結果，而本文采用了2.3的車輛路徑調整策略，將較優的配送路徑據此供需匹配結果進行調整，則能夠在確保滿足配送約束的前提下獲得最優車輛運輸路徑。

3.4" 供需匹配有效性驗證

為驗證本文供需匹配策略的有效性，分別采用一對一訂單匹配策略（策略1）、司機（騎手）搶單匹配策略（策略2）和本文的匹配策略（策略3，見表1）進行配送，將車輛總成本之和最小作為優化目標。按照參數分析所得結果設置實驗，每組運行10次，結果如表5（最優值、最差值、平均值均代表總成本）和表6（最優值、最差值、平均值均代表匹配成本）所示。

結合表5和表6可以得到采用策略3的供需匹配策略進行路徑優化結果要優于策略1和策略2，雖然策略1的總成本和供需匹配成本都比較穩定，但解空間偏小，很難有大幅度的優化，會出現行駛距離較長的情況；而策略2雖然最優值和策略3接近，行駛距離都相對較短，但其穩定性較差并且求解效率難以保證。因此，策略3是相對較好的選擇，其更有可能得到較優的供需匹配結果和車輛運輸路徑。

3.5" 可拆分的多貨品有效性驗證

為驗證本文需求拆分策略的有效性，分別采用遍歷需求拆分策略（策略1）、本文需求拆分策略（策略2，見圖1）進行配送，將車輛的總成本最小作為優化目標。按照參數分析所得結果設置實驗，每組運行10次，結果如表7（最優值、最差值、平均值均代表總成本）所示。

從表7中可以得到采用策略2的需求拆分策略進行路徑優化結果要優于優于策略1，策略1雖然可以確保滿足取送貨約束條件，同時能更靈活的調整配送路線，但也會導致拆分的需求節點過多，造成車輛訪問次數較多，降低穩定性，增加問題復雜性和運輸成本。因此策略2更有可能得到高質量的解，更加適用于多種原料的取送貨車輛路徑問題。

4" 結" 論

本文將生產運輸與調度配送問題相結合，建立了以車輛固定成本和行駛成本之和最小為目標的MCSVRPBSDMO模型，并提出了車輛路徑調整策略，采用遺傳算法進行求解。通過改進的Solomon數據集進行算例分析，得出了較優的參數取值并進行實驗，最終得到了最優車輛路徑和最小總成本，同時也驗證了本文供需匹配策略和多貨品需求拆分策略的有效性，表明其在求解質量和效率上都具有明顯優勢，可以幫助企業節約配送成本，對理論研究和企業實際運營提供了很好的借鑒意義。由于企業在實際生產過程中可能會出現意外情況，影響供需匹配對應關系，因此未來在模型上可以考慮加入供應量不確定的問題，求解上也可以結合禁忌搜索算法、模擬退火等算法進行進一步優化。

參考文獻：

[1]" MIN H. The multiple vehicle routing problem with simultaneous delivery and pick-up points[J]. Transportation Research Part A General， 1989，23（5）：377-386.

[2] 徐倩，熊俊，楊珍花，等. 基于自適應大鄰域搜索算法的外賣配送車輛路徑優化[J]. 工業工程與管理，2021，26（3）：115-122.

[3]" DOMINIK G. Granular tabu search for the pickup and delivery problem with time windows and electric vehicles[J]. European Journal of Operational Research， 2019，278（3）：821-836.

[4] 任騰，羅天羽，谷智華，等. 考慮同時取送貨的城市物流共同配送路徑優化[J]. 計算機集成制造系統，2022，28（11）：3523-3534.

[5]" CHEMLA D， MEUNIER F， WOLFLER CALVO R. Bike sharing systems： Solveing the static rebalancing problem[J]. Discrete Optimization， 2013，10（2）：120-146.

[6] 敬鵬程. 基于城市路網眾包搶單外賣配送動態路徑優化研究[D]. 重慶：重慶交通大學，2021.

[7]" CHEN Q F， LI K P， LIU Z X. Model and algorithm for an unpaired pickup and delivery vehicle routing problem with split loads[J]. Transportation Research Part E： Logistics amp; Transportation Review， 2014，69（3）：218-235.

[8] 張穎鈺，吳立云. 多中心半開放式送取需求可拆分的車輛路徑研究[J]. 計算機應用研究，2022，39（8）：2312-2316.

[9] 徐東洋，李昆鵬，鄭飄，等. 多車場多車型多品類供需未匹配與可任意拆分取送貨車輛路徑問題優化[J]. 管理學報，2020，17（7）：1086-1095.

[10]" HERNANDEZ-PEREZ H， et al. Heuristic algorithm for the split-demand one-commodity pickup-and-delivery travelling salesman problem[J]. Computers amp; Operations Research， 2018（97）：1-17.

[11] 高振迪，計明軍，孔靈睿，等. 多商品分批次取送貨的模糊需求車輛路徑問題[J]. 運籌與管理，2022，31（11）：59-64.

[12] 孫青偉，張楊. 帶同時取送貨的選址—多車型路徑問題研究[J]. 交通運輸工程與信息學報，2017，15（2）：100-104，118.

[13] 張琛，詹志輝. 遺傳算法選擇策略比較[J]. 計算機工程與設計，2009，30（23）：5471-5474，5478.

[14] 郭慶騰，董學士，李清順. 基于自適應大鄰域搜索的遺傳算法求解VRPTW研究[J]. 青島大學學報（工程技術版），2023，38（2）：1-9.

[15] 田帥輝，歐麗英. 基于改進遺傳算法的帶時間窗城市配送路徑多目標優化[J]. 物流科技，2021，44（11）：7-12，17.

收稿日期：2024-01-23

作者簡介：史" 銘（1998—），男，山西長治人，太原科技大學經濟與管理學院碩士研究生，研究方向：路徑優化；莫思敏（1977—），本文通信作者，女，山西太原人，太原科技大學經濟與管理學院，教授，博士，研究方向：智能優化、機器學習。

引文格式：史銘，莫思敏. 基于供需匹配優化的多貨品可拆分車輛路徑問題[J]. 物流科技，2025，48（3）：21-25.