前言：想要寫出一篇令人眼前一亮的文章嗎？我們特意為您整理了5篇路徑規(guī)劃典型算法范文，相信會為您的寫作帶來幫助，發(fā)現(xiàn)更多的寫作思路和靈感。

路徑規(guī)劃典型算法范文第1篇

【關鍵詞】人工神經(jīng)網(wǎng)絡 路徑規(guī)劃 移動機器人

1 引言

在移動機器人導航技術應用過程中，路徑規(guī)劃是一種必不可少的算法，路徑規(guī)劃要求機器人可以自己判定障礙物，以便自主決定路徑，能夠避開障礙物，自主路徑規(guī)劃可以自動的要求移動機器人能夠安全實現(xiàn)智能化移動的標志，通常而言，機器人選擇的路徑包括很多個，因此，在路徑最短、使用時間最短、消耗的能量最少等預定的準則下，能夠選擇一條最優(yōu)化的路徑，成為許多計算機學者研究的熱點和難點。

2 背景知識

神經(jīng)網(wǎng)絡模擬生物進化思維，具有獨特的結構神經(jīng)元反饋機制，其具有分布式信息存儲、自適應學習、并行計算和容錯能力較強的特點，以其獨特的結構和信息處理方法，在自動化控制、組合優(yōu)化領域得到了廣泛的應用，尤其是大規(guī)模網(wǎng)絡數(shù)據(jù)分析和態(tài)勢預測中，神經(jīng)網(wǎng)絡能夠建立一個良好的分類學習模型，并且在學習過程中優(yōu)化每一層的神經(jīng)元和神經(jīng)元連接的每一個節(jié)點。1993年，Banta等將神經(jīng)網(wǎng)絡應用于移動機器人路徑規(guī)劃過程中，近年來，得到了廣泛的研究和發(fā)展，morcaso等人構建利用一個能夠實現(xiàn)自組織的神經(jīng)網(wǎng)絡實現(xiàn)機器人導航的功能，并且可以通過傳感器訓練網(wǎng)絡，取得更好的發(fā)展，確定系統(tǒng)的最佳路徑。神經(jīng)網(wǎng)絡拓撲結構模型可以分為：

2.1 前向網(wǎng)絡

網(wǎng)絡中各個神經(jīng)元接受前一級的輸入，并輸出到下一級，網(wǎng)絡中沒有反饋，可以用一個有向無環(huán)路圖表示。這種網(wǎng)絡實現(xiàn)信號從輸入空間到輸出空間的變換，它的信息處理能力來自于簡單非線性函數(shù)的多次復合。網(wǎng)絡結構簡單，易于實現(xiàn)。反傳網(wǎng)絡是一種典型的前向網(wǎng)絡。

2.2 反饋網(wǎng)絡

網(wǎng)絡內神經(jīng)元間有反饋，可以用一個無向的完備圖表示。這種神經(jīng)網(wǎng)絡的信息處理是狀態(tài)的變換，可以用動力學系統(tǒng)理論處理。系統(tǒng)的穩(wěn)定性與聯(lián)想記憶功能有密切關系。Hopfield網(wǎng)絡、波耳茲曼機均屬于這種類型。

3 基于人工神經(jīng)網(wǎng)絡的移動機器人路徑規(guī)劃算法

神經(jīng)網(wǎng)絡解決移動機器人路徑規(guī)劃的思路是：使用神經(jīng)網(wǎng)絡算法能夠描述機器人移動環(huán)境的各種約束，計算碰撞函數(shù)，該算法能夠將迭代路徑點集作為碰撞能量函數(shù)和距離函數(shù)的和當做算法需要優(yōu)化的目標函數(shù)，通過求解優(yōu)化函數(shù)，能夠確定點集，實現(xiàn)路徑最優(yōu)規(guī)劃。神經(jīng)網(wǎng)絡算法在移動機器人路徑規(guī)劃過程中的算法如下：

（1）神將網(wǎng)絡算法能夠初始化神經(jīng)網(wǎng)絡中的所有神經(jīng)元為零，確定目標點位置的神經(jīng)元活性值，并且能夠神經(jīng)網(wǎng)絡每層的神經(jīng)元連接將神經(jīng)元的值傳播到出發(fā)點；

（2）動態(tài)優(yōu)化神經(jīng)網(wǎng)絡，根據(jù)神經(jīng)網(wǎng)絡的目標節(jié)點和障礙物的具置信息，在神經(jīng)網(wǎng)絡拓撲結構中的映射中產(chǎn)生神經(jīng)元的外部輸入；

（3）確定目標值附件的神經(jīng)元活性值，并且使用局部側的各個神經(jīng)元之間，連接整個神經(jīng)網(wǎng)絡，并且在各個神經(jīng)元中進行傳播。

（4）利用爬山法搜索當前鄰域內活性值最大的神經(jīng)元，如果鄰域內的神經(jīng)元活性值都不大于當前神經(jīng)元的活性值，則機器人保持在原處不動；否則下一個位置的神經(jīng)元為鄰域內具有最大活性值的神經(jīng)元。

（5）如果機器人到達目標點則路徑規(guī)劃過程結束，否則轉步驟（2）。

4 基于人工神經(jīng)網(wǎng)絡的移動機器人路徑規(guī)劃技術展望

未來時間內，人工神經(jīng)在機器人路徑規(guī)劃過程中的應用主要發(fā)展方向包括以下幾個方面：

4.1 與信息論相融合，確定神經(jīng)網(wǎng)絡的最優(yōu)化化目標解

在神經(jīng)網(wǎng)絡應用過程中，由于經(jīng)驗值較為難以確定，因此在神經(jīng)網(wǎng)絡的應用過程中，將神經(jīng)網(wǎng)絡看做是一個貝葉斯網(wǎng)絡，根據(jù)貝葉斯網(wǎng)絡含有的信息熵，確定神經(jīng)網(wǎng)絡的目標函數(shù)的最優(yōu)解，以便更好的判斷機器人移動的最佳路徑。

4.2 與遺傳算法想結合，確定全局最優(yōu)解

將神經(jīng)網(wǎng)絡和遺傳算法結合起來，其可以將機器人的移動環(huán)境設置為一個二維的環(huán)境，障礙物的數(shù)目、位置和形狀是任意的，路徑規(guī)劃可以由二維工作空間一系列的基本點構成，神經(jīng)網(wǎng)絡決定機器人的運動控制規(guī)則，利用相關的神經(jīng)元的傳感器作用獲未知環(huán)境的情況，將障礙信息和目標點之間的距離作為神經(jīng)網(wǎng)絡的輸入信息，使用遺傳算法完成神經(jīng)網(wǎng)絡的權值訓練，神經(jīng)網(wǎng)絡的輸出作為移動機器人的運動作用力，實現(xiàn)一個可以在未知環(huán)境中進行的機器人運動路徑規(guī)劃。

4.3 與蟻群算法相結合，降低搜索空間，提高路徑規(guī)劃準確性

為了提高神經(jīng)網(wǎng)絡的搜索準確性和提高效率，可以將蟻群算法與神經(jīng)網(wǎng)絡相互結合，蟻群算法的路徑規(guī)劃方法首先采用柵格法對機器人工作環(huán)境進行建模，然后將機器人出發(fā)點作為蟻巢位置，路徑規(guī)劃最終目標點作為蟻群食物源，通過螞蟻間相互協(xié)作找到一條避開障礙物的最優(yōu)機器人移動路徑。

5 結語

隨著移動機器人技術的發(fā)展，路徑規(guī)劃作為最重要的一個組成部分，其得到了許多的應用和發(fā)展，其在導航過程中，也引入了許多先進的算法，比如神經(jīng)網(wǎng)絡，更加優(yōu)化了移動的路徑。未來時間內，隨著神經(jīng)網(wǎng)絡技術的改進，可以引入遺傳算法、信息論、蟻群算法等，將這些算法優(yōu)勢結合，將會是路徑規(guī)劃更加準確和精確。

