葛顯龍，徐玖平，王偉鑫

(1.重慶交通大學(xué)管理學(xué)院，重慶 400074; 2.四川大學(xué)商學(xué)院，四川 成都 610065;3.四川外國(guó)語(yǔ)大學(xué)國(guó)際商學(xué)院，重慶 400051)

交通限行條件下基于車輛協(xié)作的城市物流換乘聯(lián)運(yùn)問(wèn)題研究

葛顯龍1,2，徐玖平2，王偉鑫3

(1.重慶交通大學(xué)管理學(xué)院，重慶 400074; 2.四川大學(xué)商學(xué)院，四川 成都 610065;3.四川外國(guó)語(yǔ)大學(xué)國(guó)際商學(xué)院，重慶 400051)

針對(duì)交通限行條件下城市配送的現(xiàn)實(shí)問(wèn)題，提出基于車輛協(xié)作的“多對(duì)多”網(wǎng)絡(luò)化換乘聯(lián)運(yùn)策略。設(shè)計(jì)協(xié)作點(diǎn)的選擇準(zhǔn)則與序貫式聯(lián)運(yùn)規(guī)則，以協(xié)作點(diǎn)銜接城市通行區(qū)域與限行區(qū)域，建立基于車輛協(xié)作的城市配送換乘聯(lián)運(yùn)模型。同時(shí)，考慮到模型的復(fù)雜性，利用云模型云滴的隨機(jī)性與傾向性，改進(jìn)遺傳算法中變異與交叉概率的設(shè)置方式，設(shè)計(jì)云遺傳算法優(yōu)先求解第二級(jí)配送問(wèn)題，再利用C-W算法求解第一級(jí)配送問(wèn)題，為了增強(qiáng)算法的求解質(zhì)量與效率，設(shè)計(jì)了擾動(dòng)算子與種群擴(kuò)張算子。最后，結(jié)合不同算例驗(yàn)證了模型與算法的有效性。

交通限行，車輛協(xié)作，換乘聯(lián)運(yùn)，城市配送

1 引言

近年來(lái)隨著汽車保有量急速增加，由交通需求增長(zhǎng)與道路資源緊張?jiān)斐傻慕煌〒矶聠?wèn)題已經(jīng)成為各大城市普遍面臨的難題。為緩解交通擁堵，對(duì)貨車分時(shí)段、分路段、分車型的交通限行政策已經(jīng)由北上廣等一線城市開始施行并向其他城市推廣開來(lái)，給城市物流配送帶來(lái)新的挑戰(zhàn)。

城市配送與交通網(wǎng)絡(luò)的狀況密切相關(guān)，時(shí)變網(wǎng)絡(luò)的車輛路徑問(wèn)題(Time Depend Vehicle Routing Problem，TDVRP)考慮了交通擁堵環(huán)境下的城市配送問(wèn)題。如，李妍峰等[1]對(duì)時(shí)變網(wǎng)絡(luò)車輛調(diào)度問(wèn)題提出一種滿足先入先出準(zhǔn)則的時(shí)變處理方法；馬華偉等[2]對(duì)時(shí)變車輛路徑問(wèn)題的求解策略進(jìn)行了研究；李妍峰與高自友[3]將車輛路徑問(wèn)題的研究與動(dòng)態(tài)城市交通路網(wǎng)相結(jié)合；Franceschetti 等[4]考慮了交通擁堵對(duì)車速和碳排放的影響；馬祖軍與胡萍[5]設(shè)計(jì)了實(shí)時(shí)/時(shí)變交通信息的結(jié)合策略，并提出了滿足先進(jìn)先出原則的路段行駛時(shí)間計(jì)算方法；Bhusiri等[6]研究了帶軟時(shí)間窗的時(shí)變車輛路徑問(wèn)題；Verbeeck等[7]設(shè)計(jì)了快速求解的啟發(fā)式算法研究事變網(wǎng)絡(luò)的車輛路徑問(wèn)題；Tas等[8]研究了事變網(wǎng)絡(luò)與隨機(jī)行駛時(shí)間的車輛路徑問(wèn)題；陳玉光與陳志祥[9]設(shè)計(jì)考慮時(shí)間的競(jìng)爭(zhēng)戰(zhàn)略與可持續(xù)發(fā)展戰(zhàn)略的快速響應(yīng)策略；唐金環(huán)等[10]以時(shí)變網(wǎng)絡(luò)下旅行速度的變化為關(guān)鍵變量，建立實(shí)時(shí)動(dòng)態(tài)配送模型；Gendreau等[11]從建模方法與求解算法兩個(gè)方面對(duì)時(shí)變車輛路徑問(wèn)題的研究現(xiàn)狀進(jìn)行了綜述分析；Soysal等[12]以行駛速度為變量建立碳排放的車輛路徑模型；Sun等[13]研究了車輛路徑問(wèn)題在大規(guī)模的城市交通網(wǎng)絡(luò)與隨機(jī)旅行時(shí)間中的應(yīng)用；王旭平等[14]以最小化訂單履行時(shí)間為目標(biāo)，構(gòu)建非線性動(dòng)態(tài)配送聯(lián)合調(diào)度模型；四兵鋒等[15]基于系統(tǒng)最優(yōu)思想的公交專用道網(wǎng)絡(luò)設(shè)計(jì)方法；Cao等[16]利用分枝定界算法研究了時(shí)變網(wǎng)絡(luò)環(huán)境下路徑優(yōu)化問(wèn)題；Ehmke等[17]以車輛速度為變量建立時(shí)變網(wǎng)絡(luò)的車輛路徑優(yōu)化模型；Qian Jiani與Eglese[18]研究了在時(shí)變網(wǎng)絡(luò)中不同速度對(duì)配送車輛碳排放的影響。交通擁堵對(duì)物流配送是軟約束，配送車輛可以通行，只是速度降低，而交通限行是硬約束，配送車輛只能在規(guī)定的時(shí)段、路段通行，否則是違法的，二者有本質(zhì)的差別。簡(jiǎn)單地以交通擁堵的方法研究交通限行條件下城市配送問(wèn)題，顯然不符合實(shí)際需求，也難以對(duì)城市配送進(jìn)行有效指導(dǎo)。

