【正文】 , 1, 2, ,iy i m? 表示選不選擇乘第 i 線公交車； , 1, 2, ,iz i m? 表示選不選擇從第 i條公交車下車后走到目的地的路。 (它們都是取 1 表示選擇而取 0 表示不選擇。 ) 恰乘一次公交車的模型如下： 目標函數(shù)：據(jù)用戶選擇的情況用點權和邊權構造，共同點都是最小值。 ( 1)步行時間最少 : 目標函數(shù) 1 , , 111m i nmmm c c d m dcds x s z????????????? (2)總時間最少 : 目標函數(shù) 1 , , 1 1 , 11 1 1 1m i nm m m mi i im c c d m d i m m E i Ec d i is x s z y g v y w? ? ? ?? ? ? ???? ? ?????? ? ? ? 其中3, , , ,iEELv ET??? ? ?? ，3, ,2, ,iEELwET??? ??? (3)車費最少 : 目標函數(shù)：1 , 113 , ,m i n 1 , , , ,20mii m miETF E LygEL???????? ??????????????? ???????? ????單 一分 段 約束條件（共 2m+1 個）： 1 1m ii y? ?? 只選擇一條公交線； , 1 , 2 , ,i i i iy x y z i m? ? ? 要乘第 i條公交線就要走相應的兩條路。 恰乘兩次公交車的模型如下： 步行時間 : 1 , 1 1 1 , 2 2 , 11 1 2 1 1m i nm m mdm c c m c c d mc c ds x s x s z? ? ?? ? ?????????? ? ? 時間最少： 12 1 2 21 , 1 1 1 , 2 2 , 1 1 1 , 1 2 1 , 1 21 1 2 1 1 1 1 2 1 2 1m i nm m m m m mii i i idm c c m c c d m E E Ei m m i m m ic c d i i iy g y g ys x s x s v v wz? ? ? ? ? ? ?? ? ? ? ? ?? ? ? ? ?? ? ? ? ? ? 費用最少： 121 1 , 1 2 1 , 11 1 2 16,m i n 2 ,2 0 2 0mmiii m m i m miiETF E Ly g y g? ? ? ???????? ??????????????????? ????? 約束條件： 121 1 2 1 2mmiiiiyy?????? 可以選擇兩條公交線路； 1212,iiiiyyxx?? 22 iiy z? 乘公交線要走的兩條相應的路線 。 恰乘乘三次公交車模型 : 步行時間的目標函數(shù)在 的基礎上添加 1, 3 331mm c cc sx??? 。 時間最少的目標函數(shù)在 的基礎上添加3 31 , 3 3 3 1 , 13 1 3 1mm i im c c Ei m mci ygs x v? ??????? 。 費用最少 : 3 2 13 1 , 1 2 1 , 1 1 1 , 13 1 2 1 1 19,m i n 3 ,20 20 20m m mi i ii m m i m m i m mi i iETF E Ly g y g y g? ? ? ? ? ?? ? ?????? ?????????????????? ???? ? ? 約束條件即在 的基礎上添加 3i 的變量即可。 五、模型求解 : 問題一： 由于題目所給的公交乘路信息是 .txt 文本文件，為了將實際問題能用數(shù)學模型來解決，我們編寫程序?qū)⑵鋵?matlab。（程序見附錄1）。 對于問題 1，我們僅僅考慮公汽線路，為此，我們將所有的公汽路線與站點（ 3957 個）關系構成一個圖網(wǎng)，為了求得最小代價的選擇路線，我們先建立起直達矩陣（程序見附錄 2），再由改進 floyd 算法（程序見附錄 3）即可求出兩公汽站點之間線路選擇的最小代價（乘換次數(shù)、時間最短、費用最少）， 乘換次數(shù) 為主 、時間最短 和 費用最少 為次 為約束條件 用搜索法 （見附錄程序 5） 搜出最優(yōu)線路， 具體結果如下所示： 起點站 → 終點站 乘換次數(shù) 時間（分鐘） 車費（元） 線路 S3359→ S1828 1 89 3 436 1673359 1784 1828L d L dS S S???? ???? S1557→ S0481 2 112 3 3 6 3 1 8 94601 5 5 7 1 9 1 93 1 8 6 0 4 8 1L u L dLuSS???? ???????? S0971→ S0485 1 119 3 013 4170971 2184 485L d L dS S S???? ???? S0008→ S0073 1 83 2 463 0570008 2083 0073L d L uS S S???? ???? S0148→ S0485 2 106 3 3 0 8 1 5 61560 1 4 8 0 0 3 63 3 5 1 0 4 8 5L u L uLuSS???? ???????? S0087→ S3676 2 52 3 3 0 8 1 5 64170 1 4 8 0 0 3 62 2 1 0 0 4 8 5L u L uLdSS???? ???????? 問題二： 對于問題 2，我們在考慮公汽線路的同時，還需將地鐵線路（ 2 條 地鐵線路 ， 39 個地鐵站點） 考慮進去，同樣 ， 將所提供的公汽（含地鐵轉(zhuǎn)換的公汽）網(wǎng)絡抽象成一個有向賦權圖 ,建立直達矩陣（程序見附錄 4）， 再由改進 floyd 算法（程序見附錄 3）即可求出兩公汽站點之間線路選擇的最小代價（乘換次數(shù)、時間最短、費用最少），以換乘次數(shù) 為主 、時間最短 與 費用最少 為次 為約束條件 用搜索法 （見附錄程序 6） 搜出最優(yōu)線路， 具體結果如下所示： 起點站 → 終點站 乘換次數(shù) 時間（分鐘） 車費（元） 線路 S3359→ S1828 1 89 3 436 1673359 1748 1828L d L dS S S???? ???? S1557→ S0481 2 112 3 0 8 4 1 8 94601 5 5 7 1 9 1 93 1 8 6 0 4 8 1L d L dLSS???? ???????? S0971→ S0485 1 119 3 013 417097 2184 0485L d L dS S S???? ???? S0008→ S0073 1 83 2 159 4740008 0400 0073L d LS S S???? ???? S0148→ S0485 2 106 3 10 2 4 0 2 2 10510 1 4 8 1 4 8 70 4 6 6 0 4 8 5 TL D DLuSS ??????? ?????????? S0087→ S3676 0 50 3 227 36008 7 367 6TDDSS?????????? 問題三： 問題 3 又增設了所有站點之間的步行時間，為了給出任意兩站點之間線路選擇問題的數(shù)學模型。我們則考慮大眾化的想法（優(yōu)先考慮乘換次數(shù)）： [1]若兩個站點之間有直達的公交車，若只有一條，我們毫無條件地選擇；若不止一條，則我們可以利用模型三的優(yōu)化模型進行時間和費用的比較，取最優(yōu)解； [2]同理，若要經(jīng)過轉(zhuǎn)乘一次、二次等轉(zhuǎn)乘情況，若轉(zhuǎn)乘線路只有一種，則選擇之；若轉(zhuǎn)乘線路有多種，則利用模型三的優(yōu)化模型進行時間和費用的比較，取最優(yōu)解。 六、模型 優(yōu)缺點 : 將公交圖 網(wǎng)能用有向賦權圖并建立 直達矩陣，再利用最短路算法及搜索算法得出線路選擇的最優(yōu)線路（含時間最少、費用最少等）； 對于第三問題中的模型，在加入步行時間后，我們能考慮到在乘換次數(shù)最少為優(yōu)先的條件下，利用優(yōu)化模型進行比較是全面些。 鑒于公交系統(tǒng)網(wǎng)絡的復雜性， 我們雖然 采用了修改 floyd 算法，編譯 運行上不太好 ，有待改進 。 七、 參考文獻 : [1]蔡志杰，丁頌康 數(shù)學工程學報 公交線路選擇模型 2021 年 12月 10053085（ 2021） 08011704 [2]朱參世 一種 Warshall 和 Fl oyd 算法 的優(yōu)化方法研究 2021年第四期 10062475（ 2021） 04004303 [3]劉韻，何建農(nóng) 基于交通網(wǎng)絡最短路徑搜索的改進算法 2021 年 10028331（ 2021） 14022003 附錄 : function [ A ] = T_SORT( A ,n , p ) %建立排序函數(shù) % T_SORT( A ,n , p ) % A 根據(jù)第 n行排序 % p=1升序， 2 降 % powered_BY_* SIZE=size(A)。 if p==1 [xx,idx]=sort(A(n,:))。 for i=1:SIZE(1) A(i,:)=A(i,idx)。 end elseif p==2 [xx,idx]=sort(A(n,:),39。descend39。)。 for i=1:SIZE(1) A(i,:)=A(i,idx)。 end end %數(shù)據(jù)處理讀入 matlab： %讀取數(shù)據(jù) clear L a fid = fopen(39。 公汽線路信息 .txt39。,39。r39。)。 i=1。 while 1 tline = fgetl(fid)。 if ~ischar(tline), break, end if strcmp(tline,39。39。) continue end if strcmp(tline(1),39。L39。) str=tline。 continue elseif strcmp(tline,39。END39。) break end if strcmp(tline,39。單一票制 1元。 39。) P=1。 continue elseif strcmp(tline,39。分段計價。 39。) P=2。 continue end if strcmp(tline(1:2),39。上行 39。) L{i,1}=str。 L{i,2}=P。 L{i,3}=39。上行 39。 L{i,4}=tline(4:end)。 i=i+1。 continue elseif strcmp(tline(1:2),39。下行 39。) L{i,1}=str。 L{i,2}=P。 L{i,3}=39。下行 39。 L{i,4}=tline(4:end)。 i=i+1。 continue elseif strcmp(tline(1:2),39。環(huán)行 39。) L{i,1}=str。 L{i,2}=P。 L{i,3}=39。環(huán)行 139。 L{i,4}=strcat(tline(4:end),tline(10:end))。 i=i+1。 %計算來回 L{i,1}=str。 L{i,2}=P。 L{i,3}=39。環(huán)行 239。 L{i,4}=strcat(tline(4:end),tline(10:end))。 i=i+1。 continue elseif strcmp(tline(1),39。S39。) L{i,1}=str。 L{i,2}=P。 L{i,3}=39。來回 139。 L{i,4}=tline。