基于遺傳算法的配送車輛路徑規(guī)劃

郭秀紅

(長(zhǎng)春職業(yè)技術(shù)學(xué)院 汽車分院，長(zhǎng)春 130033)

城市配送系統(tǒng)(city delivery system，CDS)的發(fā)展是一個(gè)城市提高其公共運(yùn)輸能力的關(guān)鍵。目前國(guó)內(nèi)外許多學(xué)者對(duì)CDS 系統(tǒng)進(jìn)行了深入研究［1-4］。其中，車輛路徑優(yōu)化問(wèn)題是城市配送系統(tǒng)中的重要環(huán)節(jié)，通過(guò)對(duì)車輛行駛路徑的優(yōu)化管理可以有效地降低城市配送成本，同時(shí)可以提高城市交通效率，節(jié)省公共資源，無(wú)論對(duì)企業(yè)還是對(duì)社會(huì)，都具有重要的意義。本文針CDS 的車輛路徑規(guī)劃問(wèn)題，采用遺傳算法(genetic algorithm，GA)作為優(yōu)化方法，提出一種配送車輛路徑規(guī)劃的設(shè)計(jì)方案，以實(shí)現(xiàn)車輛路徑選取的最優(yōu)決策。

1 配送車輛路徑規(guī)劃

1.1 城市配送系統(tǒng)

城市配送系統(tǒng)的功能構(gòu)架如圖1 所示。城市配送系統(tǒng)是聯(lián)系供應(yīng)商、信息中心、倉(cāng)庫(kù)和消費(fèi)者之間的重要紐帶。

城市配送系統(tǒng)的主要構(gòu)成如圖2 所示，其中城市配送網(wǎng)絡(luò)子系統(tǒng)負(fù)責(zé)監(jiān)管城市交通信息，城市配送運(yùn)營(yíng)調(diào)度系統(tǒng)負(fù)責(zé)對(duì)配送車輛進(jìn)行調(diào)度，城市配送監(jiān)管系統(tǒng)負(fù)責(zé)對(duì)配送車輛的任務(wù)執(zhí)行情況進(jìn)行監(jiān)督管理和實(shí)時(shí)糾錯(cuò)，城市配送信息處理系統(tǒng)負(fù)責(zé)對(duì)相關(guān)信息進(jìn)行實(shí)時(shí)分析和處理。GDS 系統(tǒng)中較為關(guān)鍵的問(wèn)題是在上述職能范圍內(nèi)，如何構(gòu)建一個(gè)最優(yōu)運(yùn)行框架來(lái)實(shí)現(xiàn)最優(yōu)化的配送效益。

圖1 配送系統(tǒng)功能構(gòu)架

圖2 城市配送系統(tǒng)的組成

1.2 車輛路徑優(yōu)化的意義

車輛路徑規(guī)劃(vehicle routing problem，VRP)自從1959年被Dantzig 和Ramse 提出的之后，迅速引起各領(lǐng)域工程師和管理學(xué)者的極大重視，成為工程管理領(lǐng)域的重點(diǎn)和熱點(diǎn)問(wèn)題［1-3］。

VRP 問(wèn)題是城市配送系統(tǒng)的主要優(yōu)化問(wèn)題之一，在城市配送系統(tǒng)中具有重要的意義。從企業(yè)運(yùn)作和社會(huì)環(huán)保、節(jié)能的角度而言，VRP 研究的研究意義具體可以概括為以下方面:

1)通過(guò)對(duì)配送路線的合理優(yōu)化，可以有效提高配送效率，從而縮短配送時(shí)間，提高服務(wù)質(zhì)量和客戶滿意度;

2)通過(guò)對(duì)配送路線的合理優(yōu)化，可以有效地降低運(yùn)輸成本，節(jié)省資金;

3)有通過(guò)對(duì)配送路線的合理優(yōu)化，可以有效降低車輛占用公路的時(shí)間，從而可以緩解交通，減少噪聲、尾氣排放等運(yùn)輸污染。

