低碳背景下求解同時取送貨車輛路徑問題

摘 要：為響應國家“雙碳”戰略的號召，本文研究了物流行業中的配送與包裝器具回收問題，通過優化物流過程減少碳排放，助力實現碳達峰與碳中和的目標。提出自適應變鄰域遺傳算法（AVNSGA）來求解同時取送貨車輛路徑問題（VRPSDP）。通過使用Solomon數據集進行算例測試，并將AVNSGA與傳統的遺傳算法（GA）進行了性能對比，結果表明AVNSGA在求解效率和優化解質量方面具有顯著優勢，車輛路徑的總成本優化效果提升幅度達到了10%以上，同時碳排放量縮減了67%，也展示該算法在物流領域節能減排、實現可持續發展目標方面的應用潛力。

關鍵詞：同時取送貨車輛路徑；遺傳算法；自適應機制；變鄰域搜索

中圖分類號：F252.14；X196" 文獻標識碼：A" 文章編號：1673-260X（2025）01-0026-08

在汽車零部件配送過程中，通常采用“送貨和取回”的方式，即物流企業在將零部件配送至客戶收貨地的同時，也將上次配送使用的非標準包裝器具取回，并經過清洗、維護等環節后，再次投入使用。這種方式有助于減少一次性包裝材料的使用，促進包裝器具的循環利用，從而減少廢棄物產生，降低整個物流過程中的碳足跡，符合綠色物流的發展方向，助力汽車制造業向更加環保、可持續的方向轉型。對于汽車零部件配送與包裝器具取回的問題，可抽象理解為同時取貨和送貨車輛路徑問題（VRPSPD），VRPSPD與傳統VRP的差異在于需要在路徑規劃過程中同時考慮取貨和送貨需求，車輛在行駛過程中的負載是取貨貨物和待配送貨物混合而成的動態變化狀態，相較于傳統VRP問題具有更高的復雜度。在汽車工業物流領域，VRPSPD的實際應用較為廣泛，對于更快速、高效地求解同時取貨和送貨車輛路徑問題具有較高的實用價值意義。

Min于1989年首次研究同時取貨和送貨車輛路徑問題[1]，將其建模為一個混合整數規劃問題，開發了自適應大鄰域搜索（ALNS）算法[2]。Avci和Topaloglu將閾值調整機制整合到禁忌搜索中，同時包含一種自適應自調節策略[3]。高遠等人研究了城市物流配送中的電動車輛路徑優化問題，考慮了電動汽車的充電特性以及車輛多行程和需求點的雙向貨流，建立了電動車輛路徑問題（EVRPMTSPD）模型，通過數值實驗驗證了模型與算法的有效性[4]。陳希瓊等人研究了同時取送貨的選址—路徑問題（LRPSPD），建立了一個雙目標模型，并采用多蟻群算法生成多個以信息素為關聯的初始解，并使用變鄰域搜索算法進行優化。通過構造四類鄰域結構，優化了初始解與變鄰域搜索解之間的正向影響關系。實驗結果表明，該算法能夠在極短的運行時間內提供權衡各目標的Pareto解[5]。李熠胥等人研究了帶同時取送貨的綠色車輛路徑問題，建立了混合整數規劃模型，并提出了三階段拉格朗日啟發式算法進行求解，實驗結果表明，該算法能有效獲得優質解，并提供緊致下界用于評估解的質量[6]。

1 同時取送貨車輛路徑問題模型構建

1.1 問題描述

同時取送貨車輛路徑問題（VRPSDP）作為常見的車輛路徑優化問題，其目標是在一系列具有取貨和送貨需求的客戶中，確定最優的配送路徑方案，每個節點客戶具有取貨需求和送貨需求，在優化過程中必須滿足一系列約束條件，包括配送車輛的數量、每輛車的最大行駛里程、車輛的負載能力等。VRPSDP問題要求制定出最優的配送路線，使得配送車輛從配送中心出發，依次訪問各個客戶節點，最終返回配送中心，如圖1，在此過程中，需要考慮如何最小化預期的目標，包括車輛固定成本、運輸成本、碳排放成本。通過合理安排取貨和送貨的順序、優化每輛車的行駛路徑，實現車輛運輸資源的最優配置。

