王榮 檀小璐

摘要：近年來，車輛路徑問題一直作為物流配送領(lǐng)域研究中的熱門話題，由于運(yùn)輸路徑選取的不同，直接決定了物流配送問題中運(yùn)輸成本的差異，企業(yè)的管理者積極尋找著各種有效的配送策略。本文分析了車輛路徑問題的實(shí)際背景，設(shè)計(jì)并實(shí)現(xiàn)了一個(gè)基于遺傳算法的車輛路徑問題的求解方法。

關(guān)鍵詞：遺傳算法；路徑選擇1VRP問題描述

物流配送車輛問題歸納為一般的網(wǎng)絡(luò)模型：設(shè)G=(V，E，A)是一個(gè)連通的混合網(wǎng)絡(luò)，V是頂點(diǎn)集(表示物流公司、客戶等)，E、A分別為無向的邊集和有向的弧集，E中的邊和A中的弧均被賦權(quán)(可以表示配送的距離、時(shí)問或費(fèi)用)，V、E、A分別為V、E、A的子集，求滿足約束條件(包括客戶的貨物需求或供應(yīng)數(shù)量約束、需求或供應(yīng)時(shí)間約束、配送車輛一次配送的最大行駛距離約束、車輛的最大載重約束等)，并包含V、E、A的一些巡回路線，使目標(biāo)函數(shù)取得優(yōu)化，目標(biāo)函數(shù)可以取配送總里程最短、配送車輛總噸位公里數(shù)最少、配送總費(fèi)用最低、配送總時(shí)間最少、使用的配送車輛最少、配送車輛的滿載率最高等。

2VRP問題的界定

一個(gè)物流公司向多個(gè)客戶送貨；物流公司和客戶的位置一定；物流公司運(yùn)送的貨物能夠達(dá)到所有客戶的需求。各個(gè)客戶需求的貨物均可以相互混裝，即可以裝在同一配送車輛內(nèi)；每個(gè)客戶的需求量不超過配送車輛的最大載重量；每個(gè)客戶的送貨要求必須滿足，且僅能一次性完成，不允許分批配送。每臺(tái)車輛的最大載重量一定，不允許超載；配送時(shí)，每臺(tái)車輛都從物流公司出發(fā)，向一些客戶提供配送服務(wù)后，最終返回物流公司。對(duì)于客戶要求將需求貨物送到的時(shí)間，無時(shí)間限制。物流中心與客戶之間以及客戶相互之間的最短距離已知且固定；不考慮運(yùn)輸網(wǎng)絡(luò)中車輛流量的限制。

3VRP問題的數(shù)學(xué)建模

設(shè)配送中心用K輛車對(duì)所有需求點(diǎn)進(jìn)行配送(K的值由算法動(dòng)態(tài)決定)。每個(gè)車的載重為bk(k=1,2,3…K)，每個(gè)需求點(diǎn)的需求量為di(i=1,2,3…L)，L為需求點(diǎn)的個(gè)數(shù)。需求點(diǎn)i到j(luò)的距離為Cij。設(shè)nk為第k輛車要負(fù)責(zé)運(yùn)送的需求點(diǎn)總數(shù)，用集合Rk={rki|0≤i≤nk|}來對(duì)應(yīng)第k輛車要送貨的需求點(diǎn)，rki表示第k輛車要送達(dá)的第i個(gè)需求點(diǎn)，rko表示第k輛車起始點(diǎn)。數(shù)學(xué)建模：

歸結(jié)出有約束條件的最優(yōu)化問題：

上述表達(dá)式中，(1)式為所有需求點(diǎn)都應(yīng)得到配送；不等式(2)為每條路徑的需求量不超過配送車輛的載重量：不等式(3)為每個(gè)車輛對(duì)應(yīng)的需求點(diǎn)總和不大于總的需求點(diǎn)數(shù)；(4)式為每需求點(diǎn)只有一輛車進(jìn)行配送。

4VRP問題的遺傳算法設(shè)計(jì)

