龐海軍，丁以中

(上海海事大學(xué) 科學(xué)研究院，上海 201306)

0 引言

近些年，電子行業(yè)在售后服務(wù)方面發(fā)生巨大的變化，許多新興產(chǎn)品不僅需要配送，而且需要專業(yè)的安裝.它們包括掛壁式電視機(jī)(家庭影院系統(tǒng))、洗衣機(jī)和干衣機(jī)、帶有凈水系統(tǒng)的冰箱、特殊烹調(diào)臺(tái)面、數(shù)控機(jī)、電腦服務(wù)器等.然而，由于維持全國(guó)配送和客戶服務(wù)網(wǎng)絡(luò)的費(fèi)用太高，企業(yè)采取將配送業(yè)務(wù)外包給第三方物流企業(yè)的方法，僅保留自己的服務(wù)隊(duì)伍.于是，電子行業(yè)中出現(xiàn)產(chǎn)品配送與安裝相分離的現(xiàn)象.依據(jù)這一特點(diǎn)，本文研究一種變形的車輛調(diào)度問(wèn)題(Vehicle Routeing Problem，VRP)，以滿足其獨(dú)特的物流配送需求.

KIM 等［1］首先對(duì)此種變形的VRP 進(jìn)行研究.他假設(shè)安裝車輛必須在配送車輛訪問(wèn)(或者到達(dá))那個(gè)顧客之后，在服務(wù)水平之內(nèi)訪問(wèn)顧客，從而保證這兩種類型的車輛同步，以滿足顧客配送和安裝的服務(wù)質(zhì)量.在他們的研究中，可以將服務(wù)水平看作是硬時(shí)間窗［2］VRP 的變形.當(dāng)前，對(duì)此種變形的VRP 的研究都是在硬時(shí)間窗的約束條件下對(duì)模型進(jìn)行的研究，然而在實(shí)際物流配送中其復(fù)雜程度遠(yuǎn)超過(guò)于此.本文在前人研究的基礎(chǔ)上考慮在軟時(shí)間窗［3］約束下的VRP，因?yàn)檐洉r(shí)間窗與實(shí)際情況更接近.此約束條件既可滿足顧客的服務(wù)質(zhì)量，同時(shí)又可兼顧企業(yè)的利潤(rùn)最大化.

可以將此變形的VRP 看作是兩個(gè)傳統(tǒng)VRP 的組合:一個(gè)是配送車輛的VRP，它具有容量限制的VRP(Capacity VRP，CVRP)的特點(diǎn)［4-5］;另一個(gè)是安裝車輛的VRP，它具有帶時(shí)間窗VRP 的特點(diǎn)［6-7］.由于該模型的復(fù)雜程度遠(yuǎn)遠(yuǎn)超過(guò)經(jīng)典VRP 模型的復(fù)雜程度，即使采用啟發(fā)式算法編程求解也很復(fù)雜，KIM 等［1］引入層次的概念將原問(wèn)題劃分為若干子問(wèn)題的組合，從而降低問(wèn)題的規(guī)模.分層后的模型是早被國(guó)際證實(shí)的NP 難問(wèn)題，采用正常方法求解十分困難，因此可利用遺傳算法(Genetic Algorithm，GA)在一個(gè)合理時(shí)間內(nèi)有效解決所考慮的問(wèn)題.

繼續(xù)采用層次的概念將原問(wèn)題變?yōu)閮蓚€(gè)子問(wèn)題的組合，即:第一階段是配送車輛的VRP，確定配送車輛的路線和調(diào)度;第二階段是安裝車輛帶軟時(shí)間窗的VRP(VRP with Soft Time Window，VRPSTW)，基于第一階段的計(jì)算結(jié)果，獲得第二階段安裝車輛的路線和調(diào)度.對(duì)大量不同規(guī)模例子的的計(jì)算表明:文中所采用的分層GA 的可行性和有效性;第一階段的最好結(jié)果并不一定是原問(wèn)題的最佳結(jié)果.該研究還可以對(duì)制訂配送車輛和安裝車輛調(diào)度的有效管理計(jì)劃提供幫助.

