公交乘車(chē)最佳換乘路線問(wèn)題

薛申芳，謝小軍

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

0 引言

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

1 問(wèn)題及其數(shù)學(xué)模型

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

以各站點(diǎn)為頂點(diǎn)，以公交線路及方向?yàn)檫叄韵噜徴军c(diǎn)的路程長(zhǎng)度為權(quán)，便可得到一個(gè)賦權(quán)有向圖G(V，E)[5]，其中：

V={S1，S2，…，SN}

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

L1，L2，…，LM.

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

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

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

目標(biāo)函數(shù)：

從Si0到Sj0站行程最短

(1)

約束條件：

當(dāng)Si不是起始站點(diǎn)或目標(biāo)站點(diǎn)時(shí)(i=1，2，…，N，i≠i0，i≠j0)，乘客乘任意路車(chē)到達(dá)其他任意站次數(shù)，應(yīng)該等于乘客乘任意路從其他任意站點(diǎn)車(chē)開(kāi)往Si站的次數(shù)，即.

(2)

從起始站點(diǎn)Si0只能乘坐某一路車(chē)去往其他某一個(gè)站點(diǎn)，即

(3)

乘坐任意路車(chē)從其他站點(diǎn)不能去往起始站點(diǎn)Si0，即

(4)

乘坐任意路車(chē)從其他站點(diǎn)去往目標(biāo)站點(diǎn)Sj0只能一次，即

(5)

從目標(biāo)站點(diǎn)Sj0不能再乘坐任意路車(chē)去往其他任意站點(diǎn)，即

(6)

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

2 模型驗(yàn)證求解

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

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

根據(jù)數(shù)學(xué)模型(1)—(6)式，假設(shè)起始站點(diǎn)為S1(即i0=1)，乘客要去往目標(biāo)站點(diǎn)S7(即j0=7)，當(dāng)w(i，j，m，n)=+∞時(shí)，在計(jì)算時(shí)取為適當(dāng)大的數(shù)(遠(yuǎn)大于任意兩站點(diǎn)之間的距離即可，這里取為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));

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

類(lèi)似地，若取i0=6，j0=1，上面程序稍加修改后得到計(jì)算結(jié)果為：目標(biāo)函數(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.這說(shuō)明始站點(diǎn)為S6，乘客要去往目標(biāo)點(diǎn)站點(diǎn)S1的最短距離為10，乘車(chē)路線和換乘情況是：

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

3 結(jié)論

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