以均衡為目標(biāo)的車輛調(diào)度問(wèn)題研究

孫有望， 宋華駿 （同濟(jì)大學(xué) 交通運(yùn)輸工程學(xué)院，上海 201804）

0 引 言

車輛調(diào)度問(wèn)題 （VRP）一般定義為：對(duì)一系列發(fā)貨點(diǎn)和收貨點(diǎn)組織適當(dāng)?shù)男熊嚶肪€，使車輛有序的通過(guò)它們，在滿足一定的約束條件下 （如貨物需求量、發(fā)送量、交發(fā)貨時(shí)間、車輛容量限制、行駛里程限制、時(shí)間限制等），達(dá)到一定的目標(biāo) （如路程最短、費(fèi)用最小、時(shí)間盡量少、使用車輛數(shù)盡量少等）[1]。它是一個(gè)復(fù)雜的組合優(yōu)化問(wèn)題，其中配送線路的調(diào)度為多目標(biāo)決策問(wèn)題，且屬于NP-Hard問(wèn)題[2]。

傳統(tǒng)的物流企業(yè)擁有自己的車隊(duì)，這些企業(yè)需要支付司機(jī)工資以及與車輛有關(guān)的一切費(fèi)用，因而以往的車輛調(diào)度模型以行駛總里程最短為目標(biāo)函數(shù)[3]，或者以行駛總里程與固定費(fèi)用總和最小為目標(biāo)函數(shù)[4]。這些物流企業(yè)存在著工作量嚴(yán)重不均衡的現(xiàn)象，有的線路吃不飽，有的線路卻任務(wù)繁重，這影響了司機(jī)的工作熱情和滿意度[2]。

目前，一些國(guó)內(nèi)物流企業(yè)的發(fā)展已經(jīng)頗具規(guī)模，他們將不同車型的車輛承包給司機(jī)，由此不再支付司機(jī)工資與車輛有關(guān)的任何費(fèi)用，而僅僅在需要調(diào)度車輛時(shí)支付給司機(jī)出車費(fèi)，以此獲得更大的利潤(rùn)。因此，這些企業(yè)需要根據(jù)顧客的需求和車輛的相關(guān)信息，以總費(fèi)用最低為目標(biāo)選配車輛。本文將車輛調(diào)度問(wèn)題分成兩個(gè)階段，第一階段設(shè)計(jì)Ak-First Fit混合算法進(jìn)行車輛選型，第二階段針對(duì)不同線路工作量不均衡問(wèn)題提出單位運(yùn)輸費(fèi)用概念，建立新的目標(biāo)函數(shù)并運(yùn)用遺傳算法 （Genetic Algorithm，GA）進(jìn)行車輛路徑優(yōu)化。

1 問(wèn)題描述和模型構(gòu)建

1.1 問(wèn)題描述

配送中心0需要向區(qū)域內(nèi)的n個(gè)客戶配送貨物，各客戶需求點(diǎn)的需求量為gi（i=1,2,…,n ）。配送中心可調(diào)度h種不同車型的車共r輛型車輛的可調(diào)度數(shù)），s型車輛的最大載重量為qs，出車費(fèi)用為Cs。各個(gè)需求點(diǎn)之間及需求點(diǎn)與配送中心之間的距離dij為已知。配送車輛從配送中心出發(fā)，沿著一條行車路線把所有貨物送到指定位置后，返回自己所在的配送中心。且有 （sl表示s型車輛的第l輛車）：

1.2 模型構(gòu)建

根據(jù)司機(jī)承包車輛以及均衡各線路工作量的物流管理理念將車輛調(diào)度問(wèn)題分解為一個(gè)車輛選型問(wèn)題P1和一個(gè)車輛路徑優(yōu)化問(wèn)題P2。

其中ms為s型車輛的調(diào)度數(shù)。式 （1）表示s型車輛的調(diào)度數(shù)不能大于該車型的可調(diào)度車輛數(shù)，式 （2）表示每個(gè)需求點(diǎn)有且僅有一輛車進(jìn)行配送。

