城市無人車同時送取貨路徑規劃研究

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

Abstract：Withthesurgeinurbanlogisticsdemand，unmannedvehicledeliveryhasatractedmuchattentionforitsflexibility andeffciency.Howtoplantheoptimalunmannedvehiclerouting problemwithsimutaneouspickupanddeliveryand time windows （VRPSPDTW），andimprovedeliveryeffciencyandservice quality，hasbecome a keychallnge inurban logistics distribution.Thearticleaimstominimizecostsand considersconstraintssuchascustomeracceptance time，numberof unmannedvehicles，andunmannedvehiclecapacity.A mathematical model forsimultaneousdeliveryand pickupisconstructed， andanimprovedgeneticalgoritisintroducedtosolveit.Ithisalgorithmimprovement，diversifiedgeneticoperators（suhas precrossovervesalsormutatio）arerodedtocelobalsach;daicfissfuctiosorpealtys areusedtohandlecomplexconstraints.Finally，basedonthesimulationanalysisofthecase，itisshownthattheimproved algorithmcanefectivelydealwithlarge-scaleVRPSPDWproblemsinashortperiodoftime，obtainsatisfactorysolutions，and provide new ideas for research and application inthe field of unmanned vehicles.

Key words： simultaneous delivery and pickup; improved genetic algorithm; time window; unmanned vehicle

0引言

隨著城市化進程的加速和電子商務的蓬勃發展，城市物流需求呈現出爆炸式增長的趨勢。這一趨勢不僅要求物流配送系統具備更高的效率，還對其靈活性和服務質量提出了更為嚴格的要求。在這一背景下，無人車配送作為一種新興的配送方式，憑借其高度的靈活性和高效的作業能力，逐漸成為解決城市物流配送難題的重要手段]。此外，在探討路徑規劃問題時，若將前向物流與逆向物流作為兩個單獨的部分進行研究，則每種物流模式均需獨立解決其特有的車輛路徑問題。從日常生活的視角來看，這種方式可能會阻礙節能減排目標的實現以及成本的有效控制。實際上，眾多與環境保護緊密相連的路徑規劃情境中，客戶往往同時存在送貨與取貨的需求，例如瓶裝牛奶的配送，不僅要向客戶送貨，還需回收空瓶。由于單獨去送貨和取貨都會產生相關的成本（運輸成本、車輛雇傭成本），如果允許同時進行送貨和取貨服務，可以減少成本，因此客戶只接受具有單一停靠的送取貨服務的路徑問題稱為VRPSDP2]。當配送任務中同時包含送貨和取貨需求，且每個服務點還附帶嚴格的時間窗口限制時，這類問題變得更加復雜和具有挑戰性。這類問題被稱為帶時間窗的同時送取貨車輛路徑問題（VRPSPDTW），它不僅要求合理規劃車輛的行駛路線以最小化總成本（如行駛距離、時間、能耗等），還需確保所有服務均在規定的時間窗內完成，從而滿足客戶需求并維持物流服務的效率與質量3]。目前也存在一些研究VRPSPDTW的文獻，比如張穎鈺等研究了半開放式送取一體的車輛路徑問題4；劉亞平等研究了帶時間窗同時送貨取貨的選址問題[5]。

傳統的路徑規劃方法在面對復雜環境下的路徑優化問題時，往往因問題規模的擴大而面臨計算復雜度的急劇增加，導致求解效率低下甚至無法求得滿意解。因此，探索更加高效、智能的求解算法顯得尤為重要。遺傳算法（GA）因其強大的全局搜索能力和對復雜問題的適應性，在解決路徑優化問題上展現出了巨大的潛力1。李章萍等認為直接將標準遺傳算法應用于復雜環境下的路徑優化問題仍然存在諸多挑戰，如早熟收斂、易陷人局部最優，以及難以有效處理時間窗和同時送取貨等復雜約束條件等。因此，對遺傳算法進行針對性的改進，以提升其求解VRPSPDTW問題的效率和效果，成為當前研究的一個重要方向。

本文以成本最小化為目標，考慮了客戶接受時間、無人車數量、無人車容量等約束條件，構建了同時送取貨數學模型，并且引人改進的遺傳算法對其求解。算法改進主要引入多樣化的遺傳操作算子以增強算法的全局搜索能力，以及采用動態適應度函數或懲罰機制來有效處理時間窗等復雜約束。通過上述改進，期望能夠提出一種高效、可靠的遺傳算法求解框架，為VRPSPDTW問題提供新的解決思路和方法。這不僅有助于提升物流配送的效率和客戶滿意度，還能為無人機領域的研究與應用提供新的思路和方法。

1帶時間窗的同時送貨取貨路徑模型建立

1.1問題描述

