熊瑞琦,馬昌喜
(蘭州交通大學 交通運輸學院,蘭州 730070)
多配送中心危險貨物配送路徑魯棒優(yōu)化
熊瑞琦,馬昌喜*
(蘭州交通大學 交通運輸學院,蘭州 730070)
(*通信作者電子郵箱machangxi@mail.lzjtu.cn)
針對危險貨物配送路徑對不確定因素敏感度較高的問題,提出了魯棒性可調的多配送中心危險貨物配送路徑魯棒優(yōu)化方法。首先,以最小化運輸風險和最小化運輸成本為目標,根據(jù) Bertsimas 魯棒離散優(yōu)化理論,建立魯棒優(yōu)化模型; 然后,在改進型強度Pareto進化算法(SPEA2)的基礎上設計一種三段式編碼的多目標遺傳算法進行求解,在遺傳操作中對不同染色體段分別采用不同的交叉和變異操作,有效避免了種群進化過程中不可行解的產(chǎn)生; 最后,以慶陽市西峰區(qū)部分路網(wǎng)為例進行實證研究,并將配送方案落實到運輸過程的路段中,形成具體的運輸路徑。研究結果表明:在多配送中心下,運用該魯棒優(yōu)化模型及算法,能快速得到具有較好魯棒性的危險貨物配送路徑。
危險貨物; 魯棒優(yōu)化; 多配送中心;改進型強度Pareto進化算法;多目標遺傳算法
多配送中心車輛配送路徑問題(Multiple Depot Vehicle Routing Problem, MDVRP)是現(xiàn)代物流系統(tǒng)研究中一項重要的內容,一般可以表述為:由多個物流配送中心,組織多輛運輸車輛按照適當?shù)倪\輸方案,對一系列有需求的客戶在滿足一定的約束條件(如車輛載重、行駛路線、配送時間等)下進行配送服務,并且達到一定的目標(如經(jīng)濟成本最小、時間最短、路段風險最低等)[1]。而危險貨物運輸作為交通運輸?shù)囊活愔匾种?,其運輸?shù)陌踩允种匾趯嶋H中準確獲得危險貨物運輸路段上的信息是十分困難的,大部分信息具有較大的不確定性, 因此,在多配送中心下,尋求對不確定因素不敏感的危險貨物配送路徑是十分必要的。
現(xiàn)有對多配送中心危險貨物配送路徑優(yōu)化問題的研究較少,相關文獻資料集中于對危險貨物的運輸風險進行分析評估以及對配送順序的優(yōu)化選擇。在國外,Verma[2]通過考慮費用最省、風險最小,構建了一個雙目標優(yōu)化模型,并采用風險費用邊界算法對模型進行求解得到優(yōu)化路徑;但該模型中路段的數(shù)據(jù)均采用的是確定值。Jassbi等[3]以最小化運輸里程、最小化受影響的居民數(shù)、最小化社會風險、最小化事故概率等制定了危險貨物運輸多目標優(yōu)化的框架,雖然該框架考慮到一定的數(shù)據(jù)不確定性,但不確定數(shù)據(jù)是由事先假定的概率分布產(chǎn)生的,具有一定的局限性。Wu等[4]將多配送中心車輛路徑優(yōu)化問題簡單劃分為兩個優(yōu)化問題:配送點的聚類問題和單配送中心車輛路徑優(yōu)化問題,這種處理問題的方法很難得到最優(yōu)解。在國內,王云鵬等[5]基于ArcGIS(Arc Geographic Information System)建立了危險貨物運輸路徑優(yōu)化模型。麻存瑞等[6]利用一種基于Prufer數(shù)編碼的改進的遺傳算法求解了不確定環(huán)境下旅行商問題的魯棒模型,但并沒有對多起點、多終點的問題作進一步研究。
基于以上文獻綜述,危險貨物配送路徑優(yōu)化問題集中于確定環(huán)境下,對不確定環(huán)境下的研究,其不確定因素往往過多依賴先驗知識以及服從概率分布的假定[7],所建立的模型對不確定數(shù)據(jù)變化的敏感度較高。此外,以往的配送路徑優(yōu)化以需求點的配送順序作為結果,并沒有具體到實際的運輸路段中?;谝陨峡紤],本文采用區(qū)間值標定不確定風險值,進而建立不確定風險條件下多配送中心危險貨物配送路徑魯棒優(yōu)化模型,并采用改進的多目標遺傳算法對實例進行求解驗證以獲得魯棒性較好的配送路徑。
多配送中心危險貨物配送路徑問題可以概括為:在一定區(qū)域內,由多個危險貨物配送中心,用多輛危險貨物運輸車輛,向多個客戶需求點進行危險貨物配送。
1.1 模型的假設條件
在基于實際配送問題的基礎上對模型進行簡化,設立以下假設條件:
1)配送中心危險貨物存儲量能夠實現(xiàn)所有需求點的需求量要求;
2)任意需求點的危險貨物需求量均小于服務該需求點的車輛的標記載重;
3)運輸車輛允許多次經(jīng)過配送中心,服務對其分配的所有需求點后,危險貨物運輸車輛行駛最短路徑回到各自配送中心;
4)路段的運輸風險不確定,用區(qū)間數(shù)表達;
5)配送中心有足夠多的危險貨物運輸車輛;
6)在一次運輸任務中,一輛危險貨物運輸車輛可服務多個需求點,一個需求點只能由一輛運輸車輛服務,車輛可多次經(jīng)過已被服務的需求點;
7)一次運輸任務中,危險貨物運輸車輛服務的需求點的需求總量不能超出車輛的標記載重。
1.2 指標體系的建立
采用G=(N,A)無向連通網(wǎng)絡圖來描述多配送中心危險貨物運輸?shù)倪\輸網(wǎng)絡,圖中所有節(jié)點間的屬性信息用鄰接矩陣表示。
1.2.1 集合定義
P1={p|p=1,2,…,n′}表示危險貨物的需求點集;P0={p′|p′=n′+1,n′+2,…,n′+m}表示危險貨物配送中心;P2={p|p=n′+m+1,n′+m+2,…,n}表示危險貨物運輸網(wǎng)絡中除配送中心和需求點外的一般節(jié)點;N=P0∪P1∪P2表示所有的節(jié)點集;W表示危險貨物運輸網(wǎng)絡中路段的集合;Vp′={k|k=1,2,…,K}表示危險貨物運輸車輛集,p′∈P0。
1.2.2 參數(shù)定義
1.2.3 相關的變量定義
相關的變量定義如下:
1.3 目標函數(shù)
(1)
(2)
(3)
(4)
(5)
上述模型中,式(1)是目標函數(shù),表示最小化危險貨物運輸風險,其中危險貨物運輸車輛完成對最后一個需求點的配送服務后,返回其配送中心間路段上的風險不計入式(1)中;式(2)也為目標函數(shù),表示最小化危險貨物運輸費用,包括裝載危險貨物時的運輸費用、空車行駛時的運輸費用以及車輛的固定使用費用;式(3)為載重約束,表示危險貨物運輸車輛的承載量不得大于該車輛的標記載重;式(4)為需求點約束,表明任意需求點只能由一輛危險貨物運輸車輛服務;式(5)為對車輛行駛的路徑約束,表示運輸車輛配送服務完相應需求點后返回到各自配送中心。
在目標函數(shù)式(1)中存在max項,因此,式(1)不能直接進行求解,還需要對其進行等價轉化。利用文獻[8]中的魯棒離散轉換規(guī)則,將上述模型中目標函數(shù)式(1)轉化為式(6):
HIJ=
ΓδIJ
(6)
遺傳算法與傳統(tǒng)的優(yōu)化方法(枚舉、啟發(fā)式等)相比,以生物進化為原型,具有很好的收斂性,在計算精度要求時,計算時間少,穩(wěn)定性高,是求解多目標優(yōu)化問題的一個有效算法[9-10]。而上述模型中含有兩個目標函數(shù),屬于NP難問題,傳統(tǒng)的單目標遺傳算法無法求解,在針對多目標優(yōu)化的眾多方法中,本文采用強度Pareto遺傳算法(Strength Pareto Evolutionary Algorithm 2, SPEA2)[11]來求解多配送中心危險貨物配送魯棒優(yōu)化問題。SPEA2算法流程如下:
步驟1 構建內部種群規(guī)模Pop與外部附屬種群規(guī)模Pop′,設定種群最大迭代次數(shù)T。
步驟2 令t=0,生成初始群體P0,并創(chuàng)建一個空的附屬種群P0′。
步驟3 計算內部種群Pt與外部附屬種群Pt′中個體的適應值。
步驟4 將Pt與Pt′中的所有非支配個體拷貝到新一代Pt+1′中。如果Pt+1′中個體的數(shù)量超過了Pop′,則對Pt′中的個體進行種群裁減操作,以減少個體的數(shù)量;如果Pt+1′中個體的數(shù)量都小于Pop′,則將Pt與Pt′中的優(yōu)良個體添加到Pt+1′中。
步驟5 檢查是否達到最大循環(huán)代數(shù)(t≥T)。若沒達到則繼續(xù)進行步驟6;否則運算終止,并采用文獻[12]中基于集合理論的Pareto集選優(yōu)方法,選出具有代表性的最優(yōu)成員集,進行輸出,獲得結果。
步驟6 拷貝Pt+1′生成新的內部種群Pt+1。由預先設定的交叉與變異概率對Pt+1中的個體進行交叉、變異操作,并令t=t+1轉步驟3。
其中,在計算內部種群Pt與外部附屬種群Pt′中個體的適應值之前,需給種群Pt與種群Pt′中每個個體x賦予強度S(x),表示從屬于該個體x的個體數(shù)目:
S(x)=|{y|y∈Pt+Pt′∧x?y}|
(7)
其中x?y表示x對y的支配關系,進而得到個體x的適應值:
(8)
然而種群Pt與種群Pt′中不僅存在支配個體,也存在非支配個體,因而需計算個體間的距離并按升序排列后引入D(x),表示個體x到其第k個鄰近個體間距離的反函數(shù):
(9)
F(x)=R(x)+D(x)
(10)
2.1 編碼和解碼
針對多配送中心危險貨物配送路徑問題,其求解算法需要考慮三個問題: 一是各危險貨物配送中心選擇合適的客戶需求點,二是每個配送中心對各客戶需求點的配送順序,三是在對客戶需求點進行配送以及返回配送中心的路徑選擇。因此,本節(jié)的遺傳算法采用了一種將配送中心、客戶需求點以及配送路徑相結合的混合編碼方式,具體將染色體分成三段。
染色體段1為各危險貨物配送中心選擇所需服務的客戶需求點,其長度為所有客戶需求點的數(shù)目,基因值為各配送中心的編號;染色體段2表示各客戶需求點被配送服務的先后順序,其長度為所有客戶需求點的數(shù)目,基因值為各客戶需求點的編號;染色體段3表示具體的配送路徑,分別由危險貨物配送中心-需求點編碼,需求點-需求點編碼,需求點-危險貨物配送中心編碼3部分來構成,其長度由配送路徑節(jié)點數(shù)目決定(若有s個需求點,完成配送任務共派出t輛危險貨物運輸車輛,則該染色體段3的長度為s+t),基因值為各節(jié)點的編號。染色體段1和染色體段2根據(jù)危險貨物運輸車輛裝載容量進行貪心選擇,染色體段3通過節(jié)點間的鄰接選擇,從而實現(xiàn)關于多配送中心危險貨物配送問題求解算法的編碼與解碼。假設運輸網(wǎng)絡中有3個危險貨物配送中心(配送中心a,b,c)參與配送7個需求點(節(jié)點1、2、3、4、5、6,7)的配送任務,需求點的需求量依次為3 t、4 t、2 t、3 t、5 t、1 t、3 t,車輛載重為10 t,其運輸網(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可知客戶需求點2,3由配送中心a來服務;客戶需求點4、5、7由配送中心b來服務;客戶需求點1、6由配送中心c來服務。根據(jù)染色體段1和染色體段2可知,配送中心a對需求點2、3的配送順序為:3→2,進而在滿足載重約束的條件下,利用貪心策略將需求點分配給相應的危險貨物運輸車輛,那么危險貨物配送中心a需派出一輛危險貨物運輸車輛,其配送順序為:a→3→2→a。同理,配送中心b需派出兩輛危險貨物運輸車輛進行配送,第一輛車的配送順序為:b→ 7→ 4→b,第二輛車的配送路徑為:b→5→b。配送中心c需派出一輛危險貨物運輸車輛,其配送順序為:c→1→6→c。
圖1 算例運輸網(wǎng)絡圖Fig. 1 Transport network diagram of the example
由染色體段3可知,該染色體段共有11組染色體子段,分別表示危險貨物配送中心-需求點,需求點-需求點,需求點-危險貨物配送中心的配送路徑。每個子段共有16個基因,代表路網(wǎng)中所有的節(jié)點。通過染色體段1和染色體段2可知,危險貨物配送中心a需先對需求點3進行配送。在這里以危險貨物配送中心a與需求點3間的配送路徑為例詳細闡述編碼與解碼過程。首先產(chǎn)生長度為16,即:7-5-10-a-1-b-11-4-13-2-6-c-9-8-3-12的初始數(shù)列,遍歷該數(shù)列尋找危險貨物配送中心a,找到后將該點從數(shù)列中刪除,此時數(shù)列的長度為15;將危險貨物配送中心a作為關鍵點,根據(jù)危險貨物運輸網(wǎng)絡中節(jié)點的鄰接關系,從數(shù)列前端遍歷該數(shù)列尋找與關鍵點鄰接的節(jié)點,找到該節(jié)點后,將節(jié)點從數(shù)列中刪除,并將其作為關鍵點繼續(xù)根據(jù)危險貨物運輸網(wǎng)絡中的鄰接關系尋找下一節(jié)點,直至找到需求點3。若將某節(jié)點作為關鍵點后,在數(shù)列中已經(jīng)不存在與關鍵點鄰接的節(jié)點,而此時尚未尋找到需求點3,則說明解碼初始數(shù)列無法得到正確的配送路徑,是不可行的,此時,應重新產(chǎn)生數(shù)列并解碼,直到獲得兩需求點間的配送路徑。由以上編碼與解碼過程可知,配送路徑染色體子段的最大長度不能超過16。其他10個子段的編碼與解碼同理。
圖2 染色體段3的編碼與解碼示意圖Fig. 2 Encoding and decoding of the third segment of chromosome
2.2 遺傳算子設計
該遺傳算法由錦標賽選擇法進行選擇操作。針對三段式的編碼方式,這里對交叉與變異操作也相應分段進行設計,從而提高算法搜索解的效率,避免不可行解的產(chǎn)生和早熟收斂。
2.2.1 選擇算子
采用錦標賽選擇法。每次選取幾個個體中適應度最高的一個個體遺傳到下一代群體中,重復該操作,直到新的種群規(guī)模達到原來的種群規(guī)模,這樣經(jīng)過選擇后的種群能以較高概率保證最優(yōu)個體被選擇,最差個體被淘汰。具體的操作步驟如下:
1)確定每次選擇的個體數(shù)量,這里以占種群數(shù)量百分比表示。
2)由種群中的個體隨機構成不同分組,在每個組中選擇適應度最高的個體遺傳到下一代種群中。
3)重復步驟2),直到子代種群規(guī)模達到原有種群規(guī)模。
2.2.2 交叉算子
染色體第1段與第2段采用雙點交叉完成交叉操作。首先,按一定的概率任意選取兩個個體作為父代染色體,并在選定的染色體的第一段任意選取兩個基因位作為交叉點;其次,將選取的兩個染色體中交叉點之間的部分進行互換,從而形成子代染色體。
針對染色體第3段由危險貨物配送中心-需求點染色體子段、需求點-需求點染色體子段、需求點-危險貨物配送中心染色體子段構成,本文規(guī)定:在染色體第3段中若兩子段間的首末位兩節(jié)點基因值相同,則稱它們?yōu)榈任蛔佣?。如圖3,選擇帶有等位子段的兩染色體S1、S2作為父代,若滿足交叉概率,則交換兩染色體中的等位子段V1、V2,獲得子代染色體S1′、S2′。采用這樣的交叉方法,既保證了交叉后產(chǎn)生的子代染色體的多樣性,又保證了其可行性,提高了算法的效率。
圖3 等位子段交叉示意圖Fig. 3 Schematic diagram of the intersection of allelic segments
2.2.3 變異算子
染色體第1段與第2段由逆轉錄法完成變異操作。在染色體段中隨機確定兩個不同基因位,如果滿足變異概率,則對這兩個基因位間的基因段執(zhí)行逆轉操作。如染色體段4-|3-5-2|,變異后為4-|2-3-5|。
染色體第3段采用等位基因變異法,由于染色體第3段為鄰接節(jié)點產(chǎn)生的路徑染色體具有特殊性,這里規(guī)定該染色體段中的等位基因為起始節(jié)點與結束節(jié)點具有相同基因值的基因。首先確定染色體R上發(fā)生變異的兩節(jié)點k1、k2,則這兩個節(jié)點間(包含k1、k2)的基因即為變異基因w,如圖4。若滿足變異概率,利用染色體段3的編碼及解碼方法產(chǎn)生相應的等位基因w′去替代原有基因w,從而得到變異后的新染色體R′。為保證后續(xù)遺傳操作的進行,這里要求變異后的染色體子段實際長度不能超過所允許的最大長度(危險貨物運輸網(wǎng)絡中節(jié)點總量N)。采用該變異方法能有效避免不可行染色體的產(chǎn)生。
圖4 染色體第3段變異示意圖Fig. 4 Mutation diagram of the third section of chromosome variation
選取慶陽市西峰區(qū)部分路網(wǎng)展開實例研究,路網(wǎng)中共47個節(jié)點,79條路段(|N|=43,|W|=79),其中節(jié)點1,2,…,12為需求點,節(jié)點13、14、15為危險貨物配送中心,危險貨物配送中心將派出運輸車輛來配送服務這12個需求點。需求點由該危險貨物配送中心發(fā)出的標記載重為10 t的車輛來服務,設車輛裝載危險貨物時運輸費用系數(shù)為200元/km,空駛時運輸費用系數(shù)為50元/km,每輛車的固定使用費為400元,各需求點的需求量見表1。運輸網(wǎng)絡中路段距離由地圖測量產(chǎn)生(單位:m),路段風險標稱值在[10,99](單位:人)中隨機產(chǎn)生,由于各種原因,得到的風險標稱值都存在一定的偏差,這里設定運輸風險偏差δij(0≤δij<0.5rij)為隨機產(chǎn)生的實數(shù),結果見圖5(Dxxx為路段距離,Rxx為路段風險標稱值)。
圖5 慶陽市西峰區(qū)部分網(wǎng)絡圖Fig. 5 Part road network in Qingyang Xifeng district
在Core i3 CPU M380 4 GB內存的計算機配置環(huán)境下,以Visual Studio6.0為平臺編寫代碼實現(xiàn)算法求解,設置種群大小100,最大進化代數(shù)200,逆轉率概率0.1,交叉概率0.6,變異概率0.1,分別設置風險魯棒控制參數(shù)Γ=0、30、60,多次運行程序得到的結果如表2~5。
表1 運輸任務信息表Tab. 1 Transport task information
作為對比,采用改進型非劣分類遺傳算法(NSGA2)對相同算例進行計算。算法參數(shù)取值和Pareto最優(yōu)解集選擇策略均與SPEA2算法相同。由表6可知,與NSGA 2算法相比,在不同Γ值下SPEA2算法所得最終解的兩個目標函數(shù)均值均較優(yōu);同時,運算時間較少。結果表明,SPEA2算法不僅能獲得較優(yōu)的滿意解,且收斂速度較快。
表2 Γ=0時所得的Pareto解集Tab. 2 Pareto solution set obtained at Γ=0
表3 Γ=30時所得的Pareto解集Tab. 3 Pareto solution set obtained at Γ=30
由表2~5可知在每個Γ值下,不同Pareto解里危險貨物配送中心服務的需求點是相同的,車輛對應服務的需求點也相同,但運輸車輛對需求點的配送順序以及配送路徑是不同的,使得每個Pareto解的目標值不同,隨著風險目標值的下降,費用目標值呈現(xiàn)逐步上升趨勢。
由表6和圖6可知,隨著風險魯棒控制參數(shù)的增加,最優(yōu)運輸風險值增大,最優(yōu)運輸費用值也增大,理論而言,解的魯棒性增強在一定程度上會削弱解的最優(yōu)性。Γ值的大小反映了路段發(fā)生變化數(shù)據(jù)的多少,進而體現(xiàn)出獲得的Pareto解對不確定數(shù)據(jù)的敏感度的高低,具體Γ取值多少,才能達到魯棒性與最優(yōu)性之間的平衡,這取決于問題本身以及決策者自身偏好,有待進一步研究。
表4 Γ=60時所得的Pareto解集Tab. 4 Pareto solution set obtained at Γ=60
表5 Γ取不同值時的Pareto解目標值Tab. 5 Pareto solution for different values of Γ
表6 SPEA2算法與NSGA 2算法的性能及運算時間比較Tab. 6 Comparison of performance and computation time between SPEA2 algorithm and NSGA2 algorithm
圖6 Γ取不同值時的Pareto解集曲線Fig. 6 Pareto solution set curves for different values of Γ
本文采用魯棒優(yōu)化的方法,避免了通過概率分布對不確定運輸風險數(shù)據(jù)進行假定的依賴,只需將不確定數(shù)據(jù)界定在合理的區(qū)間,降低了對基礎數(shù)據(jù)的要求。在求解中,針對問題特點設計了三段式編碼方法并依據(jù)編碼方法設計了相應的解碼方法、遺傳操作從而有效避免種群進化過程中不可行解的產(chǎn)生。在綜合考慮運輸風險與運輸費用的基礎上,建立了多配送中心危險貨物配送路徑的多目標魯棒優(yōu)化模型,求解模型后獲得的危險貨物運輸配送方案落實到運輸過程中的路段,具有較高的安全性、應用性與經(jīng)濟性。同時,通過設置不同的風險魯棒控制系數(shù)可獲得不同運輸條件下的危險貨物運輸配送方案。在實際生產(chǎn)生活中,決策者可應用此優(yōu)化方法,通過路段數(shù)據(jù)的區(qū)間值就可獲得魯棒性較好的危險貨物運輸配送方案。
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] 王云鵬,孫文財,李世武,等.基于ArcGIS的危險貨物城市運輸路徑優(yōu)化模型[J].吉林大學學報(工學版), 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] 麻存瑞,馬昌喜.不確定旅行商問題的魯棒模型與算法[J].計算機應用, 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)絡最短路徑多目標優(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] 馬昌喜.應急交通與物流系統(tǒng)優(yōu)化[M]. 成都:西南交通大學出版社,2014:55-58.(MA C X. Optimization of Emergency Transportation and Logistics System[M]. Chengdu: Southwest Jiaotong University Press,2014:55-58.)
[11] 鄭金華, 多目標進化算法及其應用[M].北京: 科學出版社,2007: 28-32.(ZHENG J H. Multi-objective Evolutionary Algorithm and Application[M].Beijing: Science Press,2007: 28-32.)
[12] 郭雪斌. 隧道出入口駕駛員瞳孔及視點分布特性實驗研究[D]. 上海: 同濟大學, 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。
國家自然科學基金資助項目(51408288);隴原青年創(chuàng)新創(chuàng)業(yè)人才項目(2016-43)。
熊瑞琦(1992—),男,湖北襄陽人,碩士研究生,主要研究方向:物流系統(tǒng)優(yōu)化與仿真; 馬昌喜(1979—),男,湖北漢川人,副教授,博士,主要研究方向:交通運輸系統(tǒng)優(yōu)化。
1001-9081(2017)05-1485-06
10.11772/j.issn.1001-9081.2017.05.1485
TP301.6
A