2 VRP 問(wèn)題的數(shù)學(xué)描述

為了便于研究VRP 問(wèn)題的優(yōu)化策略，首先對(duì)VRP 問(wèn)題進(jìn)行數(shù)學(xué)描述。假設(shè)配送中心和倉(cāng)庫(kù)的地理位置均為固定且已知，則倉(cāng)庫(kù)與配送中心以及倉(cāng)庫(kù)間的位置信息可以由路徑距離矩陣描述為

VRP 可行解可以描述為一系列行駛路徑的決策的集合，即

其中，ki表示第i 條路段決策結(jié)果。

VRP 優(yōu)化目標(biāo)由成本最小化來(lái)描述，即運(yùn)輸過(guò)程中所產(chǎn)生的固定成本和運(yùn)輸費(fèi)用，如式(3)所示。

其中:TV為配送車輛在運(yùn)輸過(guò)程中的總成本;Ns為運(yùn)輸途中的固定費(fèi)用;ξ(ki)為在第ki路段上的花費(fèi)，正比于ki路段的行駛里程，計(jì)算式為

其中:d(·)為距離運(yùn)算符;Ks為單位里程所需的費(fèi)用;AK為倉(cāng)庫(kù)節(jié)點(diǎn)標(biāo)號(hào)。

考慮到在實(shí)際配送過(guò)程中有許多的條件限制，因此在目標(biāo)函數(shù)上施加一定的約束條件，主要包括:車輛配送過(guò)程中所攜帶的貨物量存在上限，且車輛完成配送任務(wù)之后須返回出發(fā)點(diǎn)以備下次配送任務(wù)。

其中:Qmax為配送車輛承重上限;q(·)為載運(yùn)重量計(jì)算符;u 為平均車速;T 為配送任務(wù)所要求的最大時(shí)間限度。

3 VRP 問(wèn)題的遺傳算法優(yōu)化

結(jié)合上述模型，基于遺傳算法來(lái)解決所提出的VRP 問(wèn)題，基本參數(shù)設(shè)定為:種群M 為20，最大代數(shù)G 為100，交叉概率Pc 為0.8，變異概率Pm 為0.1，首先對(duì)VRP 問(wèn)題的可行解進(jìn)行編碼并生產(chǎn)初始種群，整個(gè)算法實(shí)施步驟如圖3 所示。根據(jù)目標(biāo)函數(shù)設(shè)計(jì)適配度，終止條件設(shè)計(jì)為:

1)當(dāng)最優(yōu)解連續(xù)5 代不發(fā)生變化;

2)當(dāng)?shù)綌?shù)超過(guò)300 步。

對(duì)于初始種群根據(jù)數(shù)學(xué)模型的輸入條件，進(jìn)行適配度計(jì)算并根據(jù)適配度計(jì)算結(jié)果進(jìn)行種群選擇操作。

3.1 編碼規(guī)則

根據(jù)VRP 問(wèn)題的特點(diǎn)，本文采用浮點(diǎn)數(shù)編碼方案，首先將各個(gè)倉(cāng)庫(kù)的節(jié)點(diǎn)數(shù)轉(zhuǎn)換為相對(duì)應(yīng)的隨機(jī)浮點(diǎn)數(shù)，同時(shí)將送貨中心(即配送過(guò)程的起點(diǎn))作為第一個(gè)浮點(diǎn)數(shù)，考慮到編程的方便，將送貨中心同時(shí)作為終點(diǎn)放入到最后一個(gè)浮點(diǎn)數(shù)，計(jì)算式為

其中:s0為生產(chǎn)中心所對(duì)應(yīng)的浮點(diǎn)數(shù);s1～sn為n 個(gè)倉(cāng)庫(kù)所對(duì)應(yīng)的浮點(diǎn)數(shù)。

越小的浮點(diǎn)數(shù)對(duì)應(yīng)有越高的優(yōu)先級(jí)，例如對(duì)于染色體

其對(duì)應(yīng)的表現(xiàn)型為

