朱澤國，廣曉平，郭 敏

(1.蘭州交通大學(xué) 交通運輸學(xué)院，甘肅 蘭州 730070；2.內(nèi)蒙古農(nóng)業(yè)大學(xué) 能源與交通工程學(xué)院，內(nèi)蒙古 呼和浩特 010018)

多車型路徑優(yōu)化問題是傳統(tǒng)車輛路徑問題的延伸和拓展，因其特有的時效性、不確定性及多重目標約束特點符合實際應(yīng)用背景，因此，具有較高的研究價值。

目前，針對多車型路徑優(yōu)化問題中外學(xué)者已經(jīng)做了深入研究。Yan等[1]在行程時間和需求隨機條件下，提出在模型中加入隨機性因素解決車輛路徑和調(diào)度問題，在成本方面顯示出更好的優(yōu)越性；Andres G等[2]在隨機需求條件下，通過改進遺傳算法求解帶時間窗的車輛路徑問題；Subramanian等[3]提出基于局部迭代搜索的啟發(fā)式算法和集合分區(qū)公式的混合算法，以確定總成本最小化的路線集，從而優(yōu)化多車型車輛路徑優(yōu)化問題；Guedes等[4]以總成本最小和原計劃分差最小為目標，對客戶需求隨時間變化問題進行研究，并利用網(wǎng)絡(luò)規(guī)劃編碼進行求解路徑；Kim等[5]解決了結(jié)合交通動態(tài)性和需求不確定性的網(wǎng)絡(luò)設(shè)計問題；Salhi等[6]在多車型車輛路徑問題中增加返程取貨的現(xiàn)實需求，并提出基于集劃分問題的啟發(fā)式算法。鐘石泉和賀國光[7]利用禁忌算法解決了多約束條件下多車場車輛調(diào)度問題，并通過相關(guān)算例證明了可行性；葛顯龍等[8]基于多車輛調(diào)度問題中使用優(yōu)先權(quán)原則的分析，設(shè)計一種改進遺傳算法對模型進行求解；鄧紅星等[9]基于隨機需求，構(gòu)建考慮時間窗物流配送的優(yōu)化模型；夏曼曼[10]、楊忠振等[11]、王文君[12]結(jié)合路網(wǎng)交通流變化的實際情況，建立了配送優(yōu)化模型；楊浩雄等[13]、羅鴻斌[14]引入了蟻群算法及粒子群算法，以此解決多個配送中心條件下的多車型調(diào)度優(yōu)化問題；陳呈頻等[15]提出一種改進遺傳算法，驗證了該算法對多車場、多車型路徑問題的有效性和實用性；張萍[16]在供應(yīng)鏈網(wǎng)絡(luò)設(shè)計中，通過對供應(yīng)鏈不確定因素來源的向上追溯，在問題求解中加入不確定考量，并建立了魯棒優(yōu)化模型。然而，當前針對路段通行時間不確定性對配送路徑問題影響的相關(guān)研究較少。

將車輛通行時間的不確定性納入到問題研究中，有著非常重要的研究意義和實際應(yīng)用背景，基于此：建立總成本和配送時間最小的多目標函數(shù)；設(shè)計多染色體編碼的改進遺傳算法；通過模型和算法求解實例，得出多車型、單車型解集，對比分析兩者配送路徑及不確定因素對結(jié)果的影響。

1 模型構(gòu)建

1.1 問題描述

本文研究的問題可描述為：城市中的多個物流配送中心，配備有多種車型車輛若干，物流配送中心需要通過對各種車型車輛的組合使用，考慮路段通行時間不確定的情況，在限定的時間窗內(nèi)為周邊眾多客戶提供服務(wù)，且配送成本和配送時間最低。該問題有幾個基本假設(shè)：

1)每個配送中心有多種車型的配送車輛，車型不同，車輛使用成本和裝載量也不同；

2)客戶點在配送中心服務(wù)范圍內(nèi)；

3)配送車輛行駛里程不受限制；

4)客戶需求小于車輛載重；

5)配送車輛需遵守各客戶時間窗限定，否則將承擔(dān)相應(yīng)的懲罰成本；

6)配送車輛從配送中心出發(fā)，為客戶提供配送服務(wù)后回到原配送中心。

1.2 模型參數(shù)及變量

表1 模型參數(shù)說明

1.3 模型構(gòu)建

針對本問題考慮2個優(yōu)化目標，即總出行成本最小和配送時間最短。

目標函數(shù)定義如下：

1)總成本最小目標函數(shù)

(1)

在式(1)中總出行成本由3部分構(gòu)成，即固定成本、車輛行駛產(chǎn)生成本及未在時間窗內(nèi)配送的懲罰成本。配送車輛運輸成本跟車型及配送路徑相關(guān)，不同車型配送車輛行駛不同距離，運輸成本也不同。

2)配送時間最短目標函數(shù)

(2)