為此，針對(duì)分時(shí)段、分路段、分車型的交通限行政策，從車型與道路匹配算法及換乘聯(lián)運(yùn)規(guī)則研究入手，提出面向交通限行的車輛協(xié)作與序貫式換乘聯(lián)運(yùn)策略，通過(guò)貨物路徑的拆分與組合、換乘點(diǎn)設(shè)置及車輛協(xié)作建立城市交通限行區(qū)域與通行區(qū)域的聯(lián)系，構(gòu)建基于車輛協(xié)作的換乘聯(lián)運(yùn)模型并設(shè)計(jì)云遺傳算法進(jìn)行求解。最后，結(jié)合修正后的兩級(jí)配送標(biāo)準(zhǔn)算例對(duì)本文模型及算法。

2 問(wèn)題分析

針對(duì)分時(shí)段、分路段、分車型的交通限行政策，在此提出基于車輛協(xié)作與換乘聯(lián)運(yùn)的城市配送策略，通過(guò)受限車輛與不受限車輛的協(xié)作及貨物的換乘聯(lián)運(yùn)策略完成城市配送。如圖1所示。

圖1 城市路網(wǎng)簡(jiǎn)單結(jié)構(gòu)示意圖

圖1中線條表示城市道路，圓邊表示繞城高速道路，五角星表示換乘協(xié)作點(diǎn)。黃色區(qū)域?yàn)橹鞒菂^(qū)域，由于城市交通限行政策規(guī)定只有符合規(guī)定的車型才可以行駛(如，核載質(zhì)量2噸及以下的廂式貨車)，綠色區(qū)域?yàn)榻煌ú幌扌械耐猸h(huán)區(qū)域，所有貨車均可以通行，黑線條為城市主干道。

如圖1所示城市配送網(wǎng)絡(luò)被限行政策分割成不同條塊，給城市配送帶來(lái)了嚴(yán)重困擾，配送過(guò)程不再具有連貫性。為此，針對(duì)城市配送的實(shí)際情況提出基于車輛協(xié)作與貨物換乘聯(lián)運(yùn)的城市配送機(jī)制。首先，在綜合考慮配送需求類別、服務(wù)范圍、服務(wù)便利性、地理結(jié)構(gòu)、行政區(qū)界、交通網(wǎng)絡(luò)狀況、城市布局等因素的基礎(chǔ)上，設(shè)計(jì)以城市主干道為界限的固定分區(qū)策略。同時(shí)，充分考慮城市配送需求的動(dòng)態(tài)性與分散性，從跨區(qū)域資源協(xié)作的視角，設(shè)計(jì)零散需求的動(dòng)態(tài)分區(qū)策略。由于交通限行對(duì)車型的約束及不同車型的規(guī)模效應(yīng)，綜合考慮交通限行狀況、配送成本、換乘成本、服務(wù)質(zhì)量等影響因素，設(shè)計(jì)城市限行區(qū)域與通行區(qū)域的協(xié)作點(diǎn)選擇規(guī)則，不同類型車輛通過(guò)協(xié)作點(diǎn)實(shí)現(xiàn)配送任務(wù)的序貫式換乘聯(lián)運(yùn)。具體如圖2所示。

圖2 車輛協(xié)作與換乘聯(lián)運(yùn)機(jī)制

如圖2所示，由于交通限行造成的客戶需求不能由大型車從倉(cāng)庫(kù)直接配送，只能通過(guò)協(xié)作點(diǎn)換乘規(guī)定的小型車完成配送。為了便于表述，在此對(duì)配送網(wǎng)絡(luò)進(jìn)行分級(jí)，由協(xié)作點(diǎn)及協(xié)作點(diǎn)與倉(cāng)庫(kù)間路徑構(gòu)成的網(wǎng)絡(luò)稱為第一級(jí)配送網(wǎng)絡(luò)，該網(wǎng)絡(luò)沒(méi)有交通限行，所有車輛均可以通行，服務(wù)于該網(wǎng)絡(luò)的車輛稱為第一級(jí)車輛。由客戶及客戶與協(xié)作點(diǎn)間路徑構(gòu)成的網(wǎng)絡(luò)稱為第二級(jí)網(wǎng)絡(luò)，該網(wǎng)絡(luò)受到交通限行政策的影響，只能由規(guī)定的車輛才能通行，服務(wù)于該網(wǎng)絡(luò)的車輛稱為第二級(jí)車輛。

考慮到城市配送的多樣性與復(fù)雜性，根據(jù)客戶靈活分區(qū)策略，在此對(duì)第二級(jí)網(wǎng)絡(luò)的配送提出網(wǎng)絡(luò)化配送機(jī)制，具體如圖3所示。

