單親遺傳算法在電力計量器具配送問題中的研究

尹 飛，李新家，祝永晉

(江蘇方天電力技術(shù)有限公司，江蘇 南京 211102)

物流配送車輛調(diào)度問題作為一個完全多項式非確定性（NP）難題，隨著客戶數(shù)量和車輛數(shù)量的增加，可選的車輛路徑方案數(shù)量將以指數(shù)速度急劇增長，窮舉法在生產(chǎn)環(huán)境中已經(jīng)不可能再使用。因此，用啟發(fā)式算法求解該問題成為研究的一個重要方向。求解物流配送車輛調(diào)度問題的方法很多，常用的有旅行商法、動態(tài)規(guī)劃法、節(jié)約法、掃描法、分區(qū)配送算法、方案評價法等。遺傳算法的出現(xiàn)為求解物流配送車輛調(diào)度問題提供了新的工具，傳統(tǒng)遺傳算法能夠方便地求得問題的近似最優(yōu)解，但對復(fù)雜問題搜索效率低，易陷入“早熟收斂”的困境[1，2]。單親遺傳算法是對傳統(tǒng)遺傳算法的一種改進，不使用傳統(tǒng)遺傳算法中常用的交叉算子，對某個個體的遺傳操作只在該條染色體上進行，即只通過單個個體繁殖后代[3]。由于單親遺傳算法不使用交叉算子，即使群體中的個體完全相同，也不影響遺傳迭代的進行，從而擺脫了對群體多樣性的要求，能克服“早熟收斂”問題。通過選擇、染色體重組等遺傳操作，使群體一代一代地進化到搜索空間中越來越好的區(qū)域，從而獲得較優(yōu)解。文中采用單親遺傳算法來對配送路徑進行近似最優(yōu)解的計算。

1 計量中心電力器具配送問題的數(shù)學(xué)模型

通用物流配送車輛調(diào)度問題可以描述為：從某物流中心用多臺配送車輛向多個客戶送貨，每個客戶的位置和貨物需求量一定，每臺配送車輛的載重量一定，其一次配送的最大行駛距離一定，要求合理安排車輛配送路線，使目標函數(shù)得到優(yōu)化，并滿足以下條件：（1）每條配送路徑上各客戶的需求量之和不超過配送車輛的載重量；（2）每條配送路徑的長度不超過配送車輛一次配送的最大行駛距離；（3）每個客戶的需求必須滿足，且只能由1臺配送車輛送貨。

在計量中心的環(huán)境，設(shè)計量中心有K臺配送車輛，每臺車輛的載重量為 Qk（k=1，2，…，K），其一次配送的最大行駛距離為Dk，需要向L個二級庫送貨，每個二級庫的貨物需求量為 qi（i=1，2，…，L），二級庫 i到 j的運距為dij，物流中心到各二級庫的距離為d0j（i，j=1，2，…，L），再設(shè)nk為第k臺車輛配送的二級庫數(shù)量（nk=0表示未使用第k臺車輛），用集合Rk表示第k條路徑，其中的元素rki表示二級庫rki在路徑k中的順序為i（不包括計量中心），令rk0=0表示計量中心，若以配送總里程最短為目標函數(shù)，則可建立如下配送車輛調(diào)度問題的數(shù)學(xué)模型：

