謝雪梅 楊家其

(武漢理工大學(xué)交通學(xué)院 武漢 430063)

帶時(shí)間窗的整車多式聯(lián)運(yùn)路徑優(yōu)化模型研究

謝雪梅 楊家其

(武漢理工大學(xué)交通學(xué)院 武漢 430063)

整車物流作為汽車物流核心組成部分，如何優(yōu)化控制成本成為物流和汽車行業(yè)關(guān)注點(diǎn).針對整車物流路徑優(yōu)化問題，在實(shí)現(xiàn)物流成本最低和滿足時(shí)間約束的條件下，引用多式聯(lián)運(yùn)理論，構(gòu)建帶有時(shí)間窗的整車物流多式聯(lián)運(yùn)0-1整數(shù)規(guī)劃模型，綜合考慮運(yùn)輸成本、換裝成本、風(fēng)險(xiǎn)成本和提早到達(dá)造成的倉儲成本或推遲到達(dá)造成的懲罰成本，設(shè)計(jì)基于Matlab的遺傳算法進(jìn)行求解，并結(jié)合實(shí)例進(jìn)行驗(yàn)證分析.結(jié)果表明，該模型和算法對于解決整車多式聯(lián)運(yùn)線路優(yōu)化具有可行性和實(shí)用性.

整車物流；多式聯(lián)運(yùn)；時(shí)間窗；路徑優(yōu)化；遺傳算法

0 引 言

整車物流作為汽車物流的核心，對于如何控制物流成本成為人們關(guān)注的焦點(diǎn).整車物流的運(yùn)輸方式包括水路、公路和鐵路，且各具特點(diǎn).我國整車物流采用鐵路運(yùn)輸占比僅為7%，公路運(yùn)輸則高達(dá)85%，其余僅8%為水路運(yùn)輸[1].然而公路運(yùn)輸具有成本和污染等方面的局限性，且只采用一種運(yùn)輸方式在物流成本與時(shí)效性上的缺陷日漸明顯，因此，在整車物流過程中如果將鐵路、公路、水路靈活分配運(yùn)用，發(fā)揮各自優(yōu)勢，引用多式聯(lián)運(yùn)的思路，對于降低物流成本具有重要的意義.

目前，針對帶時(shí)間窗的車輛路徑問題已有一些研究，易云飛等[2]采用改進(jìn)伊藤算法求解帶有軟時(shí)間窗的車輛路徑配送問題，汪秋云等[3]論證了運(yùn)用混合算法對帶有軟時(shí)間窗的車輛路徑優(yōu)化的求解優(yōu)勢.針對多式聯(lián)運(yùn)問題，Ekki[4]以配送時(shí)間和路程最短為目標(biāo)，不考慮不同運(yùn)輸方式的單位成本差異，用最短時(shí)間完成貨物配送.Chang[5]構(gòu)建多目標(biāo)多式聯(lián)運(yùn)優(yōu)化模型，實(shí)現(xiàn)不同商品共同配送.以上都是針對這兩類問題分別展開研究，帶時(shí)間窗的車輛路徑的研究主要為帶軟時(shí)間窗約束，而多式聯(lián)運(yùn)的研究對象較多針對集裝箱，但將兩者綜合研究較少，同時(shí)對整車物流多式聯(lián)運(yùn)的研究也較少.相對于傳統(tǒng)單一的運(yùn)輸方式系統(tǒng)，多式聯(lián)運(yùn)具有降低成本、節(jié)約時(shí)間等優(yōu)勢.文中將帶時(shí)間窗的車輛路徑問題引入多式聯(lián)運(yùn)的理論，對于整車物流成本問題，建立帶有時(shí)間窗的多式聯(lián)運(yùn)線路優(yōu)化模型，充分發(fā)揮多式聯(lián)運(yùn)的優(yōu)勢，實(shí)現(xiàn)降低整車物流成本的目的.在實(shí)際運(yùn)用中解決車輛路徑問題需要尋找有效的算法求解，求解算法包括啟發(fā)式算法及精確算法.規(guī)模較大的路徑問題采用啟發(fā)式算法，包括粒子群算法、遺傳算法、鄰域搜索算法、蟻群算法等，而精確算法主要適用于規(guī)模較小的路徑問題[6].竇莉薇[7]采用優(yōu)化后的蟻群算法研究路徑問題.Chen等[8]開拓了迭代鄰域下降算法處理配送時(shí)間及配送貨物種類具有周期性的車輛路徑問題.儲慶中等[9]針對危險(xiǎn)品，對其運(yùn)輸線路進(jìn)行優(yōu)化，采用遺傳算法，產(chǎn)生最穩(wěn)定的最優(yōu)解.王旭等[10]以總成本最低為目標(biāo)，但未考慮風(fēng)險(xiǎn)成本，采用遺傳算法求解.徐玨等[11]根據(jù)配送點(diǎn)分散且各自配送點(diǎn)需求量小的特點(diǎn)，建立運(yùn)輸線路網(wǎng)，使用遺傳算法優(yōu)化，使得配送成本降低及送達(dá)時(shí)間更為準(zhǔn)確.遺傳算法在解決路徑問題時(shí)，具有很好的收斂性及良好的全局搜索能力，計(jì)算時(shí)間短且精度高，過程較為簡單[12]，因此，文中采用遺傳算法進(jìn)行模型求解.

