熊瑞琦,馬昌喜

(蘭州交通大學(xué) 交通運(yùn)輸學(xué)院，蘭州 730070)

多配送中心危險(xiǎn)貨物配送路徑魯棒優(yōu)化

熊瑞琦,馬昌喜*

(蘭州交通大學(xué) 交通運(yùn)輸學(xué)院，蘭州 730070)

(*通信作者電子郵箱machangxi@mail.lzjtu.cn)

針對(duì)危險(xiǎn)貨物配送路徑對(duì)不確定因素敏感度較高的問(wèn)題，提出了魯棒性可調(diào)的多配送中心危險(xiǎn)貨物配送路徑魯棒優(yōu)化方法。首先，以最小化運(yùn)輸風(fēng)險(xiǎn)和最小化運(yùn)輸成本為目標(biāo)，根據(jù) Bertsimas 魯棒離散優(yōu)化理論，建立魯棒優(yōu)化模型; 然后，在改進(jìn)型強(qiáng)度Pareto進(jìn)化算法(SPEA2)的基礎(chǔ)上設(shè)計(jì)一種三段式編碼的多目標(biāo)遺傳算法進(jìn)行求解，在遺傳操作中對(duì)不同染色體段分別采用不同的交叉和變異操作，有效避免了種群進(jìn)化過(guò)程中不可行解的產(chǎn)生; 最后，以慶陽(yáng)市西峰區(qū)部分路網(wǎng)為例進(jìn)行實(shí)證研究，并將配送方案落實(shí)到運(yùn)輸過(guò)程的路段中，形成具體的運(yùn)輸路徑。研究結(jié)果表明：在多配送中心下，運(yùn)用該魯棒優(yōu)化模型及算法，能快速得到具有較好魯棒性的危險(xiǎn)貨物配送路徑。

危險(xiǎn)貨物; 魯棒優(yōu)化; 多配送中心；改進(jìn)型強(qiáng)度Pareto進(jìn)化算法；多目標(biāo)遺傳算法

0 引言

多配送中心車(chē)輛配送路徑問(wèn)題(Multiple Depot Vehicle Routing Problem, MDVRP)是現(xiàn)代物流系統(tǒng)研究中一項(xiàng)重要的內(nèi)容，一般可以表述為：由多個(gè)物流配送中心，組織多輛運(yùn)輸車(chē)輛按照適當(dāng)?shù)倪\(yùn)輸方案，對(duì)一系列有需求的客戶(hù)在滿(mǎn)足一定的約束條件(如車(chē)輛載重、行駛路線(xiàn)、配送時(shí)間等)下進(jìn)行配送服務(wù)，并且達(dá)到一定的目標(biāo)(如經(jīng)濟(jì)成本最小、時(shí)間最短、路段風(fēng)險(xiǎn)最低等)[1]。而危險(xiǎn)貨物運(yùn)輸作為交通運(yùn)輸?shù)囊活?lèi)重要分支，其運(yùn)輸?shù)陌踩允种匾?，但在?shí)際中準(zhǔn)確獲得危險(xiǎn)貨物運(yùn)輸路段上的信息是十分困難的，大部分信息具有較大的不確定性, 因此，在多配送中心下，尋求對(duì)不確定因素不敏感的危險(xiǎn)貨物配送路徑是十分必要的。

現(xiàn)有對(duì)多配送中心危險(xiǎn)貨物配送路徑優(yōu)化問(wèn)題的研究較少，相關(guān)文獻(xiàn)資料集中于對(duì)危險(xiǎn)貨物的運(yùn)輸風(fēng)險(xiǎn)進(jìn)行分析評(píng)估以及對(duì)配送順序的優(yōu)化選擇。在國(guó)外，Verma[2]通過(guò)考慮費(fèi)用最省、風(fēng)險(xiǎn)最小，構(gòu)建了一個(gè)雙目標(biāo)優(yōu)化模型，并采用風(fēng)險(xiǎn)費(fèi)用邊界算法對(duì)模型進(jìn)行求解得到優(yōu)化路徑；但該模型中路段的數(shù)據(jù)均采用的是確定值。Jassbi等[3]以最小化運(yùn)輸里程、最小化受影響的居民數(shù)、最小化社會(huì)風(fēng)險(xiǎn)、最小化事故概率等制定了危險(xiǎn)貨物運(yùn)輸多目標(biāo)優(yōu)化的框架，雖然該框架考慮到一定的數(shù)據(jù)不確定性，但不確定數(shù)據(jù)是由事先假定的概率分布產(chǎn)生的，具有一定的局限性。Wu等[4]將多配送中心車(chē)輛路徑優(yōu)化問(wèn)題簡(jiǎn)單劃分為兩個(gè)優(yōu)化問(wèn)題：配送點(diǎn)的聚類(lèi)問(wèn)題和單配送中心車(chē)輛路徑優(yōu)化問(wèn)題，這種處理問(wèn)題的方法很難得到最優(yōu)解。在國(guó)內(nèi),王云鵬等[5]基于ArcGIS(Arc Geographic Information System)建立了危險(xiǎn)貨物運(yùn)輸路徑優(yōu)化模型。麻存瑞等[6]利用一種基于Prufer數(shù)編碼的改進(jìn)的遺傳算法求解了不確定環(huán)境下旅行商問(wèn)題的魯棒模型，但并沒(méi)有對(duì)多起點(diǎn)、多終點(diǎn)的問(wèn)題作進(jìn)一步研究。