式（1）為目標函數(shù)，在文中目標函數(shù)為配送里程最短，實際使用可以根據(jù)情況變更為油耗最低或速度最快，多個因素綜合考慮也是可行的；式（2）保證每條路徑上各二級庫房的貨物需求量之和不超過配送車輛的載重量；式（3）保證每條配送路徑的總里程長度不超過配送車輛一次允許的最大行駛距離，行駛距離既可以作為目標函數(shù)的約束條件，也可以作為目標函數(shù)的運算項。實際使用中這一約束條件也可以變更為每輛車單次行駛時間，或移除此約束；式（4）表明每條路徑上的二級庫房數(shù)不超過總二級庫房數(shù)；式（5）表明每個二級庫房都得到配送服務(wù)，實際使用中可以將本次不進行配送的庫房移出計算表格，這樣不必修改此約束條件；式（6）表示構(gòu)造各條路徑的二級庫房的組成；式（7）限制每個二級庫房僅能由1臺配送車輛送貨，如果二級庫房需求量較大，需要多輛車進行配送，此條件也可以放寬。但是從省中心的物流管理的目標來看，小批量多批次的配送方式將可能成為主流，故此約束具有現(xiàn)實意義；式（8）表示當?shù)趉輛車服務(wù)的二級庫房數(shù)不小于1時，說明該臺車參加了配送，則used（nk）取1，當?shù)趉輛車服務(wù)的客戶數(shù)小于1時，表示未使用該臺車輛，used（nk）取 0。

2 算法的構(gòu)造

2.1 編碼方法的確定

根據(jù)計量中心配送車輛調(diào)度問題的特點，文中采用簡單直觀的自然數(shù)編碼方法[3]，用0表示配送中心，用1，2，…，L表示各提出需求的二級庫房。由于在計量中心有K臺車輛，則最多存在K條配送路徑，為了在編碼中反映車輛配送的路徑，通過增加K-1個虛擬計量中心的方法，分別用 L+1，L+2，…，L+K-1表示，將這些虛擬計量中心的整數(shù)加入原配送點集合，L+K-1個互不重復(fù)的自然數(shù)的隨機排列就構(gòu)成一個個體，并對應(yīng)一種配送路徑方案。例如，在一次配送中需要用3臺車輛對9個二級庫房進行配送，則可用1，2，…，11（1-9表示各二級庫房，10，11表示計量中心，在實際計算中與0等同）這11個自然數(shù)的隨機排列，表示物流配 送 路 徑 方 案 ， 如 個 體 “1，8，6，11，3，2，4，5，10，7，9”表示的配送方案為：路徑 1，0-1-8-6-11（0）；路徑2，11（0）-3-2-4-5-10（0）；路徑 3，10（0）-7-9-0，需 3臺車輛配送。前后分別加入的0表示，車輛最終需要返回計量中心。

2.2 初始群體的確定

隨機產(chǎn)生1至L+K-1這L+K-1個互不重復(fù)的自然數(shù)的排列，即形成一個個體。設(shè)群體規(guī)模為N，則通過隨機產(chǎn)生N個這樣的個體，即形成初始群體。規(guī)模在很大程度上決定了遺傳算法尋找到最優(yōu)解的可能性，但規(guī)模達到一定程度之后，再增加初始群體的規(guī)模則對結(jié)果影響很小，呈現(xiàn)側(cè)拋物線的形狀。選擇范圍一般會隨配送路徑點的總數(shù)量變化而進行調(diào)整，總的來說不會小于500。

2.3 適應(yīng)度評估

對于某個個體所對應(yīng)的配送路徑方案，要判定其優(yōu)劣，一是要看其是否滿足配送的約束條件；二是要計算其目標函數(shù)值（即各條配送路徑的長度之和）。

由于文中根據(jù)配送路徑選擇問題的特點所確定的編碼方法（整數(shù)序列），隱含能夠滿足每個二級庫房都得到配送服務(wù)，且每個庫房僅由1臺車輛配送的約束條件，但不能保證滿足每條路徑上各庫房的總需求量不超過汽車載重量及每條路徑的長度不超過汽車單次配送的最大行駛距離的約束條件。為此，對算法中產(chǎn)生的每個配送方案，要對各條路徑逐一進行判斷，看其是否滿足上述2個約束條件，若不滿足，則將該條路徑定為不可行路徑 （可以懲罰權(quán)重的方式來進行設(shè)定），最后計算其目標函數(shù)值。對于某個個體j，設(shè)其對應(yīng)的配送路徑方案的不可行路徑數(shù)為Mj（Mj=0表示該個體是一個可行解），其目標函數(shù)值為Zj，則該個體的適應(yīng)度Fj，可用下式表示：

