【正文】 詢計算機系統(tǒng)。對于問題三，將步行看作獨立于公汽、地鐵的第三種交通方式，仍利用問題二中的網絡圖，不再增加有向邊，并假設步行只能沿已有的有向邊行進。再定義01變量fij作為流量，當fij=1時表明該有向邊vivj中有流量通過，即最佳路線包括邊vivj，就可以建立最小費用流模型來求解。公交線路選擇的網絡優(yōu)化模型摘要本文針對城市公交線路選擇問題建立了相應的數(shù)學模型。至于有向邊vivj，并不是公汽站點間的實際線路，而是表明任意兩站點i與j之間能否直達的有向弧，各邊的容量為費用率為bij , 就構造了容量費用網絡。對于問題二，其實就是在問題一的容量費用網絡中增加了39個頂點及部分有向邊，仍舊是一個最小費用流問題，還可以用問題一中的方法求解，只是費用、換乘時間的計算比問題一復雜。關鍵詞：最佳線路；最小費用流；Dijkstra算法；優(yōu)先因子；上限約束一、 問題重述近年來，城市的公交系統(tǒng)有了很大發(fā)展，使得公眾的出行更加通暢、便利，但公眾也同時面臨著多條線路的選擇問題。并根據(jù)附錄數(shù)據(jù)，利用你們的模型與算法，求出以下6對起始站→終到站之間的最佳路線（要有清晰的評價說明）。（2）對題目中基本參數(shù)設定進行補充：同一地鐵站對應的任意兩個公汽站之間通過地鐵站換乘的平均耗時為11分鐘（其中步行時間8分鐘）。（5）所有站點之間都是相通的，即公交線路的實際地理圖是聯(lián)通圖。（9）本文中提到的費用率bij與費用沒有必然聯(lián)系，而是指有向邊的權值。而題目中的三個問題，其實是逐步考慮了公汽、地鐵、步行三種交通方式后的線路選擇問題，而評判某一線路方案好壞的原則是不變的，仍舊是花費、換乘次數(shù)及時間，因此三個問題都可以用網絡流模型來求解。1b12b13b14b23b24b34234圖1設兩個虛擬點作為網絡流的源點S（source）、匯點T（terminal），題目中給出的3957個公交站點與S、T共同構成頂點集V 。所有邊的容量都為1，即cij= cij構成集合C。如圖2，站點1為環(huán)路的始發(fā)站，若該環(huán)路的車輛行駛方向為順時針方向，則有向邊v2v6必須按順時針方向計算，不能按照逆時針方向計算。乘客如果想從站點3到站點5，可以乘坐公交從站點3直達站點5，畫出有向邊v3v5 ，其費用率為b35；但如果乘客想從站點5到站點3（僅考慮圖中這一條線路），則必須走5→2→1→2→3，此時認為乘客走了兩條線路，即在站點1處“換乘”，因而不能畫有向邊v5v31324521上行線下行線b35圖4：1為始發(fā)站，4為上行終點站（下行始發(fā)站）結合實際情況，本文選擇最佳線路時考慮了三個目標：出行花費、換乘次數(shù)、出行時間。根據(jù)假設，環(huán)行線上的各站點都是沒有區(qū)別的。3） 出行時間qij出行時間qij代表公交車從站點i直達到站點j的平均行駛時間。因此不能將三者簡單的動態(tài)加權為一綜合目標，而應分情況討論，不同情況下三個目標的優(yōu)先順序不同。因為當某一目標達到最優(yōu)時，如果其它目標的值很差，也是沒有實際意義的。D：一次轉車可達的頂點集對每個頂點，定義三個標記（l(v)，z(v)，zhuan(v)），其中：l(v)：表示從頂點u0到v的一條路的權；z(v)：v的父親點，用以確定最短路的路線；zhuan(v)：v的轉車次數(shù)，用以確定最短路中到達v點轉了幾次車。根據(jù)以上算法，利用MATLAB編程，就能求出任意兩公汽站點的最佳線路。以后的表格與之類似，不再注明。公汽線路費用計算方法與問題一相同。對于圖5中v1v4 這類邊，由于地鐵換乘地鐵時費時4分鐘，公汽換乘地鐵時費時6分鐘，故本文中設乘客從v1到v4費時2分鐘，即q14=2，q43的設置類似。 本小問中取K = 3，M = 10，Q = 150作為約束。對于目標函數(shù)，如果分別考慮乘車費用、換乘這些單目標時，繼續(xù)沿用問題二中的約束條件，而不附加任何限制，將得不到最佳線路的解。然后在約束條件中加上了步行時間的上限約束：對于最佳線路，分別考慮步行時間、出行總時間、換乘次數(shù)、乘車費用四個單目標下的最優(yōu)解。：換乘次數(shù)最少目標函數(shù)為： 但在考慮換乘次數(shù)最少這個目標時，應加入步行時間、總出行時間的上限約束，來避免全程步行這樣沒有意義的解?？傊攦牲c之間的乘車時間大于步行時間時，就選擇步行。另外網絡流理論研究已相當成熟，非常復雜的問題也能利用計算機在有限的時間內解決。題目中提到某公司要研制開發(fā)一個解決公交線路選擇問題的自主查詢計算機系統(tǒng)，而一個較好的查詢系統(tǒng)應該是智能化的，與查詢者的互動性強。x=load(39。for k=1:929 clear xx。 for i=1:(l1) for j=(i+1):l if w(xx(1,i),xx(1,j))q w(xx(1,i),xx(1,j))=q。 for i=1:(l1) for j=(i+1):l if w(xx(1,i),xx(1,j))q w(xx(1,i),xx(1,j))=q。 while i+j=length(xx(1,:)) if w(xx(1,i),xx(1,i+j))1 w(xx(1,i),xx(1,i+j))=1。 for i=1:(l1) j=1。 elseif j=40 amp。 end j=j+1。 while i+j=l if j=20 amp。amp。 end end elseif x(k,3)==2 %下行 elseif x(k,3)==3 %環(huán)線 xx=[x(k,4:last(x(k,:))1) x(k,4:last(x(k,:))1)]。amp。 w(xx(1,i),xx(1,i+j))2 w(xx(1,i),xx(1,i+j))=2。end w1_1=w。w1_139。C:\Documents and Settings\wly\桌面\新建文件夾\1\b\B2007data\39。 l=length(xx(1,:))。 l=length(xx(1,:))。 l=length(xx(1,:))/2。 end end end elseif x(k,2)==0 %分段 if x(k,3)==0 %往返 xx=[x(k,4:last(x(k,:))) fliplr(x(k,4:last(x(k,:))1))]。 end j=j+1。 while i+j=l if w(xx(1,i),xx(1,i+j))1 w(xx(1,i),xx(1,i+j))=1。 for i=1:l j=1。end w1_2=w。w1_239。C:\Documents and Settings\wly\桌面\新建文件夾\1\b\B2007data\39。 if x(k,3)==0 %往返 xx=[x(k,4:last(x(k,:))) fliplr(x(k,4:last(x(k,:))1))]。 end end end elseif x(k,3)==1 %上行 xx=[x(k,4:last(x(k,:))) x(k+1,4+1:last(x(k+1,:)))]。 end end end elseif x(k,3)==2 %下行 elseif x(k,3)==3 %環(huán)線 xx=[x(k,4:last(x(k,:))1) x(k,4:last(x(k,:))1)]。 if w(xx(1,i),xx(1,i+j))q w(xx(1,i),xx(1,i+j))=q。endw1_3=w。w1_339。C:\Documents and Settings\wly\桌面\新建文件夾\1\b\B2007data\w1_3_時間\39。)。endp=1828。 for j=1:l2 w(i,j)=inf。%%改進的Dijkstra算法m=length(wdao)。ll=l。endclear w1。k=1zhuan=zeros(1,l2)1。 if tem~=s(j) amp。 z(tem)=u。 end lv=inf。 v=tem。endl(1,end)save(39。clear。c=1。 end while x(k,last2+1)~=0 last2=last2+1。 endendtestt=sum(test)。)s=length(z(1,:))1。 ii=ii+1。lj=fliplr(lj)。,39。34