時間：2023-09-28 16:01:31
導語：在路徑規劃典型算法的撰寫旅程中，學習并吸收他人佳作的精髓是一條寶貴的路徑，好期刊匯集了九篇優秀范文，愿這些內容能夠啟發您的創作靈感，引領您探索更多的創作可能。
文章提出了一種基于時間成本的物流線路優化方法，通過科學規劃配送線路、平衡每日訂單分布等方式，使卷煙網絡分布更加合理，進一步降低固定投入和業務成本，提高供應鏈管理水平。
二、算法模型
基于時間成本的物流線路優化計算主要運用到三個求解算法，分別是聚類算法、最優路徑算法和訂單日規劃算法?；厩蠼夥桨甘牵旱谝徊桨凑哲囕v裝載率完成對客戶興趣點聚類；第二步細致優化配送路徑；第三步平衡每日訂單分布。
1.聚類算法
聚類是空間數據挖掘中的一個重要研究領域，是指將物理的或抽象的對象分組成為由類似對象組成的多個類（簇）的過程。
以紹興煙草為例，聚類計算時首先采用自下而上的一階段方法對全地區26000個零售戶點進行聚類，獲得411個初始聚類結果。再根據實際需求，按照類容量將前408個類作為直接指派的初始類核，以配送車裝載率90%作為類容量上限，進行直接指派聚類，最終獲得聚類結果。
2.最優路徑算法
最優路徑算法的目標是尋找給定起點和終點間的最短路徑，文章采用Dijkstra（迪杰斯特拉）算法。Dijkstra算法是典型的單源最短路徑算法，用于計算一個節點到其他所有節點的最短路徑。主要特點是以起始點為中心向外層層擴展，直到擴展到終點為止。
⑴初始時，S只包含源點，即S=v。U包含除v外的其他頂點，U中頂點u對應的距離值為邊上的權（若v與u有邊）或 （若u不是v的出邊鄰接點）。
⑵從U中選取一個距離v最小的頂點k，把k，加入S中（該選定的距離就是v到k的最短路徑長度）。
⑶以k為新考慮的中間點，修改U中各頂點的距離；若從源點v到頂點u的距離（經過頂點k）比原來距離（不經過頂點k）短，則修改頂點u的距離值，修改后的距離值為頂點k的距離加上邊上的權。
⑷重復步驟（2）和（3）直到所有頂點都包含在S中。
3.配送工作量模型和訂單日規劃算法
進行訂單日規劃時，文章引入工作量模型概念，將綜合作業時間作為線路優化的單一標準，把送貨戶數、送貨量、行駛里程等多維度統一轉換成工作時間，解決線路優化時指標過多，計算困難的問題。
綜合作業時間=裝車交接時間+車輛行駛時間+基本服務時間+客戶交接時間+現金繳款時間。裝車交接時間=（裝車準備時間車次）+（裝車框數單框裝車時間）
訂單日規劃算法的目標是確定各配送線路的配送車輛和配送日，規劃要求滿足以下約束條件：車輛數最少；一周內各配送車輛工作時間基本均衡；每天各配送車輛工作時間基本均衡；每天工作時間上限設定6.5小時。
訂單日規劃算法模型：
約束條件：
（1.1）
（1.2）
（1.3）
（1.4）
i 需要安排的路線序號；取值范圍從1到路線的最大數；
j 送貨車序號；取值范圍從1到指定車輛數；
k訂單日的序號；取值范圍從1到5，表示一周配送5天；
b每天所有車輛工作時間的上限；
c每輛車一周工作量上限；
d每輛車每天工作量的上限，d為6.5小時。
公式（1.1）一條路線有卻只能有某輛車在某一天配送；
公式（1.2）每天所有車
的工作量不能超過上限b；
公式（1.3）每輛車每周的工作量不能超過上限c；
公式（1.4）每輛車一天的工作量不能超過上限d。
關鍵詞：射線跟蹤，規劃仿真，傳播模型
一、概述各移動運營商及移動通信相關技術咨詢單位在進行規劃方案驗證時，傳統的方法是通過規劃仿真軟件使用宏蜂窩傳播模型及20米精度三維電子地圖對規劃方案進行仿真驗證；然而，宏蜂窩傳播模型的應用范圍和自身局限性限制了規劃方案仿真驗證的精度：首先，宏蜂窩傳播模型的應用范圍一般在500米以上，而CBD區域基站的覆蓋半徑一般在500米以下。其次，宏蜂窩傳播模型只能從宏觀上反映方案覆蓋效果，無法根據建筑物的高度從微觀上反映局部的覆蓋情況。因此，需要采用更合適的傳播模型配合高精度的三維電子地圖對CBD區域的規劃方案進行仿真驗證，以確保該重點區域無線網絡建成后的網絡性能。
目前射線跟蹤模型作為一種高精度的規劃仿真傳播模型在大中型城市覆蓋重點區域的規劃方案仿真驗證中得到廣泛應用。本文首先對射線跟蹤模型的原理進行探討，然后以WaveCall公司的WaveSight模型為例說明射線跟蹤模型的應用方法。其結果有助于應用射線跟蹤模型對規劃方案進行精確驗證，對規劃工作有積極的參考和指導作用。
二、射線跟蹤模型簡介2.1 微蜂窩傳播模型介紹 當前傳播模型根據應用范圍可分為宏蜂窩傳播模型和微蜂窩傳播模型，宏蜂窩傳播模型應用范圍為1km至幾十km；而微蜂窩傳播模型應用范圍僅為幾百米，一般只適用于基站附近區域。免費論文。由于CBD區域基站的覆蓋一般在500米以內，因此應用微蜂窩傳播模型對該區域規劃方案的效果進行仿真驗證更為合適。
微蜂窩傳播模型根據模型建立方法，可分為經驗模型，確定性模型以及混合模型；
l經驗模型
經驗模型是在大量測量的基礎上產生的，該模型與室外傳統宏蜂窩傳播模型類似，不考慮理論計算，對基站附近測量大量數據后統計歸納出經驗模型。
l確定性模型
確定性模型是依據電波傳播理論計算出接收點與發射點之間的傳播損耗。射線跟蹤模型是一種典型的確定性模型，確定性模型不考慮測量，僅在確定計算公式中的個別參數時需要測量驗證。
l混合模型
混合模型結合了經驗模型和確定性模型，一方面混合模型以電波傳播理論為依據得出電波的傳播模型，同時需要對基站附近測量大量數據以統計確定傳播模型中的參數值。
2.2 射線跟蹤模型介紹 射線跟蹤模型是一種確定性模型，其基本原理為標準衍射理論（Uniform Theory ofDiffraction，簡稱UTD）。根據標準衍射理論，高頻率的電磁波遠場傳播特性可簡化為射線（Ray）模型。因此射線跟蹤模型實際上是采用光學方法，考慮電波的反射、衍射和散射，結合高精度的三維電子地圖（包括建筑物矢量及建筑物高度），對傳播損耗進行準確預測。
由于在電波傳播過程中影響的因素過多，在實際計算預測中無法把所有的影響因素都考慮進去，因此需要簡化傳播因素；射線跟蹤算法把建筑物的反射簡化為光滑平面反射、建筑物邊緣散射以及建筑物邊緣衍射。
根據考慮路徑的種類不同，射線跟蹤模型可分為三種：
l2D射線跟蹤模型
只考慮水平切面的傳播路徑，即第一類路徑。
l3D射線跟蹤模型
只考慮水平切面以及垂直切面的傳播路徑，即第一類及第三類路徑。
l全3D射線跟蹤模型
考慮所有傳播路徑，即考慮所有第一、二、三類路徑。
三、射線跟蹤模型基本原理射線跟蹤模型的基本原理是簡化傳播因素，采用光學方法定位傳播路徑并計算各接收點與發射點之間的路徑損耗；因此，射線跟蹤模型的關鍵在于如何定位接收點與發射點之間的傳播路徑并計算路徑損耗。免費論文。
3.1 水平切面的傳播損耗從發射源在接收點之間可能存在很多傳播路徑，但是一般只有一到兩條強度最強，在傳播中起主導作用的主導傳播路徑。路徑損耗計算時只需計算主導傳播路徑的損耗即可。免費論文。
3.2 垂直切面的傳播損耗 相對于水平切面的傳播損耗，垂直切面的傳播損耗計算要簡單一些，計算垂直切面的傳播損耗時，需要首先確定發射源與接收點之間的垂直傳播路徑，然后計算其中各個刀鋒衍射損耗，其路徑損耗為各刀鋒衍射損耗之和。
3.3 射線跟蹤模型簡要結論 根據射線跟蹤模型的理論以及相關資料，可以得到射線跟蹤模型的簡要結論如下：
1.對近距離的場強預測， 水平切面算法（2D射線跟蹤算法）起主導作用。
2.全3D方向算法中全3D路徑（即第三類路徑）對遠距離的場強預測準確性影響很大。
3.在整齊規劃的建筑群中，對遠距離的場強預測，垂直切面算法可取代全3D方向算法。
四、射線跟蹤模型的應用 本節主要以WaveCall公司的WaveSight射線跟蹤模型為例，對射線跟蹤模型的應用進行說明。
WaveCall公司的WaveSight射線跟蹤模型作為AIRCOM公司的規劃軟件Enterprise的插件，可用于高精度的規劃方案仿真驗證。該模型基于標準衍射理論及射線跟蹤算法，綜合考慮電波傳播范圍內建筑物的輪廓、高度、地形剖面圖，對電波的傳播特性進行準確預測。
WaveSight模型是一種3D射線跟蹤模型，該模型包括兩種類型路徑：水平切面路徑以及垂直切面路徑。
對比傳統射線跟蹤模型，WaveSight 具有優點十分明顯：首先，WaveSight射線跟蹤模型采用了不同于傳統射線跟蹤模型的算法，空前地提高了計算效率：該模型完成一個基站的覆蓋預測所需時間僅是傳統射線跟蹤模型所需時間的1/3左右，不僅保證了覆蓋預測的精度，同時還保證了覆蓋預測的速度。此外，WaveSight 模型使用簡單，該模型不需要使用測試數據對其進行調校，僅需要輸入兩個參數：使用頻率及接收端高度。
WaveSight 射線跟蹤模型的缺點是：僅適用于市區環境，對電子地圖精度要求較高，不僅要求地圖精度必須達到5m 以上，而且要求提供建筑物矢量信息以及高度信息。
五、結論及后續工作 本文首先對射線跟蹤模型的原理進行探討，然后給出射線跟蹤模型的簡要結論，最后以WaveCall公司的WaveSight模型為例說明射線跟蹤模型的應用方法。其結果有助于應用射線跟蹤模型對規劃方案進行精確驗證，對規劃工作有積極的參考和指導作用。
今后研究工作可以再上述研究基礎上進一步展開，對全3D射線跟蹤算法進行進一步的探討，同時也可以對其它射線跟蹤模型如WinProp模型等進行研究，
進一步研究射線跟蹤傳播模型算法，更精確地城市CBD區域進行預測，指導網絡的規劃及優化工作。
【參考文獻】
1．WaveCall公司；《WaveCallPropagationWhitePaper》；2001
2．WaveCall公司；《WavecallCaseStudy》；2001
關鍵詞:C-W算法;配送車輛優化調度;啟發式算法
中圖分類號:TP312文獻標識碼:A文章編號:1009-3044(2010)09-2132-02
Application of C-W Algorithm in Logistics Distribution Vehicle Scheduling
CAO Jing-xia1,2
(1.School of Information Engineering, Jiangnan University, Wuxi 2141222, China; 2.Jiangyin Polytechnic College, Jiangyin 214400, China)
Abstract: Logistics Distribution Vehicle Scheduling is a very crucial step in the process of logistic distribution. This paper briefly describes the most representative algorithm, points out that the heuristic algorithm is the main method to solve vehicle routing problem, and demonstrates its applicability to solving the problem of vehicle scheduling by citing the examples of C-W algorithm, a typical method among the heuristic algorithm.
Key words: C-W algorithm; delivery vehicle scheduling; heuristic algorithm
隨著我國市場經濟的建立和發展,作為“第三利潤源泉”的物流日益受到政府有關部門和廣大企業的重視,成為當前最重要的競爭領域。配送是物流活動中直接與消費者相連的環節,在物流的各項成本中,配送成本占了相當高的比例。配送車輛調度的合理與否對配送速度、成本、效益影響很大,采用科學、合理的方法來進行配送車輛調度,是物流配送中非常關鍵的一環。
1 物流配送車輛路徑問題(VRP) 概述
物流配送車輛路徑問題(Vehicle Routing Problem ,VRP) 最早是由Dantzig 和Ramser于1959年提出的,一經提出立即引起了運籌學、物流科學、計算機應用等學科專家和運輸問題制定和管理者的極大關注。
該問題的研究目標是對一系列的顧客需求點設計適當的路線,使車輛有序地通過它們,在滿足一定的約束條件(如貨物需求量、發送量、交發貨時間、車輛容量限制、行駛里程限制、時間限制等) 下, 達到一定的優化目標(如里程最短、費用最少、時間盡量少、車隊規模盡量小、車輛利用率盡量高等)。
2 VRP問題的求解算法
VRP問題是組合優化領域著名的NP難題之一,即隨著客戶數量的增加,可選的配送路徑方案數量將以指數速度急劇增長,即出現組合爆炸現象,因此通常的做法就是應用相關技術將問題分解或者轉化為一個或者多個已經研究過的基本問題,再使用相對比較成熟的基本理論和方法求解。VRP問題的求解方法基本上可以分為精確算法和啟發式算法兩大類。
2.1 求解VRP問題的精確算法
求解VRP問題的精確算法主要運用線性規劃、整數規劃、非線性規劃等數學規劃技術來描述物流系統的數量關系,以便求得最優解。求解VRP問題常用的精確算法有分枝定界法、割平面法、動態規劃法、網絡流算法等。這些方法從理論上給出了VRP問題精確求法,在可以求解的情況下,其解通常要優于啟發式算法。由于精確算法在求解時引入了嚴格的數學方法(手段),因而無法避開指數爆炸問題,使其獲得整個系統的最優解越來越困難,因此,這些算法都是針對某一特定問題設計的, 適用能力較差, 在實際中其應用范圍很有限。
2.2 求解VRP問題的啟發式算法
為了克服精確算法的不足,可以運用一些經驗法則來降低優化模型的數學精確程度,并通過模仿人的跟蹤校正過程來求取運輸系統的滿意解,為此專家們主要把精力花在構造高質量的啟發式算法上。啟發式算法能同時滿足詳細描繪和求解問題的需要,較精確式算法更加實用。
目前己經提出的啟發式算法很多,按照Cesar Reg的分類法,基本可以分為構造啟發式算法(節約算法、最鄰近法、插入法、掃描法)、兩階段啟發式算法、不完全優化算法和智能化啟發式算法(禁忌搜索算法、模擬退火法、遺傳算法、神經網絡算法、蟻群算法、微粒群算法等)四類。啟發式算法中由Clarke 和Wright 在1964 年提出的節約法(簡記為C-W算法)具有非常典型的代表性。
3 C-W算法的應用
3.1 定義與原理
C-W算法是根據物流中心的運輸能力和物流中心到各送/ 取貨點以及各個送/ 取貨點之間的距離,制訂使總的車輛運輸噸公里數(或者時間或者費用)最小的方案。
C-W算法的基本思路如圖1所示,已知P點為配送中心,它分別向用戶A 和B送貨。設P點到用戶A 和用戶B 的距離分別為a 和b。用戶A 和用戶B 之間的距離為c,現有兩種送貨方案,如圖1(a)和(b)所示。
在圖1(a)中配送距離為2(a+b);圖1(b)中,配送距離為a+b+c。對比這兩個方案,2(a+b)-(a+b+c)=a+b-c,很明顯,由三角形的幾何性質可知, 三角形中任意兩條邊的邊長之和大于第三邊的邊長。即:a+b-c>0 。連接AB所得的節約量是a+b-c。
3.2 實例
為了使C-W算法體現較為明了,選取較典型的實例介紹。假設配送中心使用同類型的配送車(主要是裝載量和容積相同),保證一條線路上各用戶的貨運量之和不大于車輛的載重量。
基本資料介紹:
現有6個用戶(標號是1,…,6),各個用戶的貨運量是gi(噸)(i=1,…,6),這些用戶由配送中心(標號是0)發出的載重量為8噸的車輛完成配送任務,要求最后的路線安排使總距離最小。具體數據見表1、表2。
首先,把各個點單獨與配送中心相連,構建僅含一個點的初始路線,得到總的距離為:2*(40+60+75+90+200+100)=1130km
然后,連接兩兩用戶到同一條線路上得到節約值(節約量公式a+b-c),節約值越大,說明兩用戶連在一起時運距減少的越多,如果是負值就不應該把兩用戶連在同一條線路上。
C-W算法解題步驟:
1)計算各用戶之間的節約值(節約量公式a+b-c)
例如:連接用戶1和用戶2時,節約量=40+60-65=35
連接用戶3和用戶5時,節約量=75+200-50=225,類似可以得到其他,如表3。
2)按照從大到小的順序排序,見表4。
表4 節約里程排序表
3)連接點對,見表5。
根據表,得到最后的路線安排如下:
0-3-5-6-0
0-1-2-4-0
比初始路線節約運距:230+225+50+35=540km
通過使用C-W算法,對配送線路進行組合以后,由原來的6條初始化線路,減少到2條組合線路, 運行距離從開始的1130km 縮短為590 km ,節約的里程相當可觀。不難明白, 中國的物流行業是一座金山。只有不斷進行物流管理和技術創新,提高物流效率, 才可能大幅降低整個業務成本。
參考文獻:
[1] 李如姣.“節約里程法”在某物流公司配送中心的實際運用[J].科技咨詢,2008(28):156-158.
[2] 方金城,張岐山.物流配送車輛路徑問題(VRP)算法研究[J].徐州工程學院學報,2007(2):84-88.
關鍵詞：量子行為粒子群算法；冷鏈物流；客戶滿意度
中圖分類號：N945.12 文獻標識碼：A 文章編號：1008-4428（2016）10-12 -03
一、引言
隨著現代化制冷技術的發展，海、陸、空運輸網絡的建立，人們對生鮮冷凍食品的品質和安全提出了更高的要求，這為冷鏈物流的發展提供了有力的契機。冷鏈物流是指以保證易腐食品品質為目的，以保持低溫環境為核心，以現代化制冷技術為手段的物流信息管理和配送系統。然而我國冷鏈物流的發展起步較晚，在物流設施、冷藏技術設備及配送管理等方面與歐、美、日發達國家差距較大。據不完全統計，我國每年由于冷鏈物流問題所帶來的經濟損失高達100億美元。因此，優化配送運輸路徑成為降低社會經濟損失，提高企業經濟效益的有效途徑之一。
二、文獻綜述
物流配送運輸路徑優化方法主要包括精確算法和群體智能算法兩種。由于群體智能算法的并行性、分布式、易操作性等特點使得遺傳算法、粒子群、蟻群等典型的群體智能算法在冷鏈物流研究中得到廣泛的應用。劉鎮等人在考慮多源實時交通信息的基礎上建立了運輸成本和配送時間的優化模型，并在云計算環境下利用粗粒度并行遺傳算法對模型假設進行了有效性的驗證；陶榮綜合考慮配送、貨損與懲罰三個主要成本要素建立了帶有時間窗的優化配送運輸模型，并通過蟻群算法驗證了模型的有效性和可行性。他所提出的多溫共配思想為冷鏈物流的發展注入了新鮮血液；量子粒子群（QPSO）優化算法是在粒子群（PSO）優化算法的基礎上，從量子力學的角度提出的一種新型算法。QPSO算法通過建立δ勢阱模型使處于量子束縛態的粒子按照一定的概率密度實現全局收斂，已經證實QPSO算法克服了PSO算法因速度限制搜索空間受限的問題。本文采用量子粒子群優化算法實現模型假設的驗證。
三、冷鏈產品物流配送路徑優化模型
冷鏈產品物流配送路徑優化問題可描述為在一定范圍內和約束條件下，將冷鏈產品通過儲運的方式實現在多個配送中心與供給客戶之間的空間位移，并使目標函數達到最優化。
假設冷鏈產品的配送中心有M個，運輸車輛有P輛（載重量均為r），客戶有N個（貨物需求為ni其中i=1，2，…，N），且每輛運輸車完成任務后均返回配送中心。客戶與配送中心的編碼分別為1，2，…，N，N +1，N+2，...，N+M；變量定義如下：
其中客戶在[Bi，Li]內的意度為1，在該區間以外客戶的滿意度隨時間ti而線性減少，α，β是客戶對時間的敏感系數。
冷鏈產品的儲運直接影響產品的質量與安全，因此，需同時考慮物流運輸路徑最短和客戶滿意程度兩個最優化問題，構建數學建模如下：
其中Dij表示兩個客戶i，j之間的距離； 配送中心M具有PM輛儲運貨車。
目標函數需滿足如下約束條件：
（1）參與儲運的車輛不能超出配送中心的總車輛數，即
（2）參與儲運的車輛的承載數量是有限的，約束如下：
（3）每個客戶配送服務僅一次
（4）配送路徑無子回路
在目標函數中引入罰函數以約束車輛容量，
其中ξ取值足夠大時不可行解在迭代過程中將被淘汰。
四、基于QPSO算法的物流運輸路徑優化問題
（一） QPSO算法
QPSO算法從量子力學理論出發，通過建立δ勢阱模型束縛粒子，在收索空間中受量子束縛的粒子以一定的概率密度分布，當粒子與中心的距離趨于無窮大時，其概率密度趨于零。
在一個M維的目標搜索空間中，由N個粒子組成的種群的決策變量為粒子第t次迭代的位置向量Xti，Xti=（Xti1， Xti2，…，xtim）， 粒子個體最好位置為Pti， Pti=（ Pti1， Pti2，…，Ptim）以最小優化問題minf（x）為例，Pti由下式確定：
當參數γ由1.0線性遞減到0.5時效果較好。
（二）粒子編碼
構造X1與X2兩個N維子向量。X1為車輛信息，X1∈[1，p]，X2為車輛儲運路徑信息。假設2個配送中心，對12個客戶進行儲運服務，每個配送中心所擁有的車輛數分別為2，3，且這5輛車的編碼分別為1至6。
（三）基于QPSO算法的物流運輸路徑規劃算法
QPSO算法流程如下：
第一步：取種群規模為N，最大迭代次數T，對粒子進行編碼；
第二步：粒子初始位置Xi0，取個體最好位置P0i=X0i；
第三步：利用公式（4-3）計算平均最好位置；
第四步：利用公式（3-3）計算Xti的適應值，利用公式（4-1）計算更新粒子的當前最好位置；
第五步：當粒子的適應值優于Ptg時，更新Ptg；
第六步：利用公式（4-2）置換粒子位置Xit+1；
第七步：轉第三步繼續迭代，達到迭代次T結束；
（四）仿真實驗結果與分析
假設某地由3個配送中心對該地區的15個門店提供儲運服務，每個配送中心1，2，3的車輛數分別為2，2，2，6輛車的編碼分別為1，2，……，6；14個客戶及3個配送中心在XOY平面的位置信息如下表2，表3所示
通過Matlab7.0對QPSO算法進行計算機仿真實驗。結果表明了QPSO算法的可行性和有效性。儲運路線如圖1所示。
經粒子解碼得到有效路徑為：
配送中心1的車輛1：15101415
配送中心1的車輛2：154215
配送中心2的車輛3：16516
配送中心2的車輛4：1693716
配送中心3的車輛5：171211117
配送中心3的車輛6：17138617
仿真實驗結果如下：
由上表可見QPSO算法在解決冷鏈產品物流儲運路徑問題中呈現出較強的穩定性與收斂性。
五、結束語
隨著中國消費者對冷鏈產品需求量的增加及對產品質量安全性的重視，為冷鏈物流的發展提供了機遇，研究冷鏈產品的儲運優化路徑，是提高物流企業競爭力及消費者滿意度的關鍵。本文從現代物流管理理念出發，以冷鏈產品的儲運成本最小化與顧客的滿意程度最大化作為優化目標，使得算法的研究與實現更具有現實意義。
參考文獻：
[1]方凱，鐘漲寶，王厚俊.賀嵐基于綠色供應鏈的我國冷鏈物流企業效率分析[J].農業技術經濟，2014，（03）：50-53.
[2]邵瑞銀.河南省農產品冷鏈物流現狀、問題與對策[J].企業經濟，2013，（02）：15-17.
[3]劉鎮，徐優香，王譯.基于云計算的冷鏈物流配送車輛路徑優化方法研究[J]. 電子設計工程，2013，（04）：23-27.
[4]陶榮.基于蟻群算法的多溫共配冷鏈物流配送問題研究[J]. 物流技術，2014，（02）：31-34.
[5]孫俊. 量子行為粒子群優化[M].北京：清華大學出版社，2011，8.
[6]張仁堂，董海洲，喬旭光等.現代果蔬物流中冷鏈技術集成創新研究[J].世界農業，2007，9（3）：47―49.
關鍵詞：TSP；蟻群算法；NP完全問題
中圖分類號：TP301 文獻標識碼：A 文章編號：1009-3044（2013）13-3117-03
旅行商問題（Traveling Salesman Problem，簡稱TSP）是一個具有廣泛應用背景和重要理論價值的組合優化問題，它已被證明屬于NP難題[1]。目前對于求解該類問題的研究主要有兩個方向：一是傳統的數學規劃方法，這種算法可以得到全局最優解，但復雜性往往難以接受，因而不適應于大規模復雜問題的求解。二是近年來發展起來的各種仿生進化算法如遺傳算法、蟻群算法等，此類算法能夠在多項式時間內找到全局最優解或近似全局最優解[2]。蟻群算法（Ant Colony Algorithm， 簡稱ACA）是受自然界中螞蟻集體尋食過程的啟發而提出來的一種新的智能優化算法，它具有高度的本質并行性、正反饋選擇、分布式計算、魯棒性等優點，蟻群算法最早成功地應用于解決TSP問題。
本文在研究蟻群算法的基本優化原理的基礎上，編寫了一個基于VC的求解TSP問題的蟻群算法程序，并且通過多次實驗測試，驗證了算法的有效性，分析了螞蟻規模、周游次數等因素對蟻群算法的搜索結果和效率所產生的影響。
1 TSP問題建模
2 基于蟻群算法的TSP問題求解
2.2蟻群算法的基本原理
蟻群算法是一種源于自然生物界的新型仿生優化算法，它于20世紀90年代初由意大利學者M.Dorigo，V.Maniezzo首次提出[3]，蟻群算法的特點是模擬自然界中螞蟻尋食的群體行為。研究表明，螞蟻會在走過的路上留下信息素，信息素會隨時間的推移逐漸揮發消失，螞蟻就是通過信息素進行信息交流。螞蟻趨向于朝信息素積累較多的路徑移動，信息素濃度越高的路徑，選擇它的螞蟻就越多，則該路徑上留下的信息素濃度就越大，而高濃度的信息素反過來又會吸引更多的螞蟻，從而形成一種正反饋。通過這種正反饋機制，螞蟻最終可以發現最短的路徑，并且最后所有的螞蟻都會趨向于選擇這條最短路徑[4]。這就是蟻群算法的基本原理。
2.2求解TSP問題的蟻群算法設計
2.3算法步驟
4 結束語
本文探討了蟻群算法的基本優化原理，設計并實現了求解TSP問題的蟻群算法程序，通過實驗驗證了算法的有效性，同時，經過多次實驗測試結果，分析了對蟻群行為和算法的解產生影響的各個因素。
蟻群算法作為一種新的仿生進化算法，它在解決許多復雜組合優化問題方面顯示出了明顯的優勢，但也存在著諸如搜索時間較長等不足之處，因此，對算法的改進、收斂性分析及理論依據等方面還有待進一步深入研究。
參考文獻：
[1] 郭平，嫣文靜.求解TSP問題的蟻群算法綜述[J].計算機科學，2007，34（10）：181-184.
[2] 周康，強小利，同小軍，等.求解TSP算法[J].計算機工程與應用，2007（29）：43-47.
[3] DORIGO M， MANIEZZO V， COLORNI A. The ant system： optimization by a colony of cooperating agents[J]. IEEE Transaction on Systems，1996，26（1）：1-26.
關鍵詞：車輛路徑;節能減排;VRPRFC
背景
我國對車輛路徑問題的研究在20世紀90年代以后才逐漸興起，比國外相對落后。隨著客戶物質需求的多樣化不規則性以及經濟全球化趨勢的發展，運輸規劃的重要性日益顯著，近年來我國理論界逐漸開始關注車輛路徑問題的解決方法，已取得了較為顯著的成果。但總體來說，我國目前對車輛路徑問題的理論研究仍顯得不足，有待進一步的提高。隨著能源的日趨短缺和環境壓力的不斷增大，全社會節能、環保意識逐漸加強，節能減排成為了物流配送車輛路線優化的新突破。
本文從節能減排的角度研究車輛路徑問題（VRPRFC），并用遺傳算法求解，將建設節約型社會的全新理念貫徹到物流運輸發展過程中來。
1、VRPRFC模型的建立
1.1建立VRPRFC模型
令為客戶集合（其中0代表配送中心），為可供租賃的車輛集合，為可行解的路線集合。所有的可行路徑開始并結束于配送中心。令為兩點（和）之間的距離。令為客戶的需求，為車輛能力約束。由于點0表示配送中心，因此，。令為車輛在完成配送任務時，到達客戶前車上裝載的貨物量。令單位行駛里程空載油耗，為單位里程單位載重附加油耗。
定義決策變量，如果點 到點路線是由車輛來完成時，，否則，。由于車輛總是在配送中心（點0）裝載配送路線上的客戶需求貨物，因此。
基于節能減排的有能力約束的車輛路線優化問題數學描述如下：
式（1.1）表示本數學模型的優化目標為最小化油耗。約束條件（1.2）確保車輛每次配送任務量不超過其能力約束。等式（1.3）為平衡條件，確保車輛在某次配送任務中到達某需求點，則其也將在該次配送任務中離開該需求點。等式（1.4）確保某個客戶僅在一次配送任務中由一輛車輛提供服務。不等式（1.5）確保實現某次配送任務的車輛只離開配送中心一次。約束條件（1.6）確保不存在不經過配送中心的回路存在。約束條件（1.7）確保當時，車輛在配送任務中，從點運往點的貨物量等于該車到達點時的貨物量減去在點卸貨量（即用戶的需求），如圖1。
圖1 封閉式車輛路徑與的關系圖
Fig.1 The relationship between andof the closed one
2、遺傳算法求解
2.1編碼
現用遺傳算法解決VRPRFC問題，遺傳算法的個體編碼為一串整數，每個數字代表一個客戶或者分隔不同配送路線的標志，一串沒有被分隔標志分隔的客戶代表一條起止點為配送中心（標記為0）的配送路線。比如，假設配送中心有10個客戶，分別用1到10來表示，若估計最優配送計劃的路線不會超過5條，則可以用數字11到14作為分隔標志來分隔不同的配送路徑。由1到14的一個排列即表示一個配送計劃（該個體編碼不包含配送路徑由什么車輛完成的信息，車輛指派問題利用BFD算法求解），如個體編碼圖2。
圖2染色體編碼
Fig.2 Chromosome
即可以解碼為如下三條配送路線：
線路1：
線路2：
線路3：
2.2適應度函數
GA淘汰個體的原則是適應能力的強弱。個體的適應能力以適應度函數f(x)的值來判別的，這個值稱為適應度值（Fitness）。
f(x)的構成與目標函數有關，往往是目標函數的變種。
適應度函數的處理有：目標函數的確定、目標函數到適應度函數的映射、適應度值調整等。目標函數與具體問題緊密相關。TSP的目標函數是通過所有不重復城市的最短路徑規則歸納問題是找到覆蓋所有例子集的最小數目的規則，模糊神經網絡問題的目標是得到系統參數，使實際輸出與期望輸出達到盡可能小。個體適應度值是非負的，總是希望越大越好，而目標函數有正有負，因此，目標函數向適應度函數映射時，首先保證映射后的函數值為正，其次目標函數的優化方向對應于適應度值增大的方向[61]。
綜上，建立VRPRFC模型適應度函數如下：
式中：是一個很大的數（如果公式（5.2）不滿足），否則，。
2.3求解算法
基于Inver-over操作(Michalewicz Z. et al., 2000)的遺傳算法的解法如下：
隨機初始化種群，并計算個體適應值
3、算例分析
已知有20個客戶，詳細信息如下表。
表1客戶數據信息
表2模型參數設置
種群規模為50，則最大迭代次數為2000，（基于Inver-over操作需求的選擇概率），通過遺傳算法求解，車輛數為4，總油耗是68.788。圖3給出了應用遺傳算法得到的一個解決方案。
圖3 基于遺傳算法的封閉式解決方案
Fig 3 Closed vehicle route based on genetic algorithm
4、小結
本文建立了有能力約束的VRPRFC模型，并給出求解算法，應用Inver-over操作的遺傳算法給出車輛裝載量限制的條件下車輛路徑的選取方案。在數學模型計算過程中，車輛日行駛里程為嚴格約束，但在實際操作中，適當的超過日行駛里程限制導致的成本增加（日行駛里程超過上限可以理解為加班成本）往往在與租車成本降低、油耗節約的平衡中被允許，在以后的研究中，可以著眼于這類更加靈活的限制條件。
參考文獻：
PENG Yong, LI Hongbo. Optimization of Vehicle Route to Reduce Fuel Consumption Based
on Genetic Algorithm[C]．International Conference on Transportation Engineering, 2009, vol.3: 1920-1925.
關鍵詞：通信網絡 OSPF協議 應用 算法 優化
中圖分類號：TP391 文獻標識碼：A 文章編號：1672-3791（2013）07（a）-0005-01
3G通信技術已被廣泛的應用，并日益向4G演進，通信網絡中接入站和傳輸點的數量呈倍數增長，且仍有快速增長的趨勢。通信網絡的站點網的能力及局部故障恢復保護機制的要求也變得更高。開放最短路徑優先（OSPF）屬于一類動態路由的選擇協議，它能夠快速查探運行網絡的拓撲改變，并能夠經快速的收斂計算無環路新路由，時間短并用數據流很小，已成現代的通信網組網最佳選擇。
1 通信網絡和OSPF協議的相關概念
1.1 通信網絡的相關概念
傳統通信網絡，也就是電話交換網絡，由交換、傳輸及終端組成。交換是終端信息交換中介體，傳輸是信息傳送媒體，終端是用戶的手機、話機、計算機和傳真機等。現代的通信網由專業的機構以工作程序和通信設備建立的相關通信系統，為社會、企事業單位及個人提供的各類通信相關服務總和[1]。因特網屬于新興通信網絡，它的正常運行，需要一系列的網絡協議的保證。
1.2 OSPF的概念
OSPF（Open Shortest Path First開放式最短路徑優先）屬于一個內部的網關協議（Interior Gateway Protocol，簡稱IGP），用在單一的自治系統（autonomous system，AS）內的決策路由。它能夠實現對鏈路狀態的路由協議，屬于內部的網關協議（IGP），因此，在自治系統的內部運作[2]。
2 通信網絡中OSPF協議應用
典型線通信網絡的組網，通信網中各站點使用OSPF協議形成層次結構的組網。依據實際的情況，骨干域能夠經以太網的線路，采用直接的連接多路接至機房的網管終端?；蚪又辆钟蚓W及經2 Mbit/s的電路等方式與網管終端相連，構成多路保護的管理通道，通常情況下，上述連接方式將組合使用。
在光通信網中，OSPF協議相關的各域內的站點連接，通常采用廣播型的拓撲和點到點拓撲。對于同域內的各站點，啟動OSPF協議后，首先，需要進行手動的各端口的域值及IP等信息的配置，并初始化協議的內部相關參數，然后進行鄰居的發現和連接，并開始鏈路狀態的信息交互，同時，域內各站點需要進行定期的網絡拓撲檢測和更新。網絡收斂完成之后，同域內的各站點，具備了相同信息的數據庫，并依據信息計算構建自己為根最短的路徑樹，且路由表依據最短的路徑樹自動生成。
3 通信網絡中OSPF協議的算法優化
通常情況下，通信網絡會首先進行網絡拓撲的規劃，進行站點的手動配置，并開始調測到網絡監管[3]。網絡拓撲的規劃重點，指對于骨干網絡的布局，下級網絡通常隨業務動態擴充。使用OSPF協議的層次拓撲網絡，接入網絡站點的數量通常是骨干網數十倍。網絡建立中，前期骨干網絡的站點數量少，運維人員配備相對多，后期的非骨干的站點建立，工作量將成倍增長，運維人員將難以保證網絡正常高質量的運行，因此，開站流程環節的規范和簡化，已被運行商和設備的制造商廣泛的重視。
骨干網絡規劃好后，需要進行OSPF協議的算法的初始化和優化，促使非骨干的域內站點的接入，能夠自動進行正確域值和IP的分配，并保證網管的實時監控識別。
3.1 OSPF協議的通信網中Hello協議和總體方案優化
在使用OSPF協議的通信網絡中，鄰居的建立、維護及正確雙向通信，需要Hello協議的使用。建成底層的物理通道后，站點會對多播地址進行Hello包的發送，以動態的獲取鄰居的站點。收到正確的Hello包的站點，將報文中的信息加進自己Hello報文內，如果雙方的報文中均含有對方站點信息，通道的狀態變為2-Way，表示鄰居的建立成功。OSPF協議的算法優化基礎是鄰居建立。
非骨干域的站點沒有經正確的相關配置，需要于Hello協議的基礎上，增加新型配置的請求和答應包，在鄰居Down的狀態下運行，進行連接點和邊界的路由器正確配置連接，自動正確的分為完成域值和站點IP后，經邊界的路由器上報網管執行監管。
Hello協議總體方案優化，首先進行骨干域的網絡站點正確配置；無正確配置非骨干域的站點，入網后只能進行Hello包收發，不建立鄰居，鄰居站點控制于Down狀態；連接站點配置的請求包收到后，向邊界的路由器的站點進行轉發；會將錯誤hello信息丟棄。連接站點未正確配置站點，也將丟棄包，不予轉發。
邊界的路由器的站點分配和管理非骨干域IP信息表，對請求包判別后，分配區域值和IP信息。連接站點接受配置的響應包之后進行申請站點的轉發，申請站點的配置響應包收到后，啟用正確的配置入網，進行正常的OSPF協議和鄰居建立等。
3.2 站點運行流程的優化
非骨干域的站點，需要請求和應答機制的增加配置，進而得到正確域值和IP信息。對于邊界路由器的站點，需要算法機制的增加，進而完成域值和IP的維護和分配。
在進行邊界路由器的站點優化時，需要進行lP表的分配算法機制的增加，保證IP表連續性，提高查找的效率，進行先進先出（FIFO）的緩沖池的建立，進行多站點同時申請包處理。還需要進行IP表的記錄和分配功能的增加，及進行非骨干域IP表的定期維護，進行站點的lP信息的回收和刷新，使IP值能夠進行循環使用。需要進行非骨干域的站點信息動態上報至網管的支持功能的增加，使網管能夠動態的監管識別。
綜上所述，隨著網絡通信的快速發展，通信網絡OSPF協議組網的應用日益重要， OSPF協議能夠完成通信站點的網絡拓撲發現，根據實際的通信網絡建網情況，進行OSPF協議的算法改進和優化，能夠節省非骨干域的網絡建站的區域及IP信息的規劃配置，更加高效正確的實現網管的自動接入監管。隨著通信網絡規模的日漸擴張，OSPF協議的改進優化對通信網絡的發展具有重要意義。
參考文獻
[1] 邵國榮.OSPF應用研究[J].電腦知識與技術，2011，25（14）：67-29.
[關鍵詞] 空間填充曲線 SFC Sierpinski Curve VRP
一、物流路徑問題概述
車輛路徑問題（Vehicle Routing Problem，VRP）最早是由Dantzig和Ramser于1959年首次提出的。在物流中的解釋是對一系列客戶的需求點設計適當的路線，使車輛有序地通過它們，在滿足一定的約束條件下（如貨物需求量、發送量、交發貨時間、車輛載重量限制、行駛里程限制、時間限制等等），達到一定的優化目標（如里程最短、費用最少、時間最短，車隊規模最少、車輛利用率高）。
VPR是物流運輸過程中的關鍵環節，將直接影響對客戶需求的響應速度、客戶對物流環節的滿意度以及服務商的配送成本。
由于VRP包含了銷售員問題 (Traveling Salesman Problem，TSP)，而 TSP本身就是NP-Hard問題，所以 VRP也是一個NP組合優化難題。VRP問題和TSP問題的區別在于：客戶群體的數量大，有多輛交通工具的訪問順序進行求解。相對于TSP問題，VRP問題更復雜，求解更困難，但也更接近實際情況。國內外許多學者對VRP問題的求解方法進行了大量研究，總體上分精確算法和啟發式算法兩類。精確算法可分為分支定界法、動態規劃、整數規劃、非線性規劃。啟發式算法有：最近鄰點法（Nearest Neighbor）、最近插入法（Nearest Insertion）、節約里程法（Saving Algorithm）、掃描算法（Sweep Algorithm）。
這些解法雖然可以給出較為滿意的答案，但也存在計算過程復雜、參數可獲得性準確請較差、限制條件較多、時間花費偏長、靈活性差等缺點，尤其不利于中小企業解決物流中的實際問題。那么是否存在較為簡便直觀的方法，更快速的求解出優化的訪問順序呢？不妨換一種思路進行解答。
二、毛線團的啟示
對于古典的歐幾里德式的幾何，重視的是圖形的長度、寬度、厚度等實際可測的幾種值。于是我們可以知道：我們生活的空間是三維，平面是二維，直線是一維，一點的維度則為零。
20世紀70年代的數學家畢諾特?曼德布洛特-加龍省(Benoit Mandelbrot)提出一個問題：毛線團的維度是多少？他的答案是：這要看你的觀點而異。
遠距離來看，繩團凝聚成點，維度為零；再近一點，看出來毛線團占據球形的空間，維度擴展成三；再走近一些，看出毛線團是由一根根毛線所構成，他的維度為一，即使它已糾結充斥了三維空間。那么，再看下去呢？當我們看到線繩為圓柱、構成圓柱的一條條纖維……曼德布洛特-加龍省這樣闡釋：“數據結果視觀測者與其對象而改變。”
如此一來，VRP問題可以有一個用圖論語言的描述方式：平面上有n個點，如何用最短的線將全部的點連起來，即“一筆畫”問題（Drawing by one line）。對于“一筆畫”問題可以用“空間填充曲線”(Space Filling Curve，SFC)方法進行求解。一條線只是一維的，彎折扭曲仍是一維的，但是在這個平面上，沒有一點是SFC畫不到的。
三、希爾平斯基曲線在物流路線問題中的應用
1.希爾平斯基曲線與SFC方法簡介
SFC法是由Bartholdi和Platzman兩人提出的，以Peano(1890)、Hilbert(1891)、Sierpinski(1921)等人開發出來的空間填充曲線為基礎，根據配送地點在SFC上出現的順序決定配送次序的方法。Bartholdi和Platzman把分散在2維空間（X,Y）坐標上的配送地 投影到被SFC填充的1維曲線上，再尋找配送地在SFC上所出現的順序，把此順序作為配送的順序，再根據具體路況確定訪問路線。因為只需計算投影和順序排列，所以SFC計算速度非常快。美中不足的是解的質量不算太好，最差的時候巡回距離比最佳解長20％左右。
2.用希爾平斯基曲線填充VRP平面
希爾平斯基曲線（Sierpinski Curve）是空間填充曲線的一種，它通過自我復制和連接可以無限的擴展。很明顯希爾平斯基曲線是一個閉合的線路，而且有著優異的對稱性。
可以在上面任意取一點作為起點，當然這一點也就是終點。以沿曲線繞行一周的距離作為1，則在這個線路上的其他任何一點都對應一個0至1之間的數值，這個數值就是確定先后次序的依據，即數值小的點先訪問，而數值大的點排在后面訪問。
3.分割希爾平斯基曲線確定順序數值
用希爾平斯基曲線填充VRP所要經過的點以后，該如何確定各個點的訪問順序呢？例如求出圖中A、B點的順序。最簡單的方法就是分割法。
不妨假設左下角為起始點0%（也是終點100%），由于曲線的閉合性和對稱性，則對角點為50%，而且左上方半個區域的點總是優先于右下方的點，兩個頂點分別為25%和75%。
第一次從左下角向右上角分割后，可以知道A、B點的順序數值都在50%和100%之間；繼續將50%～100%區域分割為兩個相等的三角形，可進一步知道A、B點的順序數值在75%和100%之間；繼續分割剩下的區域，A、B點的順序數值在75%和87.5%之間；第四次分割后，A點的順序數值在75%和81.25%之間，B點的順序數值則在81.25%和87.5%之間；所以A點先于B點。
實際上由于所有的點會相互連接成一條封閉的線路，無論以何處作為起點，訪問線路都不會有什么變化，問題的關鍵在于求出點的次序。需要注意的是，要把倉庫（圖4中的D點）包括進去才能得到正確的路線。
4.訪問任務分配
簡單的TSP問題只假定了一臺交通工具，而VRP問題則考慮了一個公司協調多臺交通工具進行運輸作業的情況。在SFC方法中，安排n個交通工具的路線也很簡單，只要把訪問路線平分為1/n即可，訪問順序不變。假設一個物流公司有3輛運輸車，要完成60個客戶，則1號司機就負責送貨到線路圖上第1到20號客戶，2號司機負責送貨到第21到40號客戶，以此類推。當然，實際操作中也不必要如此精確。
SFC方法還具有很強的靈活性。如果增加新的訪問點，只需要在圖上確定它的順序數值，把它插入到已有的點的序列里面去，不再有業務的訪問點直接從序列里刪去即可；如果出動的車輛數目有變化，只需要簡單得重新劃分路線；由于只規定了訪問序列，具體的道路選擇可以由司機靈活掌握，如根據交管部門的臨時限制、車流高峰等情況變換道路。
值得注意的是，雖然每輛車分配到的客戶數目都差不多，但實際位置的遠近很可能不一樣，每輛車的路線長短可能差別較大，這就需要不均勻的分配送貨量。但如果客戶接近于均勻分布，采用希爾平斯基曲線來確定客戶點的次序，在此基礎上再在各車之間平均分配送貨量，每輛車行駛距離的差異就會比較小。
四、SFC方法的適用性
基于空間填充曲線的方法和各種精確算法、啟發算法相比具有快速、靈活、運算量少的特點，可以很好的解決確定訪問順序，規劃最短路線問題。但對于含有滿載約束、分批裝貨、回程裝載、時間窗約束的VRP的復雜情況無法給出解答。
綜合上文分析以及其他研究可以發現，每一種算法單獨工作都會存在一些比較大的缺陷，而且隨著社會的發展、問題規模不斷擴大化、結構不斷復雜化，單一的算法很難解決現實中復雜的問題，需要將幾類算法融合貫通，揚長避短，構造混合算法求解體系。
參考文獻:
[1]孫麗君胡祥培王征:車輛路徑規劃問題及其求解方法研究進展[J].當代中國出版社，2006
[2]蘇麗杰聶義勇:旅行商問題典型算法的綜合性能[J]．企業研究，2004，（11）
[3]John J.Bartholdi．A routing system based on space filling curves
關鍵詞:TSP;遺傳算法;遺傳操作;算子
中圖分類號:TP311 文獻標識碼:A文章編號:1009-3044(2010)03-672-02
Application in TSP Based on Genetic Algorithm
LI Hua-zhong, YANG Jing-hua
(Computer Science and Technology Institute of Hua Yu College from Henan Agricultural University, Shangqiu 476113, China)
Abstract: First, the passage introduced the problem of TSP, the basic feature and procedure of Genetic algorithm. Then discussed the way of coding, the function of fitness of solving TSP by Genetic algorithm. The application and effect of selection operator, crossover operator and mutation operator. At last, how to solve TSP in the future will be given.
Key words: TSP; genetic algorithm; genetic operation; operator
旅行商問題(TSP),也稱為貨郎擔問題,是一個較古老的問題。最早可以追溯到1759年Euler提出的騎士旅行問題。1948年,由美國蘭德公司推動,TSP成為近代組合優化領域的一個典型難題。應該說,TSP是一個具有廣泛應用背景和重要理論價值的組合優化難題,它已經被證明屬于NP難題。對TSP問題的大量研究使得TSP問題成為了一個著名的組合優化問題目前,求解TSP問題的較為常用的方法有二叉樹描述法、啟發式搜索法、最近鄰法、神經網絡法、模擬退火法和遺傳算法等。遺傳算法是模擬生物在自然環境中的遺傳和進化過程而形成的一種自適應全局概率搜索算法,具有良好的全局尋優能力,成為解決問題的有效方法之一。
1 TSP問題描述
TSP(旅行商問題)的簡單描述是:一名商人欲到n個城市推銷商品,每兩個城市i和j之間的距離為d,存在i,j如何使商人每個城市走一遍后回到起點,且所走的路徑最短。用數學符號表示為:設n維向量表示一條路徑X=(C1, C2, ……,Cn),目標函數為
minF(x)=∑n+1i=1d(Ci,Ci+1)+d(C1+ Cn)
用圖語言來描述TSP,給出一個圖G=(V, E),每邊e∈E上有非負權值w(e),尋找G的Hamilon圈C,使得C的總權W(C)=∑e∈E(C) w(e)最小。TSP搜索空間隨著城市數n的增加而增大,所有的旅程路線組合數為(n-1)!/2。5個城市的情形對應120/10=12條路線,10個城市的情形3628800/20=181440條路線,100個城市的情形則對應有4.6663×10155條路線。在次龐大的搜索空間中尋求最優解,對于常規方法和現有的搜索而言,存在諸多的計算困難。借助遺傳算法的搜索能力解決TSP問題是很自然的想法。
2 遺傳算法的特點及基本步驟
2.1 遺傳算法的特點
遺傳算法是模擬達爾文的“適者生存” 的自然進化論與蒙德爾的遺傳變異理論而提出的一種求解復雜系統全局優化問題的通用計算框架。它的主要特點是群體搜索策略和群體中個體之間的信息交換。它適用范圍于處理傳統搜索方法難于解決的復雜和非線性問題?？蓮V泛用于組合優化,機器學習.自適應控制,規劃設計和人工生命等領域。遺傳算法是一種有向隨機搜索法,其遺傳算子原則上執行盲目搜索,體現了隨機搜索的特點,故能廣泛搜索整個解空間而跳出局部。通過不斷計算各染色體的適應值,選擇最好的染色體,從而獲得最優解。基于遺傳算法的本質是處理復雜問題的一種啟發性隨機搜索算法故用于TSP是有效的。
2.2 遺傳算法的基本步驟
遺傳算法是通過借鑒生物界自然選擇和自然遺傳機制而產生的一種計算方法,與其他的優化算法一樣,遺傳算法也是一種迭代算法。從選定的初始解出發,通過不斷地迭代,逐步改進當前解,直到最后搜索到最優解或滿意解。其迭代過程是從一組初始解(群體)出發,采用類似于自然選擇和有性繁殖的方法,在繼承原有優良基因的基礎上生成具有更好性能的下一代解的群體。遺傳算法的運算過程為:對給定問題,給出變量的編碼方法,定義適應度函數。1)初始化。令t=0,給出正整數(最大迭代次數),交叉概率Pc及變異概率Pm,隨機生成M個個體作為初始群體P(0);2)個體評價。計算P(t)中各個體的適應度;3)選擇。對群體P(t)進行選擇操作,得到中間群體;4)交叉。把交叉操作作用于中間群體;5)變異。把變異操作作用于交叉之后所得到的群體,則得到第(t+1)代群體P(t+1);6)若t
3 遺傳算法用于TSP問題
3.1 編碼表示
用遺傳算法求解TSP時,算法的編碼表示是算法設計的重點,它對遺傳基因的操作有一定的限制。TSP的編碼策略主要包括二進制表示、順序表示、路徑表示、矩陣表示和邊表示等。由于二進制編碼具有如下的特點數據冗長,并且表達能力有限,計算機無法承受如此巨大的計算量甚至根據調整不同的參數時,所運行的時間,有時會達到近幾個小時,從時間效率來說,工作效率實在是低下,并達到無法忍受的程度,所以實際中很少使用。順序表示是指將所有城市依次排列構成一個順序表,對于一條旅程,可以依次旅行經過順序處理每個城市,每個城市在順序表中的順序就是一個遺傳因子的表示。每次處理完一個城市,從順序表中去掉該城市。處理完所有城市后,將每個城市的遺傳因子連接起來,即成為一條旅程的基因表示(染色體編碼)。
路徑表示是表示旅程歲應的基因編碼的最自然,最簡潔的表示方法。
3.2 初始化群體和適應度函數及其終止條件的設定