多車程時間窗團購車輛配送路徑研究

中圖分類號：U116.2 文獻標志碼：A DOI： 10.13714/j.cnki.1002-3100.2025.09.023

YANG Jian， WANG Yunpeng（School ofEconomicsand Management，Anhui Universityof Science and TechnologyHuainan 232o1，China）

Abstract：Focusingonthevehicleroutingproblemof groupbuyingdeliveryvehicleswithmultipletripsandcustomertimere quirements.Inresponsetotheloweficiencyandhighcostofgroupbuyingvehicledeliveryconstraintssuchasmaximumvehicle traveldistance，veicleladandieindowarecosidered.Amedintegerprogrammingmodelisonstructedwithtegoalof minimizingtheuseofvehiclesandtotaltransportationdistance，andanimprovedantcolonyalgorithmisdesignedtosolvethe problem;usingrouletewheloperationtoparticipateintheconstructionofsolutions，introducingsimulatedannealingnewsolution acceptancecriteriaand2-optoptimizationoperatorstoavoidgetingstuck inlocaloptimal solutions，andthuschangingthe pheromoeupdatestrategy.Theefectivenessandstabiltyoftheimprovedantcolonyalgorithmhavebeenverifiedthroughvarious scale experimental examples.

Key words： multiple trips; vehicle routing problem; ant colony algorithm; simulated anealing; 2-opt optimization

0引言

隨著電商行業的發展，越來越多的人有意愿在線上購買生活必需品，由此有關日常消耗用品的社區團購行業迅速發展，開展社區團購業務的企業紛紛投入市場，搶占市場份額。社區團購是指以社區為單位，運用社交軟件為平臺，軟件用戶通過軟件小程序購買商品的新零售模式。同時，為減輕末端物流配送車輛對交通和空氣環境的負面影響，國家出臺政策鼓勵采用新能源小型載貨車輛進行末端物流配送，團購模式會采用電三輪貨車作為配送車輛，由于電三輪貨車的容量較小且電量有限，配送過程中往往需要多次往返于配送中心和團長之間。此外，團購模式存在配送服務時間要求，配送車輛需在客戶規定時間前把貨物放到團長處，然后客戶去團長處或自提點自提。隨著市場開拓，社區團購業務逐漸擴大，同時，社區團購也存在因配送路徑不合理而造成運輸成本高的問題，因此，開展社區團購業務的企業應合理規劃配送路徑2?；诖?，本文針對多趟次配送和客戶時間要求，以最小化車輛使用數量和總運輸距離為團購配送制定方案。本文將所研究問題歸類為多車程多時間窗車輛路徑問題（Vehicle Routing Problem with Multiple Trips and Multiple Time Windows，VRPMTMTW）。

目前，少有同時考慮多車程和多時間窗路徑問題的研究，但有學者分別對多車程車輛路徑問題（Vehicle Routing Problemwith Multiple Trips，VRPMT）和多時間窗車輛路徑問題（Vehicle RoutingProblemwith Multiple TimeWindows，VRPMTW）進行研究。國內外學者針對這兩個問題構建過數學規劃模型和啟發式算法來獲取問題近似最優解。在VRPMT方面：Lehmann etal針對最后一公里問題構建兩級VRPMT模型，設計自適應大鄰域搜索算法求解；Wassan etal構建帶回程的VRPMT模型，并設計加入多層局部搜索的兩階段變鄰域搜索算法求解；李琦等以鐵路集卡調度總成本最小為目標構建模型，借助Gurobi精確求解車輛車程任務分配問題，并設計改進遺傳算法求解；王能民等以生鮮配送車輛運輸成本最小及客戶滿意度構建雙目標VRPMT模型，設計兩階段變鄰域搜索和模擬退火相結合算法求解。呂俊杰等以最小成本目標構建多周期VRPMT模型，并設計改進遺傳算法。在VRPMTW方面，Shalabyet al.8針對帶軟時間窗電動汽車優化路徑問題，構建混合整數規劃數學模型，設計自適應遺傳算法求解；Villamil et al以最小化旅行時間為目標構建兩級容量約束VRPMTW模型，設計一種基于混合整數線性規劃（MILP）的分解算法求解；李正雯等等構建帶時間窗的綠色多車型兩級車輛路徑問題，并設計一種集合加權 K-means算法的學習型離散排超聯算法求解；范厚明等以成本最小化為目標構建多中心混合車隊VRPMTW，設計遺傳大鄰域混合算法求解模型。在VRPMTMTW方面，PKabcomeet al12結合多類別產品分配問題構建VRPMTMTW模型，并設計數值實驗驗證模型有效性；WuYet al13考慮車輛載重和客戶時間窗以最小化車輛行駛距離為目標構建VRPMTMTW模型，設計定制的迭代局部搜索算法求解；吳廷映等以最小化車輛數量和運輸成本為目標構建VRPMTMTW，設計改進的自適應大鄰域搜索算法求解。