式中，Pw為對每條不可行路徑的懲罰權(quán)重（該權(quán)重可根據(jù)目標函數(shù)的取值范圍取一個相對較大的正數(shù)）。之所以使用懲罰權(quán)重，而不是直接將該不可行路徑移除是考慮到在基因突變的過程中，不夠優(yōu)秀甚至不可行的父代也有可能產(chǎn)生優(yōu)秀的子代。

在省中心的實際使用中，以插件的方式加入更多的約束條件，使適應(yīng)度評估更具實用性。如某2地之間的高速公路正在做短期維護導(dǎo)致路堵嚴重，則可以臨時添加1個約束條件，不允許走這條路徑。

2.4 選擇操作

將每代群體中的N個個體按適應(yīng)度由大到小排列，排在前幾位（參數(shù)G）的個體性能最優(yōu)，將它們直接復(fù)制進入下一代，并排在前位。下一代群體的其余個體的產(chǎn)生，則需要根據(jù)前代群體的N個個體的適應(yīng)度，采用賭輪選擇法產(chǎn)生。具體地說，就是按上代群體中各個個體的排名以輪盤法計算其被選擇的概率。這樣既可保證最優(yōu)個體生存至下一代，又能保證適應(yīng)度較大的個體以較大的機會進入下一代，同時允許部分劣質(zhì)個體在突變后產(chǎn)生優(yōu)質(zhì)個體后進入下一代，避免過早收斂的問題。

2.5 染色體重組

對通過選擇操作產(chǎn)生的新群體，除排在前G位的最優(yōu)個體外，另N-G個個體要運用單親遺傳算子進行染色體重組。文中選用多點基因換位算子實現(xiàn)染色體重組，現(xiàn)舉例說明其操作過程：

（1）設(shè)定基因換位次數(shù)（Nt），本例中設(shè) Nt為 1。

（2）在染色體上隨機選取Nt對基因，并交換其位置。本例中設(shè)原染色體A為478563921，隨機產(chǎn)生的第一對交換基因位為3和7，則基因換位后染色體A'變?yōu)?38567921。

（3）判斷在基因換位后個體的適應(yīng)值是否增加，若增加，則用新的個體取代原個體，進入下一代，否則原個體直接進入下一代。

（4）本例中設(shè)A'的適應(yīng)值大于A的適應(yīng)值，則A'進入下一代。

2.6 終止準則

基因進化一般使用的終止準則包括以下幾種：（1）進化次數(shù)限制；（2）計算耗費的資源限制（例如計算時間、計算占用的內(nèi)存等）；（3）一個個體已經(jīng)滿足最優(yōu)值的條件，即最優(yōu)值已經(jīng)找到；（4）適應(yīng)度已經(jīng)達到飽和，繼續(xù)進化不會產(chǎn)生適應(yīng)度更好的個體；（5）人為干預(yù)；（6）以上2種或更多種的組合。文中使用進化次數(shù)限制來進行終止。

3 運行效果和參數(shù)設(shè)置分析

為了測試算法的效果，構(gòu)建一個虛擬的環(huán)境，共有9個二級庫房，分配了3輛車（最大容量均為1）進行配送，分別采用窮舉法、節(jié)約法以及單親遺傳算法進行最優(yōu)路徑求解。庫房間里程以及需求數(shù)量如表1所示。

表1 庫房間里程及要求

3.1 窮舉法

在測試用機（普通雙核）上，通過全排列的方式進行窮舉，全部路徑數(shù)量為39916800條，最佳路徑長度為1072.6 km，用時為15 s。如果是范圍增加到13個二級庫房，用時將會增加到466830 s。即使運行在小型機上，計算用時也是無法承受的。

3.2 節(jié)約算法

采用節(jié)約算法，可以得到如表2所示的配送方案。配送總里程為1295.6 km，配送車輛數(shù)為3臺。

表2 節(jié)約算法配送方案

3.3 單親遺傳算法