式(2)中配送時間由車輛行駛時間、服務(wù)時間及車輛在路段的等待時間構(gòu)成。

3)將目標函數(shù)利用魯棒離散優(yōu)化理論轉(zhuǎn)化得到目標函數(shù)

(3)

約束條件如下

(4)

(5)

(6)

(7)

(8)

(9)

(10)

ai

(11)

(12)

2 求解算法設(shè)計

2.1 算法描述

傳統(tǒng)遺傳算法在求解單車型路徑問題時能獲得較好的效果，但多車型配送路徑優(yōu)化涉及多車型這一復(fù)雜因素，傳統(tǒng)遺傳算法不能獲得令人滿意的解，算法流程如圖1所示。本文采用多目標進化遺傳算法，結(jié)合鏈表思想，解編碼采用多染色體，以解決產(chǎn)生不可行解的問題。同時，針對多染色體，分別設(shè)計個體間、個體內(nèi)的交叉算子；在算法中還加入了擂臺賽法則和改進精英保留策略思想。

2.2 種群初始化

隨機選擇一個客戶(1～n)，將其分配到多染色體的任意一個，子染色體首位基因?qū)?yīng)配送車輛編號，分配后還需要對客戶需求與對應(yīng)車輛載重進行對比，若不超載，保留此客戶基因在車輛基因之后，否則，將此客戶分配給剩余染色體中任意一條，并對比客戶需求與車輛載重，直至客戶基因被成功分配。循環(huán)上述流程，分配剩余客戶，產(chǎn)生初始種群。

2.3 染色體編碼

文章考慮由車輛基因和子染色體兩部分來組成染色體，其中客戶基因位于子染色體，其基因排列順序代表服務(wù)客戶順序，即配送路徑；且染色體數(shù)量與配送中心車輛總數(shù)對應(yīng)相等。同時，為避免不可行解的產(chǎn)生，在染色體編碼時采用多條染色體。對配送車輛進行編號，其后的子染色體首末尾對應(yīng)配送車輛出發(fā)及返回的配送中心編號，子染色體中間基因為配送路徑及服務(wù)的客戶。

如9個客戶點(編號1～9)可由分屬3個配送中心(編號：A、B、C)的3輛車(編號：13、14、15)提供配送服務(wù)，編碼為包含3條染色體的個體車輛與客戶點之間一一對應(yīng)。

2.4 選擇算子

在初步確定的群體中，以個體適應(yīng)度為標準，隨機生成數(shù)量為N的個體集，并計算集合N中每一個體元素的適應(yīng)度，并將這些個體以適應(yīng)度為依據(jù)加以排列，選擇出序列中排名靠前的個體對象作為遺傳子代。為了種群的良好分布及多樣性，本文通過計算個體擁擠距離，并以此作為適應(yīng)度評判標準。

2.5 交叉算子

為避免算法陷入到局部最優(yōu)，導(dǎo)致產(chǎn)生早熟解；同時，為保證父代當中的優(yōu)秀基因盡可能多地遺傳到下一代，結(jié)合文章采用的多染色體編碼，本文設(shè)定兩種交叉算子，即個體間的交叉算子和染色體交叉算子。

1)個體間交叉也即交叉重組。如圖1所示，首先，根據(jù)交叉概率選取父代個體P1，P2，確定染色體編號；其次，互換此染色體攜帶的客戶基因進行交叉操作；最后，刪除重復(fù)的客戶基因并對缺失的客戶基因位進行補充，產(chǎn)生新的子代C1，C2。文中交叉點位于首位基因(車輛基因)與次位基因(第一位客戶基因)之間。

圖1 體間染色體交叉

2)子染色體交叉是指對各條染色體間的交叉重組。首先，從種群選取一個個體，將此個體中兩條子染色體作為交叉對象；其次，對其采用單點定點交叉，交叉點選擇與個體交叉相同，以此達到信息互選目的；最后，對交叉之后的子染色體進行判斷，若對應(yīng)車輛未超出載重量，則子代為交叉后的個體；否則，與父代保持一致。如圖2所示。

圖2 色體交叉

2.6 變異算子

在遺傳算法的進行過程中，令變異幾率為Pc，并假設(shè)每個染色體所包含的車輛基因信息不會有變異現(xiàn)象。對于其客戶基因，都會生成與其對應(yīng)的隨機概率r，若r≤Pc則需將該基因移動至變異基因庫中，還需要刪除與之對應(yīng)染色體中的該基因，隨后在相應(yīng)的群體中另選出客戶基因，并加入到該染色體中，如圖3所示。

圖3 色體變異

2.7 擂臺賽法則構(gòu)造非支配集

為提高算法的收斂性和解的質(zhì)量，求解多目標算法需要構(gòu)造群體的非支配解集，即Pareto解集；然而，構(gòu)造Pareto解集的速度對多目標進化算法的運行效率影響較大。目前，Deb[17-18]和Jensen[19]提出的構(gòu)造非支配集的方法應(yīng)用較廣，但擂臺賽法則相比前兩者有更好的表現(xiàn)，能明顯提高多目標進化算法的運行效率[20]。