參考文獻

[1]朱大奇,顏明重,滕蓉. 移動機器人路徑規(guī)劃技術綜述[J].控制與決策,2010,25(7): 961-967.

[2]劉毅.移動機器人路徑規(guī)劃中的仿真研究[J].計算機仿真,2011,28(6): 227-230.

[3]熊開封,張華.基于改進型 FNN 的移動機器人未知環(huán)境路徑規(guī)劃[J].制造業(yè)自動化,2013,35(22): 1-4.

[4]柳長安,鄢小虎,劉春陽.基于改進蟻群算法的移動機器人動態(tài)路徑規(guī)劃方法[J].電子學報,2011,39(5).

[5]范浩鋒,劉俊.基于 BP 神經(jīng)網(wǎng)絡的紅外目標識別技術[J].計算機與數(shù)字工程,2013,41(4): 559-560.

路徑規(guī)劃典型算法范文第2篇

關鍵詞：遺傳算法；蟻群算法；路徑規(guī)劃；旅行商問題

引言

物流與國民經(jīng)濟及生活的諸多領域密切相關，得到越來越多的重視，甚至被看作是企業(yè)“第三利潤的源泉”。因此，作為物流領域中的典型問題，旅行商問題(Traveling Salesman Problem，TSP)的研究具有巨大的經(jīng)濟意義。

TSP(Traveling Salesman Problem)問題, 是VRP[2]的特例，也稱為巡回旅行商問題,貨擔郎問題。簡稱為TSP問題，已證明TSP問題是NP難題。。TSP問題可描述為:給定一組n個城市和它們兩兩之間的直達距離,尋找一條閉合的旅程,使得每個城市剛好經(jīng)過一次而且總的旅行路徑最短。TSP問題的描述很簡單,簡言之就是尋找一條最短的遍歷n個城市的路徑,或者說搜索整數(shù)子集X={1,2,…,n}(X中的元素表示對n個城市的編號)的一個排列π(X)={v1, v2,…, vn},使取最小值.式中的d(vi,vi+1)表示城市vi到城市vi+1的距離。它是一個典型的、容易描述但卻難以處理的NP完全問題。同時TSP問題也是諸多領域內出現(xiàn)的多種復雜問題的集中概括和簡化形式。所以,有效解決TSP問題在計算理論上和實際應用上都有很高的價值。而且TSP問題由于其典型性已經(jīng)成為各種啟發(fā)式的搜索、優(yōu)化算法 (如遺傳算法、神經(jīng)網(wǎng)絡優(yōu)化法、列表尋優(yōu)法、模擬退火法等)的間接比較標準。

1 遺傳算法與蟻群算法

1.1 遺傳算法原理

遺傳算法(Genetic Algorithms，GA) 是一種借鑒生物界自然選擇和自然遺傳機制的隨機搜索算法,由美國J.Holland教授提出,其主要內容是種群搜索策略和種群中個體之間的信息交換,搜索不依賴于梯度信息.該算法是一種全局搜索算法,尤其適用于傳統(tǒng)搜索算法難于解決的復雜和非線性問題.。選擇算子、交叉算子和變異算子是遺傳算法的3個主要操作算子.遺傳算法中包含了如下5個基本要素:①對參數(shù)進行編碼;②設定初始種群大小;③設計適應度函數(shù);④設計遺傳操作;⑤設定控制參數(shù)(包括種群大小、最大進化代數(shù)、交叉率、變異率等)

1.2 蟻群算法原理

研究表明：螞蟻在覓食途中會留下一種外激素．螞蟻利用外激素與其他螞蟻交流、合作，找到較短路徑．經(jīng)過某地的螞蟻越多，外激素的強度越大．螞蟻擇路偏向選擇外激素強度大的方向．這種跟隨外激素強度前進的行為會隨著經(jīng)過螞蟻的增多而加強，因為通過較短路徑往返于食物和巢穴之間的螞蟻能以更短的時間經(jīng)過這條路徑上的點，所以這些點上的外激素就會因螞蟻經(jīng)過的次數(shù)增多而增強．這樣就會有更多的螞蟻選擇此路徑，這條路徑上的外激素就會越來越強，選擇此路徑的螞蟻也越來越多．直到最后，幾乎所有的螞蟻都選擇這條最短的路徑．這是一種正反饋現(xiàn)象．

2.算法改進

在傳統(tǒng)解決方法中，遺傳算法以其快速全局搜索能力在物流領域獲得了廣泛的應用。但遺傳算法在求解到一定程度時，往往作大量的冗余迭代，對于系統(tǒng)中的反饋信息利用不夠，效率較低；蟻群算法也以其較強的魯棒性和智能選擇能力被廣泛應用于旅行商問題 。蟻群算法是通過信息素的累積和更新而收斂于最優(yōu)路徑,具有分布、并行、全局收斂能力，但由于蟻群算法的全局搜索能力較差，易陷入局部最優(yōu)，很難得到最優(yōu)解。

為了克服兩種算法各自的缺陷,形成優(yōu)勢互補。為此首先利用遺傳算法的隨機搜索、快速性、全局收斂性產(chǎn)生有關問題的初始信息素分布。然后,充分利用蟻群的并行性、正反饋機制以及求解效率高等特征。算法流程如圖1

圖1 遺傳混合算法流程

2.1遺傳混合算法的具體描述如下：

Step1 給出，放置m個螞蟻在n個城市上。

Step 2 把所有螞蟻的初始城市號碼放置到tabuk中，列表tabuk紀錄了當前螞蟻k所走過的城市，當所有n個城市都加入到tabuk中時，螞蟻k便完成了一次循環(huán)，此時螞蟻k所走過的路徑便是問題的一個解。

Step 3 螞蟻K從起點開始，按概率的大小選擇下一個城市j,k∈{1，2，…,m},j∈allowedk如果螞蟻k轉移到j ,從allowedk中刪除,并將j加入到tabuk直至allowedk= 時重新回到起點。

Step 4 是否走完所有的城市，否，則轉入Step 3。

Step 5 計算,記錄，更新信息素濃度，所有路徑信息更新，如果,清空tabuk則轉入Step 2。

Step 6 當時，得到相對較優(yōu)螞蟻的序列。初始化種群。

Step 7 計算適應度值。

Step 8 進行遺傳交叉與變異操作。

Step 9 輸出得到的最短回路及其長度。

2.2 算法過程實現(xiàn)

（1）種群初始化

用蟻群算法進行初始化種群，放m只螞蟻對所有城市進行遍歷，將得到的結果進行優(yōu)化，做為蟻群算法的初始種群。每只螞蟻走過的路徑的就代表了一條基因（a0、a1、…、am-1、am），對于這條基因表示這只螞蟻首先從a0出發(fā)，次之訪問a1、…然后依次訪問am-1、am最后再回到a0。

（2）狀態(tài)轉移規(guī)則設置

    轉移概率，為t時刻螞蟻由i城到j城的概率。

            （1）

式中，allowedk表示螞蟻k下一步允許選則的城市，表示信息啟發(fā)因子，其值越大，該螞蟻越傾向于選擇其他螞蟻經(jīng)過的路徑，螞蟻之間的協(xié)作性超強；β為期望啟發(fā)因子，β的大小表明啟發(fā)式信息受重視的程度，其值越大，螞蟻選擇離它近的城市的可能性也越大，越接近于貪心規(guī)則［6］。為啟發(fā)因子，其表達式為: ，每條路上的信息量為：

（2）其中

其中ρ表示路徑上信息的蒸發(fā)系數(shù)，1-ρ表示信息的保留系數(shù)；表示本次循環(huán)路徑(i,j)上信息的增量。表示第k只螞蟻在本次循環(huán)中留在路徑(i,j)上的信息量，如果螞蟻k沒有經(jīng)過路徑(i,j)，則的值為零，表示為：

