移动互联网合乘系统.doc

私家车合乘系统 一．合乘趋势 公共交通日益发达的今天，私家车日渐普及，“出行难”早已成为都市人每天面对的一道难题。私家车合乘出行将成为未来交通的一种趋势，用自己的私家车搭载同路人出行，大家分担经济成本后享受出行的舒适快捷，合乘者只需要给私车主分担一点油费就可以解决“公交太慢、地铁太挤、打的太贵”的上下班交通问题。拼车既降低了社区居民的交通成本，提高了出行的效率。私人之间的“拼车”流行于苦于交通拥挤的白领一族，繁荣于热爱旅游的时尚一族。客观上来说，这对缓解交通压力大有裨益，同时还使私家车这种社会资源得到了有效利用，可谓一举多得。这一做法给乘车人带来了实惠，降低了空车率，提高了路面效益，同时减少了私人小汽车拥有量，还能减少城市环境污染，对城市中所有的人都有利。 二．合乘简述 私家车合乘系统是基于安卓/ios系统的智能选择合乘最短路线的app应用，具有寻客和寻车的功能，私家车主居于主动方。 私家车的车主，使用“寻客“功能将起点和终点发送到服务器。乘客，可以通过“寻车”功能，将自己的所在位置发送到服务器，乘客所在位置的上车点同车主的起点和终点构成一个路线网路图，服务器会根据车主所在位置，计算出到达目的地的最短路线和需要消耗费用，以及在最短路线可以得到的收益服务器将根据车主与乘客的需求，按照优先级将乘客的信息依次排列列出给车主，车主可以根据自己时间安排和方便度选择最佳路线。车主根据提供的最佳路线，与次路线上的乘客进行匹配，乘客也可以根据自己的时间和方便度，决定是否与车主匹配，匹配成功后，车主和乘客都会收到服务器发来的信息。乘客成功上车并一起达到目的地便顺利完成一次合乘。 三．合乘算法 1、 合乘优先级算法思想[1] 合乘有两种情况第一种为邻里之间的合乘，第二种为私家车与中途乘车的合乘，对于第二种，基于最短路的特性，即如果P是从D中从vs到vj的最短路，vi是P中的一个点，那么，从vs沿P到vi的路是从vs到vi的路中最短的.这一特性可以用反证法得以证明.如果结论不成立，设Q是从vs到vi的最短路，令Pˊ是从vs沿Q到达vi，再从vi沿P到达vj的路，那么,Pˊ的权就要比P的权小，这与P是从vs到vj的最短路矛盾。根据这一特性，不难想到：将vi从vs移到D中各点vj，即可得vs到vj的最短路。要使这一过程得以实现，对于所有的wij≥0的情形，目前公认最好的方法是由E.W.Dijkstra于1959年提出来的。 Dijkstra方法的基本思路是从vs出发，逐步地向外探寻最短路。执行过程中，给每个顶点予以标号，它或者表示从vs到该点的最短路的权，称为P标号（或称永久性标号，即某点vj一旦得到P标号，其标号值在整个计算过程中不改变）；或者表示从vs到该点的最短的权的上界，称为T标号（也称临时性标号或试探性标号，即某点vj得到T标号，其标号值是可以改变的）.方法的每一步是修改T标号，并且把某一个具有T标号的点改为具有P标号的点，最多经过n-1步（n为图D中顶点数）就可以求出从vs到各点的最短路。 2、有向图的Dijkstra算法基本框图如下： 程序原理框图1  程序原理框图1 开始给起点v1标上P标号，P（v1）=0(即d(v1,v1)=0);其余各点标上T标号，T（vj）=+∞.S为已得P标号的店的集合即S={v1}，?={v2,v3…vn} 第一步，设v1是刚刚得到P标号的点，考虑所有与vi相邻的点vj（指以vi为始点的弧的终点vj）,即（vi，vj）∈A,且vj 的标号为T标号（具有P标号的vj不考虑），则修改vj的T标号，使得：T（vj）=min{T(vj),P(vi)+（wij）} 对于所有与vi不相邻的点vj：T（vj）= T（vj） 第二步，若D中没有T标号的点，则算法停止，即已求出从始点到达各点的最短路权。 否则：T(vj0)=min{T(vj)} 若有多个T（vj）最小，则任取一个，然后把点vj0的T标号修改为P标号，转入第一步，其流程如图1（求v1到vn的最短路） 例1：用Dijkstra算法求图2所示出发地v1到目的地v7的最短路及最短路长。（注：v2 ~ v6为乘客所在地点，弧上为两地点之间的距离）  图2 解 起点v1标号b(1)=0. 第一轮，起点已标号终点未标号的弧集合B={（v1, v2），（v1, v3），（v1, v4）}，T（v1, v2）=b(1)+ C12=0+6=6, T（v1, v3）=0+10=10,T（v1, v4）=0+12=12,将弧的标号用圆括号填在弧上。min{T（1,2），T（v1, v3），T（v1, v4）}=min{6,10,12}=6 T（v1, v2）=6最小，在弧（v1, v2