劉慶華 汪 晶

（江蘇科技大學計算機學院 鎮(zhèn)江 212000）

1 引言

隨著經(jīng)濟和科學技術的快速發(fā)展，現(xiàn)實生活中車輛的普及率越來越高，汽車私人擁有量也急劇增加。而這些都使得出行者迫切需要正確的出行路徑，因此路線規(guī)劃問題成為了廣大國內(nèi)外學者研究的一項重要課題［1～3］。近些年來，國內(nèi)外許多學者對路徑規(guī)劃問題進行了大量的研究，這些研究主要集中在理論及算法領域方面，其中旅游業(yè)和物流業(yè)等行業(yè)中合理的路線規(guī)劃能夠為商家節(jié)約成本，創(chuàng)造更高的價值［4～6］。

在國外汽車行業(yè)相對于國內(nèi)較為發(fā)達，所以早在1959年Dantzig和 Ramser等［7］首次提出了物流配送路徑優(yōu)化問題，之后便引起了計算機應用等諸多領域的研究者們的高度重視，并很快成為了組合優(yōu)化領域和運籌學的研究熱點及前沿問題。從而使得各個領域學者們對上述問題進行了大量的資料查找、理論研究和實驗分析，并獲得了較大的進步和成果。20世紀末Dorigo M等［8］在他們的論文中提出了蟻群系統(tǒng)（ACS），一種應用于旅行商問題（TSP）的分布式算法，也就是通過ACS算法研究路徑規(guī)劃問題，在文中他們通過ACS算法和模擬退火算法等進行比較結果表明ACS算法理論上更好地解決了TSP問題。Juyoung等［9］在他們的研究中針對大型貨柜在建筑工地及購物區(qū)堆積大量的垃圾，提出了一種滾動式廢物收集車輛路徑優(yōu)化問題。Mahmoudi M等［10］提出了基于時空交通網(wǎng)絡中車輛承載狀態(tài)集成的VRPPDTW時間離散多商品網(wǎng)絡流模型，通過時間窗口（VRPPDTW）解決了一類復雜的車輛路線問題。在國內(nèi)，張維澤等［11］建立了帶約束條件的物流配送問題的數(shù)學模型，運用蟻群算法解決物流配送路徑優(yōu)化問題，同時將遺傳算法的復制、交叉和變異等遺傳算子引入蟻群算法，以提高算法的收斂速度和全局搜索能力。程碧榮［12］等針對救援關鍵期內(nèi)應急物資可能供應不足的特點，考慮適當?shù)膬?yōu)化目標，建立了隨機需求環(huán)境下應急物流車輛路徑問題的優(yōu)化模型，并基于遺傳算法設計了模型的求解方法。

對于車輛路徑優(yōu)化問題，絕大多數(shù)研究者們在眾多的仿真實驗案例中都是采用道路節(jié)點之間的線性距離之和最短作為最優(yōu)解，但是在實際的道路節(jié)點之間會存在諸多因素導致與節(jié)點之間的線性距離相差甚遠。由此本文根據(jù)鎮(zhèn)江市的實際物流配送路徑合理規(guī)劃為出發(fā)點，提出了一種首先通過高德地圖提供的對應API接口來獲取各個道路節(jié)點之間的實際道路距離，然后交給改進的蟻群算法進行優(yōu)化得到最優(yōu)解，從而有效地將理論與實際物流配送路徑相結合，具有高度的可行性和實用性。

2 高德地圖API簡介

高德地圖API是一組基于云的地圖服務接口，包括互聯(lián)網(wǎng)地圖API和手機地圖API。高德地圖API通過互聯(lián)網(wǎng)、移動互聯(lián)網(wǎng)向桌面和移動終端用戶提供豐富的地圖服務功能，如地圖顯示、標注、位置檢索、駕車出行方案檢索、公交查詢、地址解析等。通過高德地圖API，開發(fā)者可以輕松地在自己的應用中定制強大、快速、輕便的地圖功能?；诟叩碌貓D的云服務接口，開發(fā)者無需考慮系統(tǒng)維護，無需購買地圖數(shù)據(jù)，便可以結合業(yè)務需求快速構建地圖應用，可大大降低地圖服務的使用成本［13］。其中高德Web服務API向開發(fā)者提供HTTP接口，開發(fā)者可通過這些接口使用各類型的地理數(shù)據(jù)服務，返回結果支持JSON和XML格式。本文中提到的道路節(jié)點之間的實際距離就是通過高德Web服務API中的對應請求接口獲取的。

3 物流配送的數(shù)學模型建立及蟻群算法

3.1 物流配送的數(shù)學模型

3.1.1 物流配送過程介紹