（3）

其中，Q為常數(shù)， 表示第k只螞蟻在本次循環(huán)中所走過的路徑的長度。

（3）交叉算子的設計

首先隨機地在父體中選擇兩雜交點,再交換雜交段,其它位置根據(jù)保持父體中城市的相對次序來確定。例如,設兩父體及雜交點的A1和A2, A1=(2 6 4 7 3 5 8 9 1), A2=(4 5 2 8 1 6 7 9 3)。交換雜交段于是仍有B1=(2 6 4 1 8 7 6 9 1),B2=(4 5 2 7 3 5 8 9 3)。在新的城市序列中有重復的數(shù)，將雜交段中對應次序排列,即: 7-8、3-1、5-6，依此對應關系替換雜交段中重復的城市數(shù)。將B1中(2 6 4)重復的6換為5，B2(9 3)中重復的3換為1.。雜交后的兩個體為B1=(2 5 4 1 8 7 6 9 1),B2=(4 5 2 7 3 5 8 9 1)。本算法采用此方法交雜交。

3.仿真實驗

對TSP問題仿真所用的數(shù)據(jù)庫是TSPLIB典型51城市的數(shù)據(jù)。仿真平臺如表1所示。

表1  仿真試驗平臺

設備名稱

型號

CPU

Pentium(R)M 1.66 GH

內存

512M

操作系統(tǒng)

Microsoft Windows XP

仿真軟件

MierosoftVisualC++6.0

3.1 遺傳算法仿真

基本遺傳算法仿真。對51城市路徑優(yōu)化路徑優(yōu)化。參數(shù)設置如下:種群:50,最大迭代數(shù):5000,交叉概率:0.8,變異概率:0.2

遺傳算法找到最優(yōu)解的時間是95 s, ,路徑長度497。

3.2 蟻群算法仿真

基本蟻群算法對51城市路徑優(yōu)化。其參數(shù)設置如下：ρ=1α=1，β=8，τ0=0.001Qu=100., m=51

基本蟻群算法找到最優(yōu)解的時間是68 s, 路徑長度465。

3.3遺傳混合算法

遺傳混合算法對51城市路徑優(yōu)化。其參數(shù)設置如下：種群:51,最大迭代數(shù):5 000,交叉概率:0.8,變異概率:0.001;ρ=1α=1，β=8，τ0=0.001Qu=100，m=51；

遺傳混合算法找到最優(yōu)解的時間是50 s, 路徑長度459。

遺傳算法、基本蟻群算法、遺傳混合算法對TSPLIB典型51城市的數(shù)據(jù)進行仿真,仿真結

果對比如表2所

算法名稱

所用時間（s）

最優(yōu)結果

遺傳算法

95

497

基本蟻群算法

68

465

改進混合算法

50

456

4.結論

本文為了更好地解決物流領域中的旅行商問題，充分發(fā)揮遺傳算法的全局搜索能力和蟻群算法的正反饋能力和協(xié)同能力，采用了遺傳算法與蟻群算法混合算法進行求解，并且進行了模擬仿真。仿真結果表明，利用遺傳與蟻群混合算法可以找到較好解的能力，大大提高計算效率，結果質量也較好。   

參考文獻：

［1］小平,曹立明.遺傳算法———理論、應用與軟件實現(xiàn)[M].西安交通大學出版社,2002.

［2］[日]玄光男,程潤偉.遺傳算法與工程設計[M].科學出版社, 2000.

［3］胡小兵，黃席樾。蟻群優(yōu)化算法及其應用[J]. 計算機仿真 2004，24（5）

［4］王凌。智能優(yōu)化算法及其應用[M]. 北京：清華大學出版社 2001.

路徑規(guī)劃典型算法范文第3篇

關鍵詞：路徑規(guī)劃；多倉庫多配送任務；iOS；電子地圖；最優(yōu)路徑

中圖分類號：TP311 文獻標識碼：A 文章編號：1009-3044（2016）32-0190-04

Design and Implementation of Order Routing System Based on iOS

XU Jing-hui

（North China University of Technology， Beijing 100144， China）

Abstract： The routing problem of multi-warehouse and multi-distribution task in order distribution has the characteristics of picking from the warehouse and returning to the starting warehouse after completing the delivery task by multiple distribution points. In view of the current path planning applications on the mobile platform to solve the known starting point to the end of the route planning， after a number of points along the planning has not yet been a good application to achieve. Therefore， this paper combines the path planning and iOS platform to make full use of the characteristics of electronic map application， design and implement the order routing system based on iOS in order to provide the optimal path results. This paper focuses on how to realize the function of map display and operation， map location， mark drawing， route planning and so on. Finally， using the real order data of inventory management platform， the test proves the effectiveness and convenience of the system.

Key words： route plan； multi-warehouse multi-distribution tasks； iOS； digital map； optimal path

在實際訂單配送環(huán)節(jié)中，路徑規(guī)劃要求找出車輛從倉庫取貨出發(fā)依次經(jīng)過一系列配送點后返回倉庫的最短回路路徑。目前關于路徑規(guī)劃的研究多數(shù)集中在常見路徑算法的改進及優(yōu)化方面[1-3]，對于路徑規(guī)劃應用系統(tǒng)的研究還較少。國內iOS平臺上有關路徑規(guī)劃的熱門應用有高德地圖、百度地圖等App，但它們也只提供了支持公交、駕車及步行三種出行方式的點到點的路徑規(guī)劃，對于從起點經(jīng)過多個沿途點到達終點的路線規(guī)劃并未涉及。鑒于目前尚未有將路徑規(guī)劃與iOS移動平臺的應用特點充分相結合的應用，本文就設計開發(fā)了iOS平臺上基于電子地圖的路徑規(guī)劃系統(tǒng)――稱之為“易配送系統(tǒng)”。易配送系統(tǒng)可在用戶使用期間自動定位用戶當前所在位置，同時提供倉庫到各配送點的路線規(guī)劃和導航等主要功能，還通過服務端的接口服務將數(shù)據(jù)封裝成XML編碼格式通過網(wǎng)絡提供給客戶端，保障了訂單數(shù)據(jù)的真實性與實時性。在系統(tǒng)開發(fā)過程中利用高德iOS地圖SDK進行應用開發(fā)，提供了可視化的路徑規(guī)劃人機交互界面。

本文的內容首先對iOS平臺開發(fā)相關技術進行了簡要介紹，然后對訂單配送路徑規(guī)劃系統(tǒng)進行分析，設計出了整體的技術方案與系統(tǒng)架構，然后對系統(tǒng)功能進行詳細實現(xiàn)，包括倉庫、訂單查詢，地圖位置顯示、路線規(guī)劃及導航等功能，最后進行結果分析與總結。

1 iOS開發(fā)平臺介紹

1.1 iOS系統(tǒng)架構

iOS平臺應用的開發(fā)語言主要有Objective-C和Swift語言，由于swift作為一門新生語言使用人數(shù)較少的原因，本系統(tǒng)采用了主流開發(fā)語言Objective-C進行編碼開發(fā)。Objective-C作ANSI C的超集[4]，不僅擴展了面向對象設計的能力，如類、消息、繼承，同時它可以調用C的函數(shù)，也可以通過C++對象訪問方法，具有對C和C++語言的兼容性。

蘋果公司最新推出的iOS 10 SDK （Software Development Kit， 軟件開發(fā)工具包）增加了新的API （Application Programming Interface， 應用程序編程接口）和服務，能夠支持更多新類型的應用程序和功能。目前基于iOS平臺開發(fā)的應用程序可以擴展到消息、Siri、電話和地圖等系統(tǒng)自帶服務，擁有了更吸引人的功能。圖1為iOS系統(tǒng)架構圖：