綜上所述，國內外學者對多車程車輛路徑問題和多時間窗車輛路徑問題分別展開研究且研究成果較多，但少有同時考慮多車程多時間窗車輛路徑問題的研究。因此，本文結合已有研究，針對團購多趟次配送、客戶要求最遲服務時間，考慮車輛載重、車輛滿載最大行駛距離約束下，構建以最小化車輛使用和總配送距離的混合整數規劃模型，設計基于模擬退火和2-opt優化的改進蟻群算法對其求解，通過算法對比驗證該算法的有效性。

1問題描述

本文研究問題描述為：配送中心的配送車輛對“團長”提供配送服務，團購配送一般采用電三輪貨車作為運輸車，車輛從配送中心出發，在滿足約束條件下，車輛完成一個車程的服務任務后需返回配送中心，裝上下一批團長的貨物再進行下一車程的服務任務。同時應滿足以下假設：（1）只有單個配送中心，且車輛完成配送任務后，需返回配送點；（2）已知配送中心位置、團長位置、需求量、車輛最大裝載量和滿電滿載最大行駛里程、行駛速度；（3）車輛載重不得超出最大車輛載重量；（4）車輛為電三輪貨車電量有限，車輛路徑不超過車輛滿載最大行駛里程；（5）每個團長點只能由一輛車輛服務；（6）貨物放置團長處，車輛只需滿足最遲服務時間。

依據上文描述問題，構建以下數學模型：

K 為配送中心運輸車輛集合 ， I 為“團長”序號集合 ， I₀ 為配送網絡所有節點集合 ，其中：0表示配送中心， H 表示車輛被安排的車程集合， w_j 為團長 j 的需求量， W_k 為車輛 k 最大載重， d_ij 為節點 i 到節點 j 間的距離， x_ij^kh 為車輛 k 在 h 車程經過節點 i 后的下個目的地是否為節點 j ， x_ij^kh=1 為下一個節點為 j ，反之 R_k 為車輛 k 的最大行駛距離， S_k^h 為車輛 k 的第 h 段車程集合， h 為車程次數， 為該段配送節點集合中節點的個數。 t_ik 為車輛 k 抵達節點 χ_i 的時間， LT_i 為節點 i 的最遲服務時間。

VRPMTMTW4問題的目標為：使用車輛盡可能少，且總的配送距離盡可能短。在日常物流運輸中，電三輪貨車的租用成本大于車輛行駛配送成本，因此如何在電三輪貨車電量耗盡前，盡可能完成更多的配送任務，那么電三輪貨車的租用數目將減少，租車成本也將降低，因此以車輛租用數目最小化為首要目標，建立數學模型，其目標函數如下：

其中：式（1）和式（2）分別表示最小化用車數量和最小化配送距離的目標函數；式（3）和式（4）表示各團長只能被一輛車服務；式（5）表示車輛按照安排的車程按順序為團長提供服務；式（6）表示車輛應按車程順序執行配送任務；式（7）表示車輛按編號順序依次被調用；式（8）表示車輛每次完成配送任務，需返回配送中心；式（9）表示車輛每次執行配送任務的載重量不超過最大車輛載重；式（10）表示車輛完成所有車程后行駛距離不超過車輛最大行駛距離；式（11）表示車輛每次執行配送任務時不會出現子回路；式（12）表示車輛到達團長的時間不得超過最遲服務時間。

2改進的蟻群優化算法