本文物流配送的過程可以描述為從物流中心通過一定數(shù)量的車輛分別向若干個客戶點派送貨物，車輛配送完貨物后則返回物流中心。每輛車的載貨量有限，為了節(jié)約成本以及提高派送貨物的效率，則必須合理的規(guī)劃車輛行駛路線。

3.1.2 數(shù)學模型建立

建立數(shù)學模型需要引入以下符號定義：物流汽車數(shù)量K（1，2…K），汽車的載重量Qk；配送的客戶點個數(shù)為L，客戶點集合為R=（R=｛i｝|i=1，2…L），客戶點的需求量為qi；dij為客戶i到客戶j的距離，其中i、j=0，1，2…L，當i=j=0時表示配送中心；nk為車輛k（k=1，2…K）配送的客戶總數(shù)，當 nk=0時，表示車輛k沒有參與配送；Rk為車輛k配送的客戶點集合，當 nk=0時，Rk=Φ ，當 nk≠0時，Rk=其中表示在車輛k配送客戶點集合中第i個配送的客戶。根據(jù)實際情況物流配送路線優(yōu)化需要滿足如下約束條件。

1）某一個客戶點的貨物需求只能由一輛車輛來配送；

2）任意一條路徑上的客戶需求總量之和不能超過汽車的載重量Qk；

3）所有客戶點都必須完成配送

因此，本文的物流配送問題需要達到的最優(yōu)路徑理論目標值為

3.2 基本蟻群算法

3.2.1 蟻群算法的基本原理

蟻群算法是受自然界螞蟻覓食行為的啟發(fā)而產(chǎn)生的一種自然模擬進化算法。20世紀90年代，M.Dorigo在他的博士論文中闡述了蟻群算法，并對其數(shù)學模型做了分析解釋。

螞蟻從蟻穴到目的地覓食的大致過程可以描述如下：起初螞蟻選擇路徑是隨機的，后來路徑的選擇會隨著覓食的過程而適應性的搜索新的路徑，原因在于螞蟻會在它們經(jīng)過的地方釋放信息素這一化學物質，而路徑上的信息素濃度與路徑長度有關，經(jīng)過路徑越長，則路徑上的信息素濃度相對越低，同時路徑上的信息素也會隨著時間的流逝按照一定的比例逐漸減少，因此對于較短的路徑上螞蟻釋放的信息濃度會更高，如此反復形成正反饋效應，直到最后所有的螞蟻都會走信息素濃度最高的那條路徑，也就是最短路徑。關于螞蟻覓食過程的簡要流程圖如圖1所示。其中圖1中（a）表示所有蟻群都在起點處，路徑上尚未有信息素，（b）表示蟻群開始分別以相等的概率向不同的方向覓食，（c）表示走較短路徑的蟻群首先到達覓食終點，（d）表示螞蟻返回起點過程中由于較短路徑上信息素濃度較高，所以螞蟻選擇較短路徑的概率要大于較長路徑的概率，最終根據(jù)正反饋效應螞蟻都會集中在較短路徑上［14～15］。

圖1 蟻群覓食行為圖

現(xiàn)實生活中的人工蟻群算法原理就是根據(jù)蟻群覓食的這種正反饋過程來實現(xiàn)的，但是人工蟻群算法在自然界的蟻群算法上做了改進，原始自然界中的蟻群是沒有記憶功能的，而人工蟻群算法具有一定的記憶功能，它會記住已經(jīng)訪問過的節(jié)點。另外就是人工蟻群算法在選擇下一條路徑的時候并不是完全毫無無目的性的去選擇，而是按照一定的算法規(guī)律去尋找最短路徑。

3.2.2 蟻群算法的基本求解模型

當螞蟻在客戶點i時，它在t時刻由客戶點i向客戶點j轉移的概率為

在式（7）中ηij，τij分別表示某時刻客戶點i到客戶點j的可見度以及i到j路徑上的信息素濃度，且ηij=1/dij；α為信息啟發(fā)因子，β為期望啟發(fā)因子，大小分別對應螞蟻對信息素量和路線距離長短的敏感程度；由于每只螞蟻每次巡回只能訪問客戶節(jié)點一次，所以用tabu（k）表示第k只螞蟻已經(jīng)訪問過的客戶點，allowed（k）=R-tabu（k）表示第k只螞蟻尚未訪問的客戶點。

當所有的螞蟻完成一次配送循環(huán)后，需要根據(jù)各個螞蟻遍歷的好壞程度，更新相關路徑上的信息素，因為信息素是影響文中算法收斂性的重要因素，相關路徑上信息素的更新規(guī)則如下：

