【正文】 路徑，使車輛有序地通過它們，在滿足一定約束條件的情況下，達到一定的目標 (諸如路程最短、費用最小，耗費時間盡量少等 )，屬于完全 NP問題，在運籌、計算機、物流、管理等學科均有重要意義。 帶時間窗車輛路徑問題（續(xù)） 帶時間窗的車輛路徑問題 (Vehicle Routing Problem With Time Windows, VRPTW)是在 VRP問題上加了客戶要求訪問的時間窗口。由于在現(xiàn)實生活中許多問題都可以歸結(jié)為 VRPTW問題來處理 (如郵政投遞、火車及公共汽車的調(diào)度等 )，其處理的好壞將直接影響到企業(yè)的服務質(zhì)量 ,所以對它的研究越來越受到人們的重視。先后出現(xiàn)了一般啟發(fā)式算法和神經(jīng)網(wǎng)絡、遺傳算法、禁忌搜索和模擬退火等智能化啟發(fā)式算法，也取得了一些較好的效果。帶時間窗車輛路徑問題（續(xù)） 時間窗車輛路徑問題一般描述為：有一個中心倉庫，擁有車 K輛，容量分別為 qk (k=1,..,K)；現(xiàn)有 L個發(fā)貨點運輸任務需要完成，以 1,…, L表示。第 i個發(fā)貨點的貨運量為 gi (i=1,…, L)， ( max(g)i≤max(qi) )，完成發(fā)貨點 i任務需要的時間 (裝貸或卸貨 )表示為 Ti，且任務 i且必須在時間窗口 [ETi , LTi]完成，其中 ETi為任務 i的允許最早開始時間， LTi為任務 i的允許最遲開始時間。如果車輛到達發(fā)貨點 i的時間早于 ETi，則車輛需在 i處等待；如果車輛到達時間晚于 LTi，任務 i將被延遲進行。求滿足貨運要求的運行費用最少的車輛行駛線路。 時間 窗 車輛 路徑 問題 的數(shù)學描述：帶時間窗車輛路徑問題（續(xù)） 這個模型通用性很強，經(jīng)過參數(shù)的不同設定，可以將其轉(zhuǎn)換為其他組合優(yōu)化問題的數(shù)學模型。若 (1)中 ETi=0, LTi→∞ ，則 VRPTW模型就變成了普通的 VRP模型；若僅有一個車輛被利用，則該問題就變成了 TSP問題；若去掉約束 (2)，則變成了 m－ TSPTW問題。 帶時間窗車輛路徑問題（續(xù)） 如何找到一個合適的表達方法，使粒子與解對應，是實現(xiàn)算法的關鍵問題之一。構(gòu)造一個 2L維的空間對應有 L個發(fā)貨點任務的 VRP問題，每個發(fā)貨點任務對應兩維：完成該任務車輛的編號 k，該任務在 k車行駛路徑中的次序 r。為表達和計算方便，將每個粒子對應的 2L維向量 X分成兩個 L維向量： Xv (表示各任務對應的車輛 )和 Xr(表示各任務在對應的車輛路徑中的執(zhí)行次序 )。例如， 設 VRP問題 中 發(fā)貨 點任 務 數(shù) 為 7， 車輛數(shù) 為 3，若某粒子的位置向量 X為 ：發(fā)貨 點任 務 號 : 1 2 3 4 5 6 7 Xv ： 1 2 2 2 2 3 3 Xr ： 1 4 3 1 2 2 1則該 粒子 對應 解路徑 為 ：車 1： 0 ? 1 ? 0車 2： 0 ? 4 ?5 ? 3? 2? 0車 3： 0 ? 7? 6? 0粒子速度向量 V與之 對應 表示 為 Vv和 Vr。 該表示方法的最大優(yōu)點是使每個發(fā)貨點都得到車輛的配送服務，并限制每個發(fā)貨點的需求僅能由某一車輛來完成，使解的可行化過程計算大大減少。雖然該表示方法的維數(shù)較高，但由于 PSO算法在多維尋優(yōu)問題有著非常好的特性，維數(shù)的增加并未增加計算的復雜性，這一點在實驗結(jié)果中可以看到。 VRP問題為整數(shù)規(guī)劃問題，因此在算法實現(xiàn)過程中要作相應修改。具體實現(xiàn)步驟如下：Step1：初始化粒子群。 粒子群劃分成若干個兩兩相互重疊的相鄰子群； 每個粒子位置向量 Xv的每一維隨機取 1～ K（車輛數(shù)）之間的整數(shù)， Xr的每一維隨機取 1～ L(發(fā)貨點任務數(shù) )之間的實數(shù)； 每個速度向量 Vv的每一維隨機取 (K1)～ (K1)（車輛數(shù)）之間的整數(shù)， Vr的每一維隨機取 (L1)～ (L1)之間的實數(shù)； 用評價函數(shù) Eval評價所有粒子； 將初始評價值作為個體歷史最優(yōu)解 Pi，并尋找各子群內(nèi)的最優(yōu)解 Pl和總?cè)后w內(nèi)最優(yōu)解 Pg。Step2：重復執(zhí)行以下步驟，直到滿足終止條件或達到最大迭代次數(shù)。 對每一個粒子，按式 (1)計算 Ｖ v、 Ｖ r；按照式 (2)計算 Xv、 Xr，其中 Xv向上取整；當 Ｖ、 X超過其范圍時按邊界取值； 用評價函數(shù) Eval評價所有粒子； 若某個粒子的當前評價值優(yōu)于其歷史最優(yōu)評價值，則記當前評價值為該歷史最優(yōu)評價值，同時將當前位置向量記為該粒子歷史最優(yōu)位置 Pi。 尋找當前各相鄰子群內(nèi)最優(yōu)和總?cè)后w內(nèi)最優(yōu)解，若優(yōu)于歷史最優(yōu)解則更新 Pl 、 Pg。對于子群內(nèi)有多個體同為最優(yōu)值的情況，則隨機取其中一個為子群內(nèi)當前最優(yōu)解。 其中，評價函數(shù) Eval完成以下任務 :根據(jù)公式計算該粒子所代表路徑方案的行駛成本 Z，在計算中發(fā)貨點任務的執(zhí)行次序要根據(jù)對應 Xr值的大小順序，由小到大執(zhí)行。將 Xr按執(zhí)行順序進行重新整數(shù)序規(guī)范。例如，某粒子迭代一次后結(jié)果如下： Xv ： 1 2 2 2 2 3 3 Xr ： 5 則評價后重新規(guī)范的 Xr是： 1 3 4 1 2 1 2 實驗１ ：采用了無時間窗 VRP的例子，問題為一個有 7個發(fā)貨點任務的車輛路徑問題，各任務點的坐標及貨運量見下表：表 1 各 發(fā)貨 點坐 標 及 貨 運量序 號 0 1 2 3 4 5 6 7坐 標 (18,54)(22,60)(58,69)(71,71)(83,46)(91,38)(24,42)(18,40)貨 運量(gi) 注： 序號 0表示中心 倉庫 ， 設車輛 容量皆 為 q=，由 3輛車 完成所有任 務 。 (最 優(yōu) 路徑距離 為 ) GA參數(shù)：群體規(guī)模 n=40；交叉概率 Pc=；變異概率 Pm=；輪盤賭法選擇子代，最大代數(shù) 200。PSO參數(shù)：粒子數(shù) n=40；分為 2個子群，子群規(guī)模為22，子群間重疊的粒子數(shù)為 2個（子群規(guī)模的 1/10）； w=； c1=c2=；最大代數(shù) 200。兩種方法各運行 50次，結(jié)果如下表 2所示。表 2 實驗 1 GA、 PSO方法 結(jié) 果 對 比方法 達到最 優(yōu)路徑次數(shù)未達最 優(yōu)路徑次數(shù)達到最 優(yōu) 路徑平均代數(shù)達到最 優(yōu) 路徑的平均時間 (s)GA 32 18 PSO 50 0 實驗 2， 采用 VRPTW的例子，該問題有 8項貨物運輸任務，貨物點位置及時間窗略。實驗結(jié)果如下： 表 6 實驗 2 GA、 PSO方法 結(jié) 果 對 比搜索成功率 平均行 駛 成本 平均成功搜索 時間GA 24% PSO 46% Evolving Neural Networksv Evolve neural work capable of being universal approximator, such as backpropagation or radial basis function work.v In backpropagation, most mon PE transfer function is sigmoidal function: output = 1/(1 + e input )v PSO can also be used to indirectly evolve the structure of a work. An added benefit is that the preprocessing of input data is made unnecessary.Evolving Neural Networksv Evolve both the work weights and the slopes of sigmoidal transfer functions of hidden and output PEs.v If transfer function now is: output = 1/(1 + e k*input ) then we are evolving k in addition to evolving the weights.v The method is general, and can be applied to other topologies and other transfer functions.v Flexibility is gained by allowing slopes to be positive or negative. A change in sign for the slope is equivalent to a change in signs of all input weights.Evolving Neural Networksv If evolved slope is sufficiently small, sigmoidal output can be clamped to , and hidden PE can be removed. Weights from bias PE to each PE in next layer are increased by onehalf the value of the weight from the PE being removed to the nextlayer PE. PEs are thus pruned, reducing work plexity.v If evolved slope is sufficiently high, sigmoid transfer function can be replaced by step transfer function. This works with large negative or positive slopes. Network putational plexity is thus reduced.Evolving Neural NetworksvSince slopes can evolve to large values, input normalization is generally not needed. This simplifies applications process and shortens development time.vThe PSO process is continuous, so neural work evolution is also continuous. No sudden discontinuities exist such as those that plague other approaches.Other applicationsv Scheduling (Integrated automated container terminal)v Manufacturing (Product content bination optimization)v Figure of merit for electric vehicle battery packv Optimizing reactive power and voltage controlv Medical analysis/diagnosis (Parkinson’s disease and essential tremor)v Human performance prediction (cognitive and physical)Questions and Answers Thank yo