基于以上文獻(xiàn)綜述，危險(xiǎn)貨物配送路徑優(yōu)化問(wèn)題集中于確定環(huán)境下，對(duì)不確定環(huán)境下的研究，其不確定因素往往過(guò)多依賴(lài)先驗(yàn)知識(shí)以及服從概率分布的假定[7]，所建立的模型對(duì)不確定數(shù)據(jù)變化的敏感度較高。此外，以往的配送路徑優(yōu)化以需求點(diǎn)的配送順序作為結(jié)果，并沒(méi)有具體到實(shí)際的運(yùn)輸路段中。基于以上考慮，本文采用區(qū)間值標(biāo)定不確定風(fēng)險(xiǎn)值，進(jìn)而建立不確定風(fēng)險(xiǎn)條件下多配送中心危險(xiǎn)貨物配送路徑魯棒優(yōu)化模型，并采用改進(jìn)的多目標(biāo)遺傳算法對(duì)實(shí)例進(jìn)行求解驗(yàn)證以獲得魯棒性較好的配送路徑。

1 多配送中心危險(xiǎn)貨物配送路徑魯棒優(yōu)化模型

多配送中心危險(xiǎn)貨物配送路徑問(wèn)題可以概括為：在一定區(qū)域內(nèi)，由多個(gè)危險(xiǎn)貨物配送中心，用多輛危險(xiǎn)貨物運(yùn)輸車(chē)輛，向多個(gè)客戶(hù)需求點(diǎn)進(jìn)行危險(xiǎn)貨物配送。

1.1 模型的假設(shè)條件

在基于實(shí)際配送問(wèn)題的基礎(chǔ)上對(duì)模型進(jìn)行簡(jiǎn)化，設(shè)立以下假設(shè)條件：

1)配送中心危險(xiǎn)貨物存儲(chǔ)量能夠?qū)崿F(xiàn)所有需求點(diǎn)的需求量要求；

2)任意需求點(diǎn)的危險(xiǎn)貨物需求量均小于服務(wù)該需求點(diǎn)的車(chē)輛的標(biāo)記載重；

3)運(yùn)輸車(chē)輛允許多次經(jīng)過(guò)配送中心，服務(wù)對(duì)其分配的所有需求點(diǎn)后，危險(xiǎn)貨物運(yùn)輸車(chē)輛行駛最短路徑回到各自配送中心；

4)路段的運(yùn)輸風(fēng)險(xiǎn)不確定，用區(qū)間數(shù)表達(dá)；

5)配送中心有足夠多的危險(xiǎn)貨物運(yùn)輸車(chē)輛；

6)在一次運(yùn)輸任務(wù)中，一輛危險(xiǎn)貨物運(yùn)輸車(chē)輛可服務(wù)多個(gè)需求點(diǎn)，一個(gè)需求點(diǎn)只能由一輛運(yùn)輸車(chē)輛服務(wù)，車(chē)輛可多次經(jīng)過(guò)已被服務(wù)的需求點(diǎn)；

7)一次運(yùn)輸任務(wù)中，危險(xiǎn)貨物運(yùn)輸車(chē)輛服務(wù)的需求點(diǎn)的需求總量不能超出車(chē)輛的標(biāo)記載重。

1.2 指標(biāo)體系的建立

采用G=(N,A)無(wú)向連通網(wǎng)絡(luò)圖來(lái)描述多配送中心危險(xiǎn)貨物運(yùn)輸?shù)倪\(yùn)輸網(wǎng)絡(luò)，圖中所有節(jié)點(diǎn)間的屬性信息用鄰接矩陣表示。

1.2.1 集合定義

P1={p|p=1,2,…,n′}表示危險(xiǎn)貨物的需求點(diǎn)集；P0={p′|p′=n′+1,n′+2,…,n′+m}表示危險(xiǎn)貨物配送中心；P2={p|p=n′+m+1,n′+m+2,…,n}表示危險(xiǎn)貨物運(yùn)輸網(wǎng)絡(luò)中除配送中心和需求點(diǎn)外的一般節(jié)點(diǎn)；N=P0∪P1∪P2表示所有的節(jié)點(diǎn)集；W表示危險(xiǎn)貨物運(yùn)輸網(wǎng)絡(luò)中路段的集合；Vp′={k|k=1,2,…，K}表示危險(xiǎn)貨物運(yùn)輸車(chē)輛集，p′∈P0。

1.2.2 參數(shù)定義

