基于多代競爭遺傳的車輛配送路徑多峰尋優研究

王力鋒，黃 斐，黃 謙，任宇光，陳文冬,3

（1.百色學院，廣西 百色533000；2.澳門科技大學，澳門999078；3.廣州商學院，廣東 廣州 510000）

0 引 言

合適的車輛配送路徑，將縮短運輸距離，減少配送成本，配送時間也將得以縮短，目前很多研究人員對車輛配送路徑尋優問題進行了深入研究，例如葉勇等提出基于狼群算法的車輛配送路徑尋優方法，該方法可在降低車輛配送成本的條件下，有效獲取車輛配送最佳路徑，但是該方法在獲取車輛配送最佳路徑時，尋優次數較多，收斂速度慢；李卓等提出基于混合蟻群算法的車輛路徑規劃方法，蟻群算法在求解車輛路徑尋優中較為常用，可在短時間內獲取車輛配送最佳路徑，但是在所尋路徑中配送時，與同類算法相比，車輛配送成本較多，在車輛路徑尋優時的收斂效率也并不顯著。夏揚坤等為了降低連鎖超市的配送系統總成本，設計了一個自適應禁忌搜索算法，采用“隨機禁忌長度”和“禁忌表重新初始化”來對鄰域進行充分搜索，結合各超市配送的時效性，建立了相應的雙目標數學模型，增強算法的全局尋優能力，但是其約束條件不明確，無法獲取全局最優解。賀桂和等為了促進農產品流通，降低農產品電商物流配送成本，將傳統約束中客戶需求不可拆分的條件進行松弛，結合傳統帶時間窗的車輛路徑問題，研究了一種帶軟時間窗的需求單元拆分車輛路徑問題，提升禁忌搜索算法的全局尋優性能，有助于減少使用的車輛數和降低配送成本，但是其算法應用過程的迭代穩定性較差，無法實現多峰尋優。戚遠航等提出一種泰森多邊形的離散蝙蝠算法，融入了一種基于多車場多車輛問題的編解碼策略，求解多車場車輛路徑問題，表現出較強的尋優能力和穩定性，但是其目標函數與約束條件不明確，其不支持多峰尋優任務。

車輛配送路徑多峰尋優，可理解為車輛配送路徑中多個高峰期的最優路徑規劃，此問題屬于非線性函數多峰尋優問題，本文針對此問題進行深入研究。為此，本文提出基于多代競爭遺傳的車輛配送路徑多峰尋優方法，本文中的多峰尋優是指在車輛配送的高峰時段下，由固定的物流中心安排可以匹配最佳路線的車輛進行配送，是面向全時間段的車輛配送路徑多峰尋優，其關鍵在于優化遺傳算法收斂效率，并在車輛配送路徑多峰尋優問題中，應用多峰函數，結合閉區間上連續函數的零點存在定理，求解最優的車輛配送路徑即將全局最優解轉換為車輛配送路徑種群規模最優化問題，以多峰尋優的目標函數與約束條件為基礎，求解車輛配送路徑多峰尋優模型，使其具有較為顯著的優化效果。

1 基于多代競爭遺傳的車輛配送路徑多峰尋優方法

車輛配送路徑優化屬于路徑優化的范疇，但車輛配送路徑優化與路徑優化又有很大不同，主要體現在以下三個方面：（1）車輛配送路徑優化對貨物的重量、大小、體積、屬性等有一定的規定，路徑優化僅僅涉及路徑規劃內容，其影響因子存在差異。（2） 服務時效要求不同，車輛配送時間要求更嚴格，一般都是在白天，因為工作人員的工作時間固定，但具體時間要求比較寬松，例如上午、下午等，工作人員的服務時間較為靈活，而路徑優化的尋優過程是基于全時間段的。（3） 配送后，需要進行后續的、簡單的分揀作業等過程，導致其影響配送時長的因素較多，很難快速、精確地找到全局最優解。

1.1 開放式車輛路徑優化

開放式車輛是指對車載貨物重量、配送車輛數量等內容不設限制，不做約束。車輛配送路徑多峰尋優屬于動態事件，此事件具有四種情況：（1） 車輛配送時，加入新“目標”；（2） 車輛配送時，初始“目標”需求發生變化；（3） 車輛配送時，交通情況變差；（4） 車輛配送時，配送車輛出現事故。

如果出現上述四種任何一種動態事件，便需要因地制宜的設計新的車輛配送路徑多峰尋優方案。為此，構建一種基于開放式車輛路徑優化的路徑多峰尋優模型。

首先，設定路徑多峰尋優模型所用參數，如表1 所示。