1.2 模型假設

為了有效將同時取送貨車輛路徑問題抽象為可求解的數學模型，本研究結合現實企業運作情況，做出如下假設：

（1）假設所有配送車輛均從同一個配送中心出發，完成配送和取回任務后返回該中心。

（2）假設配送和取回的貨物可以混合裝載在同一輛車上，車輛不需要區分配送和回收任務。

（3）假設所有客戶和配送中心的地理位置已知，即客戶節點之間以及客戶與配送中心之間的距離是確定的。

（4）假設每個客戶只能由同一輛車進行服務，每個客戶必須被服務到，且最多被服務一次。

（5）假設所有車輛具有相同的最大行駛距離和最大承載能力。

（6）假設所有客戶節點的取貨和送貨量已知。

1.3 模型構建

1.3.1 參數說明

見表1。

1.3.2 目標函數

（1）車輛固定成本

固定成本通常包括車輛折舊或租賃費用、車輛保養費用，以及執行配送任務的司機和裝卸搬運工人的工資等[7]。固定成本不會隨配送量的變化而變化，總固定成本可通過將單輛車的固定成本與使用車輛數量相乘計算得出，如下式：

C1=c1·xijk" "（1）

（2）車輛運輸成本

車輛在執行配送任務時，會因自身的燃油消耗而產生成本。隨著貨物裝載量的增加，車輛的燃油消耗量也會相應增加，車輛每公里的油耗量與其載重量呈正相關關系，即載重量越大，單位距離的燃油消耗也隨之增加，車輛在不同載重量下的油耗量可表示為：

ρ（Qk）=a（Q0+Qk）+b" （2）

車輛空載時單位行駛距離（km）的耗油量如下：

ρ0=aQ0+b" （3）

車輛滿載時單位行駛距離（km）的耗油量如下：

ρ*=a（Q0+Q*）+b" （4）

通過聯立式（3）和式（4）可得：

a="（5）

則每千米油耗ρ（Qk）與車輛載重量Qk的關系式為：

ρ（Qk）=（Q0+Qk）+b" （6）

車輛的燃油消耗量與其裝載量和行駛距離密切相關。在上述計算中，通過考慮車輛的載重量和行駛距離，可以估算車輛的燃油消耗量?；诖擞秃臄祿?，進一步計算出車輛的運輸成本。運輸成本的計算公式如下：

C2=ρ（Qjk）·C2·dij·xijk" （7）

（3）車輛碳排放成本

車輛在行駛中會消耗燃油，進而排放出二氧化碳，基于上述油耗計算過程，可進一步計算出車輛的碳排放成本，如下式：

C3=ρ（Qj）·dij·w·C3·dij·xijk" （8）

1.3.4 模型建立

通過定義上述目標函數和約束條件，同時取送貨車輛路徑問題（VRPSDP）的最優化數學模型如下：

minZ=·c1·xijkρ（Qjk）·Pf·dij·xijk

+ρ（Qj）·dij·w·C3·xijk" （9）

St. xijk=1？坌j∈J" （10）

xipk=xpjk ？坌p∈V，？坌k∈K" （11）

xi1k=xijk ？坌k∈K" （12）

L1k=djxijk ？坌∈K " （13）

Lj≥L1k-dj+pj-M（1-xijk）？坌j∈J，？坌k∈K （14）

Lj≥Li-dj+pj-M（1-xijk）？坌i∈J，？坌j∈J （15）

L1v≤qkk∈K" （16）

Lj≤qk+M（1-xijk）？坌j∈J，？坌j∈K" （17）

xijk∈{0，1}？坌i∈V，？坌j∈V，？坌k∈K （18）

在上式中，式（10）表示每個取送貨節點必須被服務到；式（11）表示對于任意車輛，必須要保證取送貨節點的出入平衡；式（12）表示對于任意車輛，必須從配送中心出發，且返回配送中心；式（13）表示對于任意車輛，在配送中心時的裝載量等于該車輛配送的全部節點送貨量總和；式（14）和式（15）表示對于任意車輛，在到達任意送貨節點時的裝載量大于等于該車輛離開該送貨節點的裝載量；式（16）表示車輛從配送中心出發時的裝載量必須小于等于車輛最大裝載量；式（17）表示到達任意節點時的裝載量不能超過車輛最大裝載量；式（18）表示0-1決策變量，表示車輛k是否從i節點行駛至j節點。