1.2.3 相關(guān)的變量定義

相關(guān)的變量定義如下:

1.3 目標(biāo)函數(shù)

(1)

(2)

(3)

(4)

(5)

上述模型中，式(1)是目標(biāo)函數(shù)，表示最小化危險(xiǎn)貨物運(yùn)輸風(fēng)險(xiǎn)，其中危險(xiǎn)貨物運(yùn)輸車(chē)輛完成對(duì)最后一個(gè)需求點(diǎn)的配送服務(wù)后，返回其配送中心間路段上的風(fēng)險(xiǎn)不計(jì)入式(1)中；式(2)也為目標(biāo)函數(shù)，表示最小化危險(xiǎn)貨物運(yùn)輸費(fèi)用，包括裝載危險(xiǎn)貨物時(shí)的運(yùn)輸費(fèi)用、空車(chē)行駛時(shí)的運(yùn)輸費(fèi)用以及車(chē)輛的固定使用費(fèi)用；式(3)為載重約束，表示危險(xiǎn)貨物運(yùn)輸車(chē)輛的承載量不得大于該車(chē)輛的標(biāo)記載重；式(4)為需求點(diǎn)約束，表明任意需求點(diǎn)只能由一輛危險(xiǎn)貨物運(yùn)輸車(chē)輛服務(wù)；式(5)為對(duì)車(chē)輛行駛的路徑約束，表示運(yùn)輸車(chē)輛配送服務(wù)完相應(yīng)需求點(diǎn)后返回到各自配送中心。

在目標(biāo)函數(shù)式(1)中存在max項(xiàng)，因此，式(1)不能直接進(jìn)行求解，還需要對(duì)其進(jìn)行等價(jià)轉(zhuǎn)化。利用文獻(xiàn)[8]中的魯棒離散轉(zhuǎn)換規(guī)則，將上述模型中目標(biāo)函數(shù)式(1)轉(zhuǎn)化為式(6)：

HIJ=

ΓδIJ

(6)

2 求解算法

遺傳算法與傳統(tǒng)的優(yōu)化方法(枚舉、啟發(fā)式等)相比，以生物進(jìn)化為原型，具有很好的收斂性，在計(jì)算精度要求時(shí)，計(jì)算時(shí)間少，穩(wěn)定性高，是求解多目標(biāo)優(yōu)化問(wèn)題的一個(gè)有效算法[9-10]。而上述模型中含有兩個(gè)目標(biāo)函數(shù)，屬于NP難問(wèn)題，傳統(tǒng)的單目標(biāo)遺傳算法無(wú)法求解，在針對(duì)多目標(biāo)優(yōu)化的眾多方法中，本文采用強(qiáng)度Pareto遺傳算法(Strength Pareto Evolutionary Algorithm 2, SPEA2)[11]來(lái)求解多配送中心危險(xiǎn)貨物配送魯棒優(yōu)化問(wèn)題。SPEA2算法流程如下：

步驟1 構(gòu)建內(nèi)部種群規(guī)模Pop與外部附屬種群規(guī)模Pop′，設(shè)定種群最大迭代次數(shù)T。

步驟2 令t=0，生成初始群體P0，并創(chuàng)建一個(gè)空的附屬種群P0′。

步驟3 計(jì)算內(nèi)部種群Pt與外部附屬種群Pt′中個(gè)體的適應(yīng)值。

步驟4 將Pt與Pt′中的所有非支配個(gè)體拷貝到新一代Pt+1′中。如果Pt+1′中個(gè)體的數(shù)量超過(guò)了Pop′，則對(duì)Pt′中的個(gè)體進(jìn)行種群裁減操作，以減少個(gè)體的數(shù)量；如果Pt+1′中個(gè)體的數(shù)量都小于Pop′，則將Pt與Pt′中的優(yōu)良個(gè)體添加到Pt+1′中。

步驟5 檢查是否達(dá)到最大循環(huán)代數(shù)(t≥T)。若沒(méi)達(dá)到則繼續(xù)進(jìn)行步驟6；否則運(yùn)算終止，并采用文獻(xiàn)[12]中基于集合理論的Pareto集選優(yōu)方法，選出具有代表性的最優(yōu)成員集，進(jìn)行輸出，獲得結(jié)果。

步驟6 拷貝Pt+1′生成新的內(nèi)部種群Pt+1。由預(yù)先設(shè)定的交叉與變異概率對(duì)Pt+1中的個(gè)體進(jìn)行交叉、變異操作，并令t=t+1轉(zhuǎn)步驟3。

其中，在計(jì)算內(nèi)部種群Pt與外部附屬種群Pt′中個(gè)體的適應(yīng)值之前，需給種群Pt與種群Pt′中每個(gè)個(gè)體x賦予強(qiáng)度S(x)，表示從屬于該個(gè)體x的個(gè)體數(shù)目:

S(x)=|{y|y∈Pt+Pt′∧x?y}|

(7)

