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

謝雪梅 楊家其

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

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

謝雪梅 楊家其

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

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

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

0 引 言

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

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

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

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

1.1 問題描述

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

圖1 整車物流運作模式

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

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

1.2 模型構(gòu)建

1.2.1模型假設(shè)

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

2) 每兩個相鄰節(jié)點間只采用一種運輸方式，換裝必須在節(jié)點城市進行.

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

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

1.2.2模型建立

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

(1)

簡化之后可表示為

約束條件為

(4)

(5)

(6)

(7)

(8)

(9)

(10)

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

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

2 遺傳算法求解步驟

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

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

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

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

步驟4選擇操作 采用輪盤賭選擇算子進行選擇操作，見圖2，每個扇面所對應(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è)置一個平均分布的偽隨機數(shù)rand(0—1)作為依據(jù)，若rand小于設(shè)置的交叉概率則進入交叉操作.交叉操作分為兩部分，即每條向量前n-1維和后n-2維分別與對應(yīng)的向量交叉操作，交叉的位置在前n-1維和后n-2維中隨機選取.

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

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

3 算例分析

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

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

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

表1 各節(jié)點之間三種方式運輸距離、運輸時間

注：運輸距離單位，100 km；運輸時間單位，h.

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

表3 各種運輸方式的換裝時間、換裝成本

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

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

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

表5 各節(jié)點城市之間的時間窗

圖4 迭代過程

4 結(jié) 束 語

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

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

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

[3] 汪秋云,蔣文保.帶軟時間窗車輛路徑問題的求解算法研究[J].北京信息科技大學(xué)學(xué)報(自然科學(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] 竇莉薇.基于改進蟻群算法的A公司整車物流多式聯(liá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] 儲慶中,劉玉兵,吳國君.基于遺傳算法求解的危險品道路運輸線路優(yōu)化雙層規(guī)劃模型[J].交通信息與安全,2011(2):95-99.

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

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

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

[13] 陳然.上海安吉與同方環(huán)球的整車聯(liá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)域為物流管理