2 自適應變鄰域遺傳算法設計

自適應變鄰域遺傳算法（AVNSGA）的設計包括個體編碼設計、適應度函數設計、選擇算子設計、交叉算子設計、變異算子設計、鄰域搜索算子設計、自適應機制設計。

2.1 個體編碼

個體編碼設計能夠準確表達問題的解空間，提高算法的搜索效率，避免在解空間中過度集中或偏離最優解[8]。如圖2所示，個體由客戶節點的序列組成，其中每個基因表示一個客戶的編號。該序列決定了車輛的訪問順序，即車輛從配送中心出發，依次訪問這些客戶節點，最終返回配送中心?？蛻粜蛄械木幋a設計考慮了客戶的取貨或送貨需求，并確保在訪問順序上滿足問題的約束條件。

2.2 適應度函數

適應度函數的構建必須緊密結合模型的目標函數，以確保算法能夠有效優化所需的目標。為此，采用模型目標函數的倒數作為適應度函數，可以有效地評估個體解的優劣性，不僅能夠確保算法在搜索過程中朝著優化目標逐步逼近，還能夠為自適應變鄰域遺傳算法提供明確的評價標準，從而指導算法在復雜的解空間中進行全局優化，最終獲得更優的解。其表達式如下：

F=" （１９）

2.3 選擇算子

選擇函數設計能夠篩選出進入下一代的個體，并在后續的交叉和變異操作中繁衍后代，決定了高質量解在進化過程中的存活率，進而影響算法的收斂性和全局搜索能力。選擇函數的設計需要兼顧選擇壓力與種群多樣性之間的平衡，避免早熟收斂和過度集中于局部最優解。輪盤賭選擇是常見的方法，能夠保證每個個體被選擇的概率與其適應度值成正比，即適應度值越高的個體越有可能被選中進入下一代，有助于保持種群的多樣性。

2.4 交叉算子設計

交叉算子通過將兩個父代個體的部分基因進行組合，生成新的子代個體，從而在種群中提升多樣性，如圖3所示。交叉算子的選擇和設計需要考慮路徑的可行性、解的多樣性以及算法的收斂性。在VRPSDP中，由于問題的復雜性，路徑的可行性至關重要。交叉算子不僅需要確保生成的子代路徑滿足約束，還需保證解的多樣性以防止算法陷入局部最優。通過將兩個個體的部分基因進行截取，然后執行交叉操作，保證了兩個個體的基因相互融合，并生成了兩個個體。

2.5 變異算子設計

變異算子通過改變基因組合，增加種群的多樣性，防止算法陷入局部最優，如圖4所示。對于同時取送貨車輛路徑問題（VRPSDP），變異算子的設計需要確保生成的解是可行的，并且能夠有效地探索解空間。變異算子通過交換路徑中的兩個客戶點來生成新的解，同時保證滿足約束條件。交換變異操作簡單易行，能夠在局部范圍內產生基因變化。在執行交換變異操作過程中，需要選擇路徑中的兩個不同位置的客戶點，交換它們的位置，有效地調整路徑中的局部結構，提升解的質量。

2.6 三種鄰域搜索算子

提出了三種鄰域搜索算子，即子路徑節點最優交換、子路徑節點最優插入和子路徑隨機交換。子路徑節點最優交換和子路徑節點最優插入在算法求解VRPSDP的過程中，通過優化局部路徑節點排列，提高算法的收斂性和求解效率。而子路徑隨機交換則通過隨機性，有效避免算法陷入局部最優解，進一步增強算法的全局搜索能力，確保算法能夠更全面地探索解空間，從而實現更優的全局收斂效果。

2.6.1 子路徑節點最優交換

