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