郭瑞军，王晚香

(大连交通大学 交通运输工程学院，辽宁 大连 116028)

0 引言

城市公共交通是由不同运量的轨道交通、公交汽车及出租车组成.出租车因为其方便、快捷、灵活、舒适和可以满足人们日益丰富的出行需要等特点，成为公共交通必不可少的组成部分.

自上世纪70年代，许多国家采取了对出租车市场经济管制的宽松政策，如澳大利亚、瑞典、瑞士、英国和美国等，解除或者放宽对经营者服务的形式、区域以及营运线路、车辆等要求［1］.出租车合乘的形式也逐渐出现，“合乘”也称“拼客”、“拼车”，坐几个人可以由司机来决定，只要乘客去往同一方向，司机可以向每个客人收取独自乘车应收取的费用.目前在我国出租车“合乘制”还没有相关部门的严格定义，本文暂规定两个或两个以上互不相识的乘客在同一地点同时乘坐一辆出租车去往相同或相近的目的地，这种乘坐出租车的方式叫做出租车合乘.

合乘方式改变了传统的出租车一次运营的单一目的地形式，既充分利用了道路资源又减少了出租车的空驶，为提高我国大城市出租车运输效率、改变我国大城市出租车运营现状、解决城市交通拥挤和汽车空驶造成的环境污染问题提出了一种解决方案.

随着出租车合乘形式的日益增多，合乘方式运营的规范化，乘车费用的计算以及对乘客和驾驶员权益的保障等问题均须解决.卢川等人对合乘的类型划分、合乘信息的发布与反馈、合乘车辆数的确定以及出租车准点到达的技术保障等问题进行了相关探讨［2］;覃运梅等人提出了考虑出租车司机和乘客利益双赢的数学模型，并利用Floyd方法求出最短路以确定行驶路线，计算乘车费用［3］.邹四发等人根据道路交通网络模型计算出租车合乘时的最短路径，并分析了城市道路中的实际问题对最短路径网络的影响等［4-5］.论文针对出租车合乘的线路选择，运用矩阵迭代法来求解道路交通网络中的最短路径.

1 矩阵迭代法

1.1 最短路径算法

最短路径算法是交通流分配中最基本的算法，几乎所有的交通流分配方法都将它作为一个基本子过程反复使用.最短路径算法的设计问题是图论、运筹学和交通规划领域的学者们广为关注的问题，因此设计出了多种方法［6］.所谓的最短路径问题，就是在一个网络中，相邻节点间的线路长度是已知的，要从某一起点到某一终点之间，找出一条路线长度最短的通路.

最短路问题的分析分为两类:①起点到终点的最短路问题;②任意点之间的最短路问题.

由于本文主要解决出租车从起点到两个终点的最短路径，同时还要求终点间的最短路径，所以需分析任意点间的最短路问题.本文利用矩阵迭代法［7］来求解最短路径.

1.2 矩阵迭代法的算法步骤

构造距离矩阵(以距离为权的权矩阵)，矩阵给出了节点间只经过一步(一条边)到达某一点的距离，如图1所示.对距离矩阵进行迭代运算，得到经过两步到达某一点的最短距离.

因此，研究出租车的最短路径问题时，需要知道各个出行节点之间的最短路线.可以利用距离矩阵求解最短路的方法.

首先需构造一个距离矩阵D=［dij］，如图1中的距离矩阵D为

这个矩阵给出了只经过一步就能到达某点的最短距离，若想知道两步到达某一点的最短距离，可对局阵进行如下计算:

同样经过三步、四步到达某一节点的最短距离为:

这时，D(4)=D(3)为最短距离矩阵，通过矩阵可得出最短距离.

最后通过反向追踪来确定相应的最短路线.在研究两位乘客同时乘一辆出租车去不同地点时，应先考虑将其中一位乘客送达目的地后再送另一位乘客.可以先利用矩阵迭代法找出到达第一个目的地的最短路径，然后再用同样方法找出从第一个目的地到终点的最短路径，从而使得总的路线最短.

