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

《Dijkstra算法的打车软件司机端选择最短距离乘客优化问题》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、2014年6月地理空间信息Jun.,2014第12卷第3期GEOSPATIALINFORMATIONVol.12,No.3doi:10.11709/j.issn.1672-4623.2014.03.016Dijkstra算法的打车软件司机端选择最短距离乘客优化问题1何其祎（1.武汉工程大学，湖北武汉430205）摘要：对打车软件司机端所运用的包括移动终端定位技术模块、无线数据链路通信模块、搜索模块、抢单模块、最短路程规划模块进行分析，针对当前一般打车软件中依据平面最短距离选择乘客的现状，提出基于Dijkstra算法的依据司机端与乘客最短距离

2、选择合适乘客的方案，并对路线模块进行优化。关键词：最短路径；Dijkstra算法；打车软件；导航中图分类号：P208文献标志码：B文章编号：1672-4623（2014）03-0052-02近年来，城区“打车难”问题一直难以解决，打S={V}，顶点V到自身的距离为0。U包含除源点以外车软件的出现在一定程度上缓解了这一矛盾。但是部所有顶点，比较V到U中顶点距离（非邻接点距离为∞），分打车软件的司机端在选择乘客时，并未真正依据的将距离最小顶点P取出放入S中，选定距离即为V到士与乘客的实际最短距离给出最佳的乘客推荐，或给P的最短路径长度；②以顶点

3、P为新的考虑点，修改司机的线路选择余地很小。本文将运用最短路径算法顶点V到U中各顶点的距离：若从源点V到顶点U的中的Dijkstra算法对打车软件司机端的选客程序进行探距离（经过P）比原来距离（不经过P）短，则修改顶讨。文中提出的方法，可以针对的士与乘客的两点间点U的距离值，修改后的距离值为顶点V到顶点P加最短路径给出最为合理的选客方案。上边（P,U）上的权；③重复上述步骤直到S包含所有顶点。1最短路径图1为Dijkstra算法示例，由点1到点3的步骤为：在一个无权的图中，若从其中一个顶点到另一个①由点1出发，比较点1到其相邻点点2、点4、

4、点5顶点存在一条路径，则该路径所经过的边的数目为该的距离，可知到点2距离最近，权值为10；②更新源路径长度。在大多数情况下，两顶点间有多条路径，点为点2，此时点2的相邻点为点3，权值为50；③更每条路径经过的点不同，路径长度也不同，我们称路新源点为点3，到达终点，最终权值为10+50=60。径长度最短的那条叫做最短路径。1对于带权的图，考虑路径各边的权值，将一条路10100径上所经过边的权值之和定义为该路径的带权路径长度，并将带权路径最短的那条称为最短路径，其权值2530之和称为最短路径长度或最短距离。5030602Dijkstra算法基本

5、思想3204设G=（V，E）是一个带权有向图，将所有顶点V分为两组，第一组为已求出最短路径的顶点集合，用S图1Dijkstra算法示例图表示，初始是S中只有源点，随后每求出一条最短路径，3应用V1，V2，⋯VK都加入到S中，算法结束。第二组为未确定最短路径的顶点集合，用U表示，按最短路径长3.1算法分析度的递增次序依次将U中顶点放入S中，在向S中添要使用Dijkstra算法进行最短路径分析，首先要加顶点时，要保持从源点V到S中各顶点的距离为最将整个道路交通构造成赋权有向图G。令道路的交叉短路径，具体步骤为：①初始时，S中只包含源点，即点与有

6、向图中的节点对应，道路与有向图中的弧对应，收稿日期：2014-03-20。第12卷第3期何其祎：Dijkstra算法的打车软件司机端选择最短距离乘客优化问题·53·弧的方向与行车方向一致（单行线只对应一条弧，双以司机选择乘客，软件依据实际路面距离给出相应选行线则对应两条弧）。具体的权值可以依据以下原则配择及最优路线为例，来说明路线优化算法的步骤及相赋，用户可以在下面3种方法中任选一种进行操作：关技术模块的使用。①按照道路具体长度计算（软件中对应选项为“路程1）利用移动终端定位模块对车辆进行定位最短”）；②按照经过路口个数最少计算（软件中对应

7、设在某一时刻t，车辆的坐标为（x，y），记为点选项为“红绿灯最少”）；③按照行驶时间计算（软件A，司机通过打车软件的移动终端定位模块将所在坐标中对应选项为“时间最短”）。传至监控中心，附近区域内存在n个下单乘客，记第k经过权值配赋后，整个道路交通网就构成了一个个乘客为Sk（k=1，2，⋯，n），其所在坐标为（xk，yk）。符合Dijkstra算法的赋权有向图，且不存在负权值的情2）利用搜索模块对附近乘客进行搜索况。本文采用道路实际长度作为权值进行优化线路的Step1令k=1。计算。Step2以点A为中心，R为半径画圆，圆内区域即假设路径网络

8、矩阵为T，车辆由路口m到n的距为搜索区域，记区域内所有要打车乘客的集合为W，离存在直线行驶距离、环线行驶距离及转弯距离等不则有SkW，可根据实际情况放大或缩小R，计算ASk，同