基于此，文中將整車物流與多式聯(lián)運(yùn)相聯(lián)系，構(gòu)建帶時(shí)間窗的整車多式聯(lián)運(yùn)路徑優(yōu)化模型，實(shí)現(xiàn)物流總成本最低.綜合考慮運(yùn)輸成本，換裝成本，倉儲成本或懲罰成本和運(yùn)輸和換裝可能發(fā)生的風(fēng)險(xiǎn)成本，采用遺傳算法進(jìn)行求解，在Matlab中實(shí)現(xiàn)，并結(jié)合案例進(jìn)行分析.

1 帶有時(shí)間窗的整車物流多式聯(lián)運(yùn)模型分析與構(gòu)建

1.1 問題描述

整車物流運(yùn)作模式為車輛從主機(jī)廠下線入庫到整車分撥中心，進(jìn)行檢查和測試后，再由整車分撥中心(vehicle distribution center，VDC)經(jīng)過一次運(yùn)輸至各區(qū)域整車倉儲中心(vehicle storage center，VSC)，VSC起到中轉(zhuǎn)的作用，最后從各區(qū)域整車倉儲中心二次運(yùn)輸至分散的經(jīng)銷商[13]，見圖1.車輛由主機(jī)廠短途運(yùn)輸?shù)秸嚪謸苤行?，主要為公路運(yùn)輸.而一次運(yùn)輸為中長途運(yùn)輸，有鐵路、公路、水路三種方式可選，這是整車物流多式聯(lián)運(yùn)的階段，作為文中研究的對象，而二次運(yùn)輸較為分散，主要采用公路運(yùn)輸.

圖1 整車物流運(yùn)作模式

因此，文中整車物流多式聯(lián)運(yùn)研究的范圍主要是指車輛由整車分撥中心配送至整車倉儲中心的一次運(yùn)輸階段.

車輛由VDC配送至VSC，中間需要經(jīng)過N個(gè)中轉(zhuǎn)點(diǎn)，相鄰中轉(zhuǎn)點(diǎn)之間有水路、公路、鐵路三種運(yùn)輸方式可選，產(chǎn)生不同的運(yùn)輸成本和運(yùn)輸時(shí)間.各個(gè)中轉(zhuǎn)點(diǎn)若轉(zhuǎn)換其它運(yùn)輸方式，因此，產(chǎn)生一定的換裝成本和時(shí)間.不同運(yùn)輸方式在運(yùn)輸和換裝過程中，可能發(fā)生車輛的丟失、損壞等情況，產(chǎn)生不同的風(fēng)險(xiǎn)成本.同時(shí)，文中設(shè)置一定的時(shí)間窗，即完成運(yùn)輸服務(wù)要求的時(shí)間范圍，過早或過晚到達(dá)目的地，將產(chǎn)生一定的倉儲成本或懲罰成本，因此，在滿足時(shí)間和運(yùn)輸需求的條件下，實(shí)現(xiàn)物流總成本最低，包含運(yùn)輸成本、換裝成本、倉儲成本或懲罰成本、風(fēng)險(xiǎn)成本，尋找最優(yōu)的運(yùn)輸方案.