VRPMTMTW問題屬于配送路徑最優問題，可以選擇蟻群算法求解，螞蟻個體通過感知路徑上信息素的強度來指導自己選擇移動方向，信息素濃度越低，說明該路徑長度越長，反之路徑越短[，隨著信息素的更新，蟻群算法存在易陷入局部最優的問題，為了提升其局部搜索能力，本文通過改進蟻群算法來求解該模型。針對根據信息素和節點間距離來選擇下一個節點的過程，采用輪盤賭運算，通過隨機數降低信息素的相對重要程度，從而擴大了蟻群搜索的范圍，避免快速收斂的同時更有概率獲得全局最優解。針對信息素更新，改進蟻群算法在信息素更新前，加人模擬退火算法，其概率突跳性的特點用于蟻群算法中可以使局部最優解概率性跳出7，然后對模擬退火接受后的解進行2-opt 優化，根據優化后的解對信息素進行更新，避免陷人局部最優。

2.1解的編碼與解碼

多車程路徑問題分為兩層，第一層為車輛路徑，第二層為更換車輛條件，假設有10個團長，則某可行解的編碼如圖1所示。

對該可行解進行解碼操作后，其中，為了服務該10個團長需3輛車，第一輛車有一段車程，路徑為0-1-3-4-5-0；第二輛車有兩段車程，路徑為0-6-7-0和0-2-8-0；第三輛車有一段車程，路徑為 _0-9-10-0 。

2.2初始解的構造

蟻群算法初始解的構造，根據信息素和節點間距離來構造下一個節點選擇概率，用輪盤賭運算選擇下一個節點。假設螞蟻（2號 m 在 χ_t 時刻下一個目的地選擇概率 ，其計算公式為：

式中： τ_ij 為信息素， η_ij=1/d_ij 表示由節點間距離相關的啟發因子， α，β 分別表示信息素重要程度和啟發因子重要程度，allowed表示當前螞蟻 m 未訪問的節點集合。

輪盤賭運算策略，下一個節點選擇公式為：

式中： M 表示蟻群集合 ， ?_m 表示蟻群規模，rand表示（01）間的隨機數。

初始解的構造方式見算法1， tabu_m 為當前螞蟻 ?_m 的禁忌表，記錄已完成的路徑，currentRoute為當前路徑， Rl_k 為表示車輛累計行駛距離，currentTrip為路徑里的當前車程。

算法1：初始解構造。

（1）初始化allowedm， tabu_m ， Y_n ；（2） while ；（3）fori=1：length（allowede）；（4）根據信息素和節點間距離，計算節點選擇概率 ；（5）end for；（6）根據 ，以輪盤賭運算選擇下一個節點Select；（7）if t_ikgt;LT_i 車輛抵達時間超過團長最遲服務時間；（8）依次遍歷剩下可選擇節點，直到找出可服務的節點；（9）如果沒有可服務節點，那么車輛累計行駛距離 Rl_k?+∞ ；（10）else t_ik?LT_i 車輛抵達時間未超過團長最遲服務時間；（11）ifcurrentRoute的累計行駛距離 Rl_k ?R_k ；（12）開辟新的路徑，Select=配送中心，并更新 tabu_m ；（13）更新車輛行駛距離歸零；（14）elsecurrentRoute的累計行駛距離 Rl_kk ；（15）ifcurrentTrip的累計載重量 ?W_k ；（16）開辟新的車程，Select=配送中心，并更新 tabu_m ；（17）更新當下車程的車輛載重歸零；（18）elsecurrentTrip的累計載重量 ?W_k ；（19）Select不變，并更新 tabu_m ；（20）更新當下車程的車輛載重和車輛行駛距離；（21）end if；（22）endif；（23）endif；（24）更新allowedm：剔除加人 tabu_m 的節點;（25）end while。

2.3模擬退火解接受準則

為了避免陷入局部最優解，在蟻群算法中加入模擬退火新解接受準則。把當代最優解作為模擬退火的初始解，生成初始解鄰域解，對比新解和當代最優解，若新解優于當代最優解，則接受，反之，根據解的接受概率判斷是否接受該解，直至模擬退

火完成，其中模擬退火解的接受概率如下：

式中： P（Ans_new） 表示新解的接受概率， e 表示自然指數， f（Ans） 表示解的路徑長度， T 表示溫度變量，模擬退火步驟如算法2所示，其中： ζ∈[0，1 ]表示降溫系數。

算法2：模擬退火。

（1）最優解 Ans_old 為模擬退火算法初始解，初始 T 盡量足夠大；（2）while Tgt;T_min ；（3）隨機產生新解 Ans_new ，并計算新解接受概率 P（Ans_new） ；（4）if P（Ans_new）?rand（0，1） ；（5）新解 Ans_new 替換舊解 Ans_old ；（6）else保留舊解；（7）end if;（8） ；（9） end while。

2.42-opt優化算子

根據模擬退火規則選出被接受的解后，應用2-opt方法對被接受解進行更新以消除最優解中路徑中各小段路徑交叉現象，縮短路徑距離4。其中： Route_rec 表示被接受解中的所有路徑，ind表示第幾段路徑， 2-opt 優化步驟如算法3所示。

算法3：2-opt優化算子。

（1）初始化ind，index=find（ Route_rec= 配送中心）；（2）for ind=1：length（index） ^）-1 ；（3）對每段路徑中的所有不相鄰節點執行刪除，生成操作；（4）if ；（5）刪除該段路徑中邊 和邊 （j，j+1） ； （6）生成新邊，連接邊 （i，j） 和 （i+1，j+1） ；（7）if ?t_ik?LT_i ；（8）新邊替換原邊；（9）elseif保留原來的邊；（10）endif;（11）elseif保留原來的邊；（12）endif；（13）end for；（14）被接受解中的所有路徑進行優化后，2-opt優化完成。

2.5信息素更新

在對被接受解進行2-opt優化后，添加優化解路徑額外的信息素量，其更新方式如下：

式中： τ 為信息素濃度， ρ 為信息素揮發因子， ρ∈（0，1） ， Δτ_ij 表示所有螞蟻從點 i 到點 j 路徑上信息素濃度之和， Δτ_ij^m 表示螞蟻 ?_m 從點 i 到點 j 路徑上信息素濃度， Q 為信息素更新參數， L_rec 為被接受解經過2-opt優化后的路徑長度。

改進蟻群算法的步驟如下：

（1）參數初始化;

（2）根據下一個目的地轉移概率，用輪盤賭運算，在滿足所有約束條件下，構建螞蟻路線，更新禁忌表，生成初始種群；

（3）計算各螞蟻路線長度，找出局部最優解;

（4）以局部最優解為模擬退火初始解，重新構建新解，與局部最優解比較，決定被接受解；

（5）對被接受解應用2-opt方法優化;

（6）信息素更新；

（7）禁忌表清空，返回步驟2，直至達到最大迭代次數。

3實驗仿真與分析

為驗證本文數學模型和改進蟻群算法的有效性，本文使用 Solomon[8算例集，對本文數學模型和改進蟻群算法進行有效性測試，本文的算法由MATLABR2022（a）編程實現，其實驗環境為Intel（R）Core（TM）i5-8300HCPU @ 2.30GHz 2.30GHz處理器。算法參數設置方面，種群規模設為100，最大迭代次數為500，信息素重要程度為0.7，啟發因子重要程度為0.3，信息揮發因子為0.15，信息更新參數為1，模擬退火初始溫度為100，模擬退火冷卻系數為0.99，車輛滿載最大行駛距離為30km/h ，平均車速為 15km/h ，車輛載重為 400kg 。

3.1實驗算例描述

Solomom測試數據集[8根據客戶位置分布分為C型、R型和RC型數據，C型數據位置分布較集中；R型數據位置分布隨機較均勻；RC型數據一部分較集中，一部分分布較均勻，由于本文設計模型設置了車輛最大行駛里程約束，因此數據集中的有些數據離配送中心的距離可能會超過車輛最大行駛距離的一半，因此需對數據集進行篩選，篩選方法為：隨機選擇一個配送中心，以配送中心為圓心，車輛最大行駛距離為直徑，分別在C型、R型和RC型數據中，圈出位于該圓內的客戶點，中小規模數據集依次選擇圓內10、20、30個客戶，大規模數據集依次選擇圓內50、60個客戶。

3.2算例結果及分析

實驗算例采用改進蟻群算法和傳統蟻群算法以及免疫算法求解結果進行對比，每個算例均進行10次測試，統計出各算法的最好結果、最差結果以及運行時間，結果如表1、表2所示。

通過三種算法的對比，在相同參數環境下改進蟻群算法具有有效性，改進蟻群算法由于算法的復雜性，其運行時間略高，在小規模數據集尋優結果上，三種算法的差距不大，結果穩定，在中大規模數據集尋優結果上，改進蟻群算法的最好、最差結果。

4總結與展望

本文研究了團購配送車輛多車程多時間窗車輛路徑問題，以最小化使用車輛數量和總配送距離，考慮車輛載重和滿載最大行駛距離約束，構建相應的混合整數規劃模型。在模型求解算法設計階段，根據蟻群算法易陷入局部最優解問題，引入模擬退火接受準則和2-opt算子并改進信息素更新策略以跳出局部最優解。通過三種類型的Solomom數據集生成不同規模算例，并與傳統蟻群和免疫算法求得的最好解和最差解對比，驗證了算法的有效性和穩定性。本文的改進蟻群算法在中小規模算例中表現好、在大規模算例中求解結果表現穩定。此外，本文在構建模型時并未考慮多車程對于司機工作時間等其他意外情況對配送服務的影響，后續研究將考慮更多符合實際情況，例如平衡司機工作時間、不同車型、多車場、客戶優先級、交通情況等因素納入問題和模型構建中。

參考文獻：

[1]劉天雨．時間窗口約束下社區團購生鮮第三方平臺倉配模式優化問題研究[D].鄭州：鄭州大學，2019.

[2]王丹，讓桂芳．基于智能算法的社區團購配送路徑優化[J].沈陽大學學報（自然科學版），2024，36（1）：48-53.

[3]LEHMANNJ，WINKENBACHM.Amatheuristicforthetwo-echelonmulti-tripvehiclerouting problem withmixedpickupand delivery demand and time windows[J]. Transportation Research Part C，2O24，16O：104522.

[4]WASSAN NAVEED，WASSANNIAZ，NAGY GABOR，etal.The multiple trip vehiclerouting problem with backhauls：For-mulationandatwo-levelvariableneighbourhoodsearch[J].Computersamp;OperationsResearch，2O17，78（C）：454-467.

[5]李琦，魏玉光．帶時間窗的中心站多車程集卡調度優化研究[J].交通運輸系統工程與信息，2024，24（1）：272-281.

[6] 王能民，梁馨月，張萌，等．考慮個體客戶滿意度的多車程生鮮品配送路徑優化[J].運籌與管理，2024，33（4）：14-20.

[7] 呂俊杰，馮謙．基于客戶分流策略的電商促銷下車輛路徑問題研究[J].計算機應用與軟件，2019，36（5）：29-34，111.

[8]SHALABY WAM，KASSEM SS.Two-phase fuzzyreal-time approach forfuzzy demandelectric vehiclerouting problem withsoft time windows[J]. Computers，2024，13（6）：135.

[9]VILLAMILRA，TORRESMR J，JAEGLER A，etal.Stochastictwo-echelonvehiclerouting problemwithtimewindows：Citylogistics case study[J]. International Journal of Shipping and TransportLogistics，2O24，18（2）：223-248.

[10]李正雯，胡蓉，錢斌，等．學習型離散排超聯賽算法求解帶時間窗的綠色多車型兩級車輛路徑問題[J].控制理論與應用，2023，40（3）：549-557.

[11]范厚明，楊成，張躍光，等．混合時間窗下多中心混合車隊車輛路徑優化[J].計算機集成制造系統，2023，29（10）：3529-3546.

[12] P KABCOME，T MOUKTONGLANG，CHIN-CHIA WU. Vehicle routing problem for multiple product types，compartments，andtripswithsofttimewindows[J].IntermationalJournalofMathematicsandMathematicalSciences，O15，2015（Pt3）：126754-126759.

[13] WUY，DUH，SONG H.Aniteratedlocalsearchheuristicforthemulti-tripvehiclerouting problem with multiple timewindows[J]. Mathematics，2024，12（11）：1712-1728.

[14] 吳廷映，魯佳琪，夏洋．多車程多時間窗車輛路徑問題研究[J].工業工程，2024，27（2）：147-157.

[15] 濮陽，宮婧，李德辰，等．淺談蟻群算法在路徑規劃問題中的應用[J].物流工程與管理，2021，43（7）：43-45，26.

[16] 程亮，干宏程，劉勇．基于改進蟻群算法的CVRP問題研究[J]．重慶工商大學學報（自然科學版），2021，38（5）：81-86.

[17] 張立毅，王迎，費騰，等．混沌擾動模擬退火蟻群算法低碳物流路徑優化[J].計算機工程與應用，2017，53（1）：63-68，102.

[18]SOLOMONMM.Algorithmsforthevehicleroutingandscheduling problemswithtime windowconstraints[J].OperationsResearch， 1987（2）：254-265.