表1 模型參數及含義

其次，根據標記設立此模型中車輛配送路徑多峰尋優的目標函數：

車輛配送路徑多峰尋優過程中的阻抗是具有實時或歷史流量的時間屬性，最佳路線是對指定日期和時間來說最快的路線，因此，高峰時段下車輛配送路徑多峰尋優過程的目標函數與全局最優解相對應，需要應用多代競爭遺傳算法中的多峰函數對其求解。

1.2 車輛配送路徑的多代競爭遺傳算法

為了合理安排車輛路徑，使總運輸路徑最短，本文引入多代競爭遺傳方法，進行路徑多峰尋優模型設計。本文設計需在下列條件下進行：（1） 假設用戶分布在配送區域內，用戶需求小于車輛額定載重量，每個用戶只允許訪問一次，只允許使用一輛車，且每輛車只允許使用一次；（2） 分配到配送中心的每輛車在配送中心啟動和結束時，每個用戶的需求之和不超過車輛的額定。

一般來說，當遺傳算法是“遺傳”時，新個體將取代某些父個體在種群中的地位。然而，遺傳算法（復制、交叉、突變） 并不能保證后代優于父代，產生“退化”現象。為了保障優秀的個體存在充足的繁殖次數，本文將“壽命優化”應用在遺傳算法之中，防止出現“退化”情況，以此提高收斂效率。

工控網絡安全態勢分析技術首先要對各種對網絡安全性有影響的網絡要素進行檢測和獲得。影響網絡安全的要素非常廣泛，既有時間上的，也有空間上的。對要素進行采集和獲得之后，要對這些安全信息均采用分類、合并、關聯等信息分析手段進行信息融合，然后對融合后的安全信息進行綜合分析與評估，獲得當前網絡的整體安全狀態信息，最后根據已有的網絡安全態勢信息對網絡未來的安全態勢進行預測。

壽命即為個體在種群里的存活代數，年齡是個體目前已經存活的代數。年齡與壽命相同的個體，便屬于“死亡”模式。種群之中，個體的年齡并非一致，所以便會衍生多代并存的種群結構。適應度顯著的個體，壽命顯著，可以繁衍多代，以此提升了優秀基因遺傳至子代的幾率，優化種群個體質量。種群里個體競爭分為子代個體的生存機會競爭、壽命競爭、遺傳機會競爭。車輛配送路徑多峰尋優時，多代競爭遺傳的步驟如下：（1） 多代競爭遺傳中車輛配送路徑初始種群建立時，假定車輛配送路徑種群規模是W，車輛配送路徑的初始種群適應度較差的W 個個體（車輛配送路徑） 壽命是1，剩下優秀個體（可用路徑） 根據適應度實施從大到小的順序配列，年齡都是0。繁衍一代后，全部父代個體的年齡需要加1。以此壽命是1 的個體在子代個體出現后便會進入“死亡”模式，被新衍生的子代個體所取代。個體進入“死亡”模式表示某配送路徑不是車輛配送路徑多峰尋優目標，可舍棄。（2） 遺傳操作衍生子代時，各個父體個體（車輛配送路徑） 進行遺傳操作的幾率按照自身適應度設置。為了避免車輛配送路徑種群規模出現“萎縮”，各次衍生的車輛配送路徑個體數目必須充足。因為父代死亡數目最大值是W，因此遺傳之時，衍生的子代個體數目必須是W。去除父代死亡個體時，假定目前個體的年齡是C（i∈ W ），壽命是S（i∈ W ），車輛配送路徑種群通過交叉、變異衍生新一代個體時，車輛配送路徑種群個體的年齡將加1。（3） 子代以優勝劣汰的規則，擇優錄取并納入車輛配送路徑種群。假定父代個體死亡數目是Z，那么子代個體根據適應度實施對比，并擇優錄取，合適的車輛配送路徑將被納入車輛配送路徑備選種群。（4） 設置車輛配送路徑種群個體壽命與年齡時，按照優勝劣汰的宗旨，子代個體（車輛配送路徑） 里適應度顯著的個體，將納入車輛配送路徑種群。此類個體和還沒有死亡的父代個體根據適應度的大小值排列，子代個體的壽命根據自身排序方位設置，年齡設成0。父代延續個體的壽命根據適應度設置。（5） 車輛配送路徑種群更新時，去除“死亡”個體，更新后的車輛配送路徑種群，由前代延續個體與新生個體構成，車輛配送路徑種群規模不變。

多次執行上述步驟，直至迭代次數為最大值，輸出最優解。

此時，在車輛配送時，車載量約束是：