1.2 模型構(gòu)建

1.2.1模型假設(shè)

1) 考慮到城市規(guī)模對運(yùn)輸和換裝成本的影響，將各城市簡化為質(zhì)點(diǎn).

2) 每兩個(gè)相鄰節(jié)點(diǎn)間只采用一種運(yùn)輸方式，換裝必須在節(jié)點(diǎn)城市進(jìn)行.

3) 由于自然因素帶來的風(fēng)險(xiǎn)和損失難以計(jì)量，運(yùn)輸過程處于理想狀態(tài)，不考慮自然因素(如大風(fēng)大雨導(dǎo)致運(yùn)輸延遲等)的影響.

4) 文中不考慮空載返程，完成配送任務(wù)后，不必返回出發(fā)點(diǎn).

1.2.2模型建立

根據(jù)以上假設(shè)，建立整車物流多式聯(lián)運(yùn)模型，目標(biāo)函數(shù)為

(1)

簡化之后可表示為

約束條件為

(4)

(5)

(6)

(7)

(8)

(9)

(10)

式中：Z為物流總成本，萬元；Q(i)為總需求量，萬輛；q(i)為節(jié)點(diǎn)i需求量，萬輛；N為節(jié)點(diǎn)城市集合；M為運(yùn)輸方式集合，其中m∈M，m=1，2，3，(1-公路；2-鐵路；3-水路) ；vij為實(shí)際點(diǎn)到j(luò)點(diǎn)的運(yùn)輸量；Vij為i點(diǎn)到j(luò)點(diǎn)的路線最大運(yùn)輸量；ckij為在i點(diǎn)用k方式運(yùn)輸?shù)絡(luò)點(diǎn)的單位運(yùn)輸成本，萬元/(100 km·萬輛)；ekij為在i點(diǎn)用k方式運(yùn)輸?shù)絡(luò)點(diǎn)時(shí)的風(fēng)險(xiǎn)成本，萬元/(100 km·萬輛)；rkij為在i點(diǎn)用k方式運(yùn)輸?shù)絡(luò)點(diǎn)的運(yùn)輸距離，100 km；wkij為在i點(diǎn)用k方式運(yùn)輸?shù)絡(luò)點(diǎn)的運(yùn)輸時(shí)間，h；ukli為在i點(diǎn)將運(yùn)輸方式由k方式換至l方式的換裝時(shí)間，h/萬輛；pkli為在i點(diǎn)將運(yùn)輸方式由k方式換至l方式所產(chǎn)生的換裝成本，萬元/萬輛；okli為在i點(diǎn)將運(yùn)輸方式由k方式換至l方式所產(chǎn)生的風(fēng)險(xiǎn)成本，萬元/萬輛；F(t)為違反時(shí)間要求而產(chǎn)生的懲罰成本，萬元；t為將貨物從起點(diǎn)運(yùn)至目的地的總時(shí)間，h；[ai，bi]為到達(dá)i點(diǎn)的時(shí)間窗，h；S1為提前到達(dá)，倉儲成本；S2為推遲到達(dá)，懲罰成本,萬元.

式(1)為目標(biāo)函數(shù)，表示物流總成本最低，包括運(yùn)輸成本、換裝成本、風(fēng)險(xiǎn)成本、懲罰成本；式(3)為總時(shí)間t；式(4)為懲罰成本；式(5)、(6)為變量；式(7)為在i市到j(luò)市只能用一種方式運(yùn)輸；式(8)為在i市只能換裝一次；式(9)為滿足每個(gè)節(jié)點(diǎn)的運(yùn)輸需求；式(10)為兩相鄰節(jié)點(diǎn)間的運(yùn)量小于運(yùn)輸能力.

