孫有望， 宋華駿 （同濟大學 交通運輸工程學院，上海 201804）

0 引 言

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

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

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

1 問題描述和模型構建

1.1 問題描述

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

1.2 模型構建

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

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

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

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

2 算法設計

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

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

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

輸出： （m1,m2,…,mh）和出車總費用z1

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

Step2：對集合 （g1,g2,…,gn）按非遞增次序排序，設排序后結果為集合M

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

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

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

Step7：若M≠φ，則從NT集合中選取第一個元素Csl，若該元素存在，則轉Step8，否則說明原問題無可行解，停止計算

若M=φ，則轉Step9

Step8： 令T=T∪｛sl｝,tempms=tempms+1,tempz1=tempz1+Cs， 轉Step6

Step9：若tempz1≤z1，令z1=tempz1，ms=tempms，否則轉Step10

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

2.2 車輛路徑遺傳算法

2.2.1 遺傳算法編碼設計

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

2.2.2 種群的初始化

產生初始群體的步驟如下：

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

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

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

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

2.2.3 適應函數(shù)值計算

對于算法迭代過程中每代個體的優(yōu)劣通過個體適應函數(shù)值進行評價。對違反約束條件的個體引入懲罰值函數(shù)，以確保那些符合約束條件而較優(yōu)的個體有較大的生存機會。

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

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

2.2.4 選擇

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

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

2.2.5 交叉

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

首先通過隨機函數(shù)產生兩個數(shù)作為交叉點，兩個父個體交叉時，通過選擇父個體1的一部分，然后保存父個體2中的客戶碼的相對順序生成。

例如：對下面兩個父個體，隨機選擇兩個數(shù)（3,9 ）作為交叉點：

首先，將兩個交叉點之間的中間段和第一位的基因碼保留，得到：

然后取f2從第2個交叉點開始的客戶碼排列順序，當?shù)竭_表尾時返回表頭繼續(xù)記錄客戶碼，直到第2個交叉點結束，得到客戶碼排列順序 （0 4 5 0 3 7 8 1 0 62 ）。將o1中擁有的客戶碼從該排列順序中去掉，可得排列順序（7 8 16 ），將這個排列順序復制給o1，復制的起點從第2個交叉點開始，得到交叉后的客戶碼排列順序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 變異

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

2.2.7 算法的實現(xiàn)過程

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

Step2：產生初始種群，計算群體中所有個體的適應函數(shù)值fk，找出適應函數(shù)值最大的染色體

Step3：若k=K，則轉Step6，否則轉Step4

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

Step5：計算子代個體的適應函數(shù)值fk，令k=k+1，轉Step3

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

3 結束語

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

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

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

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

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

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