式（8）、（9）中ρ表示信息素揮發(fā)系數(shù)，0≤ρ＜1，1-ρ表示信息素殘留系數(shù)和分別表示本次循環(huán)過程中路徑（i，j）上的信息素增量和第k只螞蟻留在該路徑上的信息素數(shù)量；m表示該循環(huán)過程中螞蟻數(shù)量；τij(t+n)和τij(t)分別表示對應時刻在路徑上的信息素數(shù)量。最后在上述基礎上得到蟻群算法的基本求解模型：

式（10）中Q為常數(shù)，表示信息素強度，它在一定程度上會影響算法的收斂速度，Lk為第k只螞蟻在本次循環(huán)中走過的路徑總長度［16］。

3.3 蟻群算法的改進

3.3.1 客戶點選擇策略的改進

圖2 螞蟻簡略尋跡圖

如圖2所示，假設螞蟻在D點，ABC為已經(jīng)去過的客戶點，EFG為沒去過的點，現(xiàn)在螞蟻要在EFG中選擇一個點作為下一步要到達的點。且D到E，F(xiàn)，G點的信息素/距離如圖2所示，那么理論上在α=1，β=2根據(jù)式（7）算得D到E，F(xiàn)，G的概率為24%，60%，16%，這樣選擇會導致一個問題，每只螞蟻到了D點都會選擇F點作為下一個訪問點，同樣在其他的點上也會有這種情況發(fā)生，就是每只螞蟻選擇的下一個點都是同一個點，這會導致所有螞蟻找到的路徑都是相同的，會使螞蟻失去探索新路徑的機會，算法陷入停滯。因此文中采用輪盤選擇法，在［0，1］之間取一個隨機數(shù)R。然后用R減D到E的概率，如果減去后的結果小于等于0就選E作為下一個點，如果減去后還大于0，就繼續(xù)再減去D到F的概率，直到減去后的結果小于等于0。然后用最后減去時的那個概率值對應的點作為下一個點。使用輪盤選擇法可以使螞蟻往概率值大的地方走的可能性大，但也有一定的可能往概率小的地方走，這樣可以使螞蟻探索新的路徑，避免算法停滯或者進入局部最優(yōu)解。

3.3.2 信息素揮發(fā)系數(shù)ρ的取值改進

信息素揮發(fā)系數(shù)ρ是一個常量，它的取值直接影響算法的求解結果，若ρ取值過小，則影響算法的收斂速度，取值過大，則會使沒有被搜索過的路徑被選擇的概率減小，影響算法的全局搜索。所以在求解過程中對ρ的取值進行調整，在算法初期為了盡快地找到較優(yōu)解ρ的取值應該比較大；到了后期當算法停滯不前就可以將ρ的取值減小，減小信息素對蟻群的影響，取得更優(yōu)的解。ρ的調整公式如下：

式（11）中r為循環(huán)次數(shù)；rmax為一常量；μ∈（0，1），它是一個常量，控制ρ的衰減速度；ρmin為ρ的最小值，確保ρ不會因為過小而影響收斂速度。這里當r達到設定的rmax時就減小ρ，然后對r重新計數(shù)，反復循環(huán)，直到ρ達到最小值ρmin為止。

3.3.3 客戶節(jié)點間計算距離改進

本文算法中求解最優(yōu)路徑結果時去掉基本的蟻群算法通過傳統(tǒng)方法來計算任意兩個節(jié)點的距離，而是通過程序調用高德地圖web服務API接口返回任意兩個節(jié)點間的實際導航距離來求得最優(yōu)解。通過該改進，可以提高算法的實用性和運行速度。

該接口的服務地址為https：//restapi.amap.com/v3/distance？parameters，接口的請求參數(shù)包括key（請求服務權限），origins（出發(fā)點），destination（目的地），type（路徑計算的方式和方法），output（返回數(shù)據(jù)格式類型xml或json，本文中取json），callback（回調函數(shù)），上述請求參數(shù)tpye本文中直接取缺省值，表示駕車導航距離。返回結果參數(shù)包括status（0：表示請求失敗，1：表示請求成功），info（返回狀態(tài)說明），result（距離等信息列表）。這里得到的任意兩個客戶節(jié)點之間的距離是實際道路之間的有向距離，而不是傳統(tǒng)算法所采取的根據(jù)勾股定理來計算的直線距離，而且通過接口在不同時間段取得的值不同，因為服務接口中考慮了實時路況，躲避了交通擁堵等。

3.4 物流配送的算法流程圖

物流配送的算法流程簡圖如圖3所示。

圖3 算法流程簡圖

4 實驗與結果分析

4.1 實驗問題描述