2 遺傳算法求解步驟

采用遺傳算法對模型進(jìn)行求解主要進(jìn)行六個(gè)步驟的操作.將節(jié)點(diǎn)、運(yùn)輸方式編碼，隨機(jī)選擇幾組運(yùn)輸方式作為初始種群，計(jì)算各運(yùn)輸方式的適應(yīng)度值，對運(yùn)輸方式進(jìn)行交叉和變異操作.具體步驟如下：

步驟1編碼設(shè)計(jì) 采用二進(jìn)制編碼，將節(jié)點(diǎn)和節(jié)點(diǎn)之間的是否采取何種運(yùn)輸方式，以及是否換裝編碼成染色體，均采用0-1整數(shù)規(guī)劃模型.模型涉及m種運(yùn)輸方式以及n個(gè)節(jié)點(diǎn)城市，隨機(jī)編成一條長度為[2(n-2)+1]維的自然數(shù)向量，前n-1維向量表示每個(gè)節(jié)點(diǎn)之間采用何種運(yùn)輸方式，后n-2維表示是否鏈接.

步驟2種群規(guī)模的確定 種群數(shù)量為A(偶數(shù))，每次迭代生成A條[2(n-2)+1]維的向量，并從這A條向量中尋找最優(yōu)解并記錄.通過多次的選擇、交叉、變異的迭代計(jì)算，直至全局最優(yōu)解產(chǎn)生，采取隨機(jī)法生成初始種群.

步驟3適應(yīng)度函數(shù)的設(shè)計(jì) 適應(yīng)度函數(shù)為各方案的總成本Z，適應(yīng)度較高表示其總成本較低，而適應(yīng)度較低其總成本較高.

步驟4選擇操作 采用輪盤賭選擇算子進(jìn)行選擇操作，見圖2，每個(gè)扇面所對應(yīng)的圓心角不同，角度越大，表示適應(yīng)度越高，遺傳到下代的可能性越大.模型中路線總成本低的反而適應(yīng)度大，因此,均將總成本Z取倒數(shù)得1/Z，每條路線的適應(yīng)度p1即為p1=(1/Z1)/sum(1/Z).

圖2 輪盤賭選擇示意圖

步驟5交叉操作 將種群A條向量平均分成上部和下部各A/2條，并將上部第x條向量與下部第x條向量對應(yīng)配對.交叉操作從第1條向量開始，直至A/2條向量結(jié)束.設(shè)置一個(gè)平均分布的偽隨機(jī)數(shù)rand(0—1)作為依據(jù)，若rand小于設(shè)置的交叉概率則進(jìn)入交叉操作.交叉操作分為兩部分，即每條向量前n-1維和后n-2維分別與對應(yīng)的向量交叉操作，交叉的位置在前n-1維和后n-2維中隨機(jī)選取.

步驟6變異操作 從第1條向量開始，直至A條向量結(jié)束.變異操作同樣分為兩部分，即每條向量前n-1維和后n-2維，變異的位置在前n-1維和后n-2維中隨機(jī)選取.對于前n-1維變異，變異的值在原值以外的在1～m中再次選??；對于后n-2維變異，由于是0-1規(guī)劃模型，因此將0變異成1，1變異成0.

最后判斷是否達(dá)到迭代終止條件，如否，進(jìn)行群體更新迭代，跳回至步驟3重復(fù)進(jìn)行操作，循環(huán)迭代直至輸出滿足條件的結(jié)果.

3 算例分析

M公司以整車物流為主要經(jīng)營業(yè)務(wù)之一，具備穩(wěn)定的水運(yùn)、鐵路、公路運(yùn)力條件，建立了自己的水路運(yùn)輸路線，自有滾裝船13艘和鐵路車皮348節(jié)，公路可用運(yùn)力有15 000輛，并積極開展整車物流多式聯(lián)運(yùn).目前在國內(nèi)共擁有9個(gè)VDC，15個(gè)較大的VSC.

