【文章內(nèi)容簡介】 示從節(jié)點 到所有可能的節(jié)點走，再從走到節(jié)點 的最小路集．即從節(jié)點 到節(jié)點 的路長為2的所有最小路集．因此，按式(1—3)得到的路長小于2的要除去推廣為普遍形式：式中 為節(jié)點數(shù)，c 的含意：它表示從節(jié)點 到 之間路長為r的所有最小路集．因此按式(1—4)得到的路長小于r的要除去．設 為輸入節(jié)點，L為輸出節(jié)點，從定義可知，對于任意的[c] ，和[c]一樣，第L行及第列的所有元素都為0．有了聯(lián)絡矩陣[c]，只要做多次矩陣連乘，相繼求出[c] ，[c]。，? ，[c]一 即可得到任意二節(jié)點 ，J間所有的最小路集由于眾所周知研究的是運輸線路的起點(輸入節(jié)點 )到終點(輸出節(jié)點L)之間的最小短路問題，因此對于其他節(jié)點之間的最小路集可不考慮．從式(1—4)可看出，在這種情況下只需求中的第L列即：[c]2只需求出第行元素即可，而不用求整列的元素．3 最大流量最大流量按下列兩條原則進行計算：1)確定連接輸出節(jié)點上的線路個數(shù)m，如圖2—1，有兩條輸出線路G和H，所以m一2；2)根據(jù)最小路集分別計算m中每條線路的流量，直到m 條線路中各線路的流量之差≤0．在兩條輸出線路G和H 中分別有路長：{A，B，G)、{C，E，G)、{A，I，E，G)、{D，F(xiàn)，E，G)和{C，F(xiàn)，H )、{A，I，F(xiàn)，H )、{A，B，E，F(xiàn)，H )、{D，H )分別確定輸出線路G和H 中各路長的最小流量．在輸出線路G中，線路G一2為最小流量．在輸出線路H 中，線路F一3為最小流量，則剩余流量：Q 。，且F一0．對于路徑{A，I，F(xiàn)，H)，{A，B，E，F(xiàn)，H)，因元素F一0，所以不再計算．對于路徑{D，H)，在Q 。中減去最小流而元素D 已為零．計算畢．總流量為：Q—G+F+D一2+3+3—8(千輛／小時)．4 系統(tǒng)可靠度某些條件下，運輸線路的運行情況無法用準確的數(shù)值表達，如線路質(zhì)量等級，可能發(fā)生的塞車故障等，這時可用概率來描述．R為可靠度，即線路正常運行的概率．已知最小路集：由于最小路之間是相交的，所以必須用相容事件的概率公式來計算系統(tǒng)可靠度尺運輸線路網(wǎng)絡系統(tǒng)中正常運行的可靠程度為：0．835．（1）在運輸線路優(yōu)化問題的計算中，最小路集法既便于運輸網(wǎng)絡定性分析，又便于運輸線路定量計算，特別是在計算最大流量時更具有獨特的優(yōu)勢．（2）最小路集法除在最短路程和最大流量的計算、分析中有顯著的特點外，在對網(wǎng)絡系統(tǒng)的可靠性分析中也具有重要作用．從述可靠度計算可看出，它清晰地描述了運輸線路正常運行的可靠程度，便于管理者對線路的優(yōu)化和決策．問題中的一個重要問題，在解決公交最佳出行線路、城市援救最佳線路、物流配送、高速公路聯(lián)網(wǎng)收費等與人們?nèi)粘Ｉ蠲芮邢嚓P問題中發(fā)揮著重要的作用。這些年來，城市的交通系統(tǒng)有了很大發(fā)展，為公眾的出行以及進行各項日?；顒訋砹撕艽蟮谋憷?，但同時也面臨著多條線路的選擇問題。所以建立交通中最優(yōu)線路問題的數(shù)學模型，為人們進行日?；顒犹峁﹨⒖加泻艽蟮膬r值，是一個值得研 究的課題。建立交通中最優(yōu)線路問題數(shù)學模型的目的就是尋找最優(yōu)路徑，為公眾做出出行決策提供參考。目前關于最佳出行線路問題的研究主要是一些傳統(tǒng)算法和根據(jù)問題的特點對傳統(tǒng)算法進行改造。合運輸網(wǎng)絡中求解起點到終點的最短可行路徑；Pa—ola Modesti等 針對最小出行時間研究了求解綜合運輸網(wǎng)絡最短路徑問題，使用多標記圖構建運輸網(wǎng)絡和對應的數(shù)據(jù)，并提出了求解算法。但這些已有的算法都不能解決出行線路雙向選擇、環(huán)形出行線路和多權問題，因此需要一種新的算法來建立交通中最優(yōu)線路問題的數(shù)學模型。3 Floyd算法Floyd(弗洛伊德)算法 剮是一種矩陣(表格)迭代方法，對于求任意兩點間的最短路、混合圖的最短路、有負權圖的最短路等一般網(wǎng)絡問題來說均比較有效。Floyd算法通過對表示有向圖的鄰接矩陣作疊代計算來解決有向圖任意一對頂點之間的最短路徑間題。Floyd算法不僅是建立在簡單的數(shù)據(jù)結構基礎之上，而且就解決問題的徹底性而言也是最完滿的。迄今為止，它僅僅是作為解決有向圖的最短路徑問題的一個重要方法而被提及。實際上，F(xiàn)loyd算法與圖的許多重要性質(zhì)以及與圖論中其它一些重要問題的解決有著密切的聯(lián)系。3．1 Floyd算法的基本原理Floyd算法的主要思想是從代表任意2個頂點到 的距離的帶權鄰接矩陣開始，每次插入一個頂點 ，然后將 到vi間的已知最短路徑與插入頂點 作為中間頂點(一條路徑中除始點和終點外的其他頂點)時可能產(chǎn)生的 到 路徑距離比較，取較小值以得到新的距離矩陣。如此循環(huán)迭代下去，依次構造出rt個矩陣Du)，D(2’，? ?D( ，當所有的頂點均作為任意2個頂點 到 ，中間頂點時得到的最后的帶權鄰接矩陣D 就反映了所有頂點對之間的最短距離信息，成為有n個頂點的圖G的距離矩陣。最后對G中各行元素求和并比較大小，決定最優(yōu)的路線。3．2 Floyd算法構造距離矩陣的原理對一個有幾個頂點的圖G，將頂點用n個整數(shù)(從1到7,)進行編號 。把G的帶權鄰接矩陣作為距離矩陣的初值，即D（0) =W。從圖的帶權鄰接矩陣 開始，遞歸地進行a次更新，即由矩陣D(0’=W，按一個公式構造出矩陣JD(1’；又用同樣的公式由Dl構造出矩陣D(2 ；．．?最后又用同樣的公式由JD ’構造出矩陣D。矩陣D的i行_『列元素便是i號頂點到『號頂點的最短路徑長度，稱D ’為圖的距離矩陣，同時還可以引入一個路由矩陣path來記錄兩點間的最短路徑。第一步：構造D(0=W)。第二步：構造D = (d ) ，其中d =min{d ，d +d }是從 到 的只允許 。作為中間點的路徑中最短路長度。第三步：構造D= ( )? ，其中 ’=rain{d 168。，d ’+d ’}是從t， 到t，的只允許t，l，∞2作為中間點的路徑中最短路長度。第n步：構造D =(d )? ，其中d： =min{d ，d +d }是從 到vi的只允許作為中間點的路徑中最短路長度，即從 到 ，中間可插入任何頂點的路徑中最短路的長度，因此D ’即是距離矩陣。3．2．1 Floyd算法步驟上述矩陣序列{D( )可以遞歸地產(chǎn)生，利用循環(huán)迭代便可求出，算法的詳細步驟如下。對應于d 的路徑上i的后繼點，最終的取值為i到 的最短路徑上i的后繼點。Stepl：賦權值，對所有i d(i )=(i)；當a(i)=0時，path(i )=0，k= 1 ostep2，path(i )對所有i，J若d(i，k)+d(k，J) d(i)，則轉(zhuǎn)人step3，否貝Ⅱd(J)=d( ，k)+d(k，J)，path(i)=path(i，k)，k=+1；繼續(xù)執(zhí)行step3。Step3：重復step2直到k=rt+1。迭代結束后得到最終的距離矩陣D 和路由矩陣path，根據(jù)距離矩陣D ’可得任意兩點間的最短路長度，根據(jù)路由矩陣path可得任意兩點問取最短路徑。3．2．2 回溯法求最短路徑已知路由矩陣P=(P )? ，利用回溯法求解點i與點 取最短路徑，若已知P =k ，分別從點i和點 開始回溯。(a)從點i開始回溯Pa2= k3，? ，p= k，(b)從點 開始回溯工則從點i到點k 的最短路徑為：i，k，k一，?，k：，kl，ql，q2， 3．3．I 改進Floyd算法原理在原有的Floyd算法中，矩陣D 給出網(wǎng)絡中任意兩點直接到達，經(jīng)過一個、兩個、??到(2 一1)個中間點時比較得到的最短距離。一般地d=min{d (k ’十d (k }。在計算過程中，由于 )= (d ) ，其中d “ =mini d ’，d ’+d ’}從1到／7,取值。當r／,較大時，．r從1到r／,取值，比較d ’+d ”之間的值取其最小，計算量大。由于d 表示的是從i點到 點插入k個節(jié)點后的最好結果，導致插入k+1個節(jié)點應該優(yōu)于d ’，實際上 “’包含d 。然而當 從1到n取值時，不一定所有d ’+d 就優(yōu)于d ，為了簡化計算量，眾所周知將 作為計算d ’取小運算的首次比較標準。3．3．2 改進Floyd算法的計算步驟首先用 “ 來保存當r從1到n取值時d +d ’的最小值。．r。用來記載 +d ’取最小值時r的取值。stepl：初始值d ，即 “ =d 。step2：當 從1到n取值時，則 值不變；如果d +d 們，進入step3步。Step3：將 作為d 新的比較標準，r從 。到n取值時，如果 d +d ，則砭值不變；step4：循環(huán)第step3步，直到下=n，則 “ I= min n，d +d ’}。改進后，d ”的計算由原來的凡!次運算減少到2次運算。規(guī)劃式(6)是非線性多目標規(guī)劃模型，本文提出的混合變異算子的遺傳算法過程如下：（1）編碼方式整個接運公交線網(wǎng)用一個十進制整數(shù)串來表示。每個整數(shù)串又由幾個子串組成，每個子串為一條接運公交路線上接運公交車站的序列，并以它所接運的軌道交通車站結束，其十進制編碼的位數(shù)，根據(jù)接運站的編號來確定，軌道交通車站的編號從最大的接運公交車站編號后一位開始。（2）純策略集合記為{1，2，3，4}，分別代表Gaussian，Cauchy，Levy，Single Point變異[ 。（3）初始化過程：(1)產(chǎn)生由 個個體組成的初始種群，隨機選取種群中90的個體，每個個體代表一個實值向量集合是目標變量i是變異的標準差，五和 有m個獨立分量。(2)對要變異的每個個體i，為混合策略向量分配初始的概率分布：（4）變異：對種群中90 的個體i，根據(jù)混合策略向量．0中的概率選擇一種變異策略h，然后根據(jù)選擇的策略進行變異，產(chǎn)生子代。（5）交叉：對種群中其它1O 的個體i進行交叉操作，產(chǎn)生子代。（6）個父代產(chǎn)生 個子代，計算它們的適應度值廠l，j2，? ， 2 。（7）下一代的種群中的個體按如下方法更新混合策略：如果個體來自于子代種群，采用的變異純策略為h，h∈{1，2，3，4}，那么要加強這個純策略：這里07i，用來調(diào)整混合策略的概率分布。如果個體來自于父代種群，采用的變異純策略為h，h∈{1，2，3，4)，那么要減弱這個純策略：（8）重復4)到7)步，直至滿足終止條件。未來大城市的客運交通系統(tǒng)一般會采用以下模式：以快速軌道交通為骨干，常規(guī)公交為主體，個體交通為補充。接運公交線路指專門為軌道交通集疏乘客的常規(guī)地面公交線路的總稱。建設接運公交線路的目的是為了保證現(xiàn)有軌道交通線路有足夠的客流量，充分發(fā)揮軌道交通的運能。國內(nèi)軌道交通接運線路布設的研究比較少，曹玫l3]提出了基于遺傳算法的城市軌道交通接運公交線網(wǎng)規(guī)劃。提出了基于粒子群算法的城市軌道交通接運公交規(guī)劃。提出了基于改進遺傳算法的接運公交線路優(yōu)化模型。研究主要圍繞乘客等待時間最小化、運載能力最優(yōu)來求解接運公交線路布設和網(wǎng)絡優(yōu)化問題，本文提出的算法能有效地防止局部優(yōu)化陷入困境，對求解函數(shù)優(yōu)化問題是行之有效的?？偨Y：根據(jù)AHP分析結合題目，運輸作為物流的基本功能之一，在整個物流環(huán)節(jié)中占有十分重要的地位。根據(jù)相關統(tǒng)計，物流運輸成本占物流總成本的50％以上，對許多商品來說，運輸成本要占商品價格的4％一10％，也就是說運輸成本占物流總成本的比重比其他物流活動大。目前，我國的交通運輸業(yè)主要由公路、鐵路、水路、航空等多種運輸方式組成。在市場經(jīng)濟體制下，各種運輸方式之間也不可避免地存在著激烈的競爭。各種運輸方式均擁有自己固有的技術經(jīng)濟特征(見表1)。如何針對各種運輸方式的特點，選擇合適的運輸方式，使貨物能夠安全、快速、經(jīng)濟、便利的到達目的地，也就成為企業(yè)決策者必須面對的問題。運用AHP分析方法就物流運輸方式選擇問題進行一些探討，為企業(yè)決策者提供一些決策依據(jù)?？芍绊懙桨布锪鬟x擇運輸方式的只要因素為：運費和時間。其中，水路運輸?shù)倪\費和時間包括短駁運輸?shù)馁M用和時間。水路運輸?shù)奶攸c是運量大，成本低，非常適合于大宗商品車的運輸，并且通航能力幾乎不受限制。但是采用水路運輸，不可避免的會涉及到短駁問題。當船舶到達碼頭后，需要短駁車將這些商品車運往目的地。相比較水路運輸，公路運輸?shù)奶攸c是快速、機動、靈活，即車輛可隨時調(diào)度、裝運，各環(huán)節(jié)之間的銜接時間較短，可實現(xiàn)門對門的服務，因此，安吉物流的整車運輸方案中普遍采用公路運輸。但是公路運輸也有缺點，如運量少、成本高等，安吉物流在其運輸方案中，也經(jīng)常采用公路運輸與水路運輸相結合的方式。到達碼頭的整車，既可用采用短駁運輸?shù)竭_目的地，也可以長途運輸?shù)竭_目的地。安吉物流接到訂單后，首先考慮的是運輸方式的選擇，或公路運輸，或水路運輸，或多式聯(lián)運，或建立中轉(zhuǎn)站等。但是不管采用哪種運輸方式，安吉物流都需要實現(xiàn)經(jīng)濟成本最小、時間成本最短的目標。根據(jù)實際情況，選擇最優(yōu)的運輸方式。及距離較近，且公路方便的選擇公路運輸。距離較遠，且水路方便選擇水路運輸。距離長短與時間多少難于把握時應考慮多式聯(lián)運。 物流行業(yè)概況我國物流行業(yè)概況：現(xiàn)代物流是將信息、運輸、倉儲、庫存、裝卸搬運以及包裝等物流活動綜合起來的一種新型的集成式管理，通過對各種物流要素的優(yōu)化組合和合理配置，提高物流活動效率，降低社會物流總成本，為顧客提供更為全面、多樣化的物流服務，實現(xiàn)物流全過程及各個環(huán)節(jié)價值增值。中國物流行業(yè)現(xiàn)狀是：至加入世貿(mào)組織后， 隨著國民經(jīng)濟的快速發(fā)展，對社會物流需求顯著增加，推動