由于線路工作量主要取決于送貨里程和送貨量，因此引入單位運(yùn)輸費(fèi)用概念csl，即將s型車輛的第l輛車的出車費(fèi)用Cs除以該車的送貨量以及該車的送貨里程當(dāng)所有車輛的單位運(yùn)輸費(fèi)用接近時(shí)，所有線路的工作量亦接近，模型如下：

P2的目標(biāo)函數(shù)綜合考慮了配送線路總里程數(shù)以及單位運(yùn)輸費(fèi)用方差。其中b為常數(shù)，當(dāng)b取值較小時(shí)，目標(biāo)函數(shù)主要決于配送線路總里程數(shù)，此時(shí)更強(qiáng)調(diào)配送效率，而當(dāng)b取值較大時(shí)，則目標(biāo)函數(shù)主要取決于單位運(yùn)輸費(fèi)用方差，此時(shí)更強(qiáng)調(diào)線路作業(yè)量的公平性。sl表示s型車輛的第l輛車，表示平均單位運(yùn)輸費(fèi)用。式 （3）表示每輛車的裝載量不能超過(guò)其最大載重量，式 （4）表示s型車輛的出車數(shù)不能大于P1求得的調(diào)度數(shù)，式 （5）表示每個(gè)需求點(diǎn)有且僅有一輛車進(jìn)行配送，式 （6）、 （7）說(shuō)明對(duì)于每個(gè)客戶i，只有2個(gè)客戶與i相連，車輛由一個(gè)客戶直接駛向它，又由它直接駛向另一個(gè)客戶。

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

2.1 車輛選型Ak-First Fit混合算法

Ak-First Fit算法是一種混合啟發(fā)式搜索算法，算法的基本思想是：首先從全部r輛車中選出k輛車，按客戶需求量的非遞減次序?qū)⒚恳粋€(gè)需求點(diǎn)的貨物裝入第一輛可以裝得下的車，直至k輛車全部裝滿，然后按車輛出車費(fèi)用從小到大的次序挑選車輛，根據(jù)前述原則繼續(xù)裝載貨物，直至所有的貨物都裝載完畢為止。算法的主要步驟如下：

輸入： （C1, C2,…,Ch）及 （n1,n2,…,nh）和 （g1,g2,…,gn）

輸出： （m1,m2,…,mh）和出車總費(fèi)用z1

Step1： 構(gòu)造集合 （C11,C12,…,C1n1,C21,C22,…,C2n2,…,Ch1,Ch2,…,Chnh）， 并將其按非遞減次序排序， 設(shè)排序后結(jié)果為集合N

Step2：對(duì)集合 （g1,g2,…,gn）按非遞增次序排序，設(shè)排序后結(jié)果為集合M

Step3： 令 m1=0,m2=0,…,mh=0,z1=∞

Step4：從N中生成第一個(gè)元素個(gè)數(shù)≤k的子集T作為初始車輛集

Step6：從集合T中選擇第一輛裝得下集合M中第一個(gè)元素｛gi｝的車輛，若該車輛存在，則令M=M｛gi｝，轉(zhuǎn)Step6，若該車輛不存在，則轉(zhuǎn)Step7

Step7：若M≠φ，則從NT集合中選取第一個(gè)元素Csl，若該元素存在，則轉(zhuǎn)Step8，否則說(shuō)明原問(wèn)題無(wú)可行解，停止計(jì)算

若M=φ，則轉(zhuǎn)Step9

Step8： 令T=T∪｛sl｝,tempms=tempms+1,tempz1=tempz1+Cs， 轉(zhuǎn)Step6

Step9：若tempz1≤z1，令z1=tempz1，ms=tempms，否則轉(zhuǎn)Step10

Step10：若能生成下一個(gè)元素個(gè)數(shù)≤k的子集T，則轉(zhuǎn)Step4，否則，若不能再生成下一個(gè)元素個(gè)數(shù)≤k的子集T，則輸出： （m1,m2,…,mh）和z1

2.2 車輛路徑遺傳算法