其中x?y表示x對(duì)y的支配關(guān)系，進(jìn)而得到個(gè)體x的適應(yīng)值：

(8)

然而種群Pt與種群Pt′中不僅存在支配個(gè)體，也存在非支配個(gè)體，因而需計(jì)算個(gè)體間的距離并按升序排列后引入D(x)，表示個(gè)體x到其第k個(gè)鄰近個(gè)體間距離的反函數(shù)：

(9)

F(x)=R(x)+D(x)

(10)

2.1 編碼和解碼

針對(duì)多配送中心危險(xiǎn)貨物配送路徑問(wèn)題，其求解算法需要考慮三個(gè)問(wèn)題: 一是各危險(xiǎn)貨物配送中心選擇合適的客戶(hù)需求點(diǎn)，二是每個(gè)配送中心對(duì)各客戶(hù)需求點(diǎn)的配送順序，三是在對(duì)客戶(hù)需求點(diǎn)進(jìn)行配送以及返回配送中心的路徑選擇。因此，本節(jié)的遺傳算法采用了一種將配送中心、客戶(hù)需求點(diǎn)以及配送路徑相結(jié)合的混合編碼方式，具體將染色體分成三段。

染色體段1為各危險(xiǎn)貨物配送中心選擇所需服務(wù)的客戶(hù)需求點(diǎn)，其長(zhǎng)度為所有客戶(hù)需求點(diǎn)的數(shù)目，基因值為各配送中心的編號(hào)；染色體段2表示各客戶(hù)需求點(diǎn)被配送服務(wù)的先后順序，其長(zhǎng)度為所有客戶(hù)需求點(diǎn)的數(shù)目，基因值為各客戶(hù)需求點(diǎn)的編號(hào)；染色體段3表示具體的配送路徑，分別由危險(xiǎn)貨物配送中心-需求點(diǎn)編碼，需求點(diǎn)-需求點(diǎn)編碼，需求點(diǎn)-危險(xiǎn)貨物配送中心編碼3部分來(lái)構(gòu)成，其長(zhǎng)度由配送路徑節(jié)點(diǎn)數(shù)目決定(若有s個(gè)需求點(diǎn)，完成配送任務(wù)共派出t輛危險(xiǎn)貨物運(yùn)輸車(chē)輛，則該染色體段3的長(zhǎng)度為s+t)，基因值為各節(jié)點(diǎn)的編號(hào)。染色體段1和染色體段2根據(jù)危險(xiǎn)貨物運(yùn)輸車(chē)輛裝載容量進(jìn)行貪心選擇，染色體段3通過(guò)節(jié)點(diǎn)間的鄰接選擇，從而實(shí)現(xiàn)關(guān)于多配送中心危險(xiǎn)貨物配送問(wèn)題求解算法的編碼與解碼。假設(shè)運(yùn)輸網(wǎng)絡(luò)中有3個(gè)危險(xiǎn)貨物配送中心(配送中心a，b，c)參與配送7個(gè)需求點(diǎn)(節(jié)點(diǎn)1、2、3、4、5、6，7)的配送任務(wù)，需求點(diǎn)的需求量依次為3 t、4 t、2 t、3 t、5 t、1 t、3 t，車(chē)輛載重為10 t，其運(yùn)輸網(wǎng)路圖如圖1，產(chǎn)生一條三段式的混合編碼染色如下:

染色體段1：c-a-a-b-b-c-b

染色體段2：3-1-7-4-6-2-5

染色體段3： 7-5-10-a-1-b-11-4-13-2-6-c-9-8-3-12,

8-6-c-…-5,…,9-4-10-…-2

由染色體段1可知客戶(hù)需求點(diǎn)2，3由配送中心a來(lái)服務(wù)；客戶(hù)需求點(diǎn)4、5、7由配送中心b來(lái)服務(wù)；客戶(hù)需求點(diǎn)1、6由配送中心c來(lái)服務(wù)。根據(jù)染色體段1和染色體段2可知,配送中心a對(duì)需求點(diǎn)2、3的配送順序?yàn)椋?→2，進(jìn)而在滿(mǎn)足載重約束的條件下，利用貪心策略將需求點(diǎn)分配給相應(yīng)的危險(xiǎn)貨物運(yùn)輸車(chē)輛，那么危險(xiǎn)貨物配送中心a需派出一輛危險(xiǎn)貨物運(yùn)輸車(chē)輛，其配送順序?yàn)椋篴→3→2→a。同理，配送中心b需派出兩輛危險(xiǎn)貨物運(yùn)輸車(chē)輛進(jìn)行配送，第一輛車(chē)的配送順序?yàn)椋篵→ 7→ 4→b，第二輛車(chē)的配送路徑為：b→5→b。配送中心c需派出一輛危險(xiǎn)貨物運(yùn)輸車(chē)輛，其配送順序?yàn)椋篶→1→6→c。

圖1 算例運(yùn)輸網(wǎng)絡(luò)圖Fig. 1 Transport network diagram of the example