圖中可觸摸層主要提供用戶交互相關的服務如界面控件、事件管理、通知中心、地圖，包含以下框架：UIKit、Notification Center、MapKit等；媒體層主要提供圖像引擎、音頻引擎及視頻引擎框架；核心服務層為程序提供基礎的系統(tǒng)服務如網(wǎng)絡訪問、瀏覽器引擎、定位、文件訪問、數(shù)據(jù)庫訪問等。最底層的核心系統(tǒng)層為上層結構提供了最基礎的服務包括操作系統(tǒng)內核服務、本地認證、安全、加速等。

1.2 iOS 地圖SDK

iOS 地圖SDK 是高德提供的一套基于 iOS 6.0.0 及以上版本的地圖應用程序開發(fā)接口，供開發(fā)者在iOS應用中加入地圖相關的功能[6]。它提供的四種地圖模式包括：標準地圖、衛(wèi)星地圖、夜景模式地圖和導航模式地圖。開發(fā)者不僅可以利用其地圖計算工具實現(xiàn)坐標轉換和距離或面積計算，而且可以調用API完成出行路線規(guī)劃及點標注、折線、面的繪制等工作。這些實現(xiàn)的提前需要注冊并認證成為高德開發(fā)者，接著為應用申請APIKey，然后將iOS地圖SDK配置到應用工程中，這里可以采用手動和自動化兩種配置方式。前者的配置過程簡單易操作，但更新操作代價大，后者配置過程稍顯負雜，但更新很方便。手動配置的方式則需要手動向工程項目中導入MAMapKit.framework和AMapSearchKit. framework兩個包，當框架有更新時需將工程中舊框架刪除并添加新框架，其使用稍顯麻煩。本系統(tǒng)的實現(xiàn)采用了自動化配置工程的方式，利用第三方庫管理工具CocoaPods通過命令：pod ‘AMap3DMap’， ‘～>4.0’和pod ‘AMapSearch’， ‘～>4.0’完成自動導入框架的目的，當框架更新時只需執(zhí)行pod update即可實現(xiàn)項目中框架的更新。

2 整體方案設計

通常App功能復雜的情況下需要有后臺服務器的業(yè)務處理支持，本文涉及的路徑規(guī)劃功能需要處理的計算量會隨著配送點個數(shù)的增長呈指數(shù)階上升，因此需要后臺服務器的強大計算能力處理路徑規(guī)劃結果，進而減輕客戶端內存使用壓力。

本系統(tǒng)整體技術方案的設計綜合考慮了移動應用端、服務端（包括應用服務器和提供商服務器）以及數(shù)據(jù)庫服務器三部分所涉及的技術及其簡要的功能模塊劃分，如下圖2所示：

其中應用服務端是典型的電商進銷存管理系統(tǒng)，移動端LBS應用――易配送App的實現(xiàn)需要在進銷存Web系統(tǒng)的表示層、業(yè)務邏輯層、數(shù)據(jù)持久層添加相應的訂單配送接口，該接口將服務端經(jīng)過處理的數(shù)據(jù)結果封裝成XML標準的數(shù)據(jù)格式通過HTTP協(xié)議傳輸給App。

3 基于iOS的路徑規(guī)劃App設計

3.1 App開發(fā)模式

易配送App采用Objective-C開發(fā)語言，開發(fā)工具為Xcode7.0，主要針對iPhone進行設計的。系統(tǒng)的設計模式采用了MVC范型如圖3。由于系統(tǒng)所涉及的內容數(shù)據(jù)均通過網(wǎng)絡請求服務器實時更新獲取，故采用了iOS App開發(fā)模式中的Native App，以保證有較好的網(wǎng)絡環(huán)境以及節(jié)省的帶寬，以便利用充分的設備資源來提供良好的交互體驗。

該系統(tǒng)平臺中的位置信息主要體現(xiàn)在：位置服務和地圖。位置服務是由Core Location框架負責，它將用戶的位置及方向信息以Objective-C語言能識別的形式羅列出來[4]；地圖服務通過應用中集成的高德開發(fā)平臺提供的MAMapKit框架負責，利用它可以展示出地圖和圖釘標注等信息。易配送App的路徑規(guī)劃模塊有效地將Core Location框架和MAMapKit框架結合起來，以實現(xiàn)地圖定位、距離測試、路線顯示及導航功能。

3.2 重要功能設計及關鍵技術實現(xiàn)

系統(tǒng)的主界面設計采用了圖文結合的布局方式如圖4，使用戶能夠快速便捷的操作系統(tǒng)。對于信息查詢類似功能的界面多采用表視圖結構，得到了清楚地展示大量內容信息的效果如圖5所展示的待配送訂單列表。

圖4 主界面 圖5 待配送列表

圖6 路徑規(guī)劃

系統(tǒng)主要的路徑規(guī)劃功能在電子地圖的地理信息背景下完成了標注及路線可視化如圖6所示，其關鍵技術的實現(xiàn)如下：

1）初始化地圖服務

系統(tǒng)中地圖服務的使用首先需要初始化地圖控件，這需要在創(chuàng)建MAMapView之前需要先綁定APIKey：[MAMapServices sharedServices].apiKey = APIKey； 和[AMapSearchServices sharedServices].apiKey = APIKey；接著初始化MAMapView地圖控件：_mapView = [[MAMapView alloc] initWithFrame： self.view. frame]；并o系統(tǒng)添加地圖視圖：[self.view addSubview：_mapView]；

2）分組待配送訂單

因為業(yè)務要求需要將待配送訂單按各自對應的出貨倉庫進行分組配送，系統(tǒng)中通過自定義實現(xiàn)分組方法：-（void）groupAction：（NSMutableArray *）array； 其中參數(shù)array中存儲著多個配送單對象XJDeliveryOrder。方法實現(xiàn)中利用可變的集合對象NSMutableSet保存的內容對象不重復的特性，用_warehouseSet記錄不同的倉庫信息：_warehouseSet = [NSMutableSet set]； [array enumerateObjectsUsing Block： ^（ XJDeliveryOrder * _Nonnull order， NSUInteger idx， BOOL * _Nonnull stop） {[_warehouseSet addObject：order.warehouseName]； }]； 同時該方法中利用謂詞NSPredicate過濾數(shù)組array實現(xiàn)按倉庫名稱分組：[_warehouseSet enumerateObjectsUsingBlock：^（NSString * _Nonnull warehouseName， BOOL * _Nonnull stop） {NSPredicate *predicate = [NSPredicate predicateWithFormat： @"warehouseName = %@"， warehouseName]；NSArray *tempArr = [NSArray arrayWithArray：[array filteredArrayUsingPredicate：predicate]]； [groupArr addObject： tempArr]；}]；

3）添加標注及氣泡視圖

給地圖添加標注需要調用地理編碼請求：[self.search AMapGeocodeSearch： geo]； 其中對象geo為AMapGeocodeSearchRequest類對象且其屬性值address不為空，該請求會回調AMapSearchDelegate中的方法：- （void）onGeocodeSearchDone： （AMapGeocodeSearchRequest*）request response：（AMapGeocodeSearchResponse *） response；其中response對象中包含了經(jīng)緯度信息并且該方法中調用了添加標注方法：[_mapView addAnnotation：pointAn]；其中對象pointAn為MAPointAnnotation類對象。

實現(xiàn)觸摸標注彈出氣泡的效果需要實現(xiàn)MAMapViewDelegate委托中-（MAAnnotationView*）mapView：（MAMapView*）mapViewviewForAnnotaion： （id< MAAnotation>）annotation；和-（void）mapView：（MAMapView*）mapView didSelect AnnotationView：（MAAnnotationView *）view；方法。

4）路徑規(guī)劃及繪制路線