從上述模型可知，求解VRP問題的關(guān)鍵是合理確定車輛與各需求點(diǎn)的關(guān)系，在滿足車輛載重和各需求點(diǎn)的約束條件的情況下使得總路徑成本最小，因此可以構(gòu)造以下遺傳算法：

(1)染色體結(jié)構(gòu)編碼二進(jìn)制字符集{0,1}產(chǎn)生通常的0,1字符串來表示問題空間的候選解。用矢量(s1,s2,…sL)表示一個(gè)染色體(也稱個(gè)體)G，其中sj的取值范圍為[1,L]中任一個(gè)自然數(shù)，sj表示第j個(gè)被考慮的需求點(diǎn)。每個(gè)染色體G是1到L之間L個(gè)不重復(fù)自然數(shù)的一組隨機(jī)排列。隨機(jī)產(chǎn)生這樣一組染色體Gm(m=1,2,…,M)(其中M為一代種群中的個(gè)體數(shù))，構(gòu)成初始種群。

(2)可行化過程 將染色體的編碼向量映射為滿足全部約束條件的可行解的過程稱為可行化。在VRP問題中，可行化就是將編碼的個(gè)體映射為一組可行的路徑選擇方案。過程設(shè)計(jì)如下：

(a)令車輛的初始剩余裝載量

(b)考慮第j個(gè)基因sj對(duì)應(yīng)的需求點(diǎn)，令k=1即從第一輛車開始考慮；

(c)若sj對(duì)應(yīng)的需求點(diǎn)的待運(yùn)貨物重量 ，則令；如果 ，則令K=k；否則K不變，轉(zhuǎn)5；如果 ，轉(zhuǎn)(d)。

(d)令k=k+1，即考慮下一輛車是否能裝載，轉(zhuǎn)(c)。

(e)令j=j+1，即考慮下一個(gè)需求點(diǎn)，轉(zhuǎn)(b)，重復(fù)上面的過程，直到j(luò)=L。

(f)此時(shí)K記錄了所用車輛總數(shù)，即路徑總數(shù)，Rk包含了第k條路徑中依次配送的需求點(diǎn)，即Rk(k=1,2,…K)記錄了一組可行的路徑。

(3)適應(yīng)度分析 初始種群形成以后，霈要通過種群的適應(yīng)度函數(shù)，對(duì)種群中的每個(gè)染色體進(jìn)行評(píng)價(jià)，并以此為標(biāo)準(zhǔn)選擇最優(yōu)解。對(duì)某一代種群中每個(gè)染色體Gh(s1,s2,…sL)，將可行化路徑帶入目標(biāo)函數(shù)：

將得到該個(gè)體對(duì)應(yīng)的路徑代價(jià)。路徑代價(jià)越小，表示該染色體越優(yōu)。令Gh的適應(yīng)度函數(shù)為fk=1/Zh，fk表示染色體在生命競(jìng)爭(zhēng)中的能力，fk越大對(duì)應(yīng)的個(gè)體越接近最優(yōu)解。

(4)判斷停止條件 當(dāng)?shù)阉鞯拇螖?shù)滿足要求的代數(shù)N，則停止，選出該代種群中適應(yīng)度最優(yōu)的個(gè)體，將其對(duì)應(yīng)的可行路徑集合作為該VRP問題的優(yōu)化解輸出；反之，繼續(xù)進(jìn)行(5)。

(5)自然選擇 將一代種群中M個(gè)個(gè)體按適應(yīng)度fk由大到小排列。排在最先的直接進(jìn)入下一代，而下代中另外M-1個(gè)個(gè)體從前代種群M個(gè)染色體中采用輪轉(zhuǎn)法選取，即按以下概率選擇個(gè)體Gh進(jìn)入下一代： ，其中， 共選擇M-1次。用輪轉(zhuǎn)選擇法，既保證了最優(yōu)個(gè)體進(jìn)入下一代，又避免個(gè)體間因適應(yīng)度大小不同而被選擇進(jìn)入下一代機(jī)會(huì)相差懸殊，保證了下一代的多樣性并提高了算法的收斂速度。