由染色體段3可知，該染色體段共有11組染色體子段，分別表示危險(xiǎn)貨物配送中心-需求點(diǎn)，需求點(diǎn)-需求點(diǎn)，需求點(diǎn)-危險(xiǎn)貨物配送中心的配送路徑。每個(gè)子段共有16個(gè)基因，代表路網(wǎng)中所有的節(jié)點(diǎn)。通過(guò)染色體段1和染色體段2可知，危險(xiǎn)貨物配送中心a需先對(duì)需求點(diǎn)3進(jìn)行配送。在這里以危險(xiǎn)貨物配送中心a與需求點(diǎn)3間的配送路徑為例詳細(xì)闡述編碼與解碼過(guò)程。首先產(chǎn)生長(zhǎng)度為16,即：7-5-10-a-1-b-11-4-13-2-6-c-9-8-3-12的初始數(shù)列，遍歷該數(shù)列尋找危險(xiǎn)貨物配送中心a，找到后將該點(diǎn)從數(shù)列中刪除，此時(shí)數(shù)列的長(zhǎng)度為15；將危險(xiǎn)貨物配送中心a作為關(guān)鍵點(diǎn)，根據(jù)危險(xiǎn)貨物運(yùn)輸網(wǎng)絡(luò)中節(jié)點(diǎn)的鄰接關(guān)系，從數(shù)列前端遍歷該數(shù)列尋找與關(guān)鍵點(diǎn)鄰接的節(jié)點(diǎn)，找到該節(jié)點(diǎn)后，將節(jié)點(diǎn)從數(shù)列中刪除，并將其作為關(guān)鍵點(diǎn)繼續(xù)根據(jù)危險(xiǎn)貨物運(yùn)輸網(wǎng)絡(luò)中的鄰接關(guān)系尋找下一節(jié)點(diǎn)，直至找到需求點(diǎn)3。若將某節(jié)點(diǎn)作為關(guān)鍵點(diǎn)后，在數(shù)列中已經(jīng)不存在與關(guān)鍵點(diǎn)鄰接的節(jié)點(diǎn)，而此時(shí)尚未尋找到需求點(diǎn)3，則說(shuō)明解碼初始數(shù)列無(wú)法得到正確的配送路徑，是不可行的，此時(shí)，應(yīng)重新產(chǎn)生數(shù)列并解碼，直到獲得兩需求點(diǎn)間的配送路徑。由以上編碼與解碼過(guò)程可知，配送路徑染色體子段的最大長(zhǎng)度不能超過(guò)16。其他10個(gè)子段的編碼與解碼同理。

圖2 染色體段3的編碼與解碼示意圖Fig. 2 Encoding and decoding of the third segment of chromosome

2.2 遺傳算子設(shè)計(jì)

該遺傳算法由錦標(biāo)賽選擇法進(jìn)行選擇操作。針對(duì)三段式的編碼方式，這里對(duì)交叉與變異操作也相應(yīng)分段進(jìn)行設(shè)計(jì)，從而提高算法搜索解的效率，避免不可行解的產(chǎn)生和早熟收斂。

2.2.1 選擇算子

采用錦標(biāo)賽選擇法。每次選取幾個(gè)個(gè)體中適應(yīng)度最高的一個(gè)個(gè)體遺傳到下一代群體中，重復(fù)該操作，直到新的種群規(guī)模達(dá)到原來(lái)的種群規(guī)模，這樣經(jīng)過(guò)選擇后的種群能以較高概率保證最優(yōu)個(gè)體被選擇，最差個(gè)體被淘汰。具體的操作步驟如下：

1)確定每次選擇的個(gè)體數(shù)量，這里以占種群數(shù)量百分比表示。

2)由種群中的個(gè)體隨機(jī)構(gòu)成不同分組，在每個(gè)組中選擇適應(yīng)度最高的個(gè)體遺傳到下一代種群中。

3)重復(fù)步驟2)，直到子代種群規(guī)模達(dá)到原有種群規(guī)模。

2.2.2 交叉算子

染色體第1段與第2段采用雙點(diǎn)交叉完成交叉操作。首先，按一定的概率任意選取兩個(gè)個(gè)體作為父代染色體，并在選定的染色體的第一段任意選取兩個(gè)基因位作為交叉點(diǎn)；其次，將選取的兩個(gè)染色體中交叉點(diǎn)之間的部分進(jìn)行互換，從而形成子代染色體。

針對(duì)染色體第3段由危險(xiǎn)貨物配送中心-需求點(diǎn)染色體子段、需求點(diǎn)-需求點(diǎn)染色體子段、需求點(diǎn)-危險(xiǎn)貨物配送中心染色體子段構(gòu)成，本文規(guī)定：在染色體第3段中若兩子段間的首末位兩節(jié)點(diǎn)基因值相同，則稱(chēng)它們?yōu)榈任蛔佣?。如圖3，選擇帶有等位子段的兩染色體S1、S2作為父代，若滿(mǎn)足交叉概率，則交換兩染色體中的等位子段V1、V2，獲得子代染色體S1′、S2′。采用這樣的交叉方法，既保證了交叉后產(chǎn)生的子代染色體的多樣性，又保證了其可行性，提高了算法的效率。

