薛申芳，谢小军

(广州工商学院，广东 佛山 510850)

0 引言

目前，地理信息系统和电子地图技术越来越受到广泛应用，关于公交乘车车次选择以及换乘问题已有很多成熟的算法.在文[1]中利用了幂矩阵的性质建立最佳乘车路线数学模型，没涉及换乘问题；在文[2]中利用已有的地理信息系统指定的换乘站点，分别对换乘一次和两次，求从始点站到目标站经过站点最少的最优路线.常用的算法有Floyd算法、Dijkstra算法、蚁群算法[3]；禁忌搜索算法，改进禁忌搜索算法[4].该文针对明晰的公交网络，在不是预先确定换乘站点的情况下，探索距离最短以及确定换乘站点问题，把通常算法中的二维邻接矩阵拓广到四维邻接矩阵，从而可以把换乘要素一并考虑在内，去建立0-1规划模型，通过对简化的公交网络，以及Lingo软件编程计算，去验证模型.

1 问题及其数学模型

对城市公交而言，一般来讲，公交车辆较多，线路交叉、错综复杂.城市公交乘客从某站要乘车到达某目的站时往往有多种乘坐(包括换乘)路线，不同的乘坐路线又致乘坐的站次不同，乘客都需要考虑乘坐最佳路线(以乘坐路程最短为原则)以节省时间、费用和公交资源.在考虑模型时忽略步行换乘要素，即换乘时下车站点就可换乘.

以各站点为顶点，以公交线路及方向为边，以相邻站点的路程长度为权，便可得到一个赋权有向图G(V，E)[5]，其中：

V={S1，S2，…，SN}

这里Si表示第i个站点，N表示公交站点总数.且假设公交车共有M条线路(即M路车)：

L1，L2，…，LM.

记dij为两个相邻站点Si，Sj的距离；图G(V，E)的四维邻接矩阵w(i，j，m，n)定义为：

四元0-1变量x定义为：

假设顾客要从Si0站点去往Sj0站点，该问题的优化模型.

目标函数：

从Si0到Sj0站行程最短

(1)

约束条件：

当Si不是起始站点或目标站点时(i=1，2，…，N，i≠i0，i≠j0)，乘客乘任意路车到达其他任意站次数，应该等于乘客乘任意路从其他任意站点车开往Si站的次数，即.

(2)

从起始站点Si0只能乘坐某一路车去往其他某一个站点，即

(3)

乘坐任意路车从其他站点不能去往起始站点Si0，即

(4)

乘坐任意路车从其他站点去往目标站点Sj0只能一次，即

(5)

从目标站点Sj0不能再乘坐任意路车去往其他任意站点，即

(6)

以上(1)—(6)式即为该问题的数学模型.

2 模型验证求解

图1 公交网络图

为了验证上述数学模型，就下面简化的公交线路(见图1，即取N=7，M=2)的具体情况，利用Lingo[6]软件编程进行求解验证.在图1中，有向实线(记之为L1)和有向虚线(记之为L2)给出了不同的两路公交车的两条环路，任意两个相邻站点之间的距离在图1中标识，共有7个站点：S1，S2，S3，S4，S5，S6，S7；乘客在任意一个站点Si0站上车要达到任意一个目的站点Sj0，去确定乘客乘车路程最短的最佳乘车路线、换乘站点和换乘车次问题.

根据数学模型(1)—(6)式，假设起始站点为S1(即i0=1)，乘客要去往目标站点S7(即j0=7)，当w(i，j，m，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));

计算结果为：目标函数值为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，上面程序稍加修改后得到计算结果为：目标函数值为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，乘车路线和换乘情况是：

上述计算结果显然符合实际.

3 结论

该文针对城市公交网络中乘客的乘车距离最短为最优、换乘站点、换乘车次确定的有向图问题，传统方法的二维邻接矩阵只能解决单向边或双向边的有向图问题；拓广到四维邻接矩阵可以去研究有边向重复，而边向重复代表着不同方向类型的复有向图问题，它的深入研究具体有一定的理论价值.该方法在图节点较多时，带来四维矩阵的阶数较大带来的计算上困难，在上车站点、下车站点确定之后，可结合公交网络信息系统，采用剔除无用站点得到简化，以及若把乘车时间最省为最优的换乘(再考虑换乘耗费的时间)问题，这些可作为后面的深入讨论.