以M公司長江業(yè)務(wù)為例，公司沿長江有三個(gè)VDC，分別為金橋VDC、安亭總庫和儀征VDC，地處儀征和上海，為便于計(jì)算，合稱上海VDC(a)，有四個(gè)VSC，分別處于南京(b)、武漢(c)、重慶(d)、德陽(e).對M公司整車多式聯(lián)運(yùn)研究主要是由上海VDC向南京VSC、武漢VSC、重慶VSC、德陽VSC節(jié)點(diǎn)配送的過程，各節(jié)點(diǎn)有內(nèi)河水運(yùn)、鐵路和公路三種方式可選.

查詢各節(jié)點(diǎn)各種方式運(yùn)輸距離，根據(jù)各運(yùn)輸方式平均速度計(jì)算運(yùn)輸時(shí)間(鐵路、汽車、內(nèi)河船舶的平均速度分別為80，100，20 km/h)，見表1.為了方便研究，假設(shè)各運(yùn)輸方式在不同城市單位成本、換裝成本無差異，根據(jù)各運(yùn)輸方式最優(yōu)路徑和距離，以及營運(yùn)成本、管理成本、燃料成本等，計(jì)算可得各方式運(yùn)輸成本，見表2.換裝成本主要來源于裝卸設(shè)備和人力，根據(jù)裝卸設(shè)備的維修費(fèi)、燃油費(fèi)、設(shè)備折舊成本等以及人工費(fèi)估算可得換裝成本，換裝時(shí)間由各方式裝卸效率測算可得，換裝成本和換裝時(shí)間只與節(jié)點(diǎn)前后兩種運(yùn)輸方式有關(guān)；根據(jù)丟失、損壞導(dǎo)致賠償產(chǎn)生成本估算可得風(fēng)險(xiǎn)成本，見表3.A汽車品牌各個(gè)VSC需求量如表4所示，所設(shè)的時(shí)間窗見表5，若提前到達(dá)，設(shè)置倉儲成本為5萬元/(萬輛·小時(shí))，若推遲到達(dá)，設(shè)置懲罰成本為50萬元/(萬輛·小時(shí)).

表1 各節(jié)點(diǎn)之間三種方式運(yùn)輸距離、運(yùn)輸時(shí)間

注：運(yùn)輸距離單位，100 km；運(yùn)輸時(shí)間單位，h.

表2 各種方式運(yùn)輸成本、風(fēng)險(xiǎn)成本 萬元·100 km·萬輛-1

表3 各種運(yùn)輸方式的換裝時(shí)間、換裝成本

注：換裝時(shí)間單位，h/萬輛；換裝成本單位，萬元/萬輛.

通過Matlab編寫程序進(jìn)行求解，其中遺傳算法相關(guān)參數(shù)設(shè)置為：種群規(guī)模為30，變異概率為0.04，交叉概率為0.5，最大迭代次數(shù)為100，迭代過程見圖4，算法在28次循環(huán)已收斂，即該問題的最優(yōu)組合為2，2，3，1，即上?！暇⒛暇錆h、武漢—重慶、重慶—德陽各階段分別采用鐵路、鐵路、水路、公路運(yùn)輸方式，此時(shí)物流總成本最低Z=1 328.727萬元，這比純公路方式物流總成本節(jié)約了122.694萬元，充分體現(xiàn)三種運(yùn)輸方式的優(yōu)勢，可見該模型和算法優(yōu)化效果顯著.

表4 2015年A汽車品牌VSC所在城市需求量

表5 各節(jié)點(diǎn)城市之間的時(shí)間窗

圖4 迭代過程

4 結(jié) 束 語

文中綜合考慮物流成本和時(shí)效性的要求，將帶時(shí)間窗的車輛路徑和多式聯(lián)運(yùn)問題相結(jié)合，并運(yùn)用于整車物流，充分體現(xiàn)各運(yùn)輸方式優(yōu)勢，降低物流總成本.建立物流總成本最低為目標(biāo)的帶時(shí)間窗多式聯(lián)運(yùn)0-1整數(shù)規(guī)劃模型，包括不同運(yùn)輸方式產(chǎn)生的運(yùn)輸成本、換裝成本、運(yùn)輸和換裝過程中產(chǎn)生的風(fēng)險(xiǎn)成本，以及提早到達(dá)或延遲到達(dá)產(chǎn)生的倉儲成本或懲罰成本，采用遺傳算法進(jìn)行求解，解決整車物流配送中路徑優(yōu)化問題，并進(jìn)行實(shí)例驗(yàn)證，結(jié)果說明此模型和算法在整車物流多式聯(lián)運(yùn)中具有可行性和實(shí)用性.