帶時間窗的車輛路徑問題（VRPSPDTW）可以描述如下：給定一個配送中心，計劃給具有確定數量的客戶提供取貨送貨服務且時間不能提前或超過客戶所預期的時間，完成服務后最終再返回配送中心。配送中心需要具有確定數量和一定容量的配送車輛，客戶也需要有具體位置。在配送過程中，要保證在成本最小的情況下，一定程度地實現車輛的滿載配送，并且在客戶預期的時間內完成服務。為了方便表達，我們將上述一些描述用字母進行表示： σ_o 為配送中心； i， j代表客戶； N 為客戶總數； R_i 表示客戶的送貨數量； P_j 表示客戶的取貨數量； k 代表車輛； K 為配送中心的最大車輛數； α 代表單位路段內行駛所花費的費用； x_ijk 代表車輛 k 在路段 c_i，c_j 行駛為1，不通過此路段行駛則為0； F_ij 客戶i由配送車輛j完成配送服務，沒有由車輛i完成服務為0； s_i 表示配送車輛到客戶 i 的時間； ?CT_i 表示客戶能允許的最早送貨時間； DT_i 表示客戶能允許的最晚取貨時間； D 表示不在客戶允許范圍內送達的懲罰系數。 v_i 表示第i個車輛的容量； 表示車輛 k 到達客戶 i 的時間； x_oi 表示配送中心到第i個客戶路段有車為1。

1.2模型建立

基于上述問題的描述，帶時間窗路徑問題的數學表述模型可以構建如下。

CT_i?C_ki?DT_i

在以上所有公式中，公式（1）—（3）為帶時間窗路程問題的目標函數，也就是完成配送服務要花費的最低成本，包括運輸成本和懲罰成本。公式（4）規定每位客戶僅能分配一輛配送車輛，并且每位客戶僅能接受一次配送服務；公式（5）表示服務客戶時到達的車輛和離開的車輛相同；公式（6）代表客戶的送貨量；公式（7）表示客戶的取貨量；公式（8）表示所有配送客戶的貨物總量需在配送車輛的承載容量之內；公式（9）表示從配送中心發出的車輛不能超過配送中心擁有的最大車輛數目；公式（10）表示配送車輛不能提前到達的時間或超過客戶可接受的到貨時間；公式（11）表示決策變量屬性。

2遺傳算法概述

2.1遺傳算法的基本理論

遺傳算法（GA）誕生于20世紀70年代，其靈感來源于生物模擬技術，通過模擬自然界的進化流程來求解復雜問題。該算法的核心在于將待解問題轉化為染色體編碼形式，從初始種群著手進行搜索。利用適應度函數評估個體的優劣程度，并依次執行選擇、交叉、變異等遺傳操作，促使種群不斷進化發展，直至最終趨近于最優解。當前，遺傳算法已在多個領域得到了普

遍應用并展現出廣闊的應用潛力和前景，例如：組合優化、機器學習、信號處理等。隨著計算機技術的持續進步與算法的不斷優化，遺傳算法的性能將得到顯著提升，其應用領域也將進一步拓寬，未來有望與其他智能算法結合，形成更高效、魯棒性強的優化技術，為更多領域提供強有力的支持。

2.2遺傳算法的基本步驟

遺傳算法旨在通過操作染色體上的基因，發現并優化出解決問題的更優染色體。它的基本步驟如下。

步驟1，構造符合約束條件的染色體結構。由于遺傳算法無法直接操作問題空間中的解，因此需要通過特定的編碼方式，將潛在的解轉化為可操作的染色體形式。這一編碼過程確保了每個染色體都能對應問題空間中的一個有效解，并且滿足所有的約束條件。

聚2，隨機生成初始種群。生成的這些個體就構成了一個種群，每個個體代表一個可能

步驟3，適應度值的計算。適應度值是用來判定染色體優劣的，在每次迭代過程中，遺傳算法會挑選出適應度最高的染色體作為當前最優的解決方案。

步驟4，根據個體的適應度水平來決定下一代個體的篩選，適應度更高的個體將有更大機會被選中。

步驟5，進行交叉操作。根據交叉概率CR進行交叉操作，常見的選擇包括 0.6～1.0 之間的值。

步驟6，進行變異操作。根據變異概率CM進行變異操作，CM值過高可能會導致算法失去穩定性，CM值過低則可能使算法陷入早熟收斂。通常，CM一般取值較小，在 0.001～0.1 之間。

步驟7，如果滿足停止條件，則進行步驟8，否則進行步驟3。

步驟8，通過迭代選擇新種群中適應度最大的染色體，它對應的解就是解決該問題的最優解。

遺傳算法迭代的終止條件為提前給定的最大迭代數。標準的遺傳算法流程如圖1所示。

3改進遺傳算法

3.1初始種群

