郭秀紅

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

其中:d(·)為距離運算符;Ks為單位里程所需的費用;AK為倉庫節(jié)點標(biāo)號。

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

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

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

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

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

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

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

3.1 編碼規(guī)則

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

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

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

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

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

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

3.2 適配度函數(shù)

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

3.3 遺傳算子設(shè)計

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

1)選擇算子

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

2)交叉算子

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

圖4 交叉操作示意圖

3)變異算子

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

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

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

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

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

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

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

5 結(jié)束語

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

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

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

［2］李冬梅. 物流配送車輛優(yōu)化調(diào)度方法的研究與實現(xiàn)［D］.沈陽:沈陽工業(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.