圖3 網(wǎng)絡(luò)化配送機(jī)制

如圖3所示，在網(wǎng)絡(luò)化配送機(jī)制下客戶不再隸屬某個(gè)協(xié)作點(diǎn)負(fù)責(zé)配送，而是根據(jù)每次具體配送任務(wù)靈活分配?？康膮f(xié)作點(diǎn)，讓隸屬不同協(xié)作點(diǎn)的車輛可以根據(jù)配送任務(wù)、成本等因素在任意協(xié)作點(diǎn)?？颗c補(bǔ)貨作業(yè)，并且不同協(xié)作點(diǎn)的車輛可以依據(jù)當(dāng)前任務(wù)的完成情況及配送成本對(duì)配送區(qū)域內(nèi)的任何客戶進(jìn)行靈活響應(yīng)，最大限度的提高物流響應(yīng)能力。

3 協(xié)作點(diǎn)選擇規(guī)則

在傳統(tǒng)多配送中心車輛路徑問(wèn)題中，客戶固定隸屬不同配送中心負(fù)責(zé)，不存在車輛與配送中心匹配選擇問(wèn)題。然而，在網(wǎng)絡(luò)化城市配送機(jī)制下車輛可以在不同的協(xié)作點(diǎn)任意?？?。因此，車輛如何選擇最優(yōu)的停靠協(xié)作點(diǎn)是資源共享與全局優(yōu)化的關(guān)鍵。

在網(wǎng)絡(luò)化城市配送機(jī)制下，配送任務(wù)完成后車輛在選擇?？繀f(xié)作點(diǎn)時(shí)，將受到多種因素的限制，如，協(xié)作點(diǎn)的繁忙程度、車輛距協(xié)作點(diǎn)的距離、協(xié)作點(diǎn)作業(yè)容量等。本文在綜合考慮這些因素的基礎(chǔ)上，設(shè)計(jì)車輛與協(xié)作點(diǎn)的匹配矩陣。如表1。

表1 車輛與協(xié)作點(diǎn)的匹配矩陣

在表1中A、B、C表示不同協(xié)作點(diǎn)，?表示影響因素的權(quán)重，Δij表示第j個(gè)協(xié)作點(diǎn)在第i個(gè)影響因素下的評(píng)價(jià)情況。協(xié)作點(diǎn)繁忙程度表示協(xié)作點(diǎn)已有作業(yè)任務(wù)規(guī)模及是否有空閑車輛的為其他客戶提供服務(wù)有關(guān)；協(xié)作點(diǎn)作業(yè)容量表示協(xié)作點(diǎn)在保證已有作業(yè)任務(wù)的前提下是否能擁有足夠的容量為停靠車輛補(bǔ)貨作業(yè)量；車輛距協(xié)作點(diǎn)距離表示車輛需要?？繒r(shí)可供選擇協(xié)作點(diǎn)的距離；車輛實(shí)載率表示車輛的實(shí)際裝載量與最大裝載量的比率，是衡量車輛使用效率的重要指標(biāo)；因素權(quán)重表示某個(gè)影響因素根據(jù)其重要程度賦予的數(shù)值。

車輛與協(xié)作點(diǎn)最佳匹配算法：

步驟1：對(duì)匹配矩陣中不同指標(biāo)進(jìn)行標(biāo)準(zhǔn)化處理：

對(duì)于收益性指標(biāo)：

對(duì)于成本型指標(biāo)：

步驟2：采取統(tǒng)計(jì)比較打分方式確定各影響因素的權(quán)重，并進(jìn)行歸一化處理。

步驟3：計(jì)算每個(gè)協(xié)作點(diǎn)?？康木C合評(píng)價(jià)值：

最后，依據(jù)綜合評(píng)價(jià)值的大小，選擇綜合評(píng)價(jià)值最大的協(xié)作點(diǎn)作為車輛最佳?？康膮f(xié)作點(diǎn)。

4 數(shù)學(xué)模型

4.1假設(shè)說(shuō)明

為了簡(jiǎn)化問(wèn)題以便于建立模型，作以下假設(shè)說(shuō)明。

(1)客戶需求不允許由倉(cāng)庫(kù)直接配送；

(2)客戶需求不能超過(guò)第二級(jí)車輛的最大容量，每個(gè)客戶只能由一輛車服務(wù)；

(3)協(xié)作點(diǎn)沒(méi)有存儲(chǔ)功能，只負(fù)責(zé)貨物的換乘作業(yè)，其中作業(yè)量允許超過(guò)第一級(jí)車輛的最大容量；

(4)兩級(jí)網(wǎng)絡(luò)的服務(wù)車型不一樣，同一級(jí)的服務(wù)車型是一樣的；

(5)第一級(jí)車輛的起訖點(diǎn)均為倉(cāng)庫(kù)，第二級(jí)車輛的起訖點(diǎn)可以是不同的協(xié)作點(diǎn)；

(6)各協(xié)作點(diǎn)沒(méi)有作業(yè)量的限制，所有車輛均不允許超載。

4.2符號(hào)說(shuō)明

為了便于理解，給出了變量和常量的定義。

4.3建立數(shù)學(xué)模型

按照前文分析可知，解決該問(wèn)題的關(guān)鍵是如何選擇協(xié)作點(diǎn)，厘清兩級(jí)網(wǎng)絡(luò)的依存關(guān)系。在此，從兩級(jí)配送網(wǎng)絡(luò)框架結(jié)構(gòu)上設(shè)計(jì)本文的模型，使用弧上的貨物流作為主要決策變量。下面定義了5類變量集合，將其分成3組。