車輛配送時，行駛距離約束是：

預設在物流中心所派遣車輛的載量約束是：

預設在物流中心派遣車輛的行駛距離約束是：

車輛配送時，各個客戶均被1 輛車服務的約束是：

車輛配送時，全部車輛起點、終點均為物流中心的約束是：

車輛配送時，路徑多峰尋優的效率約束是：

車輛配送時，動態事件出現的時間點符合配送周期的約束是：

整合上述公式，即完成的路徑多峰尋優模型設計。

車輛配送路徑的多代競爭遺傳時，為了保障收斂效率得以優化，對遺傳算法進行優化，優化之處見下述。

1.3 車輛配送路徑多峰尋優

車輛配送路徑多峰尋優時，使用符號對每個車輛進行編碼，將編碼的個體組成為車輛配送路徑種群，多代競爭并存的車輛配送路徑種群結構，將使用遺傳與變異模式獲取新的個體，取代“死亡個體”，將其轉換為車輛配送路徑問題，若出現新的車輛加入，在車輛配送路徑種群序列里加入新車輛。根據父代種群里個體的適應度與遺傳的雙親進行交叉復制，染色體的交叉復制屬于雙親遺傳。雙親遺傳時，以拓展路徑尋優范圍為目的，使用多樣性的鄰域結構：

（1） 兩個體間的單個節點交換。任意選擇兩個體（車輛配送路徑） 相交的節點，設成交換點并實施轉換，獲取新解。

（2） OX 順序較差。在一個父代個體里選取一輛車與其他車輛的所有相交節點，在此節點中加入其他父代個體里車輛位置，反復求解，直至解出現規模是N 的車輛配送路徑種群，即車輛編碼順序與車輛走過路徑順序。

為了克服遺傳算法的早熟情況，求解車輛配送路徑多峰尋優的目標函數時，需要優化可選車輛配送路徑的種群個體多樣性。遺傳算法的搜索過程僅基于適應度函數。適應度分配方法是根據個體目標值對種群進行排序，個體適應度只取決于其在種群序列中的位置順序。通過交叉概率與變異概率設置交叉與變異出現的概率，若迭代步數最大值是M，為了避免單個子種群，特別是個體序列的第一部分過度繁殖，導致分布過程中分布目標過多，有必要優化多峰函數，選擇性地抑制子種群中的某些個體，令相鄰不同配送目標之間的同步差量為Q。

假設Q=｛Q,Q,Q,…,Q｝，代表總配送時長的約束函數H中包含k 個配送任務對應的同步差量值。因此，相鄰不同車輛配送路徑之間的同步差量W 表示為：

式中：總配送時長的約束函數H處于第k 個任務時的配送精度Q受到該段路程l 的配送任務總數影響，相鄰配送路徑對應的配送任務可表示為Q=｛q,q,q,…,q｝，l 取值1≤l≤x，當配送作業過程的配送目標過多時，配送精度逐漸減少，但相鄰不同車輛配送路徑之間的同步差量對應減少，車輛與車輛之間的多峰函數此消彼長，體現了劃分種群、調整個體適應度以提高種群多樣性的原則，即具有多峰優化性能，且不增加算法復雜度，便可停止車輛配送路徑多峰尋優，輸出車輛配送路徑多峰尋優結果，完成車輛配送路徑多峰尋優。

2 仿真分析

為測試本文方法對車輛配送路徑多峰尋優問題的使用性能，在CodeBlocks 編程環境中，通過C 語言編程，基于Inter（R）Core（TM） i3 CPU、內存是4.0GB、64 位Windows10 旗艦版操作系統的計算機之中編程本文所提方法，模擬分析本文方法對車輛配送路徑多峰尋優的效果。仿真環境中，所模擬的物流中心和每個目標點之間道路交通距離信息如表2 所示。

表2 物流中心和每個目標點之間道路交通距離信息

表2 中，A1、A2、A3、A4、A5、A6、A7、A8、A9、A10 代表配送城市；B1、B2、B3、B4、B5、B6、B7、B8 表示配送城市的十字交通路口，此路口不存在目標。

使用本文方法對該區域車輛配送路徑進行多峰尋優時，配送車輛的詳細配送順序是：配送車輛1 配送路徑規定時間：物流中心出發時間為6:30，19:50 返回物流中心。配送車輛2 配送路徑規定時間：物流中心出發時間為7:30，16:30 返回物流中心。配送車輛3 配送路徑規定時間：物流中心出發時間為7:30，18:40 返回物流中心。配送車輛4 配送路徑規定時間：物流中心出發時間為5:30，19:50 返回物流中心。

