基于遺傳算法的貨運路徑規(guī)劃系統(tǒng)研究

曹曉燕 孫穎 王辰

（1.南京工業(yè)職業(yè)技術(shù)大學(xué)計算機與軟件學(xué)院 江蘇省南京市 210023 2.南京工程學(xué)院電力工程學(xué)院 江蘇省南京市 211167）

貨運路徑規(guī)劃問題指的是貨運車輛由貨源地出發(fā)向一個或多個客戶目的地運輸貨物并在貨運結(jié)束后最終返回貨源地的過程中最優(yōu)路徑確定問題[1-2]，其中多車輛、多目標(biāo)地的貨運路徑規(guī)劃是大型貨場貨物運輸重點關(guān)注的問題。在現(xiàn)代物流系統(tǒng)中，貨運車輛最優(yōu)路徑的規(guī)劃往往需要在綜合考慮時間、距離等因素的基礎(chǔ)上以貨運成本最低為核心目標(biāo)[3]，其本質(zhì)可以抽象為一個多目標(biāo)優(yōu)化問題。因此，如何在最短時間內(nèi)以最低的成本實現(xiàn)多目的地的高效貨運，是當(dāng)前大型貨場貨運車輛路徑規(guī)劃研究的熱點問題。

近年來，智能優(yōu)化算法被廣泛應(yīng)用于貨運車輛的路徑規(guī)劃問題求解中[4]。遺傳算法起源于上世紀(jì)六十年代初期，是一種基于自然界遺傳和進(jìn)化機理而提出的計算模型，它通過模擬自然生物進(jìn)化過程中染色體的交叉、變異等來搜索現(xiàn)實工程難題中的最優(yōu)解[5-6]。與常見的優(yōu)化算法相比，遺傳算法在解決搜索問題時可以同時對空間中的多個解進(jìn)行綜合評估、陷入局部最優(yōu)的可能性較低、易于并行化的實現(xiàn)，其具有尋優(yōu)效率高、結(jié)果相對精確等優(yōu)點，在工程中被廣泛應(yīng)用。因此，本文研究基于遺傳算法的大型貨場多車輛、多目的貨運中的車輛路徑規(guī)劃問題具有重要意義。

本文研究一種基于遺傳算法的貨運車輛路徑規(guī)劃軟件系統(tǒng)。以實際貨運過程中車輛路徑規(guī)劃的需求為分析對象，構(gòu)建車輛路徑規(guī)劃的數(shù)學(xué)模型；然后以綜合成本最低為核心目標(biāo)，使用遺傳算法得到貨運的最佳路徑；最后以研究的基于遺傳算法的車輛路徑規(guī)劃模型為基礎(chǔ)，設(shè)計開發(fā)貨運路徑規(guī)劃系統(tǒng)。本文開發(fā)的貨運規(guī)劃系統(tǒng)對提高大型貨場的貨運效率、降低貨運成本等有現(xiàn)實意義。

1 基于遺傳算法的貨運路徑規(guī)劃模型

1.1 貨運路徑規(guī)劃問題建模研究

大型貨場貨物的運輸往往是單貨源地、多車輛、多目的地的貨物貨運問題。貨運過程中通常無需考慮用戶的取貨時間，從同一貨源地派出多臺貨運車輛向多個目標(biāo)點貨運貨物，車輛貨物貨運過程中目標(biāo)地址和每個目標(biāo)地的貨物需求量明確、所派出貨運車型的載重量及車輛性能參數(shù)等已知。在貨物貨運路徑規(guī)劃過程中，需要保證每個目標(biāo)地的需求均能得到滿足，而且所有目標(biāo)地的獲取需求總量不得超過規(guī)定時間內(nèi)車輛總貨運總量的上限[7-8]。因此，貨運車輛路徑規(guī)劃問題的數(shù)學(xué)模型可以描述如下：

假設(shè)C 表示貨運派出的車輛集合，k 表示車輛序號，Mk表示派出車輛集合中每輛車每行駛一公里的成本集合，Wk表示車輛的載重量集合，P 表示貨運目標(biāo)地點的集合，集合中的第一個元素P0表示貨源地，D 表示距離集合，D(i，j) 為目標(biāo)地點i 到目標(biāo)地點j的距離，PWk為每個目標(biāo)地點的貨物需求量，Sk表示具體的路徑。Fd 表示貨運成本函數(shù)，根據(jù)以上描述Fd 表達(dá)式為：