起點(diǎn)s0至為0.01，終點(diǎn)sn+1置為0.99，起點(diǎn)與終點(diǎn)參與編程，但不參與到選擇、交叉與變異。

圖3 基于遺傳算法的算法流程

3.2 適配度函數(shù)

根據(jù)上述編碼規(guī)則，對(duì)每一個(gè)可行解都可以計(jì)算出整個(gè)配送過(guò)程中的行駛路線，將行駛總距離作為適配度函數(shù)其中χs表示第s 個(gè)可行解的適配度。

3.3 遺傳算子設(shè)計(jì)

在上述基礎(chǔ)上對(duì)遺傳算法進(jìn)行選擇算子、交叉算子和變異算子的設(shè)計(jì)。

1)選擇算子

對(duì)種群中的20 個(gè)可行解根據(jù)適配度值來(lái)選擇排序靠前的10 個(gè)染色體作為選擇結(jié)果，放入后代中繼續(xù)后續(xù)操作。

2)交叉算子

對(duì)于選定的兩個(gè)父代個(gè)體，隨機(jī)選擇一個(gè)交叉位置，將其中一個(gè)父代中的前t 個(gè)基因作為子代個(gè)體的前t 個(gè)基因，同時(shí)將第2 個(gè)父輩染色體X2 的后n -t 個(gè)基因取出作為子代的后n-t 個(gè)基因，如圖4 所示。

圖4 交叉操作示意圖

3)變異算子

首選按照變異概率來(lái)決定發(fā)生變異的位，然后變異操作采用取逆算子

4 優(yōu)化結(jié)果及分析

結(jié)合上述遺傳算法設(shè)計(jì)方案，在Matlab 環(huán)境中采用謝菲爾德GA 工具箱函數(shù)來(lái)進(jìn)行算法實(shí)現(xiàn)，選擇算子采用select函數(shù)，交叉算子采用xovshrs 函數(shù)，變異算子采用mutate 函數(shù)，經(jīng)過(guò)37 次迭代后算法收斂至最優(yōu)解。

對(duì)應(yīng)的表現(xiàn)型，即最優(yōu)配送路徑為

將算法隨機(jī)生成的初始解對(duì)應(yīng)的配送路徑與最優(yōu)解所決定的規(guī)劃方案繪制成有向圖，如圖5 ～6 所示，從結(jié)果可以看出，可以有效完成配送路線的尋優(yōu)任務(wù)，共節(jié)約行駛里程20 km。

圖5 算法隨機(jī)生成的初始路徑

圖6 基于遺傳算法所確定的最優(yōu)路徑

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

1)遺傳算法非常適合用于解決城市配送系統(tǒng)中的VRP問(wèn)題，可以有效完成配送路線的尋優(yōu)任務(wù)，從而降低配送過(guò)程中的運(yùn)輸費(fèi)用;

2)采用浮點(diǎn)數(shù)編碼并使用數(shù)值大小作為優(yōu)先級(jí)決策的GA 算法設(shè)計(jì)方法正確有效，計(jì)算所得的最優(yōu)路徑與初始路徑方案相比，節(jié)約行駛里程20 km。

［1］曹進(jìn).物流配送優(yōu)化與跟蹤研究及系統(tǒng)實(shí)現(xiàn)［D］.哈爾濱:哈爾濱工業(yè)大學(xué)，2006.

［2］李冬梅. 物流配送車輛優(yōu)化調(diào)度方法的研究與實(shí)現(xiàn)［D］.沈陽(yáng):沈陽(yáng)工業(yè)大學(xué)，2007.

［3］Montemanni R，Gambardella L M，Rizzoli A E，et al. Ant Colony System for a Dynamic Vehicle Routing Problem［J］.Journal of Combinatorial Optimization，2005(4):327-343.

［4］張丹羽.現(xiàn)代物流配送中心車輛線路優(yōu)化方案研究與應(yīng)用［D］.濟(jì)南:山東大學(xué)，2005.