2.2.1 遺傳算法編碼設(shè)計(jì)

采用自然數(shù)編碼，各種車型的車輛數(shù)ms由P1求得，自然數(shù)n表示客戶的個(gè)數(shù)，染色體結(jié)構(gòu)表示為：（0,i11,1,i112,…,i11t,0,i121,i122,…,i12u,0,…,0,ihmh1,ihmn2,…,ihmhv）， 染色體的總長(zhǎng)度為其中，自然數(shù)islj表示s型車輛的第l輛車路線中的第j個(gè)客戶，自然數(shù)0表示配送中心，m個(gè)0把染色體分為m段，代表m條路徑。

2.2.2 種群的初始化

產(chǎn)生初始群體的步驟如下：

Step1：為保證模型一定有可行解，將P1階段由Ak-First Fit混合算法求得的車輛配送路徑直接加入初始種群

Step2：產(chǎn)生隨機(jī)客戶序列，如 （3,5,n,…,l），將配送中心0插入該序列第一個(gè)位置

Step3：從第一個(gè)客戶點(diǎn)開始向后搜索，逐次累加客戶需求量。當(dāng)新加入一個(gè)客戶點(diǎn)，已累加需求量大于車輛最大載重量時(shí)，則在該客戶點(diǎn)之前插入0，并重新開始累加客戶需求量。共需插入構(gòu)成長(zhǎng)度為n的一條染色體，先插入的0代表載重量較大車型的起點(diǎn)。為了防止產(chǎn)生無(wú)效的染色體，插入0后滿足任意兩個(gè)0不相鄰

Step4：重復(fù)Step2-Step3，直至滿足種群規(guī)模size

2.2.3 適應(yīng)函數(shù)值計(jì)算

對(duì)于算法迭代過(guò)程中每代個(gè)體的優(yōu)劣通過(guò)個(gè)體適應(yīng)函數(shù)值進(jìn)行評(píng)價(jià)。對(duì)違反約束條件的個(gè)體引入懲罰值函數(shù)，以確保那些符合約束條件而較優(yōu)的個(gè)體有較大的生存機(jī)會(huì)。

該指標(biāo)可綜合反映染色體配送線路總里程數(shù)及單位運(yùn)輸費(fèi)用方差。

overload為0表示車輛調(diào)度方案滿足車輛最大載重量約束時(shí)，個(gè)體適應(yīng)函數(shù)值為原值，overload為1表示車輛調(diào)度方案超載時(shí)，個(gè)體適應(yīng)函數(shù)分母需加上懲罰值，C為懲罰值。

2.2.4 選擇

采用改進(jìn)的輪盤賭選擇法。選擇過(guò)程中將群體中適應(yīng)函數(shù)值最大的個(gè)體直接復(fù)制到下一代，對(duì)于其他個(gè)體，其被選擇的概率為：

p（i）等于第i條染色體的適應(yīng)度在整個(gè)群體的適應(yīng)函數(shù)值總和中所占的比例，染色體的適應(yīng)函數(shù)值越大，則其被選中的概率越高。

2.2.5 交叉

遺傳算法思想的核心之一是在進(jìn)化過(guò)程中，子代能夠充分繼承父代的優(yōu)良基因，并且有所發(fā)展，可謂揚(yáng)棄。如果單純得使用一般的交叉算子往往會(huì)使一些優(yōu)秀的子路徑被破壞，并且在兩個(gè)父體相同時(shí)，無(wú)法再產(chǎn)生新的個(gè)體。這里采用對(duì)順序交叉 （OX）方式進(jìn)行改進(jìn)的一種交叉算子[5]：

首先通過(guò)隨機(jī)函數(shù)產(chǎn)生兩個(gè)數(shù)作為交叉點(diǎn)，兩個(gè)父?jìng)€(gè)體交叉時(shí)，通過(guò)選擇父?jìng)€(gè)體1的一部分，然后保存父?jìng)€(gè)體2中的客戶碼的相對(duì)順序生成。