圖3 等位子段交叉示意圖Fig. 3 Schematic diagram of the intersection of allelic segments

2.2.3 變異算子

染色體第1段與第2段由逆轉(zhuǎn)錄法完成變異操作。在染色體段中隨機(jī)確定兩個(gè)不同基因位，如果滿(mǎn)足變異概率，則對(duì)這兩個(gè)基因位間的基因段執(zhí)行逆轉(zhuǎn)操作。如染色體段4-|3-5-2|，變異后為4-|2-3-5|。

染色體第3段采用等位基因變異法，由于染色體第3段為鄰接節(jié)點(diǎn)產(chǎn)生的路徑染色體具有特殊性，這里規(guī)定該染色體段中的等位基因?yàn)槠鹗脊?jié)點(diǎn)與結(jié)束節(jié)點(diǎn)具有相同基因值的基因。首先確定染色體R上發(fā)生變異的兩節(jié)點(diǎn)k1、k2，則這兩個(gè)節(jié)點(diǎn)間(包含k1、k2)的基因即為變異基因w，如圖4。若滿(mǎn)足變異概率，利用染色體段3的編碼及解碼方法產(chǎn)生相應(yīng)的等位基因w′去替代原有基因w，從而得到變異后的新染色體R′。為保證后續(xù)遺傳操作的進(jìn)行，這里要求變異后的染色體子段實(shí)際長(zhǎng)度不能超過(guò)所允許的最大長(zhǎng)度(危險(xiǎn)貨物運(yùn)輸網(wǎng)絡(luò)中節(jié)點(diǎn)總量N)。采用該變異方法能有效避免不可行染色體的產(chǎn)生。

圖4 染色體第3段變異示意圖Fig. 4 Mutation diagram of the third section of chromosome variation

3 實(shí)證研究

選取慶陽(yáng)市西峰區(qū)部分路網(wǎng)展開(kāi)實(shí)例研究，路網(wǎng)中共47個(gè)節(jié)點(diǎn)，79條路段(|N|=43,|W|=79)，其中節(jié)點(diǎn)1，2，…，12為需求點(diǎn)，節(jié)點(diǎn)13、14、15為危險(xiǎn)貨物配送中心，危險(xiǎn)貨物配送中心將派出運(yùn)輸車(chē)輛來(lái)配送服務(wù)這12個(gè)需求點(diǎn)。需求點(diǎn)由該危險(xiǎn)貨物配送中心發(fā)出的標(biāo)記載重為10 t的車(chē)輛來(lái)服務(wù)，設(shè)車(chē)輛裝載危險(xiǎn)貨物時(shí)運(yùn)輸費(fèi)用系數(shù)為200元/km，空駛時(shí)運(yùn)輸費(fèi)用系數(shù)為50元/km，每輛車(chē)的固定使用費(fèi)為400元，各需求點(diǎn)的需求量見(jiàn)表1。運(yùn)輸網(wǎng)絡(luò)中路段距離由地圖測(cè)量產(chǎn)生(單位：m)，路段風(fēng)險(xiǎn)標(biāo)稱(chēng)值在[10,99](單位：人)中隨機(jī)產(chǎn)生，由于各種原因，得到的風(fēng)險(xiǎn)標(biāo)稱(chēng)值都存在一定的偏差，這里設(shè)定運(yùn)輸風(fēng)險(xiǎn)偏差δij(0≤δij<0.5rij)為隨機(jī)產(chǎn)生的實(shí)數(shù)，結(jié)果見(jiàn)圖5(Dxxx為路段距離，Rxx為路段風(fēng)險(xiǎn)標(biāo)稱(chēng)值)。

圖5 慶陽(yáng)市西峰區(qū)部分網(wǎng)絡(luò)圖Fig. 5 Part road network in Qingyang Xifeng district

在Core i3 CPU M380 4 GB內(nèi)存的計(jì)算機(jī)配置環(huán)境下，以Visual Studio6.0為平臺(tái)編寫(xiě)代碼實(shí)現(xiàn)算法求解，設(shè)置種群大小100，最大進(jìn)化代數(shù)200，逆轉(zhuǎn)率概率0.1，交叉概率0.6，變異概率0.1，分別設(shè)置風(fēng)險(xiǎn)魯棒控制參數(shù)Γ=0、30、60，多次運(yùn)行程序得到的結(jié)果如表2～5。

表1 運(yùn)輸任務(wù)信息表Tab. 1 Transport task information