(2)第二組變量表示客戶劃分的變量，用于連接兩級(jí)配送網(wǎng)絡(luò)。定義zkj為二進(jìn)制變量，如果運(yùn)往客戶j的貨物經(jīng)由協(xié)作點(diǎn)k協(xié)作時(shí)，其值為1，否則為0。

為了簡(jiǎn)化模型，在此定義輔助變量：

(1)

Dk表示經(jīng)過(guò)協(xié)作點(diǎn)k的貨物流量，其值是非負(fù)的。

下面以兩級(jí)網(wǎng)絡(luò)的總配送成本最小為優(yōu)化目標(biāo)，建立交通限行環(huán)境下基于車輛協(xié)作與貨物換乘聯(lián)運(yùn)的數(shù)學(xué)模型，具體如下：

(2)

(3)

(4)

(5)

(6)

(7)

(8)

(9)

(10)

(11)

(12)

(13)

(14)

(15)

(16)

(17)

(18)

(19)

(20)

zkj∈{0,1},?k∈Vs∪V0,?j∈Vc

(21)

xkj∈Z+,?k,j∈Vs∪V0

(22)

(23)

(24)

5 算法設(shè)計(jì)

5.1求解思路

本文建立的兩級(jí)換乘聯(lián)運(yùn)模型中第二級(jí)配送網(wǎng)絡(luò)是多車場(chǎng)開閉混合車輛路徑問(wèn)題，車輛在完成配送任務(wù)后返回協(xié)作點(diǎn)，但不必是出發(fā)的協(xié)作點(diǎn)。第一級(jí)配送網(wǎng)絡(luò)是需求可分割的車輛路徑問(wèn)題。顯然，兩級(jí)配送模型的求解復(fù)雜度遠(yuǎn)超經(jīng)典VRP，同時(shí)，由于兩級(jí)配送問(wèn)題中第一級(jí)網(wǎng)絡(luò)與第二級(jí)網(wǎng)絡(luò)的關(guān)聯(lián)性，需要首先厘清兩級(jí)間的隸屬關(guān)系。

由于協(xié)作點(diǎn)沒(méi)有作業(yè)量的約束，第二級(jí)配送方案決定第一級(jí)配送任務(wù)的分配。在此，提出自下向上的求解思路，首先求解第二級(jí)網(wǎng)絡(luò)的配送問(wèn)題，然后根據(jù)第二級(jí)配送方案確定各協(xié)作點(diǎn)的作業(yè)量，最后再求解第一級(jí)網(wǎng)絡(luò)的配送問(wèn)題。

5.2第二級(jí)網(wǎng)絡(luò)求解算法設(shè)計(jì)

由于第二級(jí)配送問(wèn)題屬于多車場(chǎng)開閉混合路徑優(yōu)化問(wèn)題，在此設(shè)計(jì)云遺傳算法求解第二級(jí)配送問(wèn)題，具體算法操作如下。

(1)初始可行解的構(gòu)造

采取自然數(shù)編碼結(jié)構(gòu)表示第二級(jí)配送路徑方案。首先根據(jù)所有協(xié)作點(diǎn)的坐標(biāo)產(chǎn)生客戶分布區(qū)域的幾何重心，然后以其與客戶構(gòu)成矢量進(jìn)行掃描，產(chǎn)生滿足容量約束的路徑子段，并由0串連所有路徑子段。其中0表示協(xié)作點(diǎn)，如圖4所示。

圖4 初始解的結(jié)構(gòu)

由于第二級(jí)網(wǎng)絡(luò)是開閉混合路徑的特征，為此設(shè)計(jì)0表示多個(gè)協(xié)作點(diǎn)，但在解碼之前不具體指定。如，第一個(gè)0表示由協(xié)作點(diǎn)選擇規(guī)則確定的協(xié)作點(diǎn)vsi1,第二個(gè)0分別表示第一路徑子段任務(wù)完成后車輛停靠的協(xié)作點(diǎn)vsi2與第二路徑子段任務(wù)開始的協(xié)作點(diǎn)vsi3,其他以此類同。

(2)適應(yīng)度計(jì)算

本文染色體的適應(yīng)度函數(shù)取與目標(biāo)函數(shù)一致，函數(shù)值越小的個(gè)體越優(yōu)良。

(3)選擇算子

(4)云交叉與變異概率生成算子

首先，利用云模型發(fā)生器生成交叉概率[19]，具體如下：

He←En/C2,其中C2為控制系數(shù)；

En′=Norm(En,He),其中Norm為云模型發(fā)生器，具體見文獻(xiàn)[17]；

然后，利用云模型發(fā)生器生成交叉概率，具體如下：

Ex←f,其中f為參與變異的個(gè)體；

En←(f-fmax)/C3,其中fmax為種群中最優(yōu)秀個(gè)體，C3為控制系數(shù)；

He←En/C4,其中C4為控制系數(shù)；

En′=Norm(En,He),其中Norm為云模型發(fā)生器；

其中，k1～k4為[0,1]范圍內(nèi)的常數(shù), 本文取k1=k3=1；k2=k4=0.5。C1=C3=6P(T+1),C2=C4=15-(T-P/2)2,P為種群規(guī)模，T為迭代次數(shù)，Pc 和Pm 初值比較大，但隨著種群的進(jìn)化逐漸減小。

(5)交叉算子