2.8 改進精英保留策略

在優(yōu)化過程中，可能會出現(xiàn)局部最優(yōu)或早熟的情況，為避免這一現(xiàn)象，在原有算法的基礎(chǔ)上增加改進的精英策略，從而使優(yōu)化算法向著正確Pareto曲面進行搜索，保障了群體的多樣性。

3 算例分析

以某城市的部分實際路網(wǎng)為例，如圖4所示，該區(qū)域有兩個配送中心(節(jié)點編號13、15)、9個客戶點(編號1～9)，其余為節(jié)點?？蛻粜畔⑷绫?所示。

表2 客戶信息表

圖4 配送網(wǎng)絡(luò)

各配送中心配置兩種車型：車型A及車型B，共計8輛(編號37～44)，車型A單車載重量6 t，固定成本100元，距離成本0.5元/km，車型B單車載重量9 t，固定成本120元，距離成本0.6元/km。各配送中心均配置2輛A車型，2輛B車型。

在windows10環(huán)境下，處理器為Intel(R)Core(TM)i7-107500H CPU@2.60 GHz、16 GB內(nèi)存平臺，使用Python語言集成開發(fā)環(huán)境Pycharm中，利用前述模型及算法分別對單車型、多車型配送路徑進行求解，得到各不確定參數(shù)下的解集，為驗證多車型解集的優(yōu)越性，與單車型解集進行比較。

當Γ=0時，即不考慮路段通行時間這一不確定因素。在此確定情況下，計算得到多車型解集，如表3所示，包括配送路徑、車輛組合、運輸成本、時間及滿載率等，多車型解集1使用車型A、B各2輛，其中編號為43的配送車輛僅為客戶8服務(wù)，滿載率較低，而解集1平均滿載率也僅為70.07%，多車型解集2的車型選擇為：1輛A車型、2輛B車型，平均滿載率達到93.14%?？梢钥闯?，多車型解集1因為車型組合不佳，存在裝載率較低車輛，嚴重拉低平均裝載率，造成車輛資源浪費，使得運輸成本升高。

表3 Γ=0時多車型Pareto 解集

為進一步驗證多車型解集的優(yōu)越性，本文分別對單車型A、B的配送路徑進行求解，單車型解集如表4所示，單車型A的兩解集均使用4輛車，單車型B的兩解集均使用3輛車。車型A因為載重量較小，相同需求量需要啟用更多的車輛，勢必造成運輸成本的直線上升。相比車型A，車型B的載重量大，車輛啟用少，運輸成本相對較低，但單車型B的兩解集均存在裝載率較低車輛，沒有充分利用車輛的載重空間。

表4 Γ=0時單車型 Pareto解集

多車型解集2相比單車型解集，不論在滿載率、運輸成本及運輸時間上都存在優(yōu)勢，說明多車型的正確優(yōu)化組合對物流配送企業(yè)更加有利。

表5為多車型與單車型解集在不同不確定參數(shù)下的解集對比，隨著不確定參數(shù)Γ的變化，多車型、單車型解集運輸成本及時間成本均有上升，但多車型解集滿載率較穩(wěn)定，變化幅度不明顯，保持了較好表現(xiàn)。且隨著參數(shù)變化，解集的目標值差異增大，增長趨勢顯著，尤其在不確定參數(shù)Γ從30變?yōu)?0時，解集運輸、時間成本呈現(xiàn)出明顯的增長趨勢。表明在同等條件下，配送企業(yè)根據(jù)客戶需求選擇多種車型車輛組合使用，相較單一車型，可為客戶提供更大的需求空間、更優(yōu)的配送路徑選擇，在配送時間和運輸成本上更具有優(yōu)勢，也使車輛資源利用最大化，為配送企業(yè)提供決策參考。同時，通過解集的對比，也驗證模型中不確實系數(shù)Γ對解集的影響。

表5 多車型與單車型解集對比

4 結(jié) 語

本文研究了在通行時間不確定背景下，多車型物流配送車輛的路徑優(yōu)化問題，建立以運輸總成本和配送時間為目標函數(shù)的優(yōu)化模型。根據(jù)模型和研究環(huán)境特點，設(shè)計了多目標進化遺傳算法，算法結(jié)合鏈表結(jié)構(gòu)，解編碼采用多染色體，并引入擂臺賽法則和改進精英保留策略，構(gòu)造非支配解集，加快算法的收斂速度。結(jié)合實際路網(wǎng)情況進行求解，最后得到多車型組合優(yōu)化配送，相比單車型有更好的經(jīng)濟效益，不確定因素的變化增加了解集配送成本及時長增長，加劇了解集的差異，但多車型配送平均滿載率受影響較小。本研究為配送企業(yè)的多車型實現(xiàn)組合優(yōu)化配送、貨物的及時配送提供了決策參考。