iOS地圖API提供了按參數(shù)順序進行路徑規(guī)劃的方法：[_search AMapDriving RouteSearch：request]；其中request為AMapDrivingRouteSearchRequ -est對象，需要給定request的屬性：起點origin、終點destination和沿途點waypoints的值。而對于最優(yōu)路徑的規(guī)劃只能通過自定義方法：-（void）planBestPaths WithLoaction：（CLLocationCoordinate2D）location wayPoints： （NSArray*） wayPoints；該方法中調用了網(wǎng)絡請求服務器方法，并能夠獲取服務器返回的處理結果，其結果中包含了多個經(jīng)緯度字符串，需要利用方法- （CLLocationCoordinate2D *）coordinatesForString：（NSString*）string coordinateCount：（NSUInteger *）coordinate Count parseToken：（NSString *）token；來解析經(jīng)緯度，然后系統(tǒng)利用解析得到的經(jīng)緯度調用[MAPolyline polylineWithCoordinates：coordinates count：count]來繪制路線。

5）最優(yōu)路徑算法

本系統(tǒng)的服務端路徑規(guī)劃接口實現(xiàn)中采用了適合解決單回路最短路徑問題的算法――最近c插入算法。最近插入法是一種啟發(fā)式算法，它不僅適用于各種復雜的TSP問題，對于中小規(guī)模問題同樣適用。圖7為算法具體流程。算法的實現(xiàn)是在后臺服務端通過java語言實現(xiàn)的，這里就不做詳細說明了。

4 系統(tǒng)測評與應用實例

為了對系統(tǒng)的功能及路徑優(yōu)化效果進行測試，采用了如下的實驗環(huán)境：客戶端是所有系統(tǒng)為iOS 7.0及以上iPhone手機，安裝App后即可使用；服務端為可安裝運行在windows平臺下的進銷存管理系統(tǒng)；數(shù)據(jù)庫為Oracle數(shù)據(jù)庫安裝在Linux數(shù)據(jù)庫服務器上。

本系統(tǒng)中路徑規(guī)劃功能的實現(xiàn)采用了將多個倉庫多配送點的路徑規(guī)劃分解為多個單倉庫多點配送的思想。下面一系列圖示說明了多個單倉庫出發(fā)到多個配送點的路徑規(guī)劃對比結果。

圖8中顯示當天需要規(guī)劃路徑的所有點，包括三個倉庫和八個客戶位置。接下來分別對三個倉庫進行出貨配送安排，如圖9為從總倉庫出發(fā)的配送路線對比，其中上圖為按下單順序依次配送的路線圖，下圖為根據(jù)與出發(fā)倉庫距離由近到遠的依次配送的路線圖，從圖中可以明顯看出兩者各自的路程代價，表1為各倉庫配送路徑的對比結果。

通過實驗測試結果表明，當單次規(guī)劃的配送數(shù)量小于等于6時，本系統(tǒng)的最優(yōu)路徑準確且計算處理很快，幾乎網(wǎng)絡無延遲。當單次規(guī)劃的配送數(shù)量大于6小于17時，優(yōu)化結果準確但是處理速度變慢，并且處理響應時間雖配送數(shù)量呈現(xiàn)指數(shù)階增長。當單次規(guī)劃的配送數(shù)量大于16時，服務端需通過一定路徑優(yōu)化算法處理大規(guī)模計算，但其結果往往是最優(yōu)解的近似值而非最優(yōu)路徑值。

5 結束語

本文是在iOS系統(tǒng)上基于電子地圖的應用開發(fā)，基本實現(xiàn)了小規(guī)模訂單配送的路徑規(guī)劃功能。經(jīng)過優(yōu)化的路徑的確節(jié)省了許多里程，真正意義上為企業(yè)提高了效益。但是本系統(tǒng)還存在一些不足之處，如適合處理小規(guī)模訂單配送路徑規(guī)劃的局限性，系統(tǒng)的可擴展性有待加強。在今后的學習和研究中，將進一步深化和擴展該應用的功能，提供更加豐富的視圖信息和交互方式，實現(xiàn)更良好的路徑規(guī)劃體驗。

參考文獻：

[1] WANG Tiejun，WU Kaijun. Study multi-depots vehicle routing based on improve -ed particle swarm optimization[J]. Computer Engineering and Applications，2013， 49（2）： 5-8.

[2] 馬建華，房勇，袁杰.多車場多車型最快完成車輛路徑問題的變異蟻群算法[J].系統(tǒng)工程理論與實踐，2011（8）.

[3] 李波，邱紅艷.基于雙層模糊聚類的多車場車輛路徑遺傳算法[J].計算機工程與應用，2014（5）.

[4] 胡楊帆，楊剛，胡顥石.結合LBS和信息推送的博物館App的設計實現(xiàn)[J].計算機應用與軟件，2013， 12（30）：108-112.

路徑規(guī)劃典型算法范文第4篇

關鍵詞：車輛路徑問題；啟發(fā)式算法；優(yōu)化

中圖分類號：U116.2 文獻標識碼：A

Abstract： Vehicle routing problem is the core problem in logistics management and in the organization and optimization of transportation， and is a classic combinatorial optimization problem in operations research. This article systematically summarized the common classifications and the basic model of VRP problems. And through referring to scholars' research situation， summarized the commonly used and efficient heuristic algorithms of solving VRP problems and the present situation of the corresponding research. Finally， summarized the problems in the research of VRP problems and discussed the future research and the solving methods for VRP problems.

Key words： vehicle routing problem； heuristic algorithm； optimization

0 引 言

隨著科技的進步和電子商務的飛速發(fā)展，作為國民經(jīng)濟中一個重要行業(yè)的物流產(chǎn)業(yè)已成為拉動國家經(jīng)濟發(fā)展與提高居民生活水平的重要動力源泉，而物流行業(yè)中的車輛路徑問題（Vehicle Routing Problem， VRP）是制約物流行業(yè)發(fā)展的一個關鍵要素，其研究也受到人們的廣泛關注。車輛路徑問題是物流管理與運輸組織優(yōu)化中的核心問題之一，是指在滿足一定的約束條件（如時間限制、車載容量限制、交通限制等）下，通過對一系列收貨點與發(fā)貨點客戶合理安排行車路線，在客戶的需求得到滿足的前提下，達到配送車輛最少、配送時間最短、配送成本最低、配送路程最短等目標。該問題由Dantzig和Ramser[1]于1959年在優(yōu)化亞特蘭大煉油廠的運輸路徑問題時首次提出，現(xiàn)已成為運籌學中一類經(jīng)典的組合優(yōu)化問題，是典型的NP-難題。

企業(yè)通過選取恰當?shù)呐渌吐窂?，對運輸車輛進行優(yōu)化調度，可以明顯提高配送效率，有效減少車輛的空駛率和行駛距離，降低運輸成本，加快響應客戶的速度從而提高客戶服務質量，提高企業(yè)的核心競爭力。VRP作為物流系統(tǒng)優(yōu)化環(huán)節(jié)中關鍵的一環(huán)，其研究成果已經(jīng)應用到快遞和報紙配送連鎖商店線路優(yōu)化以及城市綠化車線路優(yōu)化等社會實際問題中，因而車輛路徑問題的優(yōu)化研究具有很好的現(xiàn)實意義。

1 車輛路徑問題的分類與基本模型