本文物流配送以鎮(zhèn)江市實際道路點為基礎，分別向本市十個不同的客戶點進行物流配送，尋求最優(yōu)的配送路徑。這里以鎮(zhèn)江站位置為物流配送中心，以十里長山、鎮(zhèn)江南站、江蘇大學、江科大東校區(qū)、大港中學、明都大飯店、金山公園、中醫(yī)院、江大附屬醫(yī)院、八佰伴為客戶點位置。物流配送中心車輛充足，且每輛車載重量為8噸，10個客戶點的需求量qi如表1所示，現(xiàn)在要求合理安排車輛及規(guī)劃路線，使配送過程的總路程最短。

表1 客戶點需求量（單位：噸）

根據(jù)表1可知客戶總需求量為29.4噸，而每輛車的載重量為8噸，初始估計配送車輛為4輛。算法初始化參數(shù)設置為信息啟發(fā)因子α=1，期望啟發(fā)因子β=2，信息素揮發(fā)系數(shù)初始值ρ=0.95，后期根據(jù)實際情況在程序中對ρ的取值進行調整，迭代次數(shù)為200。

4.2 實驗結果分析

通過高德地圖服務API得到的物流配送中心與各個客戶點以及客戶點和客戶點之間的實際道路距離如表2所示。其中（0，0）表示物流中心，1-10表示十個客戶節(jié)點，由表1中可知dij和dji的距離是不相等的，這是因為表2中所有節(jié)點之間的距離都是根據(jù)API接口取得的實時駕車導航距離，而不是傳統(tǒng)的道路節(jié)點之間的直線距離。另外程序在取得道路節(jié)點間的實際距離時可以根據(jù)接口傳參考慮諸多因素，如實時路況，是否躲避交通擁堵路段，還是不考慮路況直接走最短路線路段，以及不走高速且避開收費等，所以通過高德地圖API取得的實際道路距離來通過蟻群算法求得最優(yōu)解更具有實際意義。

根據(jù)上述初始化條件，程序運行結果可以得到表3所示的物流配送路徑的優(yōu)化結果對比表，表中總結出了具有代表性的10次配送路徑，以及對應的根據(jù)傳統(tǒng)方式得到的節(jié)點間直線行駛路程和根據(jù)實際道路行駛得到的行駛路程。由表3可知節(jié)點間最小直線行駛路程的最優(yōu)解為62.598km，但是與其對應的節(jié)點間的實際道路行駛路程卻不是最小的，而是表中第5行所對應的路徑得出的實際道路行駛路程89.378km才是最小值。這充分說明了在實際應用中，最優(yōu)路徑求解根據(jù)節(jié)點間的直線距離來計算最小路程是難以解決實際問題的，應該根據(jù)本文中提出的由實際道路節(jié)點距離來計算最優(yōu)路徑，這樣才能得到實際的最優(yōu)解。這里由于文中提供的客戶點較少且距離比較近，所以不同路徑所對應實際道路行駛路程相差不是太大，但是在客戶點較多或客戶點之間相距比較遠時，這種差距就會十分明顯，且更能體現(xiàn)由實際道路距離作為最優(yōu)路徑求解結果的正確性與優(yōu)越性。

在算法的收斂性方面，文中的最優(yōu)解在迭代40次以上基本上已經(jīng)趨于穩(wěn)定，迭代過程中平均路徑長度和最短路徑長度如圖4所示。

圖4 路徑優(yōu)化結果收斂圖

表2 各節(jié)點之間的實際道路距離（單位：km）

表3 路徑優(yōu)化求解結果對比表

最后，在實驗中根據(jù)傳統(tǒng)蟻群算法和文中改進的蟻群算法同樣在迭代200次的基礎上以及同樣的約束條件下，取得的直線最短路程，平均路程和最大路程做了一個簡單對比如表4所示。根據(jù)結果可知文中改進的算法相比于未改進之前增強了算法的正反饋機制，很好地避免了算法停滯現(xiàn)象，對路徑規(guī)劃問題具有較好的適應性和實用性。

表4 算法改進前后數(shù)據(jù)對比表

5 結語

本文以物流配送路徑優(yōu)化問題出發(fā)，以鎮(zhèn)江市實際道路節(jié)點為基礎，通過改進的蟻群算法來求得配送過程中所走的實際道路節(jié)點的最短路程。在前人研究的基礎上，文中求得的最短路徑并非通過節(jié)點間直線行駛最短距離來求得，而是通過高德API服務接口獲取各道路節(jié)點之間的實時導航距離并由改進的蟻群算法求得最優(yōu)解。實驗結果證明，傳統(tǒng)求解方式難以運用于實際，而本文提出的求解方式在實際應用中具有更好應用價值，實用性更高。