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

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

0 引 言

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

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

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

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

1.1 開放式車輛路徑優(yōu)化

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

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

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

表1 模型參數及含義

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

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

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

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

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

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

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

多次執(zhí)行上述步驟，直至迭代次數為最大值，輸出最優(yōu)解。

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

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

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

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

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

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

車輛配送時，路徑多峰尋優(yōu)的效率約束是：

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

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

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

1.3 車輛配送路徑多峰尋優(yōu)

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

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

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

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

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

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

2 仿真分析

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

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

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

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

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

表3 不同方法尋優(yōu)結果

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

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

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

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

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

表4 本文方法尋優(yōu)效率變化

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

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

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

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

3 結 論

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

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