VRP的構成要素通常包括車輛、客戶點、貨物、配送中心（車場）、道路網(wǎng)絡、目標函數(shù)和約束條件等，根據(jù)側重點的不同，VRP可以分為不同的類型。根據(jù)運輸車輛載貨狀況分類可分為非滿載車輛路徑問題和滿載車輛路徑問題；根據(jù)任務特征可分為僅裝貨、僅卸貨和裝卸混合的車輛路徑問題；根據(jù)優(yōu)化目標的數(shù)量可分為單目標車輛路徑問題和多目標車輛路徑問題；根據(jù)配送車輛是否相同可分為同型車輛路徑問題和異型車輛路徑問題；根據(jù)客戶對貨物接收與發(fā)送有無時間窗約束可分為不帶時間窗的車輛路徑問題和帶時間窗的車輛路徑問題；根據(jù)客戶需求是否可拆分可分為需求可拆分車輛路徑問題和需求不可拆分車輛路徑問題；根據(jù)客戶是否優(yōu)先可分為優(yōu)先約束車輛路徑問題和無優(yōu)先約束車輛路徑問題；根據(jù)配送與取貨完成后車輛是否需要返回出發(fā)點可分為開放式車輛路徑問題和閉合式車輛路徑問題；還可以將上述兩個或更多約束條件結合起來，構成一些更復雜的車輛路徑問題。

由于VRP的約束條件不同引起了其分類多種多樣，而不同類型的VRP其模型構造及求解算法有很大差別。VRP的一般數(shù)學模型為：

在上述模型中，式（1）表示目標函數(shù)，式（2）表示約束條件。其他VRP模型大致都是在此模型的基礎上根據(jù)約束條件完善形成的。

2 VRP的求解算法與研究現(xiàn)狀

VRP的求解方法，基本上可分為精確算法和啟發(fā)式算法兩大類。由于精確算法的計算難度與計算量隨著客戶點的增多呈指數(shù)級增加，在實際中應用范圍有限，而啟發(fā)式算法則具有全局搜索能力強、求解效率高的特點，求出的解也具有較好的參考性，因此，目前大部分研究者們主要把精力集中在如何構造高質量的啟發(fā)式算法上，本文也主要討論一些近年來研究比較多的啟發(fā)式優(yōu)化算法。針對VRP問題目前已提出了大量的啟發(fā)式算法，其中研究較多的主要包括以下算法：

2.1 遺傳算法（Genetic Algorithm，GA）

GA是一種通過模擬生物進化過程來搜索最優(yōu)解的方法，該方法通過對群體進行選擇、交叉和變異等操作，產(chǎn)生代表新的解集的種群，根據(jù)個體適應度大小選擇個體，通過迭代逐步使群體進化到近似最優(yōu)解狀態(tài)。但是該算法具有搜索速度慢、易早熟、總體可行解質量不高等缺點。

采用遺傳算法研究VRP問題的研究現(xiàn)狀包括：蔣波[2]設計了遺傳算法求解以配送總成本最小為目標函數(shù)和帶有懲罰函數(shù)的VRPTW模型；趙辰[3]基于遺傳算法求解了從生產(chǎn)中心到倉庫之間的路徑優(yōu)化問題，設計了配送路徑優(yōu)化決策；張群和顏瑞[4]建立了多配送中心、多車型車輛路徑問題混合模型，并采用一種新的模糊遺傳算法求解該問題。

2.2 模擬退火算法（Simulated Annealing，SA）

SA同禁忌搜索算法一樣，也屬于局部搜素算法，但是模擬退火算法是模仿金屬加工中退火的過程，通過一個溫度函數(shù)作為目標函數(shù)，使其趨于最小值，是一種基于概率的算法。

采用模擬退火算法研究VRP問題的研究現(xiàn)狀包括：郎茂祥[5]研究了裝卸混合車輛路徑問題，并構造了模擬退火算法求解該問題；穆東等[6]提出了一種并行模擬退火算法，并將該算法的應用領域擴展到其他車輛路徑問題和組合優(yōu)化問題；魏江寧和夏唐斌[7]以模擬退火算法為基礎，研究了單個集散點與多個客戶之間的運輸問題；Mirabi和Fatemi Ghomi等[8]提出了一種基于模擬退火思想的三步啟發(fā)式算法求解最小化配送時間的多配送中心VRP模型。

2.3 蟻群算法（Ant Colony Optimization，ACO）

蟻群算法是人們受螞蟻可以快速找到食物的自然現(xiàn)象啟發(fā)提出的。蟻群算法所建立的機制，主要包括螞蟻的記憶、螞蟻利用信息素進行交互通信及螞蟻的集群活動三個方面。單個螞蟻缺乏智能，但整個蟻群則表現(xiàn)為一種有效的智能行為。通過這種群體智能行為建立的路徑選擇機制可使蟻群算法的搜索向最優(yōu)解靠近。

采用蟻群算法研究VRP問題的研究現(xiàn)狀包括：馬建華等[9]研究了基于動態(tài)規(guī)劃方法的多車場最快完成車輛路徑問題的變異蟻群算法；辛穎[10]通過對MMAS蟻群算法進行了三種策略的改造，指出蟻群算法可以找到相對較好的解和很強的魯棒性；陳迎欣[11]針對蟻群算法的缺點，分別對信息素更新策略、啟發(fā)因子進行改進，引入搜索熱區(qū)機制，有效解決車輛路徑優(yōu)化問題；段征宇等[12]通過最小成本的最鄰近法生成蟻群算法和局部搜索操作設計了一種求解TDVRP問題的改進蟻群算法。

2.4 粒子群算法（Particle Swarm Optimization，PSO）

PSO算法是通過對鳥群覓食行為的研究而得出的一種群體并行優(yōu)化算法，它從隨機解出發(fā)，通過迭代尋找最優(yōu)解。蟻群算法具有容易實現(xiàn)、收斂速度快、精度高等優(yōu)點，在多種優(yōu)化問題上均取得了較好的效果。但是由于PSO算法是通過粒子之間的相互作用來尋找最優(yōu)解，缺乏像遺傳算法那樣的變異機制，因而PSO算法容易陷入局部最優(yōu)。

采用粒子群算法研究VRP問題的研究現(xiàn)狀包括：馬炫等[13]提出了一種基于粒子交換原理的整數(shù)粒子更新方法求解有時間窗約束的車輛路徑問題；吳耀華和張念志[14]以處理集貨或送貨非滿載帶時間窗車輛路徑優(yōu)化問題為背景，提出了帶自調節(jié)機制的局部近鄰粒子群算法解決VRP問題。

2.5 蝙蝠算法（Bat Algorithm，BA）

蝙蝠算法是劍橋大學學者Yang[15]于2010年提出的一種新型群智能進化算法，模擬自然界中蝙蝠通過超聲波搜索、捕食獵物的生物學特性，是一種基于種群的隨機尋優(yōu)算法。截至目前，蝙蝠算法主要用于求解連續(xù)域的函數(shù)優(yōu)化問題，只有少數(shù)學者將其用來求解離散型問題，具有很好的研究前景。

采用蝙蝠算法研究VRP問題的研究現(xiàn)狀包括：馬祥麗等[16]將蝙蝠算法應用于求解VRP問題，在蝙蝠速度更新公式中引入了慣性權重，對基本蝙蝠算法進行了改進，克服了基本蝙蝠算法的不足之處；馬祥麗等[16]針對VRPTW問題的具體特性重新定義了蝙蝠算法的操作算子，設計了求解VRPTW 問題的蝙蝠算法，并采用罰函數(shù)的方式對目標函數(shù)進行了簡化求解。

3 總結與展望

車輛路徑問題由于約束條件的不同其分類多種多樣，數(shù)學模型與求解算法也層出不窮。本文總結了近幾年一些相關學者對VRP問題的研究和求解算法，通過較為系統(tǒng)地總結VRP問題，本文總結出以下當前研究存在的問題和今后可能的研究方向：

（1）研究目標太過理想化。目前學者研究VRP的研究過于注重成本最小和路徑最短，大部分是單目標優(yōu)化，而在實際應用中，配送的駕駛員也可能會因許多原因耽誤計劃的行程，顧客的需求各異甚至沖突，顧客滿意度與企業(yè)成本最小化目標之間存在效益悖反的矛盾。今后的研究可以將成本、路程、駕駛員休息、顧客滿意度等多個目標聯(lián)合起來進行研究，并可以通過線性加權的方式進行綜合求解。

