基于遺傳算法的貨運路徑規劃系統研究

曹曉燕 孫穎 王辰

（1.南京工業職業技術大學計算機與軟件學院 江蘇省南京市 210023 2.南京工程學院電力工程學院 江蘇省南京市 211167）

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

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

本文研究一種基于遺傳算法的貨運車輛路徑規劃軟件系統。以實際貨運過程中車輛路徑規劃的需求為分析對象，構建車輛路徑規劃的數學模型；然后以綜合成本最低為核心目標，使用遺傳算法得到貨運的最佳路徑；最后以研究的基于遺傳算法的車輛路徑規劃模型為基礎，設計開發貨運路徑規劃系統。本文開發的貨運規劃系統對提高大型貨場的貨運效率、降低貨運成本等有現實意義。

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

1.1 貨運路徑規劃問題建模研究

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

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

Fc 為載重限制函數，則Fc 表達式為：

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

因此，貨運車輛路徑規劃問題的目標就是要找到一個滿足條件的USk序列使得Fd 的值最小，貨運路徑規劃問題就轉換為了多目標優化問題。

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

根據以上構建的貨運路徑規劃的模型，使用遺傳算法能夠對其進行有效求解，基于遺傳算法的貨運路徑規劃求解過程描述如圖1所示。

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

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

Step1:染色體編碼

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

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

Step2:構建適應度函數

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

Step3:交叉產生新的種群

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

Step4:選擇最優種群

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

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

在區間[0,1]上選擇一個隨機數r，分別計算后進行比較，如果此時Pk-1

2 貨運路徑規劃系統的設計與實現

本文以構建的基于遺傳算法的貨運路徑規劃模型為核心，設計了貨運路徑規劃管理系統，系統由服務器端和安卓客戶端組成，通過json 傳遞數據進行實時通信。系統的設計原理如圖2所示。

圖2：貨運路徑規劃系統原理示意圖

服務器端主要實現了系統管理、用戶管理、貨運任務分配管理和貨運車輛路徑規劃管理等功能，以mysql 為后臺數據庫，使用python django 框架開發實現。其中系統管理功能主要實現系統基本參數的設置以及系統運行日志的管理；用戶管理功能主要實現用戶注冊信息審核、用戶權限的管理以及用戶的增刪改查等功能；貨運任務分配管理主要實現車輛信息管理、貨物信息管理、貨運目標地信息管理等功能，為貨運路徑規劃提供基礎數據信息；貨運車輛路徑規劃管理主要是以貨運數據信息為基礎，利用遺傳算法實現最優路徑的求解，并向安卓端提供訪問接口。

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

系統服務器端和客戶端通過json 實現貨運路徑等數據的傳遞，由安卓客戶端通過retrofit 向服務器端發起網絡請求，服務器端根據請求內容進行路徑規劃操作，并將處理結果以json 數據的形式返回，安卓客戶端接收到數據后將其解析成bean，并將數據更新到安卓端的界面上進行操作。

3 結論

針對同一貨源地、多貨運車輛、多目標地的貨運車輛路徑規劃問題，本文研究了基于遺傳算法的貨運路徑規劃策略，設計實現了車輛路徑規劃軟件系統，提高了大型貨場貨物運送過程中效率低下、路徑規劃固定不能實時動態調整等問題。接下來將以現有研究為基礎，對現有遺傳算法的性能進行優化，并進一步完善系統，提高貨運路徑規劃系統的性能及拓展系統的廣泛適用性。