Fc 為載重限制函數(shù)，則Fc 表達(dá)式為：

根據(jù)以上分析的貨運路徑規(guī)劃的具體需求，貨運路徑規(guī)劃的約束條件為：

因此，貨運車輛路徑規(guī)劃問題的目標(biāo)就是要找到一個滿足條件的USk序列使得Fd 的值最小，貨運路徑規(guī)劃問題就轉(zhuǎn)換為了多目標(biāo)優(yōu)化問題。

1.2 基于遺傳算法的貨運規(guī)劃路徑求解

根據(jù)以上構(gòu)建的貨運路徑規(guī)劃的模型，使用遺傳算法能夠?qū)ζ溥M(jìn)行有效求解，基于遺傳算法的貨運路徑規(guī)劃求解過程描述如圖1所示。

圖1：基于遺傳算法的貨運路徑求解流程圖

如圖1所示的基于遺傳算法的貨運車輛路徑規(guī)劃問題的求解過程可以描述如下：

Step1:染色體編碼

應(yīng)用遺傳算法對貨運路徑規(guī)劃模型求解時首先需要確定染色體的編碼，考慮到同時可能存在多個貨運目的地，且各目的地之間具有同等優(yōu)先級，因此使用直排列的算法對染色體進(jìn)行編碼。

在編碼過程中將貨源地和目標(biāo)地址統(tǒng)一進(jìn)行編碼，其中目標(biāo)地編號設(shè)置為1 ～N，貨源地編號設(shè)置為0，則目標(biāo)地進(jìn)序列即為一條染色體。解碼過程中則以貨運車輛及其性能參數(shù)為依據(jù)，從前往后對編碼后的染色體進(jìn)行遍歷，逐個判斷當(dāng)前車輛的載貨量、里程數(shù)等是否能夠滿足目標(biāo)地址的實際需求，能夠滿足則車輛與目標(biāo)地址進(jìn)行匹配，否則就輪替到下一貨運車輛繼續(xù)進(jìn)行判別，直至所有目標(biāo)地的貨運目標(biāo)均大道為止。在逐個匹配的過程中，當(dāng)某一貨運車輛當(dāng)前運力仍有剩余時，則調(diào)配該貨運車輛回到貨源地后重新進(jìn)行分配，此時在染色體解碼過程中增加標(biāo)志位，有效避免車輛給運力的浪費。

Step2:構(gòu)建適應(yīng)度函數(shù)

適應(yīng)度函數(shù)決定了當(dāng)前所迭代規(guī)劃方案的優(yōu)劣程度，是貨運車輛最優(yōu)方案遴選的直接依據(jù)。根據(jù)貨運路徑規(guī)劃問題的最終目標(biāo)，在適應(yīng)度函數(shù)構(gòu)建過程中需要緊密結(jié)合貨運的成本，貨運綜合成本越低的規(guī)劃方案其被優(yōu)選的可能性越大。結(jié)合貨運規(guī)劃的實際需求，假設(shè)遺傳算法迭代求解過程中，第i 個規(guī)劃方案的貨運花費為Ei，適應(yīng)度函數(shù)為Fi，則基于遺傳算法的求解模型其適應(yīng)度函數(shù)Fi的表達(dá)式可以描述如下：

Step3:交叉產(chǎn)生新的種群

在貨運車輛遺傳進(jìn)行過程中，利用父母種群中染色體的交叉重新進(jìn)行組合，以此不斷產(chǎn)生新的種群。根據(jù)直排列染色體編碼方式的特點，使用染色體兩點交叉的方式產(chǎn)生新的種群。染色體交叉的過程中，首先以兩條父染色體為對象，在染色體上隨機生成兩個點位k1和k2，然后以該兩個點位為交叉點產(chǎn)生新的染色體，新的染色體以第一條染色體的k1前的部分為前半段，以k2后的部分為后半段，以此保證種群的更新。

Step4:選擇最優(yōu)種群

在進(jìn)行最優(yōu)貨運方案選擇過程中，新的種群不斷產(chǎn)生，進(jìn)化有可能陷入局部最優(yōu)，此時不能保證貨運方案的最優(yōu)。因此，應(yīng)該充分利用遺傳算法的變異原理，在同一染色體上隨機找到兩種不同的基因片段，交換其實際值，通過變異操作擾動當(dāng)前的迭代過程，產(chǎn)生新的種群。在最優(yōu)種群選擇過程中，以適應(yīng)度函數(shù)為主要依據(jù)，假設(shè)第i 個種群可以保留的概率為fi，那么fi可以用公式表示如下：