子路徑節點最優交換算子基于兩個子路徑之間的相互關系，通過識別出在多個路徑交叉點上存在的潛在優化節點，從而實現路徑的整體優化。子路徑節點最優交換算子能夠檢測到兩個子路徑中存在路徑交叉的節點，并判斷節點交換是否有助于整體路徑的改進。以圖5為例，假設兩個子路徑分別為1-7-2-5-1和1-8-10-3-1，通過分析可以發現節點8和節點5之間存在路徑交叉，這種交叉影響了路徑的全局最優性。為了消除這種影響，應用子路徑節點最優交換算子，對節點8和節點5進行交換操作，從而消除路徑交叉，實現整體路徑的最優化。通過此算子，不僅能夠有效提高算法的收斂性，還能增強其解決復雜VRPSDP問題的全局優化能力。

2.6.2 子路徑節點最優插入

子路徑節點最優交換算子旨在對單個子路徑中的節點進行優化，通過識別路徑中存在多重交叉的節點，重新安排其位置，以實現路徑的優化。該算子首先識別出路徑中導致交叉的節點，并將其暫時移除，然后在子路徑中尋找最優的插入位置，使得整體路徑的結構得到優化。以圖6路徑1-11-6-4-9-1為例，節點9與其他路徑段形成了交叉，影響了子路徑的最優性。通過應用該算子，節點9被移除，并重新插入至節點11與節點6之間，從而消除了路徑交叉，實現了子路徑的最優化。此過程有效提升了路徑規劃的精確性，增強了算法在處理復雜路徑優化問題時的性能。

2.6.3 子路徑隨機交換

子路徑隨機交換算子通過將多個路徑中的特定節點移除，并隨機插入到不同的子路徑中，形成新的路徑結構，旨在打破算法可能陷入的局部最優解，如圖7所示。通過這種隨機化操作，算法能夠更廣泛地探索解空間，避免在局部區域內徘徊，從而增加獲得全局最優解的可能性。此算子的引入不僅豐富了路徑規劃的多樣性，還提升了算法在解決復雜路徑優化問題中的全局搜索能力。

2.7 自適應變鄰域機制設計

2.7.1 自適應變鄰域算子權重計算

在傳統遺傳算法的基礎上，本研究通過加入自適應變鄰域機制，對算法進行創新改進，以提高其在求解同時取送貨車輛路徑問題（VRPSDP）中的效率。自適應變鄰域機制依托于前述的三個變鄰域算子（即子路徑節點最優交換、子路徑節點最優插入、子路徑隨機交換），設計了算子動態選擇的策略，使算法能夠在迭代過程中根據算子的實際表現，動態調整其選擇概率。初始時，賦予每個算子一定的權重，隨后在迭代過程中根據算子在優化過程中的表現不斷更新權重。通過這一機制，算法能夠更有效地在解空間內進行搜索，避免陷入局部最優解，并顯著增強全局搜索能力，從而提高求解復雜路徑優化問題的效率與效果。

自適應變鄰域機制根據不同算子對于目標函數的改進程度進行自適應調整，設第i個算子的當前權重為wi（t），其中t為當前迭代次數。設第i個算子在第t次迭代中的表現得分為Si（t），該得分可以根據目標函數的優化幅度進行計算。設α為學習率參數，用于控制權重更新的敏感度。

當第i個算子在第t次迭代中找到的解相較于上一次迭代解的目標函數值有改善，則定義改進幅度為Si（t），Fi-1表示上一代的最優目標函數值，Fi表示當前的最優目標函數值。具體如下：

Si（t）=" （20）

為了增強算法的探索能力，發揮子路徑隨機交換算法的作用，當算子未能夠對目標函數值進行改進時，首先計算當前目標函數值與最優目標函數值的差值Fi（t），最優加入隨機擾動因子ε∈[0，1]，進而計算出算子未能夠對目標函數值進行改進時的激勵值，如下公式：

Fi（t）=max（Fi-1-Fi，0）" （21）

Ri（t）=Fi（t）·ε" （22）

最后得到，自適應變鄰域搜素算子權重的更新公式，如下：

wi（t+1）=α·Si（t）+（1-α）·Ri（t）" （23）

2.7.2 學習率參數設計

