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