對于車輛路徑優化問題，這里采用的是一種直觀的編碼方法，即基于客戶序數的編碼方案。該方法根據所需服務的客戶數

量，隨機生成一條包含客戶序號排列的染色體序列（其中， i=1，2，3 ，…， NP ），每一條染色體就是一組相關的可行解，其中，配送中心表示為0，客戶數目表示為 n ， NP 為種群規模。

3.2 計算適應度

在遺傳算法中，適應度函數定義了每個解決方案的適應度。就是說每一個可能的解都被看作一個“個體”，這些個體依據適應度函數評估的結果，經歷選擇、交叉與變異等過程，從而產生新一代個體。在該帶時間窗的路徑優化模型中，是以配送成本最低為目標來設置的。用 Z_i 來表示第i條染色體的目標函數值，適應度函數取其倒數，表示為：

適應度函數要確保較好的解能獲得較高的評分，使其有較大的機會被選中參與下一代的生成。適應度函數的確定對遺傳算法的性能及成效具有至關重要的影響。它直接關聯到算法能否有效地導向最優解，或者在可接受的時間內找到足夠好的解。 f_i 越大，表明該染色體的性能越好，越能夠接近最優解。如果某個染色體的解不符合要求，我們可以給它分配一個極大的整數值，使其適應度極低，從而排除在下一代之外。相反，那些適應度較高的染色體則會被選中，用于生成下一代。

3.3遺傳操作

3.3.1選擇算子

選擇操作的宗旨在于從當前種群中篩選出表現優異的個體，使它們有機會通過交叉和變異繁衍出新一代。這一步驟深受達爾文生物進化論中“物競天擇，適者生存”原則的啟發，即適應度更高的個體擁有更大的概率被選中。此過程模擬了自然選擇機制，其中更強大或更適應環境的生物擁有更高的生存和繁衍機會。本文采納了一種結合精英選擇與輪盤賭選擇的方法。首先，根據染色體的適應度值進行排序，直接保留適應度最高的染色體至下一代。接著，對剩余染色體的適應度值進行標準化處理，每個染色體進入下一代的概率與其適應度值在種群總適應度值中的占比大于 0 這種策略不僅確保了最優染色體能夠順利傳承至下一代，而且既提高了高適應度染色體人選的機會，又有效降低了因適應度差異過大而遺漏次優染色體的可能性。

3.3.2 交叉算子

交叉操作是遺傳算法中模擬自然界生物雜交的一個關鍵環節，它通常借助交叉算子（CO）來實現，旨在通過這一過程生成更多的染色體。該操作的核心目的是按照特定的交叉概率（CR），重新組合兩個父代染色體的部分遺傳信息，從而產生新的子代染色體。這種操作可以在解空間中創建新的解，有助于算法跳出局部最優，探索更廣泛的解空間。本文在這里采用了兩點交叉的前置交叉方式（見圖2），用下列例子進行說明：假設父代 }， ；代表交叉位置，確定子代個體方法如下：將 P₁ 交叉位置內的點，放在子代 C₂ 的首部，即 ，對于未能確定的位置，在 P₂ 中找出沒有出現的離7最近的點3，將它放在7后邊，從左到右未出現的點都移到 C₂ ，最后得到 。

3.3.3 變異算子

在遺傳算法中，變異操作是一種關鍵的遺傳機制，用來維持和引入種群的遺傳多樣性，防止算法過早收斂于局部最優解而無法探索到更優的解。變異操作通過隨機性地調整某些個體的部分基因，創造出新的個體，進而豐富了種群的多樣性。本文通過使用互換操作和逆轉操作來完成變異過程。互換操作涉及隨機選取父代染色體中的兩個基因并交換它們的位置；而逆轉操作則是隨機選定父代染色體的一段基因序列，并將這段序列中的基因位置進行反向排列（見圖3—4）。

4算例分析

某配送中心有8輛無人車向14個客戶點配送牛奶，并取回奶桶。配送中心和客戶點坐標及每個客戶點的服務時間如下所示，每輛無人駕駛配送車的派遣成本為50元，其最大裝載量為100桶貨物。車輛的平均行駛速率保持在60公里/小時，且所有車輛均從統一的配送中心啟程。本文假設車輛抵達的首位客戶時間恰好為該客戶所能接受的最早服務時間，而之后的行駛路線則需嚴格遵循每位客戶設定的時間窗口要求。表1是各客戶的位置坐標及其預期的服務到達時間列表。要求找到合適的配送方案，即求出最佳使用車輛數和對應配送路線，使得在滿足無人車容量和時間窗的約束下的配送成本最低。