由于路徑的編碼具有組間無(wú)序，組內(nèi)有序的特點(diǎn)，在此設(shè)計(jì)保護(hù)優(yōu)秀子段的交叉算子。在染色體編碼串中選擇交叉點(diǎn)時(shí)選擇0的位置，避免破壞優(yōu)秀子串，讓后將其移到首位，如此即可以最大限度保護(hù)已生成的優(yōu)秀子段，同時(shí)可以避免在雙親相同時(shí)不產(chǎn)生新個(gè)體的缺陷。

(6)變異算子

隨機(jī)產(chǎn)生兩個(gè)自然數(shù)，若其對(duì)應(yīng)非零基因，交叉這兩個(gè)基因碼，產(chǎn)生新個(gè)體，否則重新產(chǎn)生。

(7)擾動(dòng)算子

為了增加算法的搜索能力，在此設(shè)計(jì)破壞擾動(dòng)與修復(fù)擾動(dòng)兩類算子。其中，破壞擾動(dòng)算子主要針對(duì)協(xié)作點(diǎn)關(guān)閉、啟用與交換操作，當(dāng)關(guān)閉某協(xié)作點(diǎn)時(shí)，與其相連的客戶也將釋放，啟用某協(xié)作點(diǎn)時(shí)，與其最近的客戶也被釋放。修復(fù)擾動(dòng)算子是針對(duì)因協(xié)作點(diǎn)操作釋放的客戶重新編入路徑段的操作，在此設(shè)計(jì)貪婪插入修復(fù)與后悔插入修復(fù)兩類修復(fù)擾動(dòng)操作。貪婪插入操作是按最小插入成本將客戶插入所有啟用協(xié)作點(diǎn)和路徑中的位置。后悔插入操作是客戶按照后悔值的序列進(jìn)行操作，后悔值是最優(yōu)插入位置與次優(yōu)插入位置的插入成本差，最大后悔值的客戶優(yōu)先插入。

(8)種群擴(kuò)張算子

改進(jìn)傳統(tǒng)遺傳算法中只對(duì)當(dāng)前種群中個(gè)體信息的利用，根據(jù)個(gè)體適應(yīng)度的大小，將上代種群中前 p個(gè)最優(yōu)個(gè)體和當(dāng)代種群中P個(gè)個(gè)體共同構(gòu)成一個(gè)新的種群(P+p個(gè)個(gè)體)，實(shí)現(xiàn)對(duì)最優(yōu)種群的擴(kuò)張，擴(kuò)大種群空間的搜索范圍。

(9)終止條件

設(shè)置重復(fù)迭代20次種群沒(méi)有變化或迭代1000次，終止算法迭代。

5.3第一級(jí)網(wǎng)絡(luò)求解算法設(shè)計(jì)

由于第一級(jí)網(wǎng)絡(luò)的復(fù)雜度和規(guī)模都遠(yuǎn)小于第二級(jí)，在此采取節(jié)約算法(C-W法)進(jìn)行求解。同時(shí)，由于第一級(jí)網(wǎng)絡(luò)中協(xié)作點(diǎn)的作業(yè)量可能會(huì)超過(guò)第一級(jí)車輛的服務(wù)能力，在此，首先采取優(yōu)先滿載策略，也即當(dāng)協(xié)作點(diǎn)作業(yè)量大于車輛的容量約束時(shí)，讓該協(xié)作點(diǎn)的作業(yè)量減去第一服務(wù)車輛最大容量的整數(shù)倍，直至小于車輛載重量，然后利用C-W算法進(jìn)行求解第一級(jí)網(wǎng)絡(luò)的配送路徑。

6 算例實(shí)驗(yàn)

6.1算例描述與實(shí)驗(yàn)設(shè)置

本文實(shí)驗(yàn)一的算例采取Hemmelmayr等[22]中E-n33-k4客戶的位置與倉(cāng)庫(kù)位置，但協(xié)作點(diǎn)在客戶的周圍隨機(jī)選擇，實(shí)驗(yàn)二的算例與許維勝等[21]中算例進(jìn)行對(duì)比分析。

算法實(shí)現(xiàn)環(huán)境設(shè)置為：主頻1.8GHz、內(nèi)存為1GB的硬件平臺(tái)上通過(guò)Matlab+cplex12.5實(shí)現(xiàn)本文算法。算法參數(shù)設(shè)置如下，種群規(guī)模為80，上代保留10，最大迭代次數(shù)為1000，最長(zhǎng)計(jì)算時(shí)間為100s。

6.2實(shí)驗(yàn)一

E-n33-k4算例有32個(gè)客戶，1個(gè)倉(cāng)庫(kù)，2個(gè)協(xié)作點(diǎn)，其坐標(biāo)位置分別為[292,495]、[265,392]與[336,452]，第一級(jí)車輛裝載容量為20000，第二級(jí)車輛裝在容量8000，第一級(jí)網(wǎng)絡(luò)最大服務(wù)車輛數(shù)為3，第二級(jí)網(wǎng)絡(luò)最大服務(wù)車輛數(shù)為4，具體客戶坐標(biāo)及需求量見表2。

由算法5.2首先對(duì)第二級(jí)配送問(wèn)題進(jìn)行求解，結(jié)果的見表3。

表2 客戶信息