定制化的單親遺傳算法參數(shù)設(shè)定：初始群體數(shù)量1000，進化次數(shù)40，基因換位次數(shù)1。運行10次之后，結(jié)果如表3所示。

表3 單親遺傳算法結(jié)果

平均每次計算用時為0.03 s，其中有1次為最優(yōu)解，2次為次優(yōu)解，其他解也比節(jié)約法的結(jié)果要好。其次優(yōu)解配送路線如圖1所示，配送方案如表4所示。

圖1 單親遺傳算法次優(yōu)解配送路線

表4 單親遺傳算法次優(yōu)解配送方案

3.4 結(jié)果比較

窮舉法雖然必然能得到最優(yōu)解，但由于效率原因不適用于生產(chǎn)環(huán)境。節(jié)約算法效率較高，但隨著運輸節(jié)點的增加，其尋優(yōu)能力下降明顯。單親遺傳算法不僅性能好，而且在尋優(yōu)方面的表現(xiàn)明顯超過了節(jié)約法。

3.5 參數(shù)設(shè)置分析

進化次數(shù)和初始群體的大小均會對遺傳結(jié)果產(chǎn)生影響：初始群體數(shù)量如果太大，則會大大增加運算時間；如果較小，則需要更多的進化次數(shù)來彌補。

需要注意的是，初始群體的合適范圍實際上與總的可能路徑數(shù)量有關(guān)。當總路徑數(shù)量在4000萬條時，初始群體數(shù)量在1000左右即可滿足要求，而總路徑數(shù)量達到4億時，初始群體要達到4000左右才能滿足要求。應(yīng)避免因樣本太少，相對于全局來說收斂過于快速，從而忽略了最優(yōu)解。以計量中心全部72個二級庫房，使用20輛車來進行配送，預(yù)計初始群體需要達到10萬，進化次數(shù)達到4000，計算結(jié)果就可以達到令人滿意的效果。

若對最優(yōu)解有較為強烈的要求，則應(yīng)該設(shè)置一個中等的初始群體大小和進化次，再進行多次運算。

3.6 擴展應(yīng)用

在實際使用中，可以采用插件的方式對算法進行定制，如將平均等時間加入到適應(yīng)函數(shù)中，也可以動態(tài)地加入路況信息以得到更合理的配送路徑[4]。同時由于單親遺傳算法的效率非常高，故而可以在情況不明確（如配送車輛的數(shù)量，配送頻率不確定）的情況下，進行多次計算，從而為不同的配送方案的評估提供參考信息。

4 結(jié)束語

在充分分析計量中心配送車輛調(diào)度需求的基礎(chǔ)上建立了數(shù)學(xué)模型，不僅解決了傳統(tǒng)遺傳算法容易“早熟收斂”的問題，而且創(chuàng)新地采用了插件方式，更容易在求解過程中進行動態(tài)的約束添加，從而進一步提高算法可用性的尋優(yōu)能力。算法的計算結(jié)果也表明了該算法不僅性能卓越，而且其尋優(yōu)性能非常突出。文中構(gòu)造單親遺傳算法的思路是以整數(shù)編碼方式為基礎(chǔ)，添加了虛擬中心倉庫來構(gòu)造完整的路徑表達式，該方法不僅可以在路徑計算中使用，也可以作為求解其他組合優(yōu)化問題的參考。

[1]SZCZERBICKAH，BECKERM，SYRJAKOWM.Genetic Algorithms:A Tool for Modelling,Simulation and Optimization of Complex Systems[J].Cybernetics and Systems,1998，29(7)：639-659.

[2]SCHMITT LOTHAR M.遺傳算法理論，Theoretical Computer Science(259),2001：1-61.

[3]SCHMITT LOTHAR M.遺傳算法理論（二），Theoretical Computer Science(310),2004：181-231.

[4]曹一家.并行遺傳算法在電力系統(tǒng)經(jīng)濟調(diào)度中的應(yīng)用—遷移策略對算法性能的影響[J].電力系統(tǒng)自動化.2002，26（13）：23-27.