1 基于軟時(shí)間窗的配送和安裝車輛調(diào)度優(yōu)化模型

1.1 問(wèn)題描述與假設(shè)

給定一配送中心和多個(gè)不同的需求點(diǎn)，已知配送中心擁有兩種類型的最大車輛數(shù)，以及每個(gè)需求點(diǎn)(客戶)的位置，需求數(shù)量(不超過(guò)貨車最大載重量)及是否需要安裝.對(duì)于只需要配送的顧客點(diǎn)，只允許一輛配送車輛訪問(wèn)一次;對(duì)于需要配送和安裝的顧客，只允許一輛配送車輛和一輛安裝車輛分別訪問(wèn)一次.所有車輛開(kāi)始從同一配送中心出發(fā)對(duì)顧客進(jìn)行服務(wù)，安裝車輛可以在配送車輛之前訪問(wèn)顧客，這就在對(duì)應(yīng)的顧客位置產(chǎn)生安裝車輛的等待時(shí)間，超過(guò)規(guī)定時(shí)間就要受到一個(gè)與時(shí)間成正比的懲罰.如果安裝車輛在配送車輛之后訪問(wèn)客戶，若不能在顧客可以忍耐的時(shí)間內(nèi)到達(dá)，就要受到一個(gè)與時(shí)間成正比的懲罰.車輛完成服務(wù)后返回配送中心，所有客戶的需求都必須滿足.求:如何安排配送車輛和安裝車輛的路線，使整個(gè)服務(wù)過(guò)程總時(shí)間最少，總時(shí)間包括固定安裝時(shí)間、等待時(shí)間及懲罰時(shí)間、行駛時(shí)間.圖1 顯示服務(wù)水平為軟時(shí)間窗的VRP 的例子.

圖1 車輛路徑問(wèn)題實(shí)例

對(duì)上述問(wèn)題描述，假設(shè)以下幾點(diǎn)成立:

(1)不允許車輛超載;

(2)配送中心有足夠供調(diào)度的車輛，且每輛車有最大的運(yùn)行時(shí)間;

(3)所有車輛單位時(shí)間內(nèi)行駛的路程相同，且各客戶點(diǎn)與配送中心以直線連接;

(4)貨物的裝卸時(shí)間忽略不計(jì).

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

為了建立配送車輛和安裝車輛調(diào)度模型，設(shè)配送中心為0，顧客點(diǎn)為N(位置1 到N)，同時(shí)要求配送和安裝的顧客屬于A(|A|≤N)，定義以下參數(shù):

N為顧客數(shù)量;K為配送車輛數(shù)量;S為安裝車輛數(shù)量;A為同時(shí)需要配送和安裝的顧客集合;Tij為車輛從顧客i 行駛到顧客j 的時(shí)間;Di為顧客i 的需求量;VC為配送車輛的容量;Ri為顧客i 處安裝所需時(shí)間，i∈A;OT為車輛循環(huán)一次的最大操作時(shí)間;M為一個(gè)很大的實(shí)數(shù);ei為配送車輛到達(dá)顧客i 的時(shí)間，i∈N;fi為安裝車輛到達(dá)顧客i 的時(shí)間，i∈A;Pi為安裝車輛到達(dá)顧客i 的懲罰，i∈A;uip為配送車輛p 訪問(wèn)位置i 的順序數(shù);viq為安裝車輛q 訪問(wèn)位置i 的順序數(shù).

1.3 VRPSTW 模型

所考慮的問(wèn)題可以用一個(gè)混合整數(shù)非線性規(guī)劃(Mixed-Integer Nonlinear Programming，MINP)模型描述，其目標(biāo)是使所有配送車輛和安裝車輛的總運(yùn)行時(shí)間最少，決策變量提供配送車輛和安裝車輛的最佳路徑和調(diào)度.模型如下:

在VRPSTW 數(shù)學(xué)模型中，將運(yùn)行距離或運(yùn)輸費(fèi)用統(tǒng)一轉(zhuǎn)換成運(yùn)行時(shí)間在模型中體現(xiàn)，目標(biāo)函數(shù)是所有配送車輛和安裝車輛的總運(yùn)行時(shí)間最小.式(2)和(12)限制從配送中心出發(fā)的車輛;約束(3)，(4)，(5)，(13)，(14)，(15)分別保證車輛都由配送中心出發(fā)并最終回到配送中心;約束(6)，(7)，(16)，(17)表示每個(gè)客戶只能受到一輛車服務(wù)并且每個(gè)客戶都得到服務(wù);約束(8)表示每輛車所運(yùn)送的貨物重量不能超過(guò)車輛載重的限制;約束(9)和(18)表示防止車輛在內(nèi)部出現(xiàn)子循環(huán);約束(10)和(19)表示車輛在客戶點(diǎn)不動(dòng)時(shí)為零;(11)和(20)為變量取值約束;式(21)表示車輛從配送中心出發(fā)和安裝時(shí)間為零;約束(22)表示配送車輛p 到達(dá)顧客點(diǎn)i 的時(shí)間加上i 到j(luò) 的行駛時(shí)間，小于等于車輛到達(dá)j 的時(shí)間;約束(23)表示安裝車輛q 到達(dá)顧客點(diǎn)i的時(shí)間加上在i 處的等待時(shí)間、為顧客i 服務(wù)的時(shí)間、i 到j(luò) 的行駛時(shí)間總和，小于等于車輛到達(dá)j 的時(shí)間;約束(24)和(25)分別表示配送車輛和安裝車輛的最大操作時(shí)間;約束(26)為延遲懲罰函數(shù).

圖2 懲罰函數(shù)

軟時(shí)間窗約束在這里被定義為一個(gè)懲罰函數(shù)，見(jiàn)圖2.

在這種懲罰函數(shù)中，安裝車輛只有在配送車輛到達(dá)時(shí)間ei之后才能開(kāi)始服務(wù)，若提前到達(dá)將等待，當(dāng)?shù)却龝r(shí)間大于a 時(shí)，將有一個(gè)等待的機(jī)會(huì)成本發(fā)生.當(dāng)車輛到達(dá)的時(shí)間在［ei-a，ei+b］范圍內(nèi)無(wú)須罰款，而到達(dá)時(shí)間在ei+b 之后，將受到一個(gè)與遲到時(shí)間成正比的懲罰.當(dāng)車輛到達(dá)時(shí)間早于ei-a 時(shí)，也將受到類似遲到的懲罰，其中:fi是安裝車輛到達(dá)顧客點(diǎn)i 的時(shí)間，M1和M2是等待或遲到時(shí)最低(固定)成本，u1是每單位等候時(shí)間的成本，u2是每單位時(shí)間的遲到罰款.

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

由于VRP是世界公認(rèn)的NP 難問(wèn)題，本文所研究的變形VRP 更是在經(jīng)典VRP 上的疊加，困難度遠(yuǎn)超經(jīng)典VRP.若采用直接的方法求解，很少的客戶點(diǎn)求解規(guī)模也很大，即使采用啟發(fā)式算法編程求解也非常復(fù)雜.為了獲得原始問(wèn)題的良好解決方案，本文在文獻(xiàn)［1］的基礎(chǔ)上繼續(xù)引入分層思想將原問(wèn)題分為兩個(gè)階段，每階段包括一個(gè)子問(wèn)題.第一階段的子問(wèn)題是一個(gè)配送車輛的VRP，解決配送車輛的路徑和時(shí)間安排;第二階段的子問(wèn)題是一個(gè)安裝車輛的VRPSTW 問(wèn)題.第一階段子問(wèn)題是原問(wèn)題的部分解決方案，同時(shí)也用作第二階段的子問(wèn)題數(shù)據(jù)輸入部分.依據(jù)第一階段子問(wèn)題提出的部分解決方案，確定第二階段子問(wèn)題中安裝車輛的路徑和時(shí)間安排方案.安裝車輛的路徑和時(shí)間安排也是原問(wèn)題的部分解決方案.解決第二階段的子問(wèn)題后，兩種類型車輛的協(xié)同問(wèn)題也就得到解決.最后，兩個(gè)子問(wèn)題的部分解決方案也就是原來(lái)問(wèn)題的解決方案.