(6)交叉操作 交叉概率PC控制著交叉操作被使用的頻度。交叉概率PC在0.6--0.8之間時(shí)，進(jìn)化性能較好，選擇交叉概率為 PC=0.7，并引入一種新穎的交叉算子，這種交叉算子的最大特點(diǎn)是當(dāng)兩父代相同時(shí)，仍能產(chǎn)生全新的兩個(gè)個(gè)體，這就減弱了對(duì)群體多樣性的要求，能夠有效避免傳統(tǒng)遺傳算法“早熟收斂”的缺點(diǎn)。

任意選取兩個(gè)互不相同的個(gè)體A和B，設(shè)每個(gè)染色體含有n個(gè)基因，隨機(jī)產(chǎn)生1--n之間的兩個(gè)不等的整數(shù)S和 ，將染色體A和B同樣分成三個(gè)部分，其中1→s-1為第一部分，s→ι為第二部分，ι+1→n為第三部分。將A的第三部分移到B的個(gè)體首部，并除去B中相同的基因，得到新的個(gè)體B'；同時(shí)將原B中的第一部分移到A的尾部，并將于A中相同的基因除去，便得到一個(gè)新的個(gè)體A'。交叉后分別計(jì)算個(gè)體A'、B'和A、B的適應(yīng)度，選取適應(yīng)度最大的兩個(gè)個(gè)體進(jìn)入下一代。采用新的交叉算子，當(dāng)個(gè)體都相同時(shí)仍能夠進(jìn)行迭代進(jìn)化，繼續(xù)尋找問題的最優(yōu)解，避免陷入局部最優(yōu)解，克服了“早熟收斂”的缺點(diǎn)。

(7)變異操作 主要目的是維持解群體的多樣性。低頻度的變異可防止群體中重要的、單一基因的可能丟失，高頻度的變異將使遺傳算法趨于純粹的隨機(jī)搜索。變異概率Pm為0.02左右。變異策略是隨機(jī)變換選中的一個(gè)染色體中任意兩個(gè)基因值。對(duì)變異后的個(gè)體產(chǎn)生對(duì)應(yīng)的可行路徑并計(jì)算適應(yīng)度，將其適應(yīng)度與變異前個(gè)體進(jìn)行比較，擇優(yōu)進(jìn)入下一代。返回(3)、(4)步重復(fù)以上循環(huán)，直到滿足終止條件。

根據(jù)上一節(jié)對(duì)VRP問題遺傳算法的設(shè)計(jì)，對(duì)實(shí)現(xiàn)的各個(gè)步驟進(jìn)行抽象提取，共構(gòu)造了12個(gè)函數(shù)，包括：newcode()(生成隨機(jī)個(gè)體)、initGA()(產(chǎn)生初始種群)、avFitness()(平均適應(yīng)度函數(shù))、natureChek()(自然選擇函數(shù))、crossover()(交叉操作)、mutation()(變異操作)等等，使用純java編寫代碼，完成了設(shè)計(jì)的每一步操作函數(shù)。為了減少系統(tǒng)中的耦合性，在實(shí)現(xiàn)中采用EJB對(duì)路徑選擇算法進(jìn)行模塊封裝，該模塊封裝了多個(gè)函數(shù)的調(diào)用關(guān)系，留給客戶的只有一個(gè)輸入接口，客戶可以通過用戶界面對(duì)系統(tǒng)參數(shù)進(jìn)行設(shè)置，包括：種群大小M、遺傳搜索的代數(shù)N、變異概率Pm，交叉概率Pc等，確認(rèn)輸入后，系統(tǒng)開始對(duì)用戶選擇的訂單(含配送要求)進(jìn)行處理，并自動(dòng)讀取數(shù)據(jù)庫中的路徑關(guān)系表，最后得出一個(gè)優(yōu)化后的配送方案。

[參考文獻(xiàn)]

[1]李敏強(qiáng).遺傳算法的基本理論與應(yīng)用[M].科學(xué)出版社,2002.