作為對(duì)比，采用改進(jìn)型非劣分類(lèi)遺傳算法(NSGA2)對(duì)相同算例進(jìn)行計(jì)算。算法參數(shù)取值和Pareto最優(yōu)解集選擇策略均與SPEA2算法相同。由表6可知，與NSGA 2算法相比，在不同Γ值下SPEA2算法所得最終解的兩個(gè)目標(biāo)函數(shù)均值均較優(yōu);同時(shí),運(yùn)算時(shí)間較少。結(jié)果表明，SPEA2算法不僅能獲得較優(yōu)的滿(mǎn)意解，且收斂速度較快。

表2 Γ=0時(shí)所得的Pareto解集Tab. 2 Pareto solution set obtained at Γ=0

表3 Γ=30時(shí)所得的Pareto解集Tab. 3 Pareto solution set obtained at Γ=30

由表2～5可知在每個(gè)Γ值下，不同Pareto解里危險(xiǎn)貨物配送中心服務(wù)的需求點(diǎn)是相同的，車(chē)輛對(duì)應(yīng)服務(wù)的需求點(diǎn)也相同，但運(yùn)輸車(chē)輛對(duì)需求點(diǎn)的配送順序以及配送路徑是不同的，使得每個(gè)Pareto解的目標(biāo)值不同，隨著風(fēng)險(xiǎn)目標(biāo)值的下降，費(fèi)用目標(biāo)值呈現(xiàn)逐步上升趨勢(shì)。

由表6和圖6可知，隨著風(fēng)險(xiǎn)魯棒控制參數(shù)的增加，最優(yōu)運(yùn)輸風(fēng)險(xiǎn)值增大，最優(yōu)運(yùn)輸費(fèi)用值也增大，理論而言，解的魯棒性增強(qiáng)在一定程度上會(huì)削弱解的最優(yōu)性。Γ值的大小反映了路段發(fā)生變化數(shù)據(jù)的多少，進(jìn)而體現(xiàn)出獲得的Pareto解對(duì)不確定數(shù)據(jù)的敏感度的高低，具體Γ取值多少，才能達(dá)到魯棒性與最優(yōu)性之間的平衡，這取決于問(wèn)題本身以及決策者自身偏好，有待進(jìn)一步研究。

表4 Γ=60時(shí)所得的Pareto解集Tab. 4 Pareto solution set obtained at Γ=60

表5 Γ取不同值時(shí)的Pareto解目標(biāo)值Tab. 5 Pareto solution for different values of Γ

表6 SPEA2算法與NSGA 2算法的性能及運(yùn)算時(shí)間比較Tab. 6 Comparison of performance and computation time between SPEA2 algorithm and NSGA2 algorithm

圖6 Γ取不同值時(shí)的Pareto解集曲線(xiàn)Fig. 6 Pareto solution set curves for different values of Γ

4 結(jié)語(yǔ)

本文采用魯棒優(yōu)化的方法，避免了通過(guò)概率分布對(duì)不確定運(yùn)輸風(fēng)險(xiǎn)數(shù)據(jù)進(jìn)行假定的依賴(lài)，只需將不確定數(shù)據(jù)界定在合理的區(qū)間，降低了對(duì)基礎(chǔ)數(shù)據(jù)的要求。在求解中，針對(duì)問(wèn)題特點(diǎn)設(shè)計(jì)了三段式編碼方法并依據(jù)編碼方法設(shè)計(jì)了相應(yīng)的解碼方法、遺傳操作從而有效避免種群進(jìn)化過(guò)程中不可行解的產(chǎn)生。在綜合考慮運(yùn)輸風(fēng)險(xiǎn)與運(yùn)輸費(fèi)用的基礎(chǔ)上，建立了多配送中心危險(xiǎn)貨物配送路徑的多目標(biāo)魯棒優(yōu)化模型，求解模型后獲得的危險(xiǎn)貨物運(yùn)輸配送方案落實(shí)到運(yùn)輸過(guò)程中的路段，具有較高的安全性、應(yīng)用性與經(jīng)濟(jì)性。同時(shí)，通過(guò)設(shè)置不同的風(fēng)險(xiǎn)魯棒控制系數(shù)可獲得不同運(yùn)輸條件下的危險(xiǎn)貨物運(yùn)輸配送方案。在實(shí)際生產(chǎn)生活中，決策者可應(yīng)用此優(yōu)化方法，通過(guò)路段數(shù)據(jù)的區(qū)間值就可獲得魯棒性較好的危險(xiǎn)貨物運(yùn)輸配送方案。

References)

[1] DESAULNIERS G, LAVIGNE J, SOUMIS F. Multi-depot vehicle scheduling problems with time windows and waiting costs[J].European Journal of Operational Research,1998, 111(3):479-494.

[2] VERMA M. A cost and expected consequence approach to planning and managing railroad transportation of hazardous materials[J]. Transportation Research Part D: Transport and Environment, 2009, 14(5):300-305.

[3] JASSBI J, MAKVANDI P. Route selection based on soft MODM framework in transportation of hazardous materials[J]. Applied Mathematical Sciences, 2010, 63(4), 3121-3132.