例如：對(duì)下面兩個(gè)父?jìng)€(gè)體，隨機(jī)選擇兩個(gè)數(shù)（3,9 ）作為交叉點(diǎn)：

首先，將兩個(gè)交叉點(diǎn)之間的中間段和第一位的基因碼保留，得到：

然后取f2從第2個(gè)交叉點(diǎn)開始的客戶碼排列順序，當(dāng)?shù)竭_(dá)表尾時(shí)返回表頭繼續(xù)記錄客戶碼，直到第2個(gè)交叉點(diǎn)結(jié)束，得到客戶碼排列順序 （0 4 5 0 3 7 8 1 0 62 ）。將o1中擁有的客戶碼從該排列順序中去掉，可得排列順序（7 8 16 ），將這個(gè)排列順序復(fù)制給o1，復(fù)制的起點(diǎn)從第2個(gè)交叉點(diǎn)開始，得到交叉后的客戶碼排列順序o1：（0 6 3 0 5 2 0 4 7 81 ），同理可得o2： （0 4 7 8 1 0 6 2 3 50 ）。

2.2.6 變異

采用有條件變異算子，以防止種群退化。當(dāng)染色體適應(yīng)值大于a時(shí)，不進(jìn)行變異，否則據(jù)概率pm對(duì)染色體進(jìn)行基因換位變異。

2.2.7 算法的實(shí)現(xiàn)過(guò)程

Step1：令迭代次數(shù)k=0，確定算法的最大迭代次數(shù)K、種群規(guī)模size、交叉概率pc和變異概率pm

Step2：產(chǎn)生初始種群，計(jì)算群體中所有個(gè)體的適應(yīng)函數(shù)值fk，找出適應(yīng)函數(shù)值最大的染色體

Step3：若k=K，則轉(zhuǎn)Step6，否則轉(zhuǎn)Step4

Step4：將群體中最優(yōu)的個(gè)體直接復(fù)制到下一代，按照概率p（i）、pc和pm分別選擇個(gè)體進(jìn)行選擇、交叉和變異操作

Step5：計(jì)算子代個(gè)體的適應(yīng)函數(shù)值fk，令k=k+1，轉(zhuǎn)Step3

Step6：輸出最優(yōu)結(jié)果，適應(yīng)函數(shù)值fk最大的個(gè)體為算法的最優(yōu)個(gè)體，解碼得到最優(yōu)車輛路徑

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

針對(duì)新的物流管理理念提出兩階段模型，實(shí)例計(jì)算表明該模型能夠兼顧效率與公平。對(duì)于擁有自己車隊(duì)的物流配送企業(yè)，不論是否擁有多種車型，該兩階段模型仍然適用。但是模型中各項(xiàng)初始參數(shù)的設(shè)定會(huì)影響算法的收斂性、收斂速度和計(jì)算時(shí)間，因此需要通過(guò)在實(shí)際問(wèn)題中進(jìn)行大量的數(shù)值模擬，從中選擇比較理想的參數(shù)搭配，才能最大限度地提升運(yùn)行效率。

[1] 賈永基，谷寒雨，席裕庚.一類貨運(yùn)車輛調(diào)度問(wèn)題的混合禁忌搜索算法[J].信息與控制，2006(33):724-728.

[2] 曹二保，賴明勇，聶凱,等.大規(guī)模物流配送車輛調(diào)度問(wèn)題研究[J].湖南大學(xué)學(xué)報(bào)：自然科學(xué)版，2007,34(12):89.

[3] 張海剛，顧幸生.基于DNA進(jìn)化算法的車輛調(diào)度問(wèn)題[J].華東理工大學(xué)學(xué)報(bào)：自然科學(xué)版，2006,32(12):1464.

[4] 朱永亮，王金妹.物流配送車輛路線求解算法[J].交通運(yùn)輸工程學(xué)報(bào)，2006,6(2):85.

[5] 朱連章，張紅霞.基于著色Petri網(wǎng)的電子商務(wù)工作流建模[J].中國(guó)石油大學(xué)學(xué)報(bào)，2006,30(4):141-144.