薛申芳，謝小軍

(廣州工商學院，廣東 佛山 510850)

0 引言

目前，地理信息系統(tǒng)和電子地圖技術(shù)越來越受到廣泛應用，關于公交乘車車次選擇以及換乘問題已有很多成熟的算法.在文[1]中利用了冪矩陣的性質(zhì)建立最佳乘車路線數(shù)學模型，沒涉及換乘問題；在文[2]中利用已有的地理信息系統(tǒng)指定的換乘站點，分別對換乘一次和兩次，求從始點站到目標站經(jīng)過站點最少的最優(yōu)路線.常用的算法有Floyd算法、Dijkstra算法、蟻群算法[3]；禁忌搜索算法，改進禁忌搜索算法[4].該文針對明晰的公交網(wǎng)絡，在不是預先確定換乘站點的情況下，探索距離最短以及確定換乘站點問題，把通常算法中的二維鄰接矩陣拓廣到四維鄰接矩陣，從而可以把換乘要素一并考慮在內(nèi)，去建立0-1規(guī)劃模型，通過對簡化的公交網(wǎng)絡，以及Lingo軟件編程計算，去驗證模型.

1 問題及其數(shù)學模型

對城市公交而言，一般來講，公交車輛較多，線路交叉、錯綜復雜.城市公交乘客從某站要乘車到達某目的站時往往有多種乘坐(包括換乘)路線，不同的乘坐路線又致乘坐的站次不同，乘客都需要考慮乘坐最佳路線(以乘坐路程最短為原則)以節(jié)省時間、費用和公交資源.在考慮模型時忽略步行換乘要素，即換乘時下車站點就可換乘.

以各站點為頂點，以公交線路及方向為邊，以相鄰站點的路程長度為權(quán)，便可得到一個賦權(quán)有向圖G(V，E)[5]，其中：

V={S1，S2，…，SN}

這里Si表示第i個站點，N表示公交站點總數(shù).且假設公交車共有M條線路(即M路車)：

L1，L2，…，LM.

記dij為兩個相鄰站點Si，Sj的距離；圖G(V，E)的四維鄰接矩陣w(i，j，m，n)定義為：

四元0-1變量x定義為：

假設顧客要從Si0站點去往Sj0站點，該問題的優(yōu)化模型.

目標函數(shù)：

從Si0到Sj0站行程最短

(1)

約束條件：

當Si不是起始站點或目標站點時(i=1，2，…，N，i≠i0，i≠j0)，乘客乘任意路車到達其他任意站次數(shù)，應該等于乘客乘任意路從其他任意站點車開往Si站的次數(shù)，即.

(2)

從起始站點Si0只能乘坐某一路車去往其他某一個站點，即

(3)

乘坐任意路車從其他站點不能去往起始站點Si0，即

(4)

乘坐任意路車從其他站點去往目標站點Sj0只能一次，即

(5)

從目標站點Sj0不能再乘坐任意路車去往其他任意站點，即

(6)

以上(1)—(6)式即為該問題的數(shù)學模型.

2 模型驗證求解

圖1 公交網(wǎng)絡圖

為了驗證上述數(shù)學模型，就下面簡化的公交線路(見圖1，即取N=7，M=2)的具體情況，利用Lingo[6]軟件編程進行求解驗證.在圖1中，有向?qū)嵕€(記之為L1)和有向虛線(記之為L2)給出了不同的兩路公交車的兩條環(huán)路，任意兩個相鄰站點之間的距離在圖1中標識，共有7個站點：S1，S2，S3，S4，S5，S6，S7；乘客在任意一個站點Si0站上車要達到任意一個目的站點Sj0，去確定乘客乘車路程最短的最佳乘車路線、換乘站點和換乘車次問題.

根據(jù)數(shù)學模型(1)—(6)式，假設起始站點為S1(即i0=1)，乘客要去往目標站點S7(即j0=7)，當w(i，j，m，n)=+∞時，在計算時取為適當大的數(shù)(遠大于任意兩站點之間的距離即可，這里取為100)，Lingo程序如下：

sets:zhan/1..7/;zz(zhan，zhan);L/1..2/;LL(L，L);link(zhan，zhan，L，L):w，x，e;endsetsdata:w=100;enddata calc:

w(1，2，1，1)=2;w(2，3，2，2)=1;w(2，3，1，2)=1;w(2，6，1，1)=5;w(2，6，2，1)=5;w(3，1，1，1)=3;

w(3，1，2，1)=3;w(3，4，2，2)=2;w(4，3，1，1)=2;w(4，5，2，2)=3;w(4，5，2，2)=4;w(5，4，1，1)=3;

w(5，6，2，2)=3;w(6，5，1，1)=3;w(6，7，1，2)=4;w(6，7，2，2)=4;w(7，2，2，2)=2;

endcalc n=@size(zhan);

min=@sum(link:w*x);@for(link(i，j，s，t):e(i，j，s，t)=@if(s#ne#t，2，0)*x(i，j，s，t));

@for(L(s):@for(zhan(i)|i#ne#1#and#i#ne#n:@SUM(link(i，j，s，t):x(i，j，s，t))=@SUM(link(i，j，s，t):x(j，i，t，s))));

@sum(zhan(i):@sum(LL(s，t):x(1，i，s，t)))=1;@sum(zhan(i):@sum(LL(s，t):x(i，1，s，t)))=0;

@sum(zhan(i):@sum(LL(s，t):x(i，n，s，t)))=1;@sum(zhan(i):@sum(LL(s，t):x(n，i，s，t)))=0;

@for(link:@bin(x));

計算結(jié)果為：目標函數(shù)值為11，x(1，2，1，1)=1，x(2，6，1，1)=1，x(6，7，1，2)=1.這說明始站點為S1，乘客要去往目標點站點S7的最短距離為11，乘車路線和換乘情況是：

類似地，若取i0=6，j0=1，上面程序稍加修改后得到計算結(jié)果為：目標函數(shù)值為10，x(6，7，2，2)=1，x(7，2，2，2)=1，x(2，3，2，2)=1，x(3，1，2，1)=1.這說明始站點為S6，乘客要去往目標點站點S1的最短距離為10，乘車路線和換乘情況是：

上述計算結(jié)果顯然符合實際.

3 結(jié)論

該文針對城市公交網(wǎng)絡中乘客的乘車距離最短為最優(yōu)、換乘站點、換乘車次確定的有向圖問題，傳統(tǒng)方法的二維鄰接矩陣只能解決單向邊或雙向邊的有向圖問題；拓廣到四維鄰接矩陣可以去研究有邊向重復，而邊向重復代表著不同方向類型的復有向圖問題，它的深入研究具體有一定的理論價值.該方法在圖節(jié)點較多時，帶來四維矩陣的階數(shù)較大帶來的計算上困難，在上車站點、下車站點確定之后，可結(jié)合公交網(wǎng)絡信息系統(tǒng)，采用剔除無用站點得到簡化，以及若把乘車時間最省為最優(yōu)的換乘(再考慮換乘耗費的時間)問題，這些可作為后面的深入討論.