在初始種群建立后，依據種群個體多樣性，迭代步數最大值是M時，進行了多峰函數尋優，在無動態事件出現的前提下，使用本文方法與其他文獻方法（文獻[1]和文獻[2]方法） 對該區域車輛配送路徑進行多峰尋優后的結果，而本次實驗給出的數據為第一次尋優成功的迭代次數（多峰函數的第一個取值即第一個峰），如表3 所示。

表3 不同方法尋優結果

如表3 數據所述，本文方法在對該區域車輛配送路徑實施多峰尋優時，使用4 輛車、配送時間均值為46.41h、迭代次數均值為152.85 次、尋優時間均值為2.40s。為凸顯本文方法對車輛配送路徑多峰尋優的使用效果，將其與文獻[1]的基于狼群算法的車輛配送路徑尋優方法、文獻[2]的基于混合蟻群算法的車輛路徑規劃方法進行對比后，兩種對比方法的車輛配送路徑尋優結果的車輛配送時間、迭代次數、尋優時間均大于本文方法，表明本文方法和同類方法相比，在車輛配送路徑多峰尋優時，存在效率優勢。

為了增加算例分析的展現形式，體現本文方法的多峰性質，將表3 轉換為圖1，突出對多峰配送優化求解的過程、優越性。

圖1 多峰性質體現下的不同方法的迭代次數

由圖1 可以看出，本文方法較文獻[1]和文獻[2]方法的多峰函數解即有多個極值點的函數解，也就是說其峰值較多，沒有個體的區間不可能包含極值點，因此，本文取出包含個體的區間，再次細化，重復搜索過程，直到細化的區間足夠小，可以更有針對性地獲取最優解，進而為車輛配送路徑尋優提供更為優越的求解過程。

在仿真環境中，引入本文所設計四種動態事件中的事件（3），測試本文方法、文獻[1]的基于狼群算法的車輛配送路徑尋優方法、文獻[2]的基于混合蟻群算法的車輛路徑規劃方法的尋優效率，并將此前提條件下的尋優效率與無動態事件出現前的效率進行對比，結果如表4 所示。

表4 本文方法尋優效率變化

如表4 所示，在仿真環境中，引入本文所設計四種動態事件中的事件（3） 后，本文方法尋優下，車輛配送時間比無動態事件時多出0.01h，第一次尋優成功的迭代次數多比無動態事件時多出1 次，尋優時間比無動態事件時多0.1s；文獻[1]方法使用后，車輛配送時間比無動態事件時多出2.01h，第一次尋優成功的迭代次數多比無動態事件時多出11 次，尋優時間比無動態事件時多2.2s；文獻[2]方法使用后，車輛配送時間比無動態事件時多出1.56h，第一次尋優成功的迭代次數多比無動態事件時多出16 次，尋優時間比無動態事件時多1.79s。由此可見，動態事件的出現，對文獻[1]方法、文獻[2]方法應用效果存在影響，但對本文方法的影響不大。且文獻[1]方法、文獻[2]方法與本文方法相比，動態事件出現后，本文方法對車輛配送路徑多峰尋優效率仍舊最為顯著。

本文方法、文獻[1]的基于狼群算法的車輛配送路徑尋優方法、文獻[2]的基于混合蟻群算法的車輛路徑規劃方法使用下，模擬計算物流企業車輛配送的使用成本進行對比，按功能計算物流成本計算車輛折舊或修理費用、通行費、燃料費、司機工資和其他費用，降級整合為最終成本，三種方法的最終成本對比結果如表5所示。

如表5 所示，三種方法對比之下，物流企業使用本文方法后，物流企業4 輛車輛配送的日使用成本均值是244 元，使用文獻[1]方法、文獻[2]方法，物流企業4 輛車輛配送的日使用成本均值分別比本文方法多出52 元、79 元。對比之下，本文方法尋優下，更節省車輛配送的應用成本。

表5 三種方法試用下物流企業車輛配送的日使用成本單位：元

3 結 論

（1） 第三方物流企業中，物流中心的車輛路徑規劃十分重要，不僅需要準確無誤地將貨物配送至最終客戶，也需要保證車輛的配送時效。針對車輛配送問題進行專題研究，提出了基于多代競爭遺傳的車輛配送路徑多峰尋優方法。

（2） 所提方法有效提升了遺傳算法的收斂效率，可在短時間內獲取車輛配送的最佳路徑，且其配送時間、迭代次數、尋優時間均得到保證，在最短時間內完成車輛配送路徑尋優。且使用成本最少，在生產企業、物流企業的實際應用過程中均存在參考價值。