Dijkstra算法的打车软件司机端选择最短距离乘客优化问题

何其祎

（1.武汉工程大学，湖北 武汉 430205）

近年来，城区“打车难”问题一直难以解决，打车软件的出现在一定程度上缓解了这一矛盾。但是部分打车软件的司机端在选择乘客时，并未真正依据的士与乘客的实际最短距离给出最佳的乘客推荐，或给司机的线路选择余地很小。本文将运用最短路径算法中的Dijkstra算法对打车软件司机端的选客程序进行探讨。文中提出的方法，可以针对的士与乘客的两点间最短路径给出最为合理的选客方案。

1 最短路径

在一个无权的图中，若从其中一个顶点到另一个顶点存在一条路径，则该路径所经过的边的数目为该路径长度。在大多数情况下，两顶点间有多条路径，每条路径经过的点不同，路径长度也不同，我们称路径长度最短的那条叫做最短路径。

对于带权的图，考虑路径各边的权值，将一条路径上所经过边的权值之和定义为该路径的带权路径长度，并将带权路径最短的那条称为最短路径，其权值之和称为最短路径长度或最短距离。

2 Dijkstra算法基本思想

设G=（V，E）是一个带权有向图，将所有顶点V分为两组，第一组为已求出最短路径的顶点集合，用S表示，初始是S中只有源点，随后每求出一条最短路径，V1，V2，…VK都加入到S中，算法结束。第二组为未确定最短路径的顶点集合，用U表示，按最短路径长度的递增次序依次将U中顶点放入S中，在向S中添加顶点时，要保持从源点V到S中各顶点的距离为最短路径，具体步骤为：①初始时，S中只包含源点，即S={V}，顶点V到自身的距离为0。U包含除源点以外所有顶点，比较V到U中顶点距离（非邻接点距离为∞），将距离最小顶点P取出放入S中，选定距离即为V到P的最短路径长度；②以顶点P为新的考虑点，修改顶点V到U中各顶点的距离：若从源点V到顶点U的距离（经过P）比原来距离（不经过P）短，则修改顶点U的距离值，修改后的距离值为顶点V到顶点P加上边（P,U）上的权；③重复上述步骤直到S包含所有顶点。

图1为Dijkstra算法示例，由点1到点3的步骤为：①由点1出发，比较点1到其相邻点点2、点4、点5的距离，可知到点2距离最近，权值为10；②更新源点为点2，此时点2的相邻点为点3，权值为50；③更新源点为点3，到达终点，最终权值为10+50=60。

图1 Dijkstra算法示例图

3 应 用

3.1 算法分析

要使用Dijkstra算法进行最短路径分析，首先要将整个道路交通构造成赋权有向图G。令道路的交叉点与有向图中的节点对应，道路与有向图中的弧对应，弧的方向与行车方向一致（单行线只对应一条弧，双行线则对应两条弧）。具体的权值可以依据以下原则配赋，用户可以在下面3种方法中任选一种进行操作：①按照道路具体长度计算（软件中对应选项为“路程最短”）；②按照经过路口个数最少计算（软件中对应选项为“红绿灯最少”）；③按照行驶时间计算（软件中对应选项为“时间最短”）。

经过权值配赋后，整个道路交通网就构成了一个符合Dijkstra算法的赋权有向图，且不存在负权值的情况。本文采用道路实际长度作为权值进行优化线路的计算。

假设路径网络矩阵为T，车辆由路口m到n的距离存在直线行驶距离、环线行驶距离及转弯距离等不同的情况。①直行长度即为道路长度，设为dij；②弧形道路长度及转弯长度可根据弧长公式进行计算：l =απr/180°（α为圆心角），令其为Cij；③因为路况等不确定因素还可能造成别的延长路径，需根据实际情况来确定，在此将其定为β。综上所述，路径权值可表达为：L=dij+Cij+β。若道路出现交通管制或封闭，此时车辆无法通过该路段，则该路径权值可表达为：L=∞。

3.2 技术应用

打车软件司机端优化技术中，除了路线优化技术，还需实现无线数据链路通信模块、移动终端定位模块、搜索模块、抢单模块等。本文主要针对如何采用最短路径技术，帮助司机快速确定合理的候选乘客，并抵达乘客所在地为研究目标，给出相应的解决方案。

在实际打车软件的使用中，存在服务端与司机端、乘客端的通信。其中，服务端与乘客端的通信不在本文讨论之列，服务端与司机端的通信是为了：①确定的士的实时位置；②以的士所在的位置为中心，传送一定范围内的下单乘客的数据，包括乘客位置、与当前司机的距离、是否已被其他司机抢单等；③交易完成后，进行资金结算。

本文主要是对上述的第②种情况进行优化。目前，大多数打车软件司机端应用中，服务端主要是依据的士与候选乘客之间的平面距离为参照，发送候选乘客的请求到司机端。这样做的好处是服务端计算量小，便于快速处理海量的乘客请求。缺点是平面距离不能代表乘客与的士的实际路面距离，在某些特殊情况下，甚至出现非常大的偏差，从而误导司机的选择。下面以司机选择乘客，软件依据实际路面距离给出相应选择及最优路线为例，来说明路线优化算法的步骤及相关技术模块的使用。

1）利用移动终端定位模块对车辆进行定位

设在某一时刻t，车辆的坐标为（x，y），记为点A，司机通过打车软件的移动终端定位模块将所在坐标传至监控中心，附近区域内存在n个下单乘客，记第k个乘客为 Sk（k=1，2，…，n），其所在坐标为（xk，yk）。

2）利用搜索模块对附近乘客进行搜索

Step1 令 k=1。

Step2 以点A为中心，R为半径画圆，圆内区域即为搜索区域，记区域内所有要打车乘客的集合为W，则有SkÎW，可根据实际情况放大或缩小R，计算ASk，若ASk≤R，则SkÎW，将这些乘客点反馈到司机用户端上。若W={Sk|ASk≤R}=Æ，则适当放大R，直至W={Sk|ASk≤R}≠Æ，再进行下一步。

3）利用判断订单状态模块选择候选乘客

Step1 附近区域下单乘客集合为W，令第k个乘客打车状态为kp（k=1，2，…，n；p=1或0）。

Step2 判断kp的取值，若p=1，则该乘客已经接受到预订，转Step1；若p=0，保存该乘客位置信息SkÎW，判断k=n，若成立则进行下一步。

4）利用路线优化技术规划最优路线

用Dijkstra方法计算赋权有向图中，从司机所在点A到其周围所有Sk的最短路径，在得到的n个最短路径中选择最短者，其对应的乘客就是司机应选择的乘客。再按照上述步骤给出最优路径，司机按照软件所给出的指示即可到达。

[1]李春葆,尹为民,李蓉蓉,等.数据结构教程 [M].北京:清华大学出版社,2009

[2](美)维斯.数据结构与算法分析C++描述[M].北京:人民邮电出版社,2007

[3]翟振,孙鑫,李志锋.基于Dijkstra算法的车辆导航系统路线优化技术[J].测绘科学,2008(增刊):227-228

[4]付立家,巨永锋.基于Dijkstra算法的停车诱导系统路线优化技术研究[J].中国公共安全,2006(1):118-119

[5]王维民.我国城市智能交通系统的发展[J].黑龙江交通科技,2010(7): 234-235

[6]余冬梅,张秋余,马少林,等.Dijkstra算法的优化[J].计算机工程,2004(22): 145-146