由表3可見，第二級(jí)網(wǎng)絡(luò)需要4輛車完成配送，每輛車的實(shí)際裝載容量分別為8000、7250、6830與7290，而車輛的最大容量為8000，可見車輛的使用效率比較高。每輛車的出發(fā)協(xié)作點(diǎn)均為S2，目的協(xié)作點(diǎn)卻不一樣，但該現(xiàn)象并不影響車輛在各協(xié)作點(diǎn)數(shù)量的均衡性，這是因?yàn)楸疚臎](méi)有考慮碳排放、油耗等與配送噸公里相關(guān)的優(yōu)化目標(biāo)，在下一配送周期中逆向配送即可恢復(fù)原來(lái)各個(gè)協(xié)作點(diǎn)的車輛數(shù)。

表3 第二級(jí)網(wǎng)絡(luò)的配送路徑

由表3可見，第二級(jí)網(wǎng)絡(luò)需要4輛車完成配送，每輛車的實(shí)際裝載容量分別為8000、7250、6830與7290，而車輛的最大容量為8000，可見車輛的使用效率比較高。每輛車的出發(fā)協(xié)作點(diǎn)均為S2，目的協(xié)作點(diǎn)卻不一樣，但該現(xiàn)象并不影響車輛在各協(xié)作點(diǎn)數(shù)量的均衡性，這是因?yàn)楸疚臎](méi)有考慮碳排放、油耗等與配送噸公里相關(guān)的優(yōu)化目標(biāo)，在下一配送周期中逆向配送即可恢復(fù)原來(lái)各個(gè)協(xié)作點(diǎn)的車輛數(shù)。

根據(jù)第二級(jí)網(wǎng)絡(luò)的配送方案可知，協(xié)作點(diǎn)S1只?？寇囕v并沒(méi)有發(fā)出車輛，其作業(yè)量為0，所有客戶的需求量由協(xié)作點(diǎn)S2完成。協(xié)作點(diǎn)S2的作業(yè)量為29370，顯然超過(guò)第一級(jí)車輛的最大載重，由算法5.3中優(yōu)先滿載策略進(jìn)行配送，然后由C-W算法生成第一級(jí)網(wǎng)絡(luò)的配送方案。由于在本算例中只啟用兩個(gè)協(xié)作點(diǎn)，配送方案比較簡(jiǎn)單，也即第一級(jí)車輛對(duì)協(xié)作點(diǎn)S2連續(xù)配送兩次，路徑長(zhǎng)度為246.09km。

圖5 2E-VRP的完整配送方案

6.3實(shí)驗(yàn)二

為了更進(jìn)一步對(duì)本文的模型與算法進(jìn)行測(cè)試，下面結(jié)合王旭坪等[14]的算例進(jìn)行測(cè)試與對(duì)比分析。這些算例均來(lái)源于Perboli etc(2011)，由Christofides 與Eilon對(duì)E-n22-k4, E-n33-k4 與 E-n51-k5算例經(jīng)過(guò)處理而生成，其基本特征見表4。

表4 2E-VRP算例特征

本部分算例共有4類21個(gè)，每類客戶與協(xié)作點(diǎn)個(gè)數(shù)各不同，規(guī)模與復(fù)雜度也各異。為了凸顯本文模型中網(wǎng)絡(luò)化配送策略的優(yōu)越性，與已有固定分區(qū)的文獻(xiàn)進(jìn)行對(duì)比分析。在固定分區(qū)配送中車輛的路線是封閉的，而網(wǎng)絡(luò)化配送的車輛路線不封閉，車輛可以?？坎煌瑓f(xié)作點(diǎn)，特殊情況除外，如，只有一個(gè)協(xié)作點(diǎn)的配送網(wǎng)絡(luò)中，顯然車輛的路徑也是封閉的。因此，固定分區(qū)配送方案與網(wǎng)絡(luò)化配送方案是具有可比性的。最后，通過(guò)不同算法求解結(jié)果分析，驗(yàn)證設(shè)計(jì)算法的有效性。

表5中數(shù)據(jù)是本文網(wǎng)絡(luò)配送與許維勝等[21]固定分區(qū)配兩種模式的對(duì)比結(jié)果，最后一列數(shù)據(jù)為網(wǎng)絡(luò)分區(qū)相對(duì)固定分區(qū)的節(jié)約比例。從結(jié)果來(lái)看，當(dāng)客戶數(shù)量增多時(shí)網(wǎng)絡(luò)配送的效果有所下降，但協(xié)作點(diǎn)增多的情況下，網(wǎng)絡(luò)配送的效果又凸顯出來(lái)了。這是因?yàn)镋-n22-k4算例集合中客戶比較少且分散，網(wǎng)絡(luò)化配送能夠很好發(fā)揮其資源共享的優(yōu)勢(shì)，然而客戶比較密集時(shí)，客戶增多協(xié)作點(diǎn)沒(méi)有增加時(shí)，這種優(yōu)勢(shì)逐漸消失。但客戶數(shù)量相同協(xié)作點(diǎn)增加時(shí)，網(wǎng)絡(luò)化配送的優(yōu)勢(shì)則很好地凸顯出來(lái)。在此分別以算例2與20的結(jié)果為例，配送方案見圖6與7。

表5 兩種配送方案對(duì)比分析

圖6 算例2的配送方案

圖7 算例20的配送方案

為了驗(yàn)證算法的求解效果，通過(guò)與許維勝等[21]和Hemmelmayr等[22]的大鄰域搜索算法與Memetic算法分別對(duì)四個(gè)集合的算例進(jìn)行求解，具體結(jié)果見表6。