[1] 黑秀玲.汽車整車多式聯(lián)運(yùn)優(yōu)化研究[D].南京：東南大學(xué),2015.

[2] 易云飛,董文永,林曉東,等.求解帶軟時(shí)間窗車輛路徑問題的改進(jìn)伊藤算法及其收斂性分析[J].電子學(xué)報(bào),2015(4):658-664.

[3] 汪秋云,蔣文保.帶軟時(shí)間窗車輛路徑問題的求解算法研究[J].北京信息科技大學(xué)學(xué)報(bào)(自然科學(xué)版),2013(4):57-59.

[4] Ekki D K. Distance and time in intermodal goods transport networks in Europe: a generic approach[J]. Transportation Research Part A: Policy and Practice, 2008,42(7):973-993.

[5] CHANG T. Best routes selection in international intermodal networks[J]. Computers & Operations Research, 2008,35(9):2877-2891.

[6] GROMICHO J A S, OUDSHOORN E, POST G. Generating price-effective intermodal routes[J]. Statistica Neerlandica, 2011,65(4):432-445.

[7] 竇莉薇.基于改進(jìn)蟻群算法的A公司整車物流多式聯(lián)運(yùn)路徑問題研究[D]. 天津：天津師范大學(xué), 2016.

[8] CHEN P, HUANG H, DONG X. Iterated variable neighborhood descent algorithm for the capacitated vehicle routing problem[J]. Expert Systems with Applications, 2010,37(2):1620-1627.

[9] 儲慶中,劉玉兵,吳國君.基于遺傳算法求解的危險(xiǎn)品道路運(yùn)輸線路優(yōu)化雙層規(guī)劃模型[J].交通信息與安全,2011(2):95-99.

[10] 王旭,遲增彬,葛顯龍.帶時(shí)間窗的整車多式聯(lián)運(yùn)模型研究與解析[J].計(jì)算機(jī)應(yīng)用研究,2011(2):563-565.

[11] 徐玨,何利力.基于雙層遺傳算法的煙草配送路徑優(yōu)化問題研究[J].工業(yè)控制計(jì)算機(jī),2015(12):33-34.

[12] 吳小珍,李表奎,董紫嫣,等.基于SPFA的整車物流運(yùn)輸線路及運(yùn)輸方式的優(yōu)化及求解[J].物流工程與管理,2014(5):176-178.

[13] 陳然.上海安吉與同方環(huán)球的整車聯(lián)合運(yùn)輸研究[D].北京：北京交通大學(xué),2012.

Research on Route Optimization Model for Vehicle Multimodal Transport with Time Window

XIEXuemeiYANGJiaqi

(SchoolofTransportation,WuhanUniversityofTechnology,Wuhan430063,China)

Vehicle logistics is a core part of automobile logistics, and how to optimize the costs becomes the focus in logistics and automotive industry. According to the route optimization of vehicle logistics, the 0-1 integer programming model of route optimization of vehicle multimodal transport with the time window was established based on the minimum logistics cost and proper time constraints. Considering transportation cost, transit cost, risk cost, and storage cost or penalty cost without arriving on time, the genetic algorithm was designed to solve this problem based on Matlab. Meanwhile, the model was verified and analyzed by some examples. The results show that the proposed model and algorithm are reasonable and practical for the route optimization of vehicle logistics multimodal transport.

vehicle logistics; multimodal transport; time window; route optimization; genetic algorithm

U116.2

10.3963/j.issn.2095-3844.2017.06.035

2017-09-25

謝雪梅(1991—)：女，碩士生，主要研究領(lǐng)域?yàn)槲锪鞴芾?/p>