2 利用矩阵迭代法求出租车合乘的最短路径

出租车合乘路线选择模型中，合乘的乘客必须是在合乘站点上车去往同一方向的两个不同目的地，且目的地之间距离相近.在获得两名乘客的目的地后，出租车司机可以按照道路交通网络模型选择最短路径的走法并且在行驶过程中不再搭载其它乘客.

图2 道路网络实例

道路网络如图2所示，如果出租车司机要将两位乘客A和B分别送到各自的地第6点和第8点，则首先要找出从出发点1到目的地6的最短距离a、出发点1到目的地8的最短距离b和目的地6和8之间的最短距离c.然后用最短距离a和最短距离b中的最小值与最短距离c相加就得到出租车将两位乘客送达两个目的地所需最短距离.最后，通过反推法找出出发点到两个目的地的最短路径.

(1)根据图2所示得出距离矩阵为:

经过第一次迭代运算后，得到两步到达任意点的最短距离，如

同理，可以根据计算求出其他元素，得到D(2)距离矩阵.

(2)根据距离矩阵D(2)计算D(3)

然后得出距离矩阵D(3)，同理，可计算D(4)，D(5)，… ，D(n).

(3)经过不断迭代计算直到得出 D(8)=D(9)，最终的最短距离矩阵为:

因此，可以由上述距离矩阵查出网络图中任意两点之间的最短距离.例如:出发点1到目的地6的最短距离a=4、出发点1到目的地8的最短距离b=5和目的地6和8之间的最短距离c=3.由于最短距离a和最短距离b中的最小值与最短距离c相加就得到出租车将两位乘客送达两个目的地所需最短距离，所以从起点分别到两个终点的最短距离为4+3=7.

(4)找出最短路径

通过反向追踪法找最短路径.首先从最短路径的起点开始，根据起点到各节点的最短路权来搜索最短路径的每个节点直到路网的终点.

设r为起点，s为终点

①从起点r开始，寻找与r相邻的节点i满足

其中，dri为 r到 i的距离;Lmin(i，s)为 i到 s的最短路权;Lmin(r，s)为r到s的最短路权.

②再找到 i到相邻点 j，满足 dij+Lmin(j，s)=Lmin(i，s)

如上例所示，从起点1开始到6的最短路径为1－4－5－6;从目的地6开始到8的最短路径为6－5－8.

由此可知，从起点1开始将两位不同的乘客送到两个目的地6和8时，可以走的最短路径是1－4－5－6－5－8.

3 结论

出租车运营行业通过发展合乘制，可以降低出租车负面外部效应，减少了城市环境污染和噪声污染，降低了城市交通阻塞和交通事故发生率，使得人、车、路得到有效的利用，使出租车营运符合可持续发展的交通要求.

本文利用了运筹学中最短路径的矩阵迭代法建立交通网络模型，从理论上解决出租车在合乘时的路线选择问题.今后研究的内容应集中在相关制度的制定上，以保证出租车合乘的安全、规范运营.

［1］王罗.出租车共乘问题研究［D］.长沙:长沙理工大学，2008.

［2］卢川，吴群.城市居民出行合乘出租车问题的研究［J］.道路交通与安全，2007，7(5):52-55.

［3］覃运梅，石琴.出租车合乘模式的探讨［J］.合肥工业大学学报(自然科学版)，2006，28(1):77-79.

［4］邹旭东，郑四发.具有交通限制约束的道路网络最优路径算法［J］.公路交通科技，2002，19(4):82-84.

［5］周培德.交通道路网中任意两点之间最短路径的快速算法［J］.计算机科学与工程，2002，24(4):35-37.

［6］王炜.道路交通工程系统分析方法［M］.北京:人民交通出版社，2001.

［7］运筹学教材组.运筹学(修订版)［M］.北京:清华大学出版社，1990.