設置遺傳算法種群規模（ ?NP? ）為50，變異概率為0.1，交叉概率為0.9，實驗使用Matlab（R2018a）編寫，并在Intel（R）Core（TM）i7-8550U CPU @ 2.00GHZ處理器8GB內存和64位操作系統的 Windowsl0 計算機上進行。實驗8次上述改進遺傳算法的程序，200次迭代運行情況如表2所示。

在迭代了200次的改進遺傳算法Matlab程序的8次實驗中，最好的結果為表2中的第2次實驗，最優化成本為998.55元，運行時間為7.785秒。最終結果如下：選取的無人車編號為4、2、5、8。其中，第4號無人車的行駛路線為0—11—9—10—0，離開配送中心時裝載量為57桶，回到配送中心時車輛的裝載量為54桶；第2號無人車的行駛路線為0—8—7—6—13—0，離開配送中心時車輛裝載76桶，回到配送中心時車輛裝載80桶；第5號無人車的行駛路線為0—5—1—2—3—0，離開配送中心時車輛裝載83桶，回到配送中心時車輛裝載82桶；第8號無人車的行駛路線為0—4—12—14—0，離開配送中心時車輛裝載59桶，回到配送中心時車輛裝載59桶。經優化后的迭代運行結果和最優路線情況圖如圖5、圖6所示。

5總結

本文針對帶時間窗的同時送取貨路徑問題（VRPSPDTW）的傳統求解方法在計算復雜度上的局限性，提出了一系列創新性的遺傳算法改進策略，并成功構建了一個高效、可靠的遺傳算法求解框架。具體而言，本文的貢獻與成果體現在以下幾個方面。

5.1簡潔直觀的編碼機制

采用了客戶序數編碼方法，適用于同時送取貨需求的編碼機制，該機制不僅有效簡化了問題表達，還顯著提升了算法在處理復雜路徑規劃任務時的效率與靈活性，為遺傳算法在解決車輛路徑問題在取送貨和時間窗（VRPSPDTW）上的應用打下了堅實的基礎。

5.2多樣化的遺傳操作算子

本文通過融合精英選擇與輪盤賭選擇策略，并引人前置交叉算子及逆轉互換變異算子等多樣化的遺傳操作手段，有效提升了算法的全局搜索效能，使得算法能夠在求解進程中避免陷入局部最優，進而在更廣闊的解空間中進行探索，提高了找到高質量解的可能性。

5.3動態適應度函數與懲罰機制

針對VRPSPDTW問題中的時間窗等復雜約束，本文創新性地采用了動態適應度函數或懲罰機制，有效平衡了優化目標與約束條件之間的關系，確保了算法在求解過程中既能追求路徑成本的最小化，又能嚴格遵守時間窗等約束條件，從而提高了求解結果的實用性和可靠性。

綜上所述，本文提出的遺傳算法改進策略及其求解框架，在提升求解效率、增強全局搜索能力以及處理復雜約束方面均表現出顯著優勢。實驗結果表明，該框架能夠在較短時間內有效應對大規模VRPSPDTW問題，求得滿意解，為無人機領域的研究與應用提供了新思路新方法。未來，隨著算法的不斷優化和拓展，相信該求解框架將在物流配送、快遞服務、供應鏈管理等多個領域發揮更加重要的作用。

參考文獻：

[1]王軼鵬，金薇薇，張丁偉．無人配送車模塊化功能設計研究[J]．包裝工程，2024，45（10）：420-429.

[2]辛禹辰，李潤超，楊華龍．基于等待策略的同時送取貨車輛路徑問題干擾管理研究[J].交通運輸系統工程與信息，2023，23（5）：155-161.

[3]張濤，王楚楚．考慮軟時間窗的同時送取貨隨機旅行時間車輛路徑問題[J]．同濟大學學報（自然科學版），2023，51（8）：1278-1287.

[4]張穎鈺，吳立云，賈勝鈦．帶時間窗的多中心半開放式VRPSDP問題研究[J]：系統仿真學報，2023，35（11：2464-2475.

[5]劉亞平，張惠珍，張莉，等．帶時間窗同時送取貨選址路徑問題及其煙花算法求解[J].計算機應用，202242（7）：2292-2300.

[6]馬振鵬，焦晗暘，張哲，等．面向城市物流配送的車輛路徑優化算法研究[J/OL]．系統仿真學報，1-10[2024-11-07/htps//doi.org/10.16182/j.issn1004731x.joss.24-0639.

[7]安園園，馬曉寧．改進遺傳算法與多目標優化模型的航班路徑規劃[J].計算機工程與科學，2024，46（9）：1660-1666.

[8]李章萍，徐鑫．改進遺傳算法應用于地震場景下無人機路徑規劃研究[J].安全與環境學報，2025，25（1）：237-249.

[9]朱宇，王慧玲，鄭錦波，等．基于遺傳算法的貝葉斯網絡結構學習綜述[J].激光雜志，2023，44（4）：32-39.