由表6的結(jié)果可見，當(dāng)算例規(guī)模不大時(shí)，三種算法均能取得較好的效果，當(dāng)算例規(guī)模增大時(shí)三種算法在求解時(shí)間上均有所增長(zhǎng)，但大鄰域搜索與Memetic算法變化較大。在求解質(zhì)量上，由于云遺傳算法利用云模型云滴的隨機(jī)性與傾向性產(chǎn)生的交叉變異概率與增加的擾動(dòng)算子增強(qiáng)了算法的搜索能力，同時(shí)，種群擴(kuò)張機(jī)制增強(qiáng)了算法的穩(wěn)定性，在多次求解中均能得到最優(yōu)解，而大鄰域算法與Memetic算法卻沒(méi)有如此效果。因此可以得出結(jié)論，云遺傳算法完全能勝任本文模型的求解。

表6 不同算法測(cè)試結(jié)果對(duì)比

7 結(jié)語(yǔ)

針對(duì)分時(shí)段、分路段、分車型的城市交通限行政策，在深入分析道路、車輛、需求的屬性特征的基礎(chǔ)上，從道路-車輛-需求優(yōu)化匹配的視角研究交通限行條件下城市配送問(wèn)題。因此，本文的研究結(jié)論與創(chuàng)新體現(xiàn)在以下幾個(gè)方面：

(1)為了充分發(fā)揮不同車型的經(jīng)濟(jì)性與靈活性，提出面向交通限行的車輛協(xié)作與序貫式換乘聯(lián)運(yùn)策略，通過(guò)換乘協(xié)作點(diǎn)的設(shè)置與車輛協(xié)作規(guī)則貫通交通限行區(qū)域與通暢區(qū)域，建立兩級(jí)網(wǎng)絡(luò)化換乘聯(lián)運(yùn)模型。

(2)根據(jù)模型特點(diǎn)提出自下向上的求解思路，設(shè)計(jì)兩階段求解算法，首先利用云模型理論改進(jìn)遺傳算法交叉算子與變異算子，設(shè)計(jì)云遺傳算法求解第二級(jí)配送問(wèn)題，然后依據(jù)配送方案并結(jié)合協(xié)作點(diǎn)選擇規(guī)則確定啟用的協(xié)作點(diǎn)，采用C-W法求解第一級(jí)配送問(wèn)題。

(3)通過(guò)算例對(duì)模型和算法進(jìn)行了實(shí)驗(yàn)分析，從不同方面對(duì)算法進(jìn)行檢驗(yàn)，結(jié)果表明本文設(shè)計(jì)的模型和算法取得了較好的效果。

由于篇幅和精力原因，本文只對(duì)靜態(tài)的交通限行配送問(wèn)題進(jìn)行了研究，沒(méi)有考慮交通網(wǎng)絡(luò)的時(shí)變性和客戶需求的動(dòng)態(tài)性，而這些問(wèn)題是城市多區(qū)域配送問(wèn)題不可忽視也難以回避的現(xiàn)實(shí)，在下一步的研究將繼續(xù)關(guān)注這兩個(gè)方面。

[1] 李妍峰,李軍,高自友.大規(guī)模鄰域搜索算法求解時(shí)變車輛調(diào)度問(wèn)題[J].管理科學(xué)學(xué)報(bào),2012,15(1):22-32.

[2] 馬華偉,靳鵬,楊善林.時(shí)變車輛路徑問(wèn)題的啟發(fā)式算法[J].系統(tǒng)工程學(xué)報(bào),2012,27(2):256-262.

[3] 李妍峰,高自友,李軍.基于實(shí)時(shí)交通信息的城市動(dòng)態(tài)網(wǎng)絡(luò)車輛路徑優(yōu)化問(wèn)題[J].系統(tǒng)工程理論與實(shí)踐, 2013,33(7):1813-1819.

[4] Franceschetti A, Honhon P,Van Woensel T,et al. The time-dependent pollution-routing problem[J].Transportation Research Part B,2013,56(10):265-293.

[5] 馬祖軍,胡萍.實(shí)時(shí)/時(shí)變路網(wǎng)環(huán)境下城市出救點(diǎn)選擇與救援車輛路徑的集成動(dòng)態(tài)優(yōu)化[J].管理工程學(xué)報(bào), 2014,(4):165-172.

[6] Bhusiri N, Qureshi A G,Tanóguchi E. The trade-off between fixed vehicle costs and time-dependent arrival penalties in a routing problem[J].Transportation Research Part E,2014,62(2):1-22.

[7] Verbeeck C, S?rensen K,Aghezzaf E H,et al.A fast solution method for the time-dependent orienteering problem[J].European Journal of Operational Research,2014,236(2):419-432.

[8] Tas D, Dellaert N,Van Woensel T,et al.The time-dependent vehicle routing problem with soft time windows and stochastic travel times[J].Transportation Research Part C-Emerging Technologies,2014,246(48):66-83.

[9] 陳玉光,陳志祥.基于準(zhǔn)時(shí)送貨和最小耗油的配送車輛路徑問(wèn)題研究[J].中國(guó)管理科學(xué),2015,23(11):156-165.

[10] 唐金環(huán),戢守峰,沈貴財(cái).時(shí)變網(wǎng)絡(luò)下考慮碳排放的車輛路徑優(yōu)化[J].系統(tǒng)工程,2015,33(9):37-44.

[11] Gendreau M, Ghiani G,Guerriero E.Time-dependent routing problems: A review[J].Computers & Operations Research,2015,128(64):189-197.