通過(guò)分層方法將原問(wèn)題劃分為兩個(gè)階段的子問(wèn)題，從而簡(jiǎn)化原問(wèn)題的規(guī)模和復(fù)雜度.對(duì)于規(guī)模不太大的問(wèn)題，可以通過(guò)LINGO 求得目標(biāo)函數(shù)的精確解.但LINGO 不適用于大規(guī)模的問(wèn)題，本文通過(guò)GA求解，只能得到近似解.通過(guò)利用LINGO 9.0和GA分別求得精確解和近似解，并對(duì)兩種結(jié)果進(jìn)行比較分析.

2 算 例

設(shè)有1個(gè)配送中心和16個(gè)顧客點(diǎn)，其中有7個(gè)顧客點(diǎn)同時(shí)需要配送與安裝.假設(shè)所有客戶隨機(jī)位于50 ×50 的正方形上，并且將配送中心設(shè)在正方形的中心位置.為了便于對(duì)GA 以及分層方法進(jìn)行檢驗(yàn)，假設(shè)隨機(jī)產(chǎn)生的坐標(biāo)點(diǎn)、每個(gè)客戶點(diǎn)的需求量以及客戶是否需要安裝見(jiàn)表1.假設(shè)配送車輛與安裝車輛的速度相同并且行駛時(shí)速度V=1 m/min 不變，配送車輛的最大載重單位為15個(gè)(不允許超載)安裝時(shí)間，R=10 min 不變.懲罰函數(shù)的參數(shù)如下:M1=M2=0，u1=2 min，u2=2 min，a=10 min，b=10 min.

表1 客戶點(diǎn)的編號(hào)、坐標(biāo)、需求量、安裝與否

2.1 精確算法

所有求解計(jì)算都在CPU為酷睿雙核2.40 GHz，內(nèi)存為4 GB 的計(jì)算機(jī)上實(shí)現(xiàn)，使用LINGO 9.0 編程求解算例.為了便于LINGO 9.0 求解并提高求解速度，對(duì)模型中的一些非線性約束進(jìn)行變換，例如將約束(25)轉(zhuǎn)換成fj＜OT最終運(yùn)行1 h 5 min 7 s，求解得目標(biāo)函數(shù)值及配送車輛和安裝車輛的最優(yōu)路徑結(jié)果見(jiàn)表2.

表2 最優(yōu)解和近似解

2.2 GA 近似算法與近似解

由于精確算法的求解過(guò)程耗時(shí)過(guò)長(zhǎng)，不適合實(shí)際配送企業(yè)的決策，本算例采用GA 進(jìn)行求解.GA由HOLLAND(1975)首先提出.由于它能在一個(gè)合理的時(shí)間內(nèi)取得解決復(fù)雜優(yōu)化問(wèn)題的良好結(jié)果，已被廣泛應(yīng)用.特別是近幾年的基于GA 的啟發(fā)式搜索策略［8-10］，就是為了增強(qiáng)解決VRPSTW 問(wèn)題的效果.

本文采用基于自然數(shù)的編碼方式［10］.由于車輛數(shù)可事先估出，故進(jìn)化群體中的一個(gè)染色體可以表示為:(0，i11，i12，…，i1s，0，i21，…，i2t，0，…，0，im1，…，imv，0).其中，自然數(shù)ikj表示客戶點(diǎn)的編號(hào)，染色體的總長(zhǎng)度為N+m+1，0 代表配送中心，一共有m+1個(gè)0 把整個(gè)染色體分成m 段，即代表m個(gè)路徑.