在權重更新公式中，學習率參數起到了平衡算法探索與優化能力的關鍵作用。它不僅確保算法在初期能夠進行充分的探索，還在后期助力算法跳出局部最優解，以實現全局最優。當學習率趨近于1時，算法能夠更快速地收斂；而當學習率趨近于0時，算法則傾向于探索新的解?；诖?，本文設計了一種非線性函數，用以調整學習率，根據總迭代次數動態更新，以實現優化過程中的有效平衡。該非線性函數的設計旨在保證算法在不同階段能夠根據具體需要自適應調整探索與優化的力度，從而提高整體算法性能。公式如下：

α=" （24）

在上述公式中，M表示最大迭代次數，k表示學習率參數的下降速率，該公式的核心思想在于調節算法在不同階段的尋優能力。在迭代初期，算法通過較高的學習率（大于0.5）確保了較強的探索能力，能夠更廣泛地搜索解空間以避免早期陷入局部最優解。而在迭代的后期，學習率逐漸降低（小于0.5），從而增強算法的收斂性。學習率的非線性設計平衡了算法在不同迭代階段的探索與開發能力，提升算法的全局搜索性能和最終優化效果。圖8展示了該非線性函數的圖像，直觀地體現了學習率隨迭代次數變化的趨勢。

2.7.3 自適應變鄰域算子選擇方法

在自適應變鄰域遺傳算法中，通過輪盤賭進行算子選擇，根據算子的權重來確定選擇的概率，權重越高的算子被選擇的概率越大。假設有n個算子，每個算子的權重分別為w1，w2，...wn，每個算子被選中的概率為

pi=" （25）

通過產生均勻分布的隨機數rand，當第i個算子的累計概率pigt;rand，則將該算子作為當前迭代的變鄰域搜索算子。

3 算例求解

3.1 算例描述與參數設置

3.1.1 算例描述

在車輛路徑問題研究中，Solomon數據集被廣泛應用于測試基準。本文基于Solomon數據集中的C1數據集進行算例測試。C1數據集包含一個配送中心和100個客戶節點，共計101個節點，屬于大規模車輛路徑問題數據集。Solomon數據集專門針對帶時間窗的車輛路徑問題（VRPTW）而設計，對于同時涉及取送貨的車輛路徑問題（VRPSPD），并沒有現成的對應數據集。為解決這一局限性，本文在VRPSPD的特定要求下，基于Solomon數據集進行擴展，設計出適用于VRPSPD的測試數據集，以便更有效地評估所提出算法的求解效果。

3.1.2 參數設置

針對測試數據集的求解，本文將車輛的容量設定為9噸，并通過對基礎遺傳算法（GA）與自適應變鄰域遺傳算法（AVNSGA）的對比，驗證兩種算法在基準測試數據集上的求解效果。為了保證比較的準確性，本文對兩個算法的參數進行了如下設置，見表2。

3.2 求解結果分析

3.2.1 算法對比分析

通過對比圖9兩個算法的求解過程，可以明顯看出自適應變鄰域遺傳算法（AVNSGA）在優化效率和求解效果上相較于基礎遺傳算法（GA）具有顯著優勢。在算法迭代初期，AVNSGA能夠迅速降低目標函數值，并在較少的迭代次數內達到相對穩定的狀態，最終收斂于一個較低的目標值。在前50次迭代中，AVNSGA的目標函數值迅速降至3 100，并在200次迭代時基本收斂至最優解，最終得出的結果為2 837.19。而GA的優化過程則相對緩慢，目標函數值的下降幅度較小，整個迭代過程中GA的收斂效果明顯不如AVNSGA，最終求解結果為 3 149.91。與GA相比，AVNSGA的優化效果提升幅度達到10%。因此，AVNSGA在求解效率和最終解的質量上表現出更強的優越性，這也進一步驗證了該算法在解決大規模復雜問題中的有效性。

AVNSGA和GA的最終求解結果如表3、表4所示，需要使用10輛車服務100個節點，詳細數據如下：