[12] Soysal M, Bloemhof-Ruwcoard J M,Bekatas T.The time-dependent two-echelon capacitated vehicle routing problem with environmental considerations[J].International Journal of Production Economics,2015, 164(36):366-378.

[13] Sun Sichao,Duan Zhengyu,Yang Dongyuan. Urban freight management with stochastic time-dependent travel times and application to large-scale transportation networks[J].Discrete Dynamics in Nature and Society,2015(1)：1-10.

[14] 王旭坪,張珺,易彩玉.B2C電子商務(wù)環(huán)境下訂單揀選與配送聯(lián)合調(diào)度優(yōu)化[J].中國(guó)管理科學(xué),2016,24(7):101-109.

[15] 四兵鋒,楊小寶,高亮.基于系統(tǒng)最優(yōu)的城市公交專用道網(wǎng)絡(luò)設(shè)計(jì)模型及算法[J].中國(guó)管理科學(xué),2016, 24(6):106-114.

[16] Cao Zhiguang,Zhang Jie,Nigato D,et al.Improving the efficiency of stochastic vehicle routing: A partial lagrange multiplier method[J].Ieee Transactions on Vehicular Technology,2016,65(6):3993-4005.

[17] Ehmke J F, Campbell A M,Thomas B W.Vehicle routing to minimize time-dependent emissions in urban areas[J].European Journal of Operational Research,2016,251(2):478-494.

[18] Qian Jiani,Eglese R.Fuel emissions optimization in vehicle routing problems with time-varying speeds[J].European Journal of Operational Research,2016,248(3):840-848.

[19] 李德毅.不確定性人工智能[M].北京:國(guó)防工業(yè)出版社,2005.

[20] Perboli G, Tadei R, Vigo D. The two-echelon capacitated vehicle routing problem: Models and math-based heuristics[J]. Transportation Science,2011,45(3):364-380.

[21] 許維勝,曾正洋,徐志宇.一種求解兩級(jí)車輛路徑問(wèn)題的Memetic算法[J].控制與決策,2013,28(10): 1587-1590.

[22] Hemmelmayr V C, Cordeau J F, Crainic T G. An adaptive large neighborhood search heuristic for two-echelon vehicle routing problems arising in city logistics[J]. Computers & Operations Research,2012,39(12):3215-3228.

TheVehiclecoordinationStrategyandTransferCombinedTransporttoUrbanDistributionProblemUnderTrafficRestrictions

GEXian-long1,2，XUJiu-ping2，WANGWei-xin3

(1.School of Management Chongqing Jiaotong University，Chongqing 400074,China;2.Business college, Sichuan University, Chengdu 610065,China;3.School of International Management Sichuan International Studies University，Chongqing 400051,China)

Urban distribution is a complex ecosystem, which bears the interactive features of the city and the outside world, it guaranteed of the development of city economic and the better of Urban residents. In recent years, however, with the sharp increase of cars in city and road resources nervous, which caused serious traffic congestion in large cities. In order to alleviate traffic pressure, especially peak period congestion in road, domestic and overseas cities have adopted some methods to solve this problem, for example, Night deliveries, Restricting truck. However it is difficult for urban distribution and bring new challenges to the city logistics distribution. In order to deal with traffic restrictions policies for different vehicle types in different route section and different time section, characteristics of route, vehicles, demand are analyzed in depth and then urban distribution under such traffic restrictions is studied from the perspective of optimal Route-Time-Vehicle-Demand matching. In the first place, the incoherence in distribution caused by traffic restriction is about to be solved by studying partitioning distribution, matching method between vehicle types and traffic routes, interchange rules in multi-modal transportation. Corresponding collaborative strategies for vehicles and sequential interchanges strategies will be proposed. Secondly, the economic and flexibility of different vehicle types can be fully made use via introducing the freight route concept, also, the restricted traffic area and artery traffic network are connected by stripping and combining freight route, setting interchange point and coordinating the vehicles. The two-stage optimization model is built and according cloud quantum genetic algorithm is designed to provide quantitative studies for logistics distribution in this vehicle collaboration and integrated transportation problem. Meanwhile, using the randomness and bias stability of the cloud droplet cloud model, the Cloud Genetic algorithm is designed for the secondary distribution problem and the C-W algorithm is designed for the first level distribution problem, in order to enhance the solving quality and efficiency of algorithm, the disturbance operator and population expansion operator are designed. For the comparison, several different cases are conducted to illustrate the established model and solving algorithm.

1003-207(2017)10-0130-10

10.16381/j.cnki.issn1003-207x.2017.10.014

U4

A

2016-03-25；

2016-10-28

國(guó)家自然科學(xué)基金資助項(xiàng)目(71502021)；教育部人文社會(huì)科學(xué)基金項(xiàng)目(2014YJC630038)；教育部人文社會(huì)科學(xué)基金項(xiàng)目(2015XJC630007)；博士后科學(xué)基金項(xiàng)目(2016T90862)；重慶市基礎(chǔ)與前沿研究項(xiàng)目資助(cstc2016jcyjA0160)

葛顯龍(1984-)，男(漢族)，河南信陽(yáng)人，重慶交通大學(xué)管理學(xué)院副教授，博士，研究方向：網(wǎng)絡(luò)配送與路徑優(yōu)化，E-mail: gexianlong@cqjtu.edu.cn.

Keywords： traffic restrictions; vehicle collaborations; transfer combined transport; urban distribution