適應(yīng)度函數(shù)的設(shè)計(jì)，對(duì)于第一階段的非滿載CVRP，將容量約束式(7)變換為目標(biāo)函數(shù)的一部分:

對(duì)于第二階段的安裝車輛VRPSTW，使用如下目標(biāo)函數(shù)式的一部分:

一般地，適應(yīng)度函數(shù)要求非負(fù)，所以將目標(biāo)函數(shù)變換為適應(yīng)度函數(shù)，即fi=1/Zi.式中:fi為染色體i的適應(yīng)值;Zi為染色體i 對(duì)應(yīng)的經(jīng)過(guò)約束處理后的目標(biāo)函數(shù)式(27)或(28).

對(duì)于染色體的交叉與變異，采用文獻(xiàn)［11］中設(shè)計(jì)的最大保留交叉來(lái)保證群體多樣性，其具體操作過(guò)程為:如果染色體交叉點(diǎn)處的兩個(gè)基因?yàn)?，直接進(jìn)行PMX［2］(部分匹配交叉)運(yùn)算;如果染色體交叉點(diǎn)處的基因不全為0，則將交叉點(diǎn)左移(右移)，直到左右兩個(gè)交叉點(diǎn)處的基因都為0，再進(jìn)行PMX 運(yùn)算.變異采用文獻(xiàn)［12］中的2-交叉變異，即隨機(jī)選擇一個(gè)染色體的兩個(gè)非零元素，交換這兩個(gè)元素的位置生成新的染色體.

算法中的各參數(shù):交叉率pc=0.85，變異概率pm=0.3，種群規(guī)模為30，最大迭代次數(shù)為100;計(jì)算過(guò)程使用C#語(yǔ)言編程求解，第一階段和第二階段的子問(wèn)題分別經(jīng)過(guò)42 次和31 次迭代，耗時(shí)分別為54 s和32 s，GA 的收斂過(guò)程見(jiàn)圖3，可行最優(yōu)解見(jiàn)表2.

圖3 GA 的收斂過(guò)程

此外，為了進(jìn)一步驗(yàn)證采用分層的GA 的有效性和可行性，將算例中的客戶點(diǎn)增加至30個(gè)，其中需要安裝的客戶點(diǎn)為10個(gè)，每個(gè)顧客的需求量是1～4個(gè)，6 輛配送車輛和2 輛安裝車輛.求解過(guò)程中總的運(yùn)算時(shí)間為125 s，運(yùn)算結(jié)果為843.4 min，運(yùn)行路徑見(jiàn)圖4(配送中心出發(fā)到客戶點(diǎn)和返回配送中心的路線省略).

圖4 車輛路徑計(jì)算結(jié)果

2.3 求解方法有效性分析

為了說(shuō)明采用分層的GA 的有效性，首先用LINGO 9.0 求解出該算例以最小運(yùn)行時(shí)間為目標(biāo)函數(shù)的車輛行駛路徑結(jié)果;再用分層的方法將模型分為兩個(gè)子問(wèn)題考慮;最后通過(guò)GA 求解近似結(jié)果.從圖3中可以看出，雖然近似解結(jié)果不如精確結(jié)果優(yōu)異，但是可以說(shuō)明采用分層的GA 所求結(jié)果的可行性.由于LINGO 9.0 只能求解較小規(guī)模的MINP 模型，且費(fèi)時(shí)較長(zhǎng)，在現(xiàn)實(shí)生活中物流配送量往往很大，要求在合理的時(shí)間得到配送方案，精確算法就不適合，而GA可以在一個(gè)合理的時(shí)間內(nèi)得到一個(gè)較滿意的解.為了進(jìn)一步對(duì)所提出的分層的GA 的有效性和可行性檢驗(yàn)，文中隨機(jī)生成大量規(guī)模較大的MINP 模型進(jìn)行求解計(jì)算，圖4 就是其中一個(gè)算例.計(jì)算結(jié)果表明:該分層算法可以在合理的時(shí)間內(nèi)找到問(wèn)題的最優(yōu)解或者近似最優(yōu)解;第二階段子問(wèn)題的結(jié)果受第一階段子問(wèn)題結(jié)果的影響，第一階段子問(wèn)題的最優(yōu)解決方案不能保證原問(wèn)題的解決方案最優(yōu).