以經(jīng)典的輪盤賭注法為基本原理，設(shè)Pi為第i 個種群的累積概率，則Pi可以用公式表示如下：

在區(qū)間[0,1]上選擇一個隨機數(shù)r，分別計算后進(jìn)行比較，如果此時Pk-1

2 貨運路徑規(guī)劃系統(tǒng)的設(shè)計與實現(xiàn)

本文以構(gòu)建的基于遺傳算法的貨運路徑規(guī)劃模型為核心，設(shè)計了貨運路徑規(guī)劃管理系統(tǒng)，系統(tǒng)由服務(wù)器端和安卓客戶端組成，通過json 傳遞數(shù)據(jù)進(jìn)行實時通信。系統(tǒng)的設(shè)計原理如圖2所示。

圖2：貨運路徑規(guī)劃系統(tǒng)原理示意圖

服務(wù)器端主要實現(xiàn)了系統(tǒng)管理、用戶管理、貨運任務(wù)分配管理和貨運車輛路徑規(guī)劃管理等功能，以mysql 為后臺數(shù)據(jù)庫，使用python django 框架開發(fā)實現(xiàn)。其中系統(tǒng)管理功能主要實現(xiàn)系統(tǒng)基本參數(shù)的設(shè)置以及系統(tǒng)運行日志的管理；用戶管理功能主要實現(xiàn)用戶注冊信息審核、用戶權(quán)限的管理以及用戶的增刪改查等功能；貨運任務(wù)分配管理主要實現(xiàn)車輛信息管理、貨物信息管理、貨運目標(biāo)地信息管理等功能，為貨運路徑規(guī)劃提供基礎(chǔ)數(shù)據(jù)信息；貨運車輛路徑規(guī)劃管理主要是以貨運數(shù)據(jù)信息為基礎(chǔ)，利用遺傳算法實現(xiàn)最優(yōu)路徑的求解，并向安卓端提供訪問接口。

安卓客戶端主要實現(xiàn)了用戶信息管理、當(dāng)前位置查看、貨運任務(wù)信息查看、貨運路徑導(dǎo)航等功能。使用retrofit 網(wǎng)絡(luò)請求框架和rxjava 框架異步框架設(shè)計實現(xiàn)，通過百度地圖實現(xiàn)定位和導(dǎo)航功能。其中用戶信息管理主要實現(xiàn)貨運工作人員個人信息的管理與維護(hù)功能；當(dāng)前位置查看主要實現(xiàn)當(dāng)前位置信息的獲取及發(fā)送等功能；貨運任務(wù)信息查看主要實現(xiàn)當(dāng)前用戶通過與服務(wù)器端的通信獲取貨運任務(wù)及最優(yōu)路徑信息，并可以查看參與貨運的列表信息及貨運詳情信息的瀏覽；貨運路徑導(dǎo)航主要通過百度地圖實現(xiàn)目標(biāo)點地址的路徑導(dǎo)航以及路況信息的查看等。

系統(tǒng)服務(wù)器端和客戶端通過json 實現(xiàn)貨運路徑等數(shù)據(jù)的傳遞，由安卓客戶端通過retrofit 向服務(wù)器端發(fā)起網(wǎng)絡(luò)請求，服務(wù)器端根據(jù)請求內(nèi)容進(jìn)行路徑規(guī)劃操作，并將處理結(jié)果以json 數(shù)據(jù)的形式返回，安卓客戶端接收到數(shù)據(jù)后將其解析成bean，并將數(shù)據(jù)更新到安卓端的界面上進(jìn)行操作。

3 結(jié)論

針對同一貨源地、多貨運車輛、多目標(biāo)地的貨運車輛路徑規(guī)劃問題，本文研究了基于遺傳算法的貨運路徑規(guī)劃策略，設(shè)計實現(xiàn)了車輛路徑規(guī)劃軟件系統(tǒng)，提高了大型貨場貨物運送過程中效率低下、路徑規(guī)劃固定不能實時動態(tài)調(diào)整等問題。接下來將以現(xiàn)有研究為基礎(chǔ)，對現(xiàn)有遺傳算法的性能進(jìn)行優(yōu)化，并進(jìn)一步完善系統(tǒng)，提高貨運路徑規(guī)劃系統(tǒng)的性能及拓展系統(tǒng)的廣泛適用性。