（2）單個約束的VRP問題由于研究時間較長，現(xiàn)在已經(jīng)研究的較為成熟，而且其應用局限也比較大，應該考慮將多個約束條件結合起來，建立符合實際的多約束條件的車輛路徑問題，更好地解決企業(yè)的配送優(yōu)化。

（3）雖然啟發(fā)式算法具有全局搜索能力強，運算方便等優(yōu)點，但是也存在著局部搜索能力差、收斂時間過長、易陷于局部最優(yōu)等問題。使用單一的群智能算法不是求解VRP的最有效算法，將兩種和多種群智能算法結合起來研究車輛路徑問題，取長補短，是今后應該考慮的問題；同時，應考慮尋求更多的智能優(yōu)化算法來求解VRP問題。

參考文獻：

[1] GB. Dantzig， JK. Ramser. The truck dispatching problem[J]. Management Science， 1959，6（1）：80-91.

[2] 蔣波. 基于遺傳算法的帶時間窗車輛路徑優(yōu)化問題研究[D]. 北京：北京交通大學（碩士學位論文），2010.

[3] 趙辰. 基于遺傳算法的車輛路徑優(yōu)化問題研究[D]. 天津：天津大學（碩士學位論文），2012.

[4] 張群，顏瑞. 基于改進遺傳算法的混合車輛路徑問題[J]. 中國管理科學，2012，20（2）：121-128.

[5] 郎茂祥. 裝卸混合車輛路徑問題的模擬退火算法研究[J]. 系統(tǒng)工程學報，2005，20（5）：485-491.

[6] 穆東，王超，王勝春，等. 基于并行模擬退火算法求解時間依懶型車輛路徑問題[J]. 計算機集成制造系統(tǒng)，2015，21（6）：1626

-1636.

[7] 魏江寧，夏唐斌. 基于混合模擬退火算法的多階段庫存路徑問題研究[J]. 工業(yè)工程與管理，2015，20（3）：1-8.

[8] M Mirabi， SMTF Ghomi， F Jolai. Efficent stochastic hybrid heuristics for the multi-depot vehicle routing problem[J]. Robotics and Computer-Integrated Manufacturing， 2010，26（6）：564-569.

[9] 馬建華，房勇，袁杰. 多車場多車型最快完成車輛路徑問題的變異蟻群算法[J]. 系統(tǒng)工程理論與實踐，2011，31（8）：1508

-1516.

[10] 辛穎. 基于蟻群算法的車輛路徑規(guī)劃問題求解研究[D]. 長春：吉林大學（碩士學位論文），2015.

[11] 陳迎欣. 基于改進蟻群算法的車輛路徑優(yōu)化問題研究[J]. 計算機應用研究，2012，29（6）：2031-2034.

[12] 段征宇，楊東援，王上. 時間依賴型車輛路徑問題的一種改進蟻群算法[J]. 控制理論與應用，2010，27（11）：1557-1563.

[13] 馬炫，彭M，劉慶. 求解帶時間窗車輛路徑問題的改進粒子群算法[J]. 計算機工程與應用，2009，45（27）：200-204.

[14] 吳耀華，張念志. 帶時間窗車輛路徑問題的改進粒子群算法研究[J]. 計算機工程與應用，2010，46（15）：230-235.

[15] Yang X S. A new metaheuristic bat-inspired algorithm[C] // Nature-Inspired Coopreative Strategies for Optimization， 2010：65

路徑規(guī)劃典型算法范文第5篇

Key words:distribution regional division; distribution vehicle routing optimization; algorithm

0 引 言

流通領域中,許多物流配送企業(yè)借助外部經(jīng)濟的發(fā)展,實現(xiàn)了規(guī)模擴張與快速發(fā)展,但對如何控制成本,提高運營效率的迫切性并不強?，F(xiàn)在隨著經(jīng)營環(huán)境的變化,物流需求量更大,客戶、網(wǎng)絡更復雜,對服務的要求更多樣化。但面臨的競爭更加激烈,不管是從事跨區(qū)域配送還是城市配送,首先需要考慮顧客服務水平,贏得客戶的認可,然后考慮配送運營的成本問題,因而如何創(chuàng)新物流服務,提高運營效率和控制日常運營成本成為每個配送企業(yè)需要時刻思考的問題。

傳統(tǒng)的基于經(jīng)驗的方法,在企業(yè)規(guī)模有限,客戶數(shù)量不是非常多,配送網(wǎng)絡相對簡單的情況下,只要員工和管理者技能過關,執(zhí)行力好,都應該能夠較好地完成配送任務,獲得企業(yè)的發(fā)展。但是隨著銷售區(qū)域擴大,客戶數(shù)量的不斷增加,客戶需求持續(xù)增長,配送業(yè)務量大增,配送周期縮短,配送線路更復雜,并且需求的隨機性、變動性加大,光憑經(jīng)驗和手工安排,已無法做到配送計劃的優(yōu)化,必須借助于統(tǒng)計分析、利用數(shù)學模型和智能算法,才能獲得較好的配送計劃,節(jié)省時間,提高效率。本文就是針對這些問題,從企業(yè)應用的角度,提出先合理劃分配送區(qū)域,再優(yōu)化配送路線的方法,從而達到降低成本,提高競爭力的目標。

1 論文總體思路綜述

排單和車輛調度是整個配送計劃和作業(yè)實施的核心,是配送任務和客戶服務按時完成的有力保證。

傳統(tǒng)的訂單排單和車輛調度、路線安排都是由公司里業(yè)務能手來完成,送貨區(qū)域大了,客戶多了,這項工作的效率和完成工作的成本控制都會不理想,現(xiàn)在常用的智能優(yōu)化方法,把它作為一個典型的VSP問題,建立數(shù)學模型,利用智能化的算法,求解可行的配送路徑規(guī)劃,作為理論研究,這樣的做法是有意義的。但是有兩個問題:(1)這個模型數(shù)據(jù)的收集整理工作量特別大,計算過程也較長,因而成本不會低。(2)模型本身一定要適合實際的作業(yè)過程,這就需要有一個不斷測試和優(yōu)化的過程,并且還要適應每天的動態(tài)變化,否則反而會影響到日常的作業(yè)過程。許多研究理論完備、精深,但是在適應產(chǎn)業(yè)化運營時,工程上的可實現(xiàn)性還有待提高和完善。因而影響了這些很有價值的研究在企業(yè)實際中的運用。

本文的研究并不針對配送路徑規(guī)劃做理論上的深究,而是立足實際應用,在可接受的范圍內,利用較簡易實用的智能優(yōu)化方法,在較短的時間內,以較低的成本獲得相對優(yōu)化的配送路徑規(guī)劃方案。不求最佳,但求有效。為今后電子排單和送貨線路優(yōu)化軟件的開發(fā)和應用作必要的鋪墊。

具體設想:第一步,利用聚類分析法對配送區(qū)域進行合理分區(qū),先把復雜問題簡單化。第二步,每個分區(qū)內就是個典型的TSP問題,有很成熟的解決辦法。在平衡好各分區(qū)工作時間安排后,就能很快獲得較理想的配送方案。

重點是第一步,分區(qū)時一定要考慮到客戶位置、需求量、車輛載重、作業(yè)時間均衡限制等因素,需要花費好多功夫。

2 配送區(qū)域動態(tài)優(yōu)化及其方法