3 結(jié)束語(yǔ)

隨著現(xiàn)代物流配送的發(fā)展，不同行業(yè)對(duì)其要求不同，各有特點(diǎn).本文依據(jù)電子行業(yè)配送的新特點(diǎn)，研究一種變形的VRP.所考慮的問(wèn)題是兩種不同類型的配送服務(wù):一種只需要配送服務(wù)，一種是配送與安裝都需要的服務(wù).為了高效率地滿足顧客需求，企業(yè)采用兩種類型配送車輛分開(kāi)運(yùn)作的方式.在保證顧客的服務(wù)質(zhì)量方面，所要考慮的問(wèn)題是如何更好地解決兩種車輛的協(xié)同操作.本文在對(duì)所提出的模型求解時(shí)采用分層的方法進(jìn)行求解，這將導(dǎo)致第二階段子問(wèn)題的最優(yōu)結(jié)果受第一階段子問(wèn)題最優(yōu)結(jié)果的影響，第一階段子問(wèn)題的最優(yōu)解決方案不能保證是原問(wèn)題的最優(yōu)解決方案.未來(lái)的研究可以同時(shí)考慮兩個(gè)子問(wèn)題，在此模型的基礎(chǔ)上研究不確定因素下的模型等.

［1］KIM Kyoung Cheol，LEE Shiwoo.Hierarchical approach to vehicle routeing problem for delivery and installation［J］.Sci Direct，2010:7458-7471.

［2］van LANDEGHEM H R G.A bi-criteria heuristic for the vehicle routeing problem with time windows［J］.Eur J Operational Res，1988，36(2):217-226.

［3］KOSKOSIDIS Y A，POWELL W B，SOLOMON M M.An optimization-based heuristic for vehicle routeing and scheduling with soft time window constraints［J］.Transporting Sci，1992，26(2):69-85.

［4］CAMPOS V，MOTA E.Heuristic procedures for the capacitated vehicle routeing problem［J］.Computational Optimization ＆ Application，2000，16(3):265-277.

［5］PISINGER D，ROPKE S.A general heuristic for vehicle routeing problems［J］.Comput Operation Res，2007，34(8):2403-2435.

［6］ALVARENGA G B，MATEUS G R，de TOMI G.A genetic and set partitioning two-phase approach for the vehicle routeing problem with time windows［J］.Sci Direct，2007，34(6):1561-1584.

［7］CHENG Chibin，WANG Kengpin.Solving a vehicle routeing problem with time windows by a decomposition technique and a genetic algorithm［J］.Sci Direct，2009，36(4):7758-7763.

［8］TAN K C，LEE L H，OU K.Artificial intelligence heuristics in solving vehicle routeing problems with time window constraints［J］.Eng Applications of Artificial Intelligence，2001，14(6):825-837.

［9］BERGER J，BARKAOUI M，BRASY O.A route-directed hybrid GA approach for the VRPTW［J］.Inform Systems＆Operational Res，2003，41(2):179-194.

［10］盛麗俊，周溪召.帶有時(shí)間窗的車輛路徑問(wèn)題優(yōu)化［J］.上海海事大學(xué)學(xué)報(bào)，2007，28(4):64-67.

［11］李軍，謝秉磊，郭耀煌.非滿載車輛調(diào)度遺傳算法［J］.系統(tǒng)工程理論與實(shí)踐，2000，20(3):235-239.