從圖10中可以直觀地看出，自適應變鄰域遺傳算法（AVNSGA）和基礎遺傳算法（GA）在求解同時涉及取送貨的車輛路徑問題（VRPSPD）時，產生了不同的結果。對于AVNSGA的求解結果，可以看出配送路徑分布合理，車輛的行駛路徑較短且緊湊，且避免了多余的路線重復，表明AVNSGA能夠有效地找到優化的路徑組合，使得每輛車的行駛路線達到最優。此外，不同的車輛路徑之間的負載分配較為均衡，節點覆蓋良好，說明AVNSGA在考慮取送貨需求的同時，能夠很好地優化車輛的調度與分配，減少了不必要的空駛和繞行。而相比AVNSGA，GA所得到的路徑顯得更加復雜，存在較多交叉和重疊的線路，不僅增加了車輛的總行駛距離，也導致車輛之間的協調出現問題。GA的求解結果中，一些車輛的路徑較長且覆蓋了多個分散的節點，而其他車輛的行駛路線則較短或集中，表明GA在優化路徑時，對不同車輛的負載分配不夠均衡，導致部分車輛的行駛效率低下。

通過對比可以明顯看出，AVNSGA在求解VRPSPD問題時展現了更強的優化能力，能夠生成更高質量的解。相比之下，GA的求解結果較為混亂，缺乏良好的全局性，表明其在應對復雜問題時存在一定的局限性。因此，AVNSGA在求解VRPSPD問題上的有效性得到了驗證。

3.2.2 碳排放縮減分析

通過對比GA和AVNSGA在車輛路徑優化中的碳排放量縮減效果，如圖11所示，可以明顯看出AVNSGA在優化初期能夠快速尋找到碳排放量較小的車輛路徑方案。AVNSGA在算法迭代初期，通過自適應變異和鄰域搜索機制，能夠更有效地探索解空間，從而在較短的時間內找到碳排放量較低的路徑方案。相比之下，GA的尋優過程相對緩慢，需要經過更多的迭代次數才能達到類似的優化效果。從最終的結果來看，GA優化出的車輛路徑方案的碳排放量為1143kg，而AVNSGA優化出的車輛路徑方案最終的碳排放量為379kg，碳排放量的縮減幅度為67%。

4 結語

本文針對汽車制造業中日益增長的物流需求，提出了一種新的自適應變鄰域遺傳算法（AVNSGA），旨在解決同時取送貨車輛路徑問題（VRPSDP）。實驗結果顯示，AVNSGA不僅在目標函數值的降低上取得了顯著成效，與傳統遺傳算法（GA）相比，優化效果提升了超過10%。此外，在迭代效率方面，AVNSGA能夠在較少的迭代次數內達到穩定狀態，平均迭代次數減少了約20%，并且最終能夠收斂至一個更低的目標值，證明了AVNSGA在處理VRPSDP問題時具有更強的全局尋優能力。在優化過程中，AVNSGA求解出來的車輛路徑方案能夠對碳排放量進行大幅度的縮減，碳排放的縮減量達到了67%，促進了環境的可持續性發展，為實現綠色物流提供了有力的技術支撐。

——————————

參考文獻：

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

〔2〕Qu Y， Bard J F. The heterogeneous pickup and delivery problem with configurable vehicle capacity[J]. Transportation Research Part C： Emerging Technologies， 2013， 32： 1-20.

〔3〕Avci M， Topaloglu S. A hybrid metaheuristic algorithm for heterogeneous vehicle routing problem with simultaneous pickup and delivery[J]. Expert Systems with Applications， 2016， 53： 160-171.

〔4〕高遠，孫卓，楊敏，等.考慮多行程與同時取送貨的電動車路徑問題研究[J].數學的實踐與認識，2023， 53（05）：13-21.

〔5〕陳希瓊，胡大偉，王寧.多目標同時取送貨選址-路徑問題的多起點變鄰域搜索算法[J].控制理論與應用，2022，39（07）：1229-1241.

〔6〕李熠胥，胡蓉，吳紹云，等.三階段拉格朗日啟發式算法求解帶同時取送貨的綠色車輛路徑問題[J].控制與決策，2023，38（12）：3525-3533.

〔7〕程元棟，劉天.考慮碳排放的冷鏈物流配送路徑優化[J].棗莊學院學報，2024，41（02）：95-106.

〔8〕魏巍，郭晨，段曉東，等.基于蟻群遺傳混合算法的裝配序列規劃方法[J].系統仿真學報，2014，26（08）：1684-1691.