2.1 配送區(qū)域的初始劃分方法。配送區(qū)域優(yōu)化方法對最終優(yōu)化的結果有很大的影響,因而合理的劃分方法的選擇十分重要,目前常用的劃分方法有掃描法和聚類算法,在配送客戶有限、區(qū)域較小時運用掃描法就可以了,但是當客戶數(shù)量很多,區(qū)域較大,又要考慮約束條件時,聚類算法就是我們必然的選擇了,聚類算法中K- means比較成熟,操作簡單,原理是:把大量d維(二維)數(shù)據(jù)對象n個聚集成k個聚類k 在運用聚類分析法時有幾個問題要注意:第一,k的選擇,以一天送貨總量/單車載重量,也可以放寬一些,到:一天送貨總量/單車載重量+1。第二,k個聚類內的密度,分區(qū)密度大,效率高,成本低。第三,每個分區(qū)內工作時間大體相當,這樣便于運行的穩(wěn)定,進行成本控制和人員、車輛的考核。第四,每個聚類間不重合。做到這樣分區(qū)效果會比較好。

傳統(tǒng)的K-means聚類法,k個聚類區(qū)內,初始點是隨機產(chǎn)生的,運行時間長,收斂效果差。基于均衡化考慮,在配送對象分布不均勻時,用密度法效果較好,初始中心點以密度來定義,運用兩點間歐氏距離方法,求解所有對象間的相互距離,并求平均數(shù),用meanD表示,確定領域半徑R,n是對象數(shù)目,coefR是半徑調節(jié)系數(shù),0 coefR=0.13時,效果最好。如果使用平均歐

氏距離還不理想,可增加距離長度,甚至用最大距離選擇法,收斂速度比較快。 在配送對象分布較均勻時,可考慮用網(wǎng)格法,效果較好,整個配送區(qū)域劃分用k=Q/q,k為初始點個數(shù),假設k=mn,將地圖劃分成m行n列,以每格中心點為初始點,通過網(wǎng)格內的反復聚類運算,達到收斂,獲得網(wǎng)格穩(wěn)定的聚類中心。

2.2 分區(qū)內配送工作量的均衡。這樣就完成了配送區(qū)域的初步劃分,但是沒有考慮各個分區(qū)內工作量的均衡問題,如果工作量不均衡,對于客戶服務水平的保證,成本的控制,作業(yè)的安排,人員、車輛的考核都存在問題。

在實際的物流企業(yè)配送作業(yè)過程中,一般一輛車一天也就送貨10多家或20來家,多余的時間要用于收款,與公司財務部門交賬,核算出車相關費用,所以不考慮同一車同一天出車多次的情況,多次出車待以后深入探討。那么就意味著每個分區(qū)就是一輛車一條線路,把問題大大簡化了,需要說明的是:這種方法對于配送規(guī)模不是特別大的單個城市配送是適用的,也具有廣泛性。

各分區(qū)內的每日配送工作量是以配送作業(yè)耗用時間來衡量的,耗用時間有兩部分構成:(1)車輛行駛時間;(2)客戶服務時間。由于配送分區(qū)有限,每個分區(qū)內的客戶數(shù)量不是很多,可以采用實地測時的方式,把每條線路的配送時間統(tǒng)計出來,這是一種手工辦法,但比較符合實際來調整超過差值的分區(qū)內的客戶,從而使得各區(qū)作業(yè)時間基本均衡。

如果客戶數(shù)量眾多,分區(qū)也較復雜,就需要借助統(tǒng)計學方法,通過對樣本線路車輛行駛時間以及服務時間,擬合出分區(qū)作業(yè)時間函數(shù),然后,計算出所有線路作業(yè)時間,即使分區(qū)重新調整,線路重新組合,仍可以很快計算出線路作業(yè)時間。本文不在這個方面進行深入探討。

2.3 重新組合客戶,確定最終區(qū)域劃分。觀察各線路作業(yè)時間超過允許差值的部分,由大到小來調整,將離聚類中心最遠的數(shù)據(jù)點彈出,使本區(qū)T值下降,直至在差值以內,將彈出點加入到臨近的不足均衡作業(yè)時間的分區(qū)內,如果臨近分區(qū)作業(yè)時間超過允許差值,這個點就不能彈出,只能彈出另外的次遠數(shù)據(jù)點,以此類推,任何一個數(shù)據(jù)點只能彈出一次,直到所有數(shù)據(jù)點和分區(qū)調整完畢。

這樣最終確定的分區(qū),既能做到區(qū)域劃分緊密,效率、成本更低,又能做到各區(qū)作業(yè)時間均衡,便于工作指派,車輛、人員核算。

以上是本文的第一部分工作,也是最有意義的工作,確定好合理的區(qū)域劃分,不僅是配送作業(yè)合理化的重要步驟,也是業(yè)務人員訪銷工作和客戶服務的重要依據(jù)。

3 基于改進蟻群算法的分區(qū)線路優(yōu)化方法

分區(qū)內線路安排,就是一輛送貨車由DC出發(fā),依次經(jīng)過分區(qū)內每一個客戶點,完成送貨后返回DC,求出近似最優(yōu)的行車順序,這是個典型的旅行商問題(Traveling Salesman Problem,TSP),TSP是NP完全問題,解法很多,有精確算法,也有啟發(fā)式算法,目前許多智能算法就屬于啟發(fā)式算法,可以解決較復雜的線路優(yōu)化問題,對于一般線路優(yōu)化也能做得更準確,這里介紹蟻群算法解決實際問題。原因是蟻群算法與其他啟發(fā)式算法相比,在求解性能上,具有較強的魯棒性和搜索較好解的能力,是一種分布式的并行算法,一種正反饋算法,易于與其它方法結合?？朔舅惴ㄈ秉c,改善算法性能。

3.1 蟻群算法簡介。蟻群算法(Ant Colony Algorithm, ACA)是由意大利學者M.Dorigo等人于20世紀90年代初提出的一種新的模擬進化算法,其真實地模擬了自然界螞蟻群體的覓食行為。 M.Dorigo等人將其用于解決旅行商問題TSP,并取得了較好的實驗結果。

蟻群算法用于解決優(yōu)化問題的基本思路是:用螞蟻的行走路徑表示待優(yōu)化問題的可行解,整個螞蟻群體的所有路徑構成待優(yōu)化問題的解空間。路徑較短的螞蟻釋放的信息素數(shù)量較多,隨時間推移,較短路徑上積累的信息素濃度逐步增高,選擇該路線的螞蟻數(shù)量也越來越多,最終整個螞蟻會在正反饋的作用下集中到最佳線路上,這個路線就是最有解。

蟻群算法解決TSP問題具體步驟:(1)基本參數(shù)設置:包括螞蟻數(shù)m,信息素重要程度因子0≤α≤5,啟發(fā)函數(shù)重要因子1≤β≤5,信息素消逝參數(shù)0.1≤ρ≤0.99,信息素釋放總量10≤Q≤10 000,最大迭代次數(shù)iter_max,迭代次數(shù)初值iter=1。用試驗方法確定α、β、ρ、Q值,以獲得較優(yōu)的組合,有助于改進基本蟻群算法,提高整體優(yōu)化效果,并縮短運算時間。(2)初始解的求解:利用最近鄰算法,以縮短算法運算時間,并以此算法產(chǎn)生初始解的路徑長度作為產(chǎn)生初始信息素的基礎。 (3)構建解空間:將各個螞蟻隨機地置于不同出發(fā)點,對每個螞蟻,按公式(1)計算其下一個待訪問的網(wǎng)點,直到所有螞蟻訪問完區(qū)域內所有網(wǎng)點。(4)更新信息素:計算各個螞蟻經(jīng)過的路徑長度Lk=1,2,…,m,記錄當前迭代次數(shù)中的最優(yōu)解。同時,根據(jù)(2)式和(3)式對各個網(wǎng)點連接路徑上的信息素濃度進行更新。(5)判斷是否終止:若iter 蟻群算法如結合其他啟發(fā)式算法,建立混合算法,能夠解決許多現(xiàn)實問題,達到較好運算效果,結合具體問題,可以深入研究。

4 本文的局限與進一步研究的方向