[4] WU T H, LOW C, BAI J W. Heuristicsolutions to multi-depot location routing problems[J].Computers and Operations Research,2002,29(10):1393-1415.

[5] 王云鵬，孫文財(cái)，李世武,等．基于ArcGIS的危險(xiǎn)貨物城市運(yùn)輸路徑優(yōu)化模型[J]．吉林大學(xué)學(xué)報(bào)(工學(xué)版), 2009, 39(1):45-49.(WANG Y P，SUN W C, LI S W, et al. Route optimization model for urban hazardous material transportation based on ArcGIS[J].Journal of Jilin University (Engineering and Technology Edition),2009，39(1):45-49.)

[6] 麻存瑞,馬昌喜.不確定旅行商問(wèn)題的魯棒模型與算法[J].計(jì)算機(jī)應(yīng)用, 2014, 34(7): 2090-2092.(MA C R, MA C X. Robust model and algorithms for uncertain traveling salesman problem[J].Journal of Computer Applications, 2014, 34(7): 2090-2092.)

[7] CAPLICE C, MAHMASSANI H S. Aspects of commuting behavior: preferred arrival time, use of information and switching propensity[J]. Transportation Research Part A: Policy & Practice, 1992, 26(5):409-418.

[8] BERTSIMAS D, SIM M. The price of robustness[J]. Operations Research,2004,52(1):35-53.

[9] 閻嘯天，武穆清．基于GA的網(wǎng)絡(luò)最短路徑多目標(biāo)優(yōu)化算法研究[J]．控制與決策，2009，24(7):1104-1109.(YAN X T, WU M Q. Research on multi-objective optimization for shortest path algorithm based on GA[J]. Control and Decision, 2009, 24(7):1104-1109.)

[10] 馬昌喜．應(yīng)急交通與物流系統(tǒng)優(yōu)化[M]. 成都:西南交通大學(xué)出版社，2014:55-58.(MA C X. Optimization of Emergency Transportation and Logistics System[M]. Chengdu: Southwest Jiaotong University Press，2014:55-58.)

[11] 鄭金華, 多目標(biāo)進(jìn)化算法及其應(yīng)用[M].北京: 科學(xué)出版社，2007： 28-32.(ZHENG J H. Multi-objective Evolutionary Algorithm and Application[M].Beijing: Science Press,2007: 28-32.)

[12] 郭雪斌. 隧道出入口駕駛員瞳孔及視點(diǎn)分布特性實(shí)驗(yàn)研究[D]. 上海: 同濟(jì)大學(xué), 2006.(GUO X B. Research on characteristic of the driver ’s pupil and eye fixation point and its distribution at the tunnel entrance and exit based on experiment [D]. Shanghai: Tongji University, 2006.)

This work is partially supported by the National Natural Science Foundation of China (51408288), the Longyuan Youth Innovation and Entrepreneurship Project (2016-43).

XIONG Ruiqi, born in 1992, M. S. candidate. His research interests include optimization and simulation of logistics system.

MA Changxi, born in 1979, Ph. D., associate professor. His research research interests include optimization of transportation system.

Robust vehicle route optimization for multi-depot hazardous materials transportation

XIONG Ruiqi,MA Changxi*

(SchoolofTrafficandTransportation,LanzhouJiaotongUniversity,LanzhouGansu730070,China)

Focused on the issue that the sensitivity of hazardous materials transportation routes to uncertain factors is excessively high, a robust vehicle route optimization method for multi-depot hazardous materials transportation was proposed. Firstly, a robust optimization model was designed under the Bertsimas robust discrete optimization theory with the objective function of minimizing transportation risks and minimizing transportation costs. Secondly, on the basis of Strength Pareto Evolutionary Algorithm 2 (SPEA2), a multi-objective genetic algorithm with three-stage encoding was designed for the model. Then, different crossover and mutation operations were performed on the different segments of chromosomes during genetic manipulation,which effectively avoided the generation of infeasible solutions during population evolution. Finally, part of Qingyang Xifeng district road network was chosen as an empirical research example. Distribution plan was carried out at transportation process to form some specific transportation routes. The results show that better robust hazardous materials transportation routes can be quickly obtained by using the robust model and algorithm under multi-depot situation.

hazardous materials; robust optimization; multi-depots; Strength Pareto Evolutionary Algorithm 2 (SPEA2); multiple objectives genetic algorithm

2016-10-31;

2016-12-30。

國(guó)家自然科學(xué)基金資助項(xiàng)目(51408288)；隴原青年創(chuàng)新創(chuàng)業(yè)人才項(xiàng)目(2016-43)。

熊瑞琦(1992—)，男，湖北襄陽(yáng)人，碩士研究生，主要研究方向：物流系統(tǒng)優(yōu)化與仿真； 馬昌喜(1979—)，男，湖北漢川人，副教授，博士，主要研究方向：交通運(yùn)輸系統(tǒng)優(yōu)化。

1001-9081(2017)05-1485-06

10.11772/j.issn.1001-9081.2017.05.1485

TP301.6

A