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

尹 飛，李新家，祝永晉

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

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

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

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

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

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

2 算法的構(gòu)造

2.1 編碼方法的確定

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

2.2 初始群體的確定

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

2.3 適應(yīng)度評(píng)估

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

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

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

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

2.4 選擇操作

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

2.5 染色體重組

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

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

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

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

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

2.6 終止準(zhǔn)則

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

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

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

表1 庫(kù)房間里程及要求

3.1 窮舉法

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

3.2 節(jié)約算法

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

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

3.3 單親遺傳算法

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

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

平均每次計(jì)算用時(shí)為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é)約算法效率較高，但隨著運(yùn)輸節(jié)點(diǎn)的增加，其尋優(yōu)能力下降明顯。單親遺傳算法不僅性能好，而且在尋優(yōu)方面的表現(xiàn)明顯超過了節(jié)約法。

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

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

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

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

3.6 擴(kuò)展應(yīng)用

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

4 結(jié)束語

在充分分析計(jì)量中心配送車輛調(diào)度需求的基礎(chǔ)上建立了數(shù)學(xué)模型，不僅解決了傳統(tǒng)遺傳算法容易“早熟收斂”的問題，而且創(chuàng)新地采用了插件方式，更容易在求解過程中進(jìn)行動(dòng)態(tài)的約束添加，從而進(jìn)一步提高算法可用性的尋優(yōu)能力。算法的計(jì)算結(jié)果也表明了該算法不僅性能卓越，而且其尋優(yōu)性能非常突出。文中構(gòu)造單親遺傳算法的思路是以整數(shù)編碼方式為基礎(chǔ)，添加了虛擬中心倉(cāng)庫(kù)來構(gòu)造完整的路徑表達(dá)式，該方法不僅可以在路徑計(jì)算中使用，也可以作為求解其他組合優(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)濟(jì)調(diào)度中的應(yīng)用—遷移策略對(duì)算法性能的影響[J].電力系統(tǒng)自動(dòng)化.2002，26（13）：23-27.