朱澤國(guó)，廣曉平，郭 敏

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

多車型路徑優(yōu)化問(wèn)題是傳統(tǒng)車輛路徑問(wèn)題的延伸和拓展，因其特有的時(shí)效性、不確定性及多重目標(biāo)約束特點(diǎn)符合實(shí)際應(yīng)用背景，因此，具有較高的研究?jī)r(jià)值。

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

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

1 模型構(gòu)建

1.1 問(wèn)題描述

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

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

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

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

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

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

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

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

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

1.3 模型構(gòu)建

針對(duì)本問(wèn)題考慮2個(gè)優(yōu)化目標(biāo)，即總出行成本最小和配送時(shí)間最短。

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

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

(1)

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

2)配送時(shí)間最短目標(biāo)函數(shù)

(2)

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

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

(3)

約束條件如下

(4)

(5)

(6)

(7)

(8)

(9)

(10)

ai

(11)

(12)

2 求解算法設(shè)計(jì)

2.1 算法描述

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

2.2 種群初始化

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

2.3 染色體編碼

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

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

2.4 選擇算子

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

2.5 交叉算子

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

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

圖1 體間染色體交叉

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

圖2 色體交叉

2.6 變異算子

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

圖3 色體變異

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

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

2.8 改進(jìn)精英保留策略

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

3 算例分析

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

表2 客戶信息表

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

各配送中心配置兩種車型：車型A及車型B，共計(jì)8輛(編號(hào)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)存平臺(tái)，使用Python語(yǔ)言集成開發(fā)環(huán)境Pycharm中，利用前述模型及算法分別對(duì)單車型、多車型配送路徑進(jìn)行求解，得到各不確定參數(shù)下的解集，為驗(yàn)證多車型解集的優(yōu)越性，與單車型解集進(jìn)行比較。

當(dāng)Γ=0時(shí)，即不考慮路段通行時(shí)間這一不確定因素。在此確定情況下，計(jì)算得到多車型解集，如表3所示，包括配送路徑、車輛組合、運(yùn)輸成本、時(shí)間及滿載率等，多車型解集1使用車型A、B各2輛，其中編號(hào)為43的配送車輛僅為客戶8服務(wù)，滿載率較低，而解集1平均滿載率也僅為70.07%，多車型解集2的車型選擇為：1輛A車型、2輛B車型，平均滿載率達(dá)到93.14%。可以看出，多車型解集1因?yàn)檐囆徒M合不佳，存在裝載率較低車輛，嚴(yán)重拉低平均裝載率，造成車輛資源浪費(fèi)，使得運(yùn)輸成本升高。

表3 Γ=0時(shí)多車型Pareto 解集

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

表4 Γ=0時(shí)單車型 Pareto解集

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

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

表5 多車型與單車型